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.
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.
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
But the submission does not mention job interviews. The linked book (the author is “one of the organizers of the Finnish Olympiad in Informatics […] coached and led the Finnish team at several international programming contests, including the International Olympiad in Informatics”) is someone's labour of love, written for people interested in this hobby. It brings joy and satisfaction to many people, most of them young students. Why throw cold water on them, by reacting to mention of such a book with terms like “irritating”, based on something that others do in some other setting entirely? Or, even if bringing up job interviews is justified (no doubt your irritation is real), it would be nice IMO to at least preface the comment by clarifying that the comment is not about the hobby/competitive-programming world that are the subject and audience of this book, but about something else.
It's also detrimental to the business.
There are tests and interviews because not everyone can
In a high pressure situation like an interview, I personally find it difficult to think naturally through a problem. Familiarizing myself with different types of interview questions regularly helps a lot.
10 years ago I was pretty handy with CLRS, but now I'd be hard pressed to implement quicksort without looking it up.
One self-driving car start-up in SV wanted me to solve a long-standing research problem (Deep Learning) as their week-long take home test. Thanks, but when I do, you can license my tech, I will gladly make it available to you for $.
The shit is ridiculous.
EDIT: Please write that blog post!
People in their 20s and 30s now will regret not stamping out ageism when they hit their 40s and 50s, as they inevitably will
The problem is, everyone in their 20s and 30s assumes they'll be gazillionaires by the time they're 40, because of course they're brilliant and hard work always pays off! Ageism is only a factor if you're not smart enough to make a billion by the time you're facing it.
In my practical experience I find that to get the "aptitude" requires a lot of effort put in it. It definitely would vary depending on the person and his experiences but practicing it is very important to go forward.
They are a test of how recently you crammed for your CS finals, that’s all.
Which, to some extent, makes sense. You're basically filtering out people who won't put in the effort to get the job. Whether or not those who put in the extra effort are actually going to be better employees is a different decision.
To your larger point, data structures and algorithms are popular in interviews for the same reason Project Euler is popular - it is very easy to ask a well defined, but interesting question about core CS or math.
As is, it's more like advertising for python, then surprise java.
But those kinds of questions make zero sense and have zero value if the job is actually implementing CRUD apps in a high level language. You might as well quiz candidates on their assembly language skills too, for a Python job...
So there is obviously an ulterior motive.
https://github.com/LoupVaillant/Monocypher/commit/d7bb73f65a...
So I have this function, `crypto_wipe()` that wipes memory regions with `volatile` so the compiler doesn't optimises it away. In the link above I was using it thus:
crypto_stuff(stuff_ctx *ctx) {
// stuff
crypto_wipe(ctx, sizeof(ctx)); // BUUUG!!
}
Now I write this instead:
crypto_stuff(stuff_ctx *ctx) {
// stuff
WIPE_CTX(ctx); // correct!
}
That being said, I've found that competitive programmers sometimes write extremely ugly code. It's surprising to see how they are able to solve such complex problems, and yet can't (or don't value) write readable and structured code. Maybe they are so sharp that they don't feel the need to make their code more readable.
Speed is the goal here.
Then why is it used in the interview process for the latter?
During my professional time I write software to make money. During my free time I write software to make money. As an aging software engineer algorithmic questions just screen for how much time you're willing to put into an interviewing. GitHub screens for how much of a sucker you are.