Hacker News new | past | comments | ask | show | jobs | submit login
Competitive Programmer's Handbook (2017) [pdf] (cses.fi)
594 points by linouk23 on April 29, 2018 | hide | past | favorite | 121 comments

The most irritating thing with these competitive/algo stuff is that no matter how many times you master it - eventually you always forget it, because you don't need it on a daily (or more like yearly) basis in the real world.

It's not about needing it in "the real world". It's about having fun. It's about the adrenalin rushing through your veins as the clock ticking down. It's about burst of joy when your brain just clicks and the invisible wall falls down, showing a path to the solution. I still do Putnam and IMO every year, I also occasionally take an hour or two during work and just solve Math problems. Solving problems is a hobby, just like video games. There's nothin really practical about it and there doesn't have to be.

What I'm saying is that aligning interviews to prefer candidates with this particular hobby (which is not related to the job) is not fair.

I think I agree with you, and I say this as someone who was probably a beneficiary of such an alignment, after college.

But the submission does not mention job interviews. The linked book (the author is “one of the organizers of the Finnish Olympiad in Informatics […] coached and led the Finnish team at several international programming contests, including the International Olympiad in Informatics”) is someone's labour of love, written for people interested in this hobby. It brings joy and satisfaction to many people, most of them young students. Why throw cold water on them, by reacting to mention of such a book with terms like “irritating”, based on something that others do in some other setting entirely? Or, even if bringing up job interviews is justified (no doubt your irritation is real), it would be nice IMO to at least preface the comment by clarifying that the comment is not about the hobby/competitive-programming world that are the subject and audience of this book, but about something else.

> What I'm saying is that aligning interviews to prefer candidates with this particular hobby (which is not related to the job) is not fair.

It's also detrimental to the business.

if we're going to take the video game comparison further, then there is something better you could be doing with your time.

For what? The man is happy doing his things. Who are you to judge him?

This is the case with anything you didn't discover it yourself but rather 'learned it', that's actually just a replaceable term for 'memorized it'.

People who discovered/invented these algorithms traversed several years of curiosity, blind alleys, dead ends, failures and successes. You can't possibly expect to get it all and make it up on memorization alone.

Algorithm learning is hard for the same reasons memorizing Math tables are hard.

As of today there is nothing novel about merely learning how a algorithm works and spitting it out in an interview, if anything it achieves the exact opposite goal of what it is supposed to.

This is true for lots of things though, right? Programming languages, spoken languages, mathematics, muscle mass...use it or lose it, but it gets easier to re-learn/re-gain everything each time. Plus you don't necessarily have to forget or lose it if you're able to set aside the time to maintain it.

Exactly. Having the experience of solving difficult algorithmic puzzles under time pressure makes parts of software engineering (writing working code, debugging) easier, so you can focus on the hard parts. Algorithmically, almost anything written in the real world is trivial in comparison.

If you really needed to remember it, you could employ spaced-repetition: https://en.wikipedia.org/wiki/Spaced_repetition

I use Spaced Repition for chess openings as I can't refer to a book while playing a tournament game. That's not the case for programming.

A lot of software developers are asked to code solutions to difficult problems using nothing other than a whiteboard. Given that under normal circumstances we use a computer, IDE, and the internet, I can see why some might opt to use spaced repetition to ensure employment.

If the interviewers aren't generous in offering corrections to small issues when you're at the whiteboard, you don't want to work for them. Whiteboard exercises are there to see how you think through a problem, not how much algo shit you crammed ahead of time.

You still often have to be familiar with approaches to problem solving and data structures. And you have to be practiced enough to know when to apply them.

In a high pressure situation like an interview, I personally find it difficult to think naturally through a problem. Familiarizing myself with different types of interview questions regularly helps a lot.

As convoluted Spaced Repetition sounds I am debating using it to brush up on algorithms.

10 years ago I was pretty handy with CLRS, but now I'd be hard pressed to implement quicksort without looking it up.

Kek - i employed this technique in learning starcraft 2 openings. Def. Seperated the top 10% from top 5%

The point is why people have to remember them ?

Why not look them up when necessary ?

I guess most of the problems are relatively small, but for Advent of Code¹, the "competitive" people are finishing most of their solutions in a minute or two.

1. http://adventofcode.com/

