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.
Why not look them up when necessary ?
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.
2 https://www.topcoder.com/members/dangelo/
3 https://www.topcoder.com/members/mzuckerberg
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.
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.
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:
If area_needed > area_cast:
rotate_cube(delta)
delta=/2
else similar rotation on -delta
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.
for (int i = 0; i < n; ++i) {
for (int j = 0; i < n; ++j) {
...
So if you have (in your pre-written library of snippets) a macro like
#define FOR(i, n) for(int i = 0, _n = n; i < _n; ++i)
FOR(i,n) FOR(j,n) {
...
And I don't mean to say the whole thing is bunk. I found some really good info farther into the book, especially about algorithms, which I think will help towards interviewing candidates.
This is a great summary to a ton of CS algorithms and datastructures. Thanks for compiling this.
Boring but immensely more useful.