The most irritating thing with these competitive/algo stuff is that no matter how many times you master it - eventually you always forget it, because you don't need it on a daily (or more like yearly) basis in the real world.
It's not about needing it in "the real world". It's about having fun. It's about the adrenalin rushing through your veins as the clock ticking down. It's about burst of joy when your brain just clicks and the invisible wall falls down, showing a path to the solution. I still do Putnam and IMO every year, I also occasionally take an hour or two during work and just solve Math problems. Solving problems is a hobby, just like video games. There's nothin really practical about it and there doesn't have to be.
This is the case with anything you didn't discover it yourself but rather 'learned it', that's actually just a replaceable term for 'memorized it'.
People who discovered/invented these algorithms traversed several years of curiosity, blind alleys, dead ends, failures and successes. You can't possibly expect to get it all and make it up on memorization alone.
Algorithm learning is hard for the same reasons memorizing Math tables are hard.
As of today there is nothing novel about merely learning how a algorithm works and spitting it out in an interview, if anything it achieves the exact opposite goal of what it is supposed to.
This is true for lots of things though, right? Programming languages, spoken languages, mathematics, muscle mass...use it or lose it, but it gets easier to re-learn/re-gain everything each time. Plus you don't necessarily have to forget or lose it if you're able to set aside the time to maintain it.
Exactly. Having the experience of solving difficult algorithmic puzzles under time pressure makes parts of software engineering (writing working code, debugging) easier, so you can focus on the hard parts. Algorithmically, almost anything written in the real world is trivial in comparison.
I guess most of the problems are relatively small, but for Advent of Code¹, the "competitive" people are finishing most of their solutions in a minute or two.
How will you look it up when necessary during a programming contest (like the IOI/ICPC mentioned in the book)? It's usually not allowed by the contest rules to look up an entire book's worth.
And if your teams algo and data structure knowledge isn't at the level where you know about these solutions or their applicability?
I have a checklist of possible interview topics and I think I might an esoteric data structure part to it (knowledge not code) and some implementation choice questions - given this situation and data, with these queries what would your data structures look like.
Maybe also a few quotations on the last paper they've read in CS or related topic.
I'm not sure I understand: the linked book is meant for high-school and college students, or anyone participating regularly in programming contests:
> The book is especially intended for students who want to learn algorithms and possibly participate in the International Olympiad in Informatics (IOI) or in the International Collegiate Programming Contest (ICPC). Of course, the book is also suitable for anybody else interested in competitive programming.
Anyone in the target audience of the book will encounter most of this frequently enough; I definitely didn't have the experience (when I was in college and doing competitive programming, over a decade ago) that I was forgetting most of it.
Of course, if someone is not interested in competitive programming and never uses any of the knowledge they're likely to eventually forget it; it's just like learning a bit of French or group theory (say) and not touching it again for years — it's possible to forget. But not sure why that's irritating; it's just the nature of learning, at least after a certain age or below a certain threshold of practice.
That’s the entire point of those kinds of interviews. It’s a strong filter for “recent graduate” while maintaining plausible deniability for ageism. It has a secondary effect of filtering for “willing to do unpaid overtime”.
I see in the comments that some people conflate competitive programming and technical interviews. Technical interviews (at least in companies such as facebook and google) are usually much easier than competitive programming problems. The problem you find on leetcode for interview preparation would be considered beginner problems in competitions such as google code jam.
> Technical interviews (at least in companies such as facebook and google) are usually much easier than competitive programming problems.
Probably. But if you are a student outside U.S where the opportunities are an order of magnitude less the only way to even land an interview with these companies is by doing competitive programming. Google selects students through APAC test in Asia where you have to be top n% in the leaderboard to even get an interview. Doing leetcode and all would not take you anywhere in these contests as you are competing with hardcore student programmers who have been practicing competitive programming their entire University life in search of an escape from the middle class. All the persons I know of in my country who works at Google or Facebook got their job through competitive programming.
Most people who are doing competitive programming aren't good at the harder problems. For example, there are >2500 people listed on the TopCoder Top Ranked Algorithm Competitors page (https://community.topcoder.com/tc?module=AlgoRank), but only the top 115 or so are Red, and only about 415 more are Yellow.
A programming contest, even if you just do the easy problems, can be a more enjoyable way to practice for interviews than reading a book or even going through online puzzles like those on LeetCode.
This is a good resource that I'm currently going through to prepare for interviews. Another one would be Competitive Programming (3rd edition) [1] but for general interview skills the Codility lessons are also OK [2].
I like this book, but I have some reservations for using it for interview practice. There is no discussion on implementation of some of the algorithms, which may be relevant in an interview (e.g. if you're not allowed to use std::sort).
There are also a lot of topics where there's a brief overview of the algorithm, but no code - e.g. the geometry section is interesting and has some useful ideas, but no implementation. This gets worse as the algorithms get more complicated, and some quite difficult topics get a cursory glance.
For the general categories of problems that you find on e.g. LeetCode or Intervewbit, this book is really useful. It's a good, practical, companion to a proper algorithms textbook.
Perhaps most irritating - if using this for prep - is that there are virtually no case studies, and the case studies that are in there assume a lot of code which isn't in the book (either boilerplate or assistance functions). This book would be incredibly valuable if each chapter had a list of example problems (solved or unsolved) to see how things are applied.
Has anybody gotten into this kind of programming post-college? Are there communities outside of high school and college competitions for this sort of thing?
Yup. Check out TopCoder[1]. They have regular programming contests every week or so. The contests are conducted in two divisions(amateur - div 2) and (pro - div 1) and candidates are assigned different colors on the basis of their performance. Becoming a red coder in TopCoder is a pretty big thing in the competitive programming community. For example, Adam D Angelo who is the co-founder of Quora used to be Red on Topcoder[2]. Most of the red coders of TopCoder get hired by companies like Google, Facebook etc. It's pretty hard for one to fuck up a competitive programming interview once you became a Red level candidate in TopCoder. Mark Zuckerberg also tried TopCoder for a few months while in Harvard [3].
CodeForces[4] also has a pretty big online community. I think it has become more popular than TopCoder these days. They also have regular contests every few days.
Facebook[5] and Google[6] also hosts competitive programming contests every year. If you managed to make it to the final round I think they would invite you for an interview.
As few comments already mentioned, post college, preparing for this type of thing immensely helps in job interviews. I find it very hard to clear job interviews and in 2017 alone, I appeared for ~25 job interviews. I'm very convinced that competitive programming skills gives you a leg up in job interviews.
Many people may already may know this, but Peter Norvig indicated that it correlates poorly with on the job performance (at least at Google) [1]. I wonder why, then, companies still continue to do this style of interviews.
Well, I think you're kind of misrepresenting his point as "competitive programming doesn't improve your programming abilities".
It's not that competitive programming correlates poorly with job performance; it's that, given you've been hired by Google, being a competitive programmer correlates poorly with job performance.
Hypothetically, let's say there's 2 dimensions for a programmer's ability, competitive programming and job experience. Each of these is distributed independently from 0-10. You get hired by Google if competitive programming + job experience > 10. However, let's say that for their actual job performance, it's 0.5 x competitive programming + 1.5 x job experience.
You now have a case where competitive programming could correlate poorly with job performance at Google, despite having a positive correlation in general.
Yeah, I think they are a terrific way to "keep your sword sharp". Jump start the neurons in the early AM or lazy summer day. As well as a way to learn new algorithms, new languages via problem solving.
Code Jam had a particularly juicy one in the recent Qualifying Round, that could easily be part of a modern shadow rendering game engine. Just to put it into perspective, only around 1000 out of 25000 entrants were able to solve the large data set in the allotted time!
Google Code Jam 2018 Qualifying Round Problem D: Cubic UFO
Incidentally, I don't really learn a lot from books or tutorials such as the one linked. But rather from the contest analyses and top winners code solutions.
I imagine the juicy part is that there is no clear cut formula for determining the rotation from the area needed.
Thus the task is to come up with a fast approximation algorithm to work backwards.
So brute force way:
If area_needed > area_cast:
rotate_cube(delta)
delta=/2
else similar rotation on -delta
Now, my 3d geometry is rusty, so maybe rotation on 2 axis is enough but still optimizing 2 arguments is not going to be easy. Maybe you can max one rotation then max 2nd one.
My first instinct says that if you just project the corners straight down (because of orthographic projection) onto the XZ plane, then the area of the shadow is just the area of the convex hull of those projected points.
I don’t know how to calculate that hull off the top of my head, but that’s the type of stuff you can look up during real world scenarios.
I participated while in high school and university and kept having fun on Codeforces[1]. It's a great community with very frequent tournaments and they always have detailed explanations of the expected solutions after the tournaments.
In my experience, most of the time goes into coming up with an algorithm or debugging. I don’t know about you, but I don’t think those would be particularly interesting to watch.
I am mostly just fascinated by people able to stream their coding. I think most of my stream would consist of googling stuff and procrastinating on hacker news and tabloids
Readit News
People who discovered/invented these algorithms traversed several years of curiosity, blind alleys, dead ends, failures and successes. You can't possibly expect to get it all and make it up on memorization alone.
Algorithm learning is hard for the same reasons memorizing Math tables are hard.
As of today there is nothing novel about merely learning how a algorithm works and spitting it out in an interview, if anything it achieves the exact opposite goal of what it is supposed to.
Deleted Comment
Deleted Comment
Why not look them up when necessary ?
1. http://adventofcode.com/
I have a checklist of possible interview topics and I think I might an esoteric data structure part to it (knowledge not code) and some implementation choice questions - given this situation and data, with these queries what would your data structures look like.
Maybe also a few quotations on the last paper they've read in CS or related topic.
> The book is especially intended for students who want to learn algorithms and possibly participate in the International Olympiad in Informatics (IOI) or in the International Collegiate Programming Contest (ICPC). Of course, the book is also suitable for anybody else interested in competitive programming.
Anyone in the target audience of the book will encounter most of this frequently enough; I definitely didn't have the experience (when I was in college and doing competitive programming, over a decade ago) that I was forgetting most of it.
Of course, if someone is not interested in competitive programming and never uses any of the knowledge they're likely to eventually forget it; it's just like learning a bit of French or group theory (say) and not touching it again for years — it's possible to forget. But not sure why that's irritating; it's just the nature of learning, at least after a certain age or below a certain threshold of practice.
Arguably competitive programming helps with this problem by letting you drill the concepts you've learned.
I fear it is like chess, the cognitive decline starts to become noticable in the mid 40s and only gets worse from then on.
There are a few exceptions like Korchnoi was in chess so there must be Fabrice Bellards and Bill Joys who would be able to keep up.
Still looking at completion times for Advent of Code made me feel old.
Probably. But if you are a student outside U.S where the opportunities are an order of magnitude less the only way to even land an interview with these companies is by doing competitive programming. Google selects students through APAC test in Asia where you have to be top n% in the leaderboard to even get an interview. Doing leetcode and all would not take you anywhere in these contests as you are competing with hardcore student programmers who have been practicing competitive programming their entire University life in search of an escape from the middle class. All the persons I know of in my country who works at Google or Facebook got their job through competitive programming.
Are any of them bad developers?
A programming contest, even if you just do the easy problems, can be a more enjoyable way to practice for interviews than reading a book or even going through online puzzles like those on LeetCode.
1 - https://www.amazon.com/Competitive-Programming-3rd-Steven-Ha...
2 - https://drive.google.com/open?id=1WjXxbdle0_Syip_LygBpnZkfHv...
There are also a lot of topics where there's a brief overview of the algorithm, but no code - e.g. the geometry section is interesting and has some useful ideas, but no implementation. This gets worse as the algorithms get more complicated, and some quite difficult topics get a cursory glance.
For the general categories of problems that you find on e.g. LeetCode or Intervewbit, this book is really useful. It's a good, practical, companion to a proper algorithms textbook.
Perhaps most irritating - if using this for prep - is that there are virtually no case studies, and the case studies that are in there assume a lot of code which isn't in the book (either boilerplate or assistance functions). This book would be incredibly valuable if each chapter had a list of example problems (solved or unsolved) to see how things are applied.
1 https://www.topcoder.com/
2 https://www.topcoder.com/members/dangelo/
3 https://www.topcoder.com/members/mzuckerberg
4 http://codeforces.com
5 https://www.facebook.com/hackercup/
6 https://code.google.com/codejam/
Many people may already may know this, but Peter Norvig indicated that it correlates poorly with on the job performance (at least at Google) [1]. I wonder why, then, companies still continue to do this style of interviews.
[1] https://www.youtube.com/watch?v=DdmyUZCl75s
It's not that competitive programming correlates poorly with job performance; it's that, given you've been hired by Google, being a competitive programmer correlates poorly with job performance.
Hypothetically, let's say there's 2 dimensions for a programmer's ability, competitive programming and job experience. Each of these is distributed independently from 0-10. You get hired by Google if competitive programming + job experience > 10. However, let's say that for their actual job performance, it's 0.5 x competitive programming + 1.5 x job experience.
You now have a case where competitive programming could correlate poorly with job performance at Google, despite having a positive correlation in general.
Deleted Comment
Code Jam had a particularly juicy one in the recent Qualifying Round, that could easily be part of a modern shadow rendering game engine. Just to put it into perspective, only around 1000 out of 25000 entrants were able to solve the large data set in the allotted time!
Google Code Jam 2018 Qualifying Round Problem D: Cubic UFO
https://codejam.withgoogle.com/2018/challenges/0000000000000...
Incidentally, I don't really learn a lot from books or tutorials such as the one linked. But rather from the contest analyses and top winners code solutions.
I imagine the juicy part is that there is no clear cut formula for determining the rotation from the area needed.
Thus the task is to come up with a fast approximation algorithm to work backwards.
So brute force way:
Now, my 3d geometry is rusty, so maybe rotation on 2 axis is enough but still optimizing 2 arguments is not going to be easy. Maybe you can max one rotation then max 2nd one.I don’t know how to calculate that hull off the top of my head, but that’s the type of stuff you can look up during real world scenarios.
[1]: codeforces.com
There was a HN discussion recently about programming livestreams.
Skiena and Sedgewick both have excellent books and online courses if you need more depth.
A nice thing about this book is that the full TeX source is on github.