How will you look it up when necessary during a programming contest (like the IOI/ICPC mentioned in the book)? It's usually not allowed by the contest rules to look up an entire book's worth.

And if your teams algo and data structure knowledge isn't at the level where you know about these solutions or their applicability?

I have a checklist of possible interview topics and I think I might an esoteric data structure part to it (knowledge not code) and some implementation choice questions - given this situation and data, with these queries what would your data structures look like.

Maybe also a few quotations on the last paper they've read in CS or related topic.

Why test for anything in an interview? Why not assume anyone can learn everything on the job?

Why even have the interview? Why not just hire everyone who applies and assume they can do the job?

There are tests and interviews because not everyone can

I'm not sure I understand: the linked book is meant for high-school and college students, or anyone participating regularly in programming contests:

> The book is especially intended for students who want to learn algorithms and possibly participate in the International Olympiad in Informatics (IOI) or in the International Collegiate Programming Contest (ICPC). Of course, the book is also suitable for anybody else interested in competitive programming.

Anyone in the target audience of the book will encounter most of this frequently enough; I definitely didn't have the experience (when I was in college and doing competitive programming, over a decade ago) that I was forgetting most of it.

Of course, if someone is not interested in competitive programming and never uses any of the knowledge they're likely to eventually forget it; it's just like learning a bit of French or group theory (say) and not touching it again for years — it's possible to forget. But not sure why that's irritating; it's just the nature of learning, at least after a certain age or below a certain threshold of practice.

Not the intended audience but now, technical interviews now have a lot of competitive programming in them so this book can help you.

Same goes for most of your theoretical computer science education...

Arguably competitive programming helps with this problem by letting you drill the concepts you've learned.


Just like sql and regular expressions. You work hard to get it to work and then forget about it.

That’s the entire point of those kinds of interviews. It’s a strong filter for “recent graduate” while maintaining plausible deniability for ageism. It has a secondary effect of filtering for “willing to do unpaid overtime”.

I do wonder how many 40+ programmers are able to keep up with "young ones" in these contests.

I fear it is like chess, the cognitive decline starts to become noticable in the mid 40s and only gets worse from then on.

There are a few exceptions like Korchnoi was in chess so there must be Fabrice Bellards and Bill Joys who would be able to keep up.

Still looking at completion times for Advent of Code made me feel old.

I think also the interviewer gets to feel smart. Always nice to have the answers.

Yeah, right. Clearly they have nothing better to do and are all egomaniacs.

I think its more of aptitude test in a domain common to all programmers.

The problem with this thinking is this "aptitude" is something which comes naturally. I was drilled with this "aptitude" nonsense when I was a student where the teachers would say that if a person "gets" a problem and finds a solution then he is a natural for the subject.

In my practical experience I find that to get the "aptitude" requires a lot of effort put in it. It definitely would vary depending on the person and his experiences but practicing it is very important to go forward.

Yeah right. Tell me the last time you built your own red-black tree in real actual code at work. Or did a sort by any other means than tacking “order by” on the end of a query.

They are a test of how recently you crammed for your CS finals, that’s all.

Or how much effort you're willing to put into prepping for interviewing and getting a new job. It definitely filters against the casual looker.

Which, to some extent, makes sense. You're basically filtering out people who won't put in the effort to get the job. Whether or not those who put in the extra effort are actually going to be better employees is a different decision.

There are languages - C and Go, and to a lesser extent, C++ - in which re-implementation of data structures and algorithms is not uncommon.

To your larger point, data structures and algorithms are popular in interviews for the same reason Project Euler is popular - it is very easy to ask a well defined, but interesting question about core CS or math.

Would be legit if the job required tasks like implementing red-black trees or sorts.

As is, it's more like advertising for python, then surprise java.

Indeed. If the job was implementing algorithms on bare metal then bring it on! That job sounds like a lot of fun!

But those kinds of questions make zero sense and have zero value if the job is actually implementing CRUD apps in a high level language. You might as well quiz candidates on their assembly language skills too, for a Python job...

So there is obviously an ulterior motive.

Tell me a better standardized question set for programmers that measures intelligence efficiently.

Do you think that that’s what that does? Interesting.


It's not ok to comment like this here, regardless of how wrong someone else is or you feel they are. Please post civilly and substantively, or not at all.


Sorry, it was indeed an off-the-cuff remark in poor taste.

That's enlightening. Never thought of it that way.

Maybe it's just a way to provide a fair test that anyone with ability can pass with a little practice?

I wouldn't call it "a little practice". There are people who are "into" competitive programming and there are people who aren't, and those "fair" tests are skewed towards the former group. The worst thing is that the actual job has nothing to do with the competitive programming at all.

Another filter for age is that 20-something’s are more likely to have time for this whereas older people may have more time commitments already

People in their 20s and 30s now will regret not stamping out ageism when they hit their 40s and 50s, as they inevitably will

> People in their 20s and 30s now will regret not stamping out ageism when they hit their 40s and 50s, as they inevitably will

The problem is, everyone in their 20s and 30s assumes they'll be gazillionaires by the time they're 40, because of course they're brilliant and hard work always pays off! Ageism is only a factor if you're not smart enough to make a billion by the time you're facing it.

Hard work does pay off. Believe in karma.

Karma goes both ways. Those that practiced ageism will find that out themselves eventually.

Unfortunately then the victims of ageism now will find that cold comfort in the future.

Rote leaning and getting a piece of paper is not a good way to interview for candidates who can when given a task that wasn't on the test research and implement a solution under their own power.

Memorising derivations of algorithms and solutions to puzzles from a book like Cracking The Coding Interview surely is just rote learning. There should be a high correlation between the content of the interview and the actual job, or what is the interview really for?

That's not a popular viewpoint around here. :D

I see in the comments that some people conflate competitive programming and technical interviews. Technical interviews (at least in companies such as facebook and google) are usually much easier than competitive programming problems. The problem you find on leetcode for interview preparation would be considered beginner problems in competitions such as google code jam.

> Technical interviews (at least in companies such as facebook and google) are usually much easier than competitive programming problems.

Probably. But if you are a student outside U.S where the opportunities are an order of magnitude less the only way to even land an interview with these companies is by doing competitive programming. Google selects students through APAC test in Asia where you have to be top n% in the leaderboard to even get an interview. Doing leetcode and all would not take you anywhere in these contests as you are competing with hardcore student programmers who have been practicing competitive programming their entire University life in search of an escape from the middle class. All the persons I know of in my country who works at Google or Facebook got their job through competitive programming.

> All the persons I know of in my country who works at Google or Facebook got their job through competitive programming.

Are any of them bad developers?

The general trend is that students do either competitive programming or development. Most students who do competitive program hardly work on any personal projects or open source as it is of almost zero value when it comes to campus placements. Companies like Flipkart, Morgan Stanely, Goldman, Amazon, Cisco etc conducts a competitive programming test as the first round in Universities. The remaining rounds are mostly data structures and algorithm/DBMS questions taken from GeeksForGeeks. Very few companies ask questions about development, personal projects, open source contributions etc. If a student does only development and hardly do any competitive programming it is very difficult for them to pass the first round.

Most people who are doing competitive programming aren't good at the harder problems. For example, there are >2500 people listed on the TopCoder Top Ranked Algorithm Competitors page (https://community.topcoder.com/tc?module=AlgoRank), but only the top 115 or so are Red, and only about 415 more are Yellow.

A programming contest, even if you just do the easy problems, can be a more enjoyable way to practice for interviews than reading a book or even going through online puzzles like those on LeetCode.

This is a good resource that I'm currently going through to prepare for interviews. Another one would be Competitive Programming (3rd edition) [1] but for general interview skills the Codility lessons are also OK [2].

1 - https://www.amazon.com/Competitive-Programming-3rd-Steven-Ha...

2 - https://drive.google.com/open?id=1WjXxbdle0_Syip_LygBpnZkfHv...

I like this book, but I have some reservations for using it for interview practice. There is no discussion on implementation of some of the algorithms, which may be relevant in an interview (e.g. if you're not allowed to use std::sort).

There are also a lot of topics where there's a brief overview of the algorithm, but no code - e.g. the geometry section is interesting and has some useful ideas, but no implementation. This gets worse as the algorithms get more complicated, and some quite difficult topics get a cursory glance.

For the general categories of problems that you find on e.g. LeetCode or Intervewbit, this book is really useful. It's a good, practical, companion to a proper algorithms textbook.

Perhaps most irritating - if using this for prep - is that there are virtually no case studies, and the case studies that are in there assume a lot of code which isn't in the book (either boilerplate or assistance functions). This book would be incredibly valuable if each chapter had a list of example problems (solved or unsolved) to see how things are applied.

Has anybody gotten into this kind of programming post-college? Are there communities outside of high school and college competitions for this sort of thing?

Yup. Check out TopCoder[1]. They have regular programming contests every week or so. The contests are conducted in two divisions(amateur - div 2) and (pro - div 1) and candidates are assigned different colors on the basis of their performance. Becoming a red coder in TopCoder is a pretty big thing in the competitive programming community. For example, Adam D Angelo who is the co-founder of Quora used to be Red on Topcoder[2]. Most of the red coders of TopCoder get hired by companies like Google, Facebook etc. It's pretty hard for one to fuck up a competitive programming interview once you became a Red level candidate in TopCoder. Mark Zuckerberg also tried TopCoder for a few months while in Harvard [3]. CodeForces[4] also has a pretty big online community. I think it has become more popular than TopCoder these days. They also have regular contests every few days. Facebook[5] and Google[6] also hosts competitive programming contests every year. If you managed to make it to the final round I think they would invite you for an interview.

1 https://www.topcoder.com/

2 https://www.topcoder.com/members/dangelo/

3 https://www.topcoder.com/members/mzuckerberg

4 http://codeforces.com

5 https://www.facebook.com/hackercup/

6 https://code.google.com/codejam/

As few comments already mentioned, post college, preparing for this type of thing immensely helps in job interviews. I find it very hard to clear job interviews and in 2017 alone, I appeared for ~25 job interviews. I'm very convinced that competitive programming skills gives you a leg up in job interviews.

Many people may already may know this, but Peter Norvig indicated that it correlates poorly with on the job performance (at least at Google) [1]. I wonder why, then, companies still continue to do this style of interviews.

[1] https://www.youtube.com/watch?v=DdmyUZCl75s

Well, I think you're kind of misrepresenting his point as "competitive programming doesn't improve your programming abilities".

It's not that competitive programming correlates poorly with job performance; it's that, given you've been hired by Google, being a competitive programmer correlates poorly with job performance.

Hypothetically, let's say there's 2 dimensions for a programmer's ability, competitive programming and job experience. Each of these is distributed independently from 0-10. You get hired by Google if competitive programming + job experience > 10. However, let's say that for their actual job performance, it's 0.5 x competitive programming + 1.5 x job experience.

You now have a case where competitive programming could correlate poorly with job performance at Google, despite having a positive correlation in general.

Berkson’s paradox

Do you think there is no correlation or the correlation is in fact positive? I wondered if they every AB test with lower standards for new hires.

Yeah, I think they are a terrific way to "keep your sword sharp". Jump start the neurons in the early AM or lazy summer day. As well as a way to learn new algorithms, new languages via problem solving.

Code Jam had a particularly juicy one in the recent Qualifying Round, that could easily be part of a modern shadow rendering game engine. Just to put it into perspective, only around 1000 out of 25000 entrants were able to solve the large data set in the allotted time!

Google Code Jam 2018 Qualifying Round Problem D: Cubic UFO


Incidentally, I don't really learn a lot from books or tutorials such as the one linked. But rather from the contest analyses and top winners code solutions.

Interesting problem.

I imagine the juicy part is that there is no clear cut formula for determining the rotation from the area needed.

Thus the task is to come up with a fast approximation algorithm to work backwards.

So brute force way:

  If area_needed > area_cast:
  else similar rotation on -delta
Now, my 3d geometry is rusty, so maybe rotation on 2 axis is enough but still optimizing 2 arguments is not going to be easy. Maybe you can max one rotation then max 2nd one.

My first instinct says that if you just project the corners straight down (because of orthographic projection) onto the XZ plane, then the area of the shadow is just the area of the convex hull of those projected points.

I don’t know how to calculate that hull off the top of my head, but that’s the type of stuff you can look up during real world scenarios.

I participated while in high school and university and kept having fun on Codeforces[1]. It's a great community with very frequent tournaments and they always have detailed explanations of the expected solutions after the tournaments.

[1]: codeforces.com

Yes they are called job interviews these days :d


He's not joking though. I've experienced 3 rounds of stupid tricky questions followed by a 4 hour "take home" project at a UK startup in Deep Learning before they were willing to even send flight tickets to London, and the feedback I've received was so comical that I almost wrote a blog post about it (I still might). Another robotic startup in SV grills with 6-hour stupid codility tests as a first phase (i.e. waste 6 hours just as a handshake). Not sure if they think time grows on trees or people have no other things to do just to pretend a day has 48 hours. I took those to see what the interviews are these days to stay fit, and I must say it's like a panopticon of Google-wannabes for uncompetitive salaries and useless equity with bad liquidation preference.

The problem is, for every person like you, there's a person like me that actually likes those types of challenges and wouldn't actually mind being thrown into that type of gauntlet. My years of experience be damned.

Sure, that might be the case. But for those funny needs I have a "crazy algorithm course" from a top 10 university, ACM ICPC and Kaggle or other paid competitions I can attend. I am not going to go through such an interview doing simple silly things I did dozen times before at FB/Goog/etc., when I know I can use that time to work on something more interesting, or just for relaxing after a hard work/enjoying accomplishments. I would advise companies hiring to at least once read CV and click through GitHub code, and then just focus on the only important question - would they like to work with me as a person or not? That would save everyone time and lead to better results.

One self-driving car start-up in SV wanted me to solve a long-standing research problem (Deep Learning) as their week-long take home test. Thanks, but when I do, you can license my tech, I will gladly make it available to you for $.

There's irony. Asking for GitHub is 10x worse than algorithmic questions. I just went through the interview process at big companies, with all the resources out there it's easy to get good at these types of questions.

During my professional time I write software to make money. During my free time I write software to make money. As an aging software engineer algorithmic questions just screen for how much time you're willing to put into an interviewing. GitHub screens for how much of a sucker you are.

Yeah, could be. Though if you provide a hiring company with a GitHub profile demonstrating your dominance, and then you are expected to waste another 6 hours on trivial algorithmic questions you probably did 100 times in the past 10 years, you'd probably just pass on that "opportunity". Those algorithmic questions were anyway originally meant to find the "best of the best", now they are used for entry-level positions. It's like asking an accomplished lawyer about what happened in 1758 and what was the effect on common law.

I have a sneaking suspicion that I’ve built a feature that was presented as a coding exercise, possibly more than once.

Imagine you get that very feature during some interview and the feedback you get is that you failed :DDD Reminds me when I created a few jokes as a kid that got nation-wide popularity; it was difficult to explain I made them from the scratch and the only thing those attempts gave me was to be marked as an "asshole" and "liar" :D

What was the problem they asked you to solve? Out of curiosity

I don't want to ruin their test...

Oh I agree! Not sure who downvoted me but I’ve been dealing with the same shit for quite some time (https://news.ycombinator.com/item?id=16127697).

The shit is ridiculous.

EDIT: Please write that blog post!

Google Code Jam

I would watch programming contests live streams.. Are there any available?

Petr usually posts screencasts on Youtube: https://www.youtube.com/user/petrmitrichev


There was a HN discussion recently about programming livestreams.

In my experience, most of the time goes into coming up with an algorithm or debugging. I don’t know about you, but I don’t think those would be particularly interesting to watch.

I am mostly just fascinated by people able to stream their coding. I think most of my stream would consist of googling stuff and procrastinating on hacker news and tabloids

Not sure if that's a thing but I've heard of developers streaming their screen on nights and weekends on something like Twitch.

twitch.tv/devwars is a great competition. 3 vs 3 and you have an hour to make a better website than your competitor.

This book gets to the point fast. But for the fundamentals this book serves more as a refresher than a course.

Skiena and Sedgewick both have excellent books and online courses if you need more depth.

A nice thing about this book is that the full TeX source is on github.

There are some sections that are a bit dense and may require some additional work. The string algorithms section is very dense compared to the rest.

Seemed interesting up until the "Shortening code" section, that'd drive me mad.

Another reason for shortening code in programming contests (apart from being able to type and edit/iterate faster) is that it helps you avoid errors. For example, in the heat of the moment and under intense time pressure (e.g. you have finally figured out the algorithm to solve the problem, but you have only 13 minutes left to implement it or whatever), it's easy to write code like this:

    for (int i = 0; i < n; ++i) {
        for (int j = 0; i < n; ++j) {
instead of what was intended (j < n).

So if you have (in your pre-written library of snippets) a macro like

    #define FOR(i, n) for(int i = 0, _n = n; i < _n; ++i)
then you can write:

    FOR(i,n) FOR(j,n) {
(the _n in the macro is for cases like FOR(i, v.size()) to avoid recomputation) and at least avoid that particular error. Of course other sorts of silly errors are still possible; some examples here: https://www.quora.com/What-is-the-worst-mistake-youve-made-i...

Thanks for the example, I actually like this FOR macro. It was mostly the things like 'typedef long long ll;' or 'typedef pair<int,int> pi;' that bothered me.

And I don't mean to say the whole thing is bunk. I found some really good info farther into the book, especially about algorithms, which I think will help towards interviewing candidates.

I'm not sure that you avoid errors by forcing yourself to write short code. With C macros.

Here's a real world example:


So I have this function, `crypto_wipe()` that wipes memory regions with `volatile` so the compiler doesn't optimises it away. In the link above I was using it thus:

  crypto_stuff(stuff_ctx *ctx) {
      // stuff
      crypto_wipe(ctx, sizeof(ctx)); // BUUUG!!
See the bug? I should have dereferenced `ctx` in the sizeof operator. As it was, was only wiping a pointer's worth of data instead of the whole structure. Oops.

Now I write this instead:

  crypto_stuff(stuff_ctx *ctx) {
      // stuff
      WIPE_CTX(ctx); // correct!
The amount of repetition I avoid this way is almost negligible, but that was enough to trigger a mistake (I had quite a lot of wiping to do). With the macro, errors are much easier to spot (so much so that I am willing to give 100€ to anyone who finds such an error, see https://monocypher.org/quality-assurance/bug-bounty)

In this case the use of macros may increase the readability or assurance of the code, still there are a lot of cases where macros can easily lead to bugs: https://wiki.sei.cmu.edu/confluence/pages/viewpage.action?pa...

Of course. You will note I only went macro to prevent an error I already made. C macros suck, I don't use them lightly.

When you write "FOR(i,n)", instead of "for (int i = 0; i < n; i++)" you only write "i" once instead of 3, which makes it less likely to make mistakes.

That being said, I've found that competitive programmers sometimes write extremely ugly code. It's surprising to see how they are able to solve such complex problems, and yet can't (or don't value) write readable and structured code. Maybe they are so sharp that they don't feel the need to make their code more readable.

Well, when your code has a lifetime of five hours max, readable doesn't matter, correct does.

code golf is its own thriving subculture; and a lot of fun


Code should be written for readability, not typing speed.

This is not production quality code that is running on some important business. It's competitive programming.

Speed is the goal here.

This is not production quality code that is running on some important business.

Then why is it used in the interview process for the latter?

I don't think code shortening is ever used for interview questions?

But if you're in a competitive environment that requires speed, why would you write for readability?

Because you’ll end up debugging the code an hour later when it fails on an edge case?

The really good competitors won't make that sort of mistake...

Because you probably have to re-read some, if not most, of the code while working through a solution.

This was the first resource I used to help me prep during my most recent interviews. Read and implement the examples yourself.

Is there a printed hard copy version available as a book? I’d love to buy it. I’m a big fan of highlighting and annotating books with a pencil.

This is a great summary to a ton of CS algorithms and datastructures. Thanks for compiling this.

Yeah the author actually came out with a physical book that he published with springer. It’s linked here [1]. I believe it’s the same book just with extra materials.

[1]: https://cses.fi/book.html

This book seems very useful for a job exams preparation.

Nice! Reading through this doc is like going back to Computer Science classes again.

I wonder if there is something similar to this but for pragmatic, design-oriented challenges. Writing obfuscated code in the shortest amount of time is akin to the people who change tires during a race car competition. I would love to see challenges where you build the race car parts instead.

Boring but immensely more useful.

If you wonder why you need to learn competitive programming when you can just look it up? I would like to refer you to B.F.Skinner's quote on education: "Education is what survives when what has been learned has been forgotten."

Only book I used for USACO.

Chapter 8.1 shows an awesome algorithm!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact