Hacker News new | comments | show | ask | jobs | submit login
A Competitive Programmer's Handbook (cses.fi)
1118 points by aaggarwal 163 days ago | hide | past | web | 157 comments | favorite



There should be references to problems for each topic at online judges. Like this one:

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.


The 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/


I bought the A5 version and the printing quality was extremely low, they shouldn't sell something this bad. I would get another format if I had to buy it again.


Are the only difference between CP 1,2 and 3 that each is a newer version? It's hard to tell from the site.


Subsequent versions contain more algorithms and details. Some subtler optimizations are also mentioned in later books.


yes, i believe so.


I see, thanks.


are there other good resources for learning how to apply data structures to problems?


Positive 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.


I have had a lot of experience with competitive programming (competed in NWERC and NCPC multiple times) and this idea that competitive programming makes you worse at software engineering comes up every now and then. From what I've noticed your statement holds a bit of truth, but I just wanted to add from my own experiences. To me it seems like those that have done a little bit of competitive programming are good coders. They can code a FizzBuzz in 2 minutes without blinking, they are people that will reach the magic 10K hours of coding quicker than most. However, those that excel at competitive programming can code FizzBuzz in 30 seconds but you will have a hard time understanding what they have actually written. I think that there is a point in competitive programming you pass where you actively have to sacrifice the understandability of your code (and your algorithm library) for increased implementation speed. I also think that in order to excel at competitive programming you have to devote a lot of time to learning algorithmic theory and training on problems which can be solved in <1K lines of code. (Most solutions I've written are less than 300 lines) The hypothesis I have is that in order to be a great competitive programmer you will have to routinely write bad code and put a lot of effort into solving problems which you will later throw away the solution to and never look at again. Two properties that do not help with software engineering skills. However, if you are only moderately devoted to competitive programming, then you can earn the practical experience (hours of coding) without reducing the quality of your code.


    write bad code [...] which 
    you will later throw away
Implementing a quick & dirty prototype, throwing it away and reimplementing it from scratch is not such a bad software engineering techique: first time to understand the problem, second time to make the implementation nice.

A lot of bad software comes from not throwing the prototype away, but insteat trying to refine it into a product. Result = spaghetti.


I agree. I got into the practice after I picked up F#. I used to create simple solutions in the interactive REPL as mainly proof of concepts. Once I had the basics down, I sat down and wrote a list of possible edge cases, expected user inputs, the format of output and the command line interface for the tool. Then I started coding from scratch and had a good and clean working solution ready. Helped me a lot.


I think part of the misconception comes from the fact that programs written in a competitive programming setting look very cryptic. Variables are not given meaningful names, there're very little comments, sometimes clever tricks are used etc. But people don't realize that in a professional software, they can take the time to write readable code and still make use of their competitive programming skills.


Being good at programming competitions correlates negatively with being good on the job - Peter Norvig

http://www.catonmat.net/blog/programming-competitions-work-p...


This has been circulated around HN and Reddit several times, and it's disappointing that someone of Norvig's stature would present the data in such a misleading way.

Here's a good explanation posted by "tedsanders" the last time this came up on HN:

""" All of these claims from Google that say competition performance hurts or that GPA doesn't matter are missing one huge thing: selection bias.

Google only sees the performance of the employees that it hires, not the performance of the employees that it doesn't hire. Because of this, the data they analyze is statistically biased: all data is conditioned on being employed by Google. So when Google says things like "GPA is not correlated with job performance" what you should hear is "Given that you were hired by Google, GPA is not correlated with job performance."

In general, when you have some thresholding selection, it will cause artificial negative correlations to show up. Here's a very simple example that I hope illustrates the point: Imagine a world where high school students take only two classes, English and Math, and they receive one of two grades, A or B. Now imagine a college that admits students with at least one A (AB, BA, or AA) and that rejects everyone without an A (BB). Now imagine that there is absolutely zero correlation between Math and English - performance on one is totally independent of the other. However, when the college looks at their data, they will nonetheless see a stark anticorrelation between Math and English grades (because everyone who has a B in one subject always has an A in the other subject, simply because all the BBs are missing from their dataset).

When Google says that programming competitions are negatively correlated with performance and GPA is uncorrelated with performance, what that likely means is that Google's hiring overvalues programming competitions and fairly values GPA. """

I've also heard people involved in Google's Code Jam competition say that Norvig's study was done a long time ago, and no longer really applies.



