A Competitive Programmer's Handbook
cses.fi
cses.fi
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.
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).
write bad code [...] which
you will later throw away
A lot of bad software comes from not throwing the prototype away, but insteat trying to refine it into a product. Result = spaghetti.
http://www.catonmat.net/blog/programming-competitions-work-p...
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 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.
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.
https://github.com/poteto/hiring-without-whiteboards has a list of companies who don't participate in this particular flavor of shenanigans.
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.
And I'd argue programming is closer to building an airplane than it is to the almost innate skill of jumping.
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.
However, if you recognize the differences and use the skills you learn in the two as complementary, you can be better at both.
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.
You can find the course material and assignments from https://cses.fi/alon/ - however, it's all in Finnish.
[0] https://en.wikipedia.org/wiki/Brian_Reid_(computer_scientist...
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.
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.
Nothing to do with getting a better job or a better salary.
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.
So I was grateful for the clarification, and didn't take it as algorithm-hate.
There's a lot more than just the core problem solving bits involved in making software, but it's a v. useful skill.
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.
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.
Shall we start a comprehensive list of skills and activities tangentially related to making more money?
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.
Sorry, these are completely different things and frankly sounds like nonsense.
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.
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 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.
Norvig seems to think it's a negative signal though. https://www.youtube.com/watch?v=DdmyUZCl75s
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 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.
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.
"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...
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!
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] ?
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.
> 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).
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.
I failed to negotiate recently with other offers.
>"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...
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.
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"
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.
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.