12 ms·
A Competitive Programmer's Handbook
- BatFastard 9y agoThanks for sharing, will look it over and send you some feedback.
- Zarov 9y agoThanks for this, it may be exactly what I was looking for :)
- user5994461 9y agoCompetitive programming = coding challenges, like Google Code Jam and HackerRank. Nothing to do with getting a better job or a better salary.
- 40acres 9y agoThe same skills used in competitive programming are needed to pass a modern day technical interview at some of the larger companies. So I wouldn't necessarily say it has nothing to do with getting a better job or salary.
- mod 9y agoIn the sense of "this article has nothing to do with jobs or salaries," I would rate the claim true. The article has not one mention of either. If you're trying to argue that improving your skillset makes you more employable, sure, but that's such a general statement that I'm not sure it holds up as a retort.
- TeMPOraL 9y agoI think the GP means that problems solved in programming competitions are similar to what you'll find on some job interviews.
- mod 9y agoSure, and I think the comment he replied to means "the term competitive is ambiguous, let me clear it up: this is not talking about advancing your career."
- kbenson 9y agoI guess, to the degree that you would assume "competitive programming" could be interpreted as something specifically to advance your career, which I know I didn't, and I'm not sure how you could (but I could easily be missing a common different interpretation). That is, I wouldn't assume "A Competitive Fisher's Handbook" would apply to my career as a bulk tuna fisherman, and I would find a comment that points out that there is nothing related between the two as as both obvious (colloquially), and overreaching (specifically) to the point I might feel the need to counter-correct as there very well might be links between them that could help in non-obvious ways. That competitive programming and interviews share more than superficial similarities might make me even more likely to do so.
- __jal 9y agoStaying fit also helps job performance, as does public speaking. Shall we start a comprehensive list of skills and activities tangentially related to making more money?
- atemerev 9y agoActually, yes please. Can be published as a book and sold for money!
- deleted 9y ago[deleted]
- throwaway_374 9y agoSadly the proliferation of sites like HackerRank (YC funded shamefully) means competitive programming is the first "filter" stage for interviews these days.
- __jal 9y agoI actually don't mind that. The filter works both ways - it tells me the company in question is clueless about hiring tech talent, so I can ignore them.
- deleted 9y ago[deleted]
- kevinclancy 9y agoIs that sad? It's a better filter than college degrees.
- throwaway_374 9y agoSo your ability in a pressured limited-time environment come up with an O(N) dynamic programming algorithm for a fictitious scenario is a testament to your ability as a software engineer versus a competitive programmer who can pattern match scenarios?
- mciancia 9y agoBut algo questions are usually just part of the interview, not the whole thing. And usually they are fairly simple, so every good software engineer should be able to solve them.
- throwaway_374 9y agoReally, I've had an example of deriving (I didn't know what it was called at the time) Manacher's Palindromic substrings: http://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/ http://www.geeksforgeeks.org/manachers-algorithm-linear-time...
- cyorir 9y agoI can do well enough on programming challenges at a place like HackerRank. However, I very rarely actually get to the technical interview in a job application; most commonly, I apply and don't hear back from the company. So as far as I'm concerned, I need better something but that something isn't better skills.
- oblio 9y agoMore networking, possibly better networking (easy, I think). Better university name (hard to do). Better company names (not that hard, I think). (Major) Open Source contributions (not hard, but time consuming). Other studies or certifications (easy). If they're not calling you, I'd work on these.
- user5994461 9y agoYou forgot the most important. More real world experience, and a well formatted resume.
- cyorir 9y agoDefinitely all things I'd like to work on.
- webaholic 9y agoI wish this was true. If you are good at competitive programming, it is more than likely that you will be good on the whiteboard interview questions for a software developer position.
- zerr 9y agoNothing to do with the actual job but it is heavily used for interviews to get that actual job, unfortunately.
- sundvor 9y agoThis is my understanding as well. Data structures and basic algo comes up in interviews, and if you pass that's probably the last of it too. I never studied them originally, but once I realised it was a blocker to getting a new job I spent some time to learn the basics at least which truly helped a lot. It was also a bit of fun, to be honest - even though they have almost no bearing on the day to day work. So I'm interested in this book as it's a remarkably concise list of related things to learn.
- zerr 9y agoBesides basics, I've learned and forgot several times, so I don't have enough motivation nor time to re-learn again :)
- sundvor 9y agoI read you. It's funny how it blocked a couple of jobs, and it only took me a few hours to learn enough to pass the basics. I understand the need to filter, but still believe it's a crappy way of doing it.
- paulsutter 9y agoEspecially given the importance of teamwork. Competitive people tend towards tedious one-upmanship. It's something you want to screen out in the hiring process.
- poikniok 9y agoCompetitive people are often very good at working in teams, see any team sport, or team programming contests.
- paulsutter 9y agoI would choose a person who is driven to solve problems over a person who is driven to exceed others, every time. Competition is for losers.
- poikniok 9y agoOk you must love competitive programmers then, because they are very driven to solve problems :)
- cossatot 9y agoI had to compete for my job, in which I get to spend a lot of time working relatively unconstrained on scientific problems of my choosing, as long as they're quite broadly mission-oriented. I like working on questions no one else is asking and avoiding the 'a large debate exists in the community as to whether X or Y' messes that Nature loves to publish. I had to compete for my wife, who supports me and inspires me and etc. me, with few constraints (such as no others compete for our affections). I hate games of all sorts (they have rules and the fun is to remember them and play by them?). But nonetheless I realize: Competition is for organisms.
- paulsutter 9y agoElon Musk and Steve Jobs never spent time responding to competitors. VC funding is another example. Fundable companies are so rare that VCs never sit around debating whether to fund company A vs company B, it's two separate decisions. It sounds like what you treasure most about your job is that you're released from competing. Finding a relationship is about fit, and a good relationship is about the investment you make. I've never seen competing to work in any phase of a relationship.
- kyleschiller 9y agoAgree with other comments about similarity to interviews. Norvig seems to think it's a negative signal though. https://www.youtube.com/watch?v=DdmyUZCl75s https://www.youtube.com/watch?v=DdmyUZCl75s
- samuraijack 9y agoI wouldn't say he considers it a negative signal considering how he said if he had to pick someone off the street he would prefer the one who is good at programming competitions. However if you are above the bar required to get hired by google, then a higher success rate in programming competitions correlates negatively with job performance.
- rlanday 9y agoI suspect this is because if someone is hired, they were necessarily good at solving Google's interview questions, which are very similar to (easy) competitive programming questions. The fact that someone is good at competitive programming doesn't give you much further information since you already tested for that ability during the interview, and in fact may indicate that this person is spending energy studying competitive programming that they could otherwise be spending accomplishing stuff at work.
- deleted 9y ago[deleted]
- stoic 9y agoIt says right on the tin that this is meant for IOI/ICPC-style contests, whose participants are high school and undergraduate students respectively. As a former competitor in USACO, ACSL, etc., I would have loved to have resources like this around for practice and self-study back in high school.
- dsacco 9y agoBut no one mentioned those things, and the book doesn't seem to either. Why make this book about the crusade against Google's interviewing zeitgeist? For what it's worth, I work with someone who used to be (is? I think he stopped competing) red on TopCoder. He's one of the best developers I've ever worked with. I don't know about the causation there, but his development process and skill is better than most of what I've seen in many other tech companies (I say this in the context of reviewing other companies' source code for errors and getting an understanding of what their respective SDLCs look like). That's obviously a sample size of one, but I felt like saying it because I think you're really pushing it with your comment. It almost just seems like you have an axe to grind. I can agree that a good developer doesn't need to be adept at competitive programming, but it does help with understanding things like algorithms, data structures and time complexity. I think you trying to claim that competitive programming has "nothing to do with getting a better job" is just as egregious as people who only hire engineers that can produce impeccable red-black trees on a whiteboard with little preparation.
- gpawl 9y agoRelax, parent poster was simply clarifying that the 'competitive' referred to programming "sports" contests, not competing for a programming job.
- dsacco 9y agoSure, but I don't think a good faith interpretation of the title would require that sort of disclaimer, and look at the rest of the thread that resulted.
- rattray 9y agoI hadn't heard of "competitive programming" before, and at first assumed this was a post exactly about "getting a better job or a better salary" (the most likely alternative interpretation). So I was grateful for the clarification, and didn't take it as algorithm-hate.
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- rlanday 9y agoI had been practicing competitive programming questions for several months the last time I was out interviewing for a new job, they're very relevant for both of those insofar as they help you pass interviews...
- SamReidHughes 9y agoIf you do the Google Code Jam, they might use that info to recruit you.
- signa11 9y agoin a similar vein there is : https://cpbook.net/ https://cpbook.net/ which is also pretty cool. will take look at this also. thank you :)
- alexee 9y agoThere is also https://e-maxx-eng.appspot.com/ https://e-maxx-eng.appspot.com/ (translated from russian, original: https://e-maxx.ru/algo/ https://e-maxx.ru/algo/)
- thomasahle 9y agoThis is a great 'advanced' resource! I've been reading the google translate version of the Russian page. Really nice to have a real translation!
- hal9000xp 9y agoThere should be references to problems for each topic at online judges. Like this one: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=118 https://uva.onlinejudge.org/index.php?option=com_onlinejudge... Learning algorithms per se is only a small part of training. Much bigger part of training is learning how to recognize these algorithms in problems. After reading about some algorithm, I always solve a couple of related problems. P.S. Looks well-written. Bookmarked. I appreciate the effort of the author to create this book.
- joaorico 9y agoThe book I recommend to people getting started is Competitive Programming 3 [1] by Steven and Felix Halim. It's pretty great if you have already a basic grasp of simple algorithms and a bit of C++. And as you say you need to practice, and the book incentivizes it. They accompany the book with precisely problems from UVa Online Judge, some of them solved and with code (in the book and in the site). [1] https://cpbook.net/ https://cpbook.net/
- bogomipz 9y agoAre the only difference between CP 1,2 and 3 that each is a newer version? It's hard to tell from the site.
- dimitar9 9y agogreat stuff.read this,understand this and you'll get google offer for 350k per year.
- preordained 9y agoWhy would you? How is knowing (and understanding) all that worth 350k per year? It shows that you are sharp and know your algorithms...is that all it takes to solve "350k yr" class problems? What do those problems look like? I suppose if they look just like hacker rank or something, then yes... Certainly some companies put all their faith in those type of demonstrations of skill, I grant you...I'm just wondering if you or others really believe you are "Google material" by that measure.
- deleted 9y ago[deleted]
- dimitar9 9y agoif you live in bay area you would understand. this is how it works in US west coast. Wall street is pouring money to here and big companies just pay that much to new grads who can do algorithm questions on whiteboard. believe it or not, it is true.
- just2n 9y agoI don't know where you're getting those figures from, but they're off by more than a factor of 2 based on information I have from friends in Google and previous disclosures here on HN by Googlers. Google won't pay most new hires out of school much over $100k in the bay area, and they adjust based on living expense. AFAIK the higher end of junior compensation is close to $200k, which is where you start getting into the entry senior level salaries. There certainly are engineers at Google getting paid $350k in base + bonus compensation but they're not people who only know how to do basic competition problems and enough theory to get a 4 year degree.
- tagag 9y ago
- balazsdavid987 9y agoThis is a well-written book, very nice work!
- TheAlchemist 9y agoFor those interested -> TopCoder annual competition just started (Marathon track which is usually 2 weeks length optimization problems): https://community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=55119&rd=16903 https://community.topcoder.com/longcontest/?module=ViewProbl...
- mrcactu5 9y agoi like this book because it has certain time and resource constraints in mind. that maybe a typical professional programmer does not have. but maybe someone from another subject can learn.
- mrcactu5 9y agoi like this book because it has certain time and resource constraints in mind. that maybe a typical professional programmer does not have. but maybe someone from another subject can learn.
- camperman 9y agoNot only is this an excellent introduction to competitive programming, it's also a very nice overview of some of the nuts and bolts of C++. I recently have had to deal with a large C++ codebase and this is a really good little refresher.
- fosco 9y agothis is great! that being said, I really like text files. Does anyone know if there is a way to migrate the pdf to a text file [omitting figures/pictures] ?
- SuprDewd 9y agoThe LaTeX source for the book is on Github: https://github.com/pllk/cphb https://github.com/pllk/cphb
- xsegfault 9y agoGood review for algorithms and data structures. Hopefully we can get a printed copy later.
- uptownfunk 9y agoExcellent writing, clear and easy to understand. Would appreciate the links to example problems as others have mentioned (and solutions too if available). Seems like an interesting book to keep me sharp for if/when I ever go on the job market. Well done.
- mattdodge 9y agoGreat timing considering Google Code Jam Round 1 starts tonight too
- shahzeb 9y agoLink? / What is it? / Is it a good thing to test out for beginners?
- bergie3000 9y agoHere's the link, but the qualification round for this year has already passed. https://code.google.com/codejam/ https://code.google.com/codejam/
- mattdodge 9y agoIt's certainly good for beginners who are looking to get into competitive programming. The problems can be somewhat challenging to someone not familiar with algorithms or computer science fundamentals I think. The code for solutions often isn't complex at all, but they typically involve applying some sort of algorithm to a made-up (often funny) real world problem. You're not building a to-do list app, you're writing algorithms. It's sort of like a word problem in high school math. The math itself is often just addition and multiplication, the hard part is figuring out which math to use and which numbers to apply it to. All of the old problems are on the CodeJam website though so you can go check them out and give them a go!
- bmay 9y agoThoughts on this vs. Steven Halim's handbook?
- atemerev 9y agoOK, who has published cheat codes for most programming interviews? Seriously, if you can program at all, and want to be a better programmer (like, really well paid one), this is the greatest single thing I ever saw for this purpose. Just run through all examples and understand how they work, and you are already in top 1%. Then, you can move to SICP and Project Euler in your spare time.
- taway_1212 9y agoIf you want to be a really well paid programmer, just learn java and assorted technologies and go work for a bank.
- atemerev 9y ago...and be outsourced to the fine Bangalorian sweatshops sooner or later. :) And it is not "really well paid". Really well paid is, like, 250k/year, and it is somewhat hard to extract it from just Java in an average bank.
- alexbanks 9y ago> ...and be outsourced to the fine Bangalorian sweatshops sooner or later. In my experience, the jobs of the mediocre get outsourced to said sweatshops to be done by equally mediocre people for cheaper. I've worked for two big banks as a software dev, and there are plenty of long term, extremely high paid positions for Java engineers that'll never get outsourced. The model seems to be: have a group of on-site, well paid smart people build out a toolset, toss it to offshore to build useless CRUD features onto. > Really well paid is, like, 250k/year, and it is somewhat hard to extract it from just Java in an average bank. I disagree. There were a bunch of engineers at both banks that were clearing ~200-300k a year, and not in San Francisco. Granted, some of them were Oracle DBAs, but there were a bunch of Java-specific people as well.
- atemerev 9y agoI agree with both your points.
- SnowingXIV 9y agoReally into how this is written. I don't understand much (any) c/c++ but I'm familiar with ruby and JavaScript so basic programming functions I'm aware of. This book still is making sense and hitting on issues that I've always been interested in calculating O(n) and others.
- hkon 9y agoGreat. Thanks!
- arvinsim 9y agoAnother good resource for clearing technical whiteboarding tests.
- csnewb 9y agoThat was my thought while reading through it, but its basically just an algorithms textbook, which makes technical interviews seem even more daunting.
- elnygren 9y agoThis book is being used for an optional undergrad algorithms course at University of Helsinki. We have programming competition style assignments: pass/fail tests on a server with time and memory limits. Really fun challenges (and hard!!). Nice to see the author getting some recognition at HN :) You can find the course material and assignments from https://cses.fi/alon/ https://cses.fi/alon/ - however, it's all in Finnish.
- boltzmannbrain 9y agoPositive correlation between Competitive Programmer’s Handbook and software engineer interviews? Yes. Positive correlation between being a strong competitive programmer and a strong software engineer? Doubtful.
- mck- 9y agoAgreed. These kinds of competitions or coding interviews may cause over-fitting.
- nkozyra 9y agoIs there really risk in being particularly adept at algorithm design?
- aswanson 9y agoNo, but by definition, any non-trivial software product (or academic CS paper, for that matter) is the outcome of a collaborative process, not an artificially time-constrained hack-a-thon/competition. You have to put things like this in their proper place, and let them be what they are. (I downloaded the pdf, btw).
- deleted 9y ago[deleted]
- closeparen 9y agoThe risk is that you might be less useful than someone who is particularly adept at system design. It seems most problems are actually not sorting, searching, or finding the optimal whatever. Maybe it's just the bubble I work in, but from my perspective it seems that most programmers aren't addressing a problem of the form, "the obvious solution to this well-defined problem is too slow, please have a clever insight that leads to a faster one." The problems we work on are instead of the form, "please model this sprawling and subtle domain with reasonable fidelity and in a way that'll handle future changes to the domain." "Please satisfy these five dozen individually trivial requirements in a way that gets every corner-case interaction exactly right, and won't turn into a nightmare when there are a dozen more next quarter." "Please decompose this problem in such a way that 10 different people can work on it in separate parts of the codebase in parallel." "Please take this problem that's solved for one machine and make it work over an arbitrary number of machines, and make it reliable under all the weird and abusive scenarios that a few years of usage in production can manage to throw at you." "Please design a monitoring and dashboarding strategy that will identify all outages immediately while not overwhelming the oncall with false alarms, and provide first-class instrumentation, debugging, and remediation tools so that someone new to the codebase can find out exactly what went wrong and fix it in the middle of the night. It's not at all uncommon to deliberately ignore the optimal algorithm in favor of the readable algorithm. We usually try to keep cleverness behind the curtain of abstraction (RDBMS, standard library, etc). Of course, someone has to build them, but then they are widely reusable. Of course, people who can do all of the above while interacting fluently with the code for the optimal algorithm are so incredibly highly paid in the Bay Area that they can buy houses.
- aaggarwal 9y agoThe author originally released the book here (http://codeforces.com/blog/entry/50728 http://codeforces.com/blog/entry/50728).
- jiangplus 9y agoAt first glance, I saw String Theory and was about to laugh, but then I found it was String Algorithm and Game Theory :D
- z3t4 9y agoi love solving problems. but hate solving programming riddles with artificial rules. it feels much more like work then actually real work does.
- bogomipz 9y agoThis seems to be horribly written. Example: >"In the German Lotto you have to select 6 numbers from the set {1,2,...,49}. A popular strategy top lay Lotto - although it doesn’t increase your chance of winning — is to select a subset S containing k (k > 6) of these 49 numbers, and then play several games with choosing numbers only from S. For example, for k = 8 and S = {1, 2, 3, 5, 8, 13, 21, 34} there are 28 possible games: [1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34]. Your job is to write a program that reads in the number k and the set S and then prints all possible games choosing numbers only from S." if K needs to be > 8 how are the numbers in the selected subset {1, 2, 3, 5, 8, 13, 21, 34}? The majority of those are less than K. I have scratched my head about this for a few minutes. There are many that are equally as confusing. See: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=137 https://uva.onlinejudge.org/index.php?option=com_onlinejudge...
- njonsson 9y agoThe size of S is k.
- aisofteng 9y agoThe problem is your reading comprehension. That reads just fine to me. Pretty standard writing.
- bogomipz 9y agoYour snide comment is completely uncalled for. My reading comprehension is just fine, the following statement is full of ambiguity: "subset S containing k (k > 6)" A more articulate way to express that would be "subset S that contain k elements where k is greater than 6"
- detaro 9y ago"subset S containing k (k > 6) of these 49 numbers", don't cut something important out of the statement and then argue it is "full of ambiguity".
- grepthisab 9y agoI really like this. I don't like how you handle array indices though. The book is written in C++, yet you initialize all arrays where the first element is at index 1, which makes things really confusing, or at least annoying to think about when converting from your text to an IDE.
- Aardwolf 9y agoAgreed, like it as well except hate the 1-based indexing. The first element of an array in C++ has index 0 and the last has index < n. Almost every single for loop I need in C++ has this form: "for(int i = 0; i < n; i++)" In this book all for loops are alien: "for(int i = 1; i <= n; i++)", and it is also accessing arrays like this here and there which would normally be out of bounds unless you make them one larger which would be very odd to do. Very weird in an otherwise fine book. The main point imho is that if you have a range starting at some index a, then the first element of that range is at a+0, not a+1, and if n is the amount of element of the range and a is the index of its first element, the last will be at a+n-1, not a+n. The start and end of an array is the same, an array's indexes are also a range. You may want to make it feel all natural by setting a to 1 instead of 0 for arrays, but it then becomes all messy as soon as you work with multiple ranges, especially sub ranges of an existing range since you then really need to add 0, not 1, to get the first one of that sub range, so if you want to treat your arrays the same, easiest is to also have them also start at 0. The least messy solution requiring the least subtracting of 1 to fix things is to use 0-based indexing, inclusive start index and exclusive end index such that end - start = size. But probably somebody like Dijkstra can explain it better: "E.W. Dijkstra Archive: Why numbering should start at zero (EWD 831)": https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/E...
- grepthisab 9y agoNice explanation, very in depth. I had to check one of the algorithms a number of times, thinking I was missing something as I couldn't see why it wouldn't iterate beyond the array. Figured it out as the initial arrays are labeled with the 1 as the first index, but as you pointed out the whole iterator changes subtley and looks alien.
- ScottBurson 9y agoI have to tell a story I heard once about Brian Reid [0]. He was in one of these competitions -- this would have been sometime in the 1970s -- and they were given a deck of data cards and told to sort them. Most of the contestants started to write a sorting program in Fortran; Reid looked at the size of the deck and decided he could sort it by hand. He did, and won. [0] https://en.wikipedia.org/wiki/Brian_Reid_(computer_scientist) https://en.wikipedia.org/wiki/Brian_Reid_(computer_scientist...
- wwarner 9y agoeveryone should read this. btw, the problems at http://train.usaco.org/usacogate http://train.usaco.org/usacogate are really fun.
- yuanotes 9y agoNice work.
- webluser 9y agoGreat idea to name file with your book "book.pdf"