I think what you said is true. But the main point implied here but I didn't mentioned is the mindset or competence is quite different between programming competition & real work. After all, being good on the job depends more on reflection, going slowly, making things right. ;-)


This is relative to other people who had been hired at Google - there's probably still a positive correlation between those two variables amongst the general population.


Very interesting. Although I think he's speaking specifically about competition winnners, not just being good at them.


Oh cool, I was hesitant to say "positive correlation" without data. Thanks for the link!


Not doubtful at all. You can expect a positive correlation between being an good driver and a good software engineer. Definitely some random person with the CS fundamentals, coding fluency, and creative problem solving ability to be good at competitive programming is more likely to be good at software engineering than some random developer. You're basically saying, high intelligence isn't correlated with being a strong software engineer. Or maybe you think people doing competitive programming are damaged. This is nuts.


>> Or maybe you think people doing competitive programming are damaged. This is nuts.

I don't see how that is implied by GP's comment. It is one thing to read between the lines, but now you are reading between the characters.


Yup. More mental "shortcuts" that seek magic "signals" to avoid both evidence and pragmatic interviewing effort testing both business problem-solving critical thinking and cultural fit. There are no shortcuts. Furthermore, "competitive" programming has little to do with the real world, and it's more about showing off and ego inflation.


Reading between the lines: Problems that are typical of software engineering interviews and in competitive programming are poor evaluation of one's capabilities as a professional software engineer.


I'm pretty sure there is a positive correlation, just because people who tend to be good at competitions usually do them because they like computer science in general, so they learn other stuff too (and they are likely smart). And this is also a reason why this side is tested so much in interviews - it is easy to test and the result is somewhat significant.

Now, most good software engineers would probably not be very good at competitions, because competitions require certain specific skills that are not useful outside of competitions. And that's why good interviews don't put too much weight on algorithmic skills.


It sounds like it may have been awhile since you've interviewed. The modern "good" interview is all data structure and algorithm white boarding nonsense. For me, who is not a competitive programmer, the standard interview prep is spending a couple of hours on Hacker Rank every day and making sure I can delete a node in a binary tree on a white board without so much a missing semicolon. For some reason that signals "good developer" more than a catalog of work on github, big name companies, or experience in general.


From my experience i'd rather work with programmers with strong CS skills. They put out better code


I'd rather work with the ones who actually care about the people they're solving problems for vs the ones who can write bubble sort with no reference material, which happens in the real world precisely never. Employers pay developers to solve problems, not necessarily to write the most efficient code possible. I get that it's a craft and it's good to understand what happens under the hood, but you can get pretty damn far solving actual business problems for people without having to care which brand of sort ES2016 uses. These skills in micro-optimizations / textbook CS don't help much with understanding customers and solving their problems at the end of the day, so they're really not that valuable for many business scenarios. I think that a lot of engineers in this industry forget that they're not generally paid to write the most efficient data structures and algorithms for 40 hours a week, and that ironically, attempting to do so would very likely not be the most efficient means of increasing shareholder value. Can't see the forest for the B-trees, if you will.

https://github.com/poteto/hiring-without-whiteboards has a list of companies who don't participate in this particular flavor of shenanigans.


I don't think knowing details of algorithms is why strong CS skills are important.

Understanding CS teaches a lot about seeing abstractions and choosing between different levels of abstraction and problem solving. It greatly helps modelling business problems as software. I don't think it is important as an end in itself.


being good at physics doesnt help you jump higher. its good to know theory, but to be good at something you need practice.


True, but being good at physics helps you build a better airplane.

And I'd argue programming is closer to building an airplane than it is to the almost innate skill of jumping.


I interviewed this week. While there were a few whiteboard coding questions that I personally wouldn't ask, most of the interviews were quite reasonable (mostly algorithmic still, but it was in robotics, so understandable). But yeah, I actually don't understand why people insist on using a whiteboard so much. Everybody has a computer these days and typing is much faster.

At my previous company (not robotics) I conducted a lot of interviews and I think we hit a good balance between algorithmic problems and design/architecture ones. Then again, even algorithms questions can be formulated as real world problems - it help weeding out obvious brain teasers. We also didn't asks people to write code on the whiteboard - there was a separate coding exercise.

I don't even think that asking about algorithms is such a bad thing if you do it correctly and it's not all what you do. But perhaps too many people just throw a problem at the interviewee without and help or guidance.

Overall, conducting a good interview is hard and it is not a primary job of most engineers who do it, so it's not surprising there are quite a few bad interviewers out there.


I observed a correlation between competitive programmers and those who come across as just hacking at it until it works in interviews. If your interview system is looking for people who think about things then it probably already biases against many competitive programmers correctly.


Your second assumption is only valid for people who conflate the two disciplines. If you don't recognize that competitive programming and software engineers have completely different goals and requirements, then being trained in competitive programming may very well lead you to bad programming practices - e.g. single-letter names are usually fine for competitions, while at the same time usually horrible for engineering.

However, if you recognize the differences and use the skills you learn in the two as complementary, you can be better at both.


Maybe not, but just skimming through the topics looks like there is a lot of overlap between competitive programming and popular job interview questions.


You have a very weak understanding of what the word 'correlation' means.


Agreed. These kinds of competitions or coding interviews may cause over-fitting.


Is there really risk in being particularly adept at algorithm design?


The 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.


This comment is so good that I think just being able to write it would qualify someone for a midlevel programming job!


Senior


Think of it this way: there's only a certain amount of productive hours available to people for side programming, and either you spend a majority contributing to open source/building prototypes/learning new technologies/getting your hands dirty; or you spend a majority of the time solving artificial problems to get a leg up on programming interviews. It's a catch-22 if ever there was one.


No, 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).


This 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/ - however, it's all in Finnish.


I 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...


There is also https://e-maxx-eng.appspot.com/ (translated from russian, original: https://e-maxx.ru/algo/)


This is a great 'advanced' resource! I've been reading the google translate version of the Russian page. Really nice to have a real translation!


OK, 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.


If you want to be a really well paid programmer, just learn java and assorted technologies and go work for a bank.


...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.


> ...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.


I agree with both your points.


Working at a Big4 or prop shop pays even better (in most cases...)


Yeah, figured that already.


Competitive programming = coding challenges, like Google Code Jam and HackerRank.

Nothing to do with getting a better job or a better salary.


But 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.


Relax, parent poster was simply clarifying that the 'competitive' referred to programming "sports" contests, not competing for a programming job.


Sure, 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.


I 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.


Doing + training for local & ACM programming competitions was easily as valuable for me as the CS classes I took in college. (It helped that our coach was the awesome Eugene Luks.)

There's a lot more than just the core problem solving bits involved in making software, but it's a v. useful skill.


The 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.


In 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.


I think the GP means that problems solved in programming competitions are similar to what you'll find on some job interviews.


Sure, 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."


I 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.


Staying 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?


Actually, yes please. Can be published as a book and sold for money!


Sadly the proliferation of sites like HackerRank (YC funded shamefully) means competitive programming is the first "filter" stage for interviews these days.


I'd love it if there were more opportunities from companies like HackerRank. It's other "filters" that I'm worried about; companies that filter out degree-less candidates, companies that filter out depressed candidates, companies that filter out transgender candidates, etc.


Do you have links to any articles about these practices?


First, I should warn you that I'm no expert! I'm not the most informed or up-to-date about discrimination in hiring. However, I'll try to provide some helpful links.

First, depression. The correlation between unemployment and depression has been studied since at least the 1980's. One issue that has been considered but never completely explained is the "direction of causality." In other words, does unemployment cause depression, or are depressed people more likely to be left unemployed? Some articles suggest the former, while others suggest the latter; it may well be that both are true. From what I've seen, much of the research focuses on the impact of unemployment on mental health. Here's a Forbes article which is a bit more approachable:

https://www.forbes.com/sites/susanadams/2014/06/09/how-unemp...

If you'd like, you could dive into some of the relevant research articles yourself. Here are a couple articles I found that may be relevant:

https://link.springer.com/article/10.1007/s00420-016-1178-7

https://www.cambridge.org/core/journals/psychological-medici...

http://neuro.psychiatryonline.org/doi/abs/10.1176/appi.neuro...

http://ps.psychiatryonline.org/doi/full/10.1176/appi.ps.55.1...

https://academic.oup.com/ije/article/28/1/95/777542/Unemploy...

There are probably better sources out there, but as I said, I'm no expert and I'm not up-to-date on the research!

There are several challenges facing research into the relationship between unemployment and depression. For one thing, depression can have a number of other causes, and associated risk factors. It can be hard to pick apart the causes from employment status. Another issue is gathering data. Many companies here in the US will ask for voluntary self-identification when a candidate applies; often, however, depression is considered to be in the same category as other disabilities so that it's impossible to pick apart the rate of depression among candidates from the rate of disability among candidates. Another issue that applicants may decline to self-identify. Some companies are better than others at gathering data about depression among workers, and trying to help those employees.

Next, transgender. Here, the research is less well-developed. The transgender population is rather small, so data-gathering hasn't been a high priority until recently. Most data comes from survey of transgender individuals rather than from employers. There may be some inherent bias as a result, but at the moment it's really the best data we have. I'll point you to the National Transgender Discrimination Survey, which was released in 2016 based on data gathered in 2015:

http://www.transequality.org/sites/default/files/docs/resour...

The report is rather long, but it had several important findings: 1) Transgender employees have double the rate of unemployment as the average. 2) 26% reported being fired due to their gender identity. 3) 90% reported harassment at work. 4) The effects compounded with other factors such as race or poverty.

It's worth noting that many states in the US offer no or few protections against LGBT employment discrimination. Here's a map to show how protections differ across states:

https://en.wikipedia.org/wiki/LGBT_employment_discrimination...

I won't touch the degree issue; it's been discussed plenty elsewhere on hacker news, and there's still the mentality that candidates with degrees are better than candidates without.


>>degree-less candidates, companies that filter out depressed candidates, companies that filter out transgender candidates, etc.

Sorry, these are completely different things and frankly sounds like nonsense.


Would you say that there is no discrimination along these lines, and that most companies aren't biased against, say, transgender candidates when making hiring decisions? I'm just curious.


I've no doubt that tech is discriminatory - as a minority myself I've definitely experienced odd feedback at interviews "the team were impressed by your abilities but we've decided to proceed with someone else" etc. I just mean to compare rejecting degree-less candidates is not equivalent to discrimination against "non-fit" groups (gender, ethnic, sexuality minorities) as a degree is a technical qualification and not a protected characteristic.


I 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.


Is that sad? It's a better filter than college degrees.


So 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?


But 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.


Really, 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...


I 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.


More 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.


You forgot the most important. More real world experience, and a well formatted resume.


Definitely all things I'd like to work on.


It 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.


I 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.


Nothing to do with the actual job but it is heavily used for interviews to get that actual job, unfortunately.


This 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.


Besides basics, I've learned and forgot several times, so I don't have enough motivation nor time to re-learn again :)


I 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.


Agree with other comments about similarity to interviews.

Norvig seems to think it's a negative signal though. https://www.youtube.com/watch?v=DdmyUZCl75s


I 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.


I 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.


I 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...


Especially given the importance of teamwork. Competitive people tend towards tedious one-upmanship. It's something you want to screen out in the hiring process.


Programmers participate to ICPC in teams of three. According to my experiences, teamwork is a fairly important part of success since there is only one computer for each team.


Competitive people are often very good at working in teams, see any team sport, or team programming contests.


I 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.


I 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.


Elon 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.


Ok you must love competitive programmers then, because they are very driven to solve problems :)


If you do the Google Code Jam, they might use that info to recruit you.


For those interested -> TopCoder annual competition just started (Marathon track which is usually 2 weeks length optimization problems): https://community.topcoder.com/longcontest/?module=ViewProbl...


The author originally released the book here (http://codeforces.com/blog/entry/50728).


in a similar vein there is : https://cpbook.net/ which is also pretty cool. will take look at this also. thank you :)


Excellent 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.


i love solving problems. but hate solving programming riddles with artificial rules. it feels much more like work then actually real work does.


This is a well-written book, very nice work!


I 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.


Agreed, 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/E...


Looks like the indexing will be changed to 0-based in the next draft. https://github.com/pllk/cphb/commit/35d53d39d494cdc2d8f884c3...


Nice 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.


Really 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.


Good review for algorithms and data structures. Hopefully we can get a printed copy later.


Not 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.


everyone should read this. btw, the problems at http://train.usaco.org/usacogate are really fun.


Great timing considering Google Code Jam Round 1 starts tonight too


Link? / What is it? / Is it a good thing to test out for beginners?


It'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!


Here's the link, but the qualification round for this year has already passed. https://code.google.com/codejam/


Another good resource for clearing technical whiteboarding tests.


That was my thought while reading through it, but its basically just an algorithms textbook, which makes technical interviews seem even more daunting.


Thoughts on this vs. Steven Halim's handbook?


Great idea to name file with your book "book.pdf"


At first glance, I saw String Theory and was about to laugh, but then I found it was String Algorithm and Game Theory :D


i 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.


this 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] ?


The LaTeX source for the book is on Github: https://github.com/pllk/cphb


Thanks for sharing, will look it over and send you some feedback.


Nice work.


Great. Thanks!


great stuff.read this,understand this and you'll get google offer for 350k per year.


Why 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.


> be me

> go to grad school, get PhD in mathematics

> get hired at Google (also works anywhere else)

> 300k starting

Pretty sure this is how it works (just ask around on 4chan).


if 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.


I 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.


For new grad (B.S.) software engineers this year, the standard offer is ~160k total compensation amortized over the first four years, including signing/target annual bonus but not including any raises or stock refreshers that may happen.

I'm graduating with an M.S., starting this summer. Using competing offers, I negotiated up to 190-195k amortized over four years, including 215-220k in the first year (because of signing bonus). I ended the negotiation a little early because of stress and likely could've pushed 210k amortized.

My resume isn't anything special, but I practiced enough to be good at the whiteboard interviews. The best-of-the-best new grads are probably getting close to 250k, but there aren't many of them.


There might be a few that accidentally fall into unicorn jobs, but best-of-the-best are right about in your range. There's just not enough data on potential hires to create that kind of valuation, and if they are best-of-the-best, they'll rapidly rise.


Off topic from parent. But which companies were your competing offers from?

I failed to negotiate recently with other offers.


Facebook. From what I can tell, Google's negotiating strategy is to offer max(their initial offer, highest competing offer+10k). The only people I heard of them not doing that for were those getting absurd amounts of stock from Snap, pre-IPO (like $300k+ worth at estimated IPO price over four years).


Any particular resources you'd recommend for getting good at white boarding?


Elements of Programming Interviews until you can do Leetcode mediums with a good success rate. Then grind Leetcode, try to work your way up to hards. Practice EPI problems with a friend on a physical whiteboard throughout. I did this for a month leading up to my interviews and it helped immensely.


This 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...


We detached this subthread from https://news.ycombinator.com/item?id=14116263 and marked it off-topic.


First, the parent poster was referring to the book being well written, not to the set of practice problems from an entirely different book. Thus, your "horribly written" comment comes off as a non sequitur.

Second, the subset contains k elements. The phrasing "select a subset S containing k of these elements" is standard mathematical terminology. I'm not sure how you read this as meaning that each element needed to be less than k.


The size of S is k.


The problem is your reading comprehension. That reads just fine to me. Pretty standard writing.


Your 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"


I've always looked at internet conversations as gentleman's agreements in politeness and respect. What I mean by this is that any given internet comment can be a hate filled flexbox of bile and swear words, but most aren't, because that would be a violation of the agreement. But once the agreement is broken (or one of the tiers of the agreement is broken) then no subsequent discussion is beholden to that level.

So in this example, you broke the tier of "blunt criticism". Now that the tier is broken, all responses to your comment are not beholden to that implied agreement. And rightfully so, one of the comments bluntly tells you that you're the one with the issue. Then you said this was completely uncalled for even though a) you started being blunt and b) their response was less rude than yours.

So in summary. Don't dish it if you can't take it.


wait, I broke the "the tier of blunt criticism"? Ha ha.

Not only are you accusing me of breaking some arbitrary rule you invented but that is definitely the pompous phrase I have ever read on HN.


When discussions get to this level they automatically don't belong on HN. Please don't do this here, regardless of how wrong other people are.


"Horribly written" is blunt criticism, like it or not. The parent post is saying that because you delivered blunt criticism, you should be prepared to take it too.


If you actually read what I wrote I said "This seems to be horribly written." Note the word "seems" that is not the same thing as saying "it is." I then go on to ask a question for clarification which some folks were kind of enough to point out helpful and corrected interpretations. Asking a question and admitting something wasn't making sense to you are not at all the same thing as "dishing out criticism."


"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".


I didn't cut anything out I actually reposted verbatim the entire problem description in my post. Or did you choose not to read that part?


I specifically meant the post I replied to (where I'd agree, just that piece would be ambiguous. The full one as quoted in your initial post is not, because the part I highlighted clarifies the meaning)


It looks like k doesn't even matter apart from reading the input for the problem.


Thanks for this, it may be exactly what I was looking for :)




Applications are open for YC Winter 2018

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: