This is nice list and ability to implement these algorithms certainly won't hurt.
But I have to say that knowing these algorithms alone won't help you much during job interview with smart employer like Google.
The reason is simple but often overlooked by many people: the most important thing is not these algorithms themselves but ability to recognize them in problems.
You may learn pretty quickly how these algorithms work and implemented but it may take years of practice to earn ability to recognize them.
Google won't ask you directly to implement Dijkstra algorithm. They may give you a problem which on surface have nothing to do with graphs. It may take a while before you actually have a light-bulb/aha moment when you realize it's a graph problem.
In practical non-interview problems, ability to recognize algorithms is much more important than knowing their implementation. You can always find their implementation on the Internet after all.
This is why I'm trying hard to improve my problem solving skills by solving competitive programming problems almost everyday.
And then when you get the job, you will likely never use this skill again. 50% of your time will be spent on plumbing and wiring, 40% on meetings and politics and "agile processes", 9% on learning new ways to plumb and wire, and maybe 1% of your time will utilize these sorts of skills that can otherwise be identified from afar and solved by looking up in a book.
Once you get your foot in the door, this sort of trivia becomes vastly less important than your ability to impress the right people and politically maneuver yourself into winning situations. This is the reality of life in a mega tech corp.
That, of course, depends where you work. My daily work is math intensive and performance critical. I constantly need to think about cache sizes, big-O scaling and that ever-important constant factor. I've seen commits failed by QA because they inadvertently added a shared_ptr copy in a tight loop, which affected performance of the entire pipeline by 20%.
So yeah, I regularly have to think about dynamic programming, switching away from a linear low-constant algorithm once the problem is no longer small, how something could be restructured to be massively parrellizable, even alignment of arrays so that we get reasonable SIMD performance.
Yes, these jobs exist, and yes, they do require a strong algorithms background, as well as a good understanding of memory heirarchy, branching delays and what can be offloaded to GPU or at least parallized.
My daily work is math intensive and performance critical. I constantly need to think about cache sizes, big-O scaling and that ever-important constant factor.
Me too, at least for some of the projects I'm working on, but it's probably fair to say that I've never used most of the "textbook algorithms" I've come across over the years in a production system.
The interesting and challenging problems are mostly the ones that aren't just a direct application of such an algorithm. Consequently, I think the more valuable ability is recognising when a part of such a problem probably does have a standard solution, so you can spend a few minutes looking up the current state of the art.
Obviously you still need enough familiarity with the theory in the areas you're working in for that recognition to work, and then to understand the current state of the art when you need it.
Small correction: it depends on what problems you work on.
There are people at top companies making big money working on complex problems, there are also people at those companies who passed through a super-algorithm-heavy interview and work on much less mathematically demanding code. And there are people at small companies you've never heard of working on much more intense problems than them. But the people doing boring work at big companies are often making $$$ compared to the people working at small companies working on interesting stuff. (I've been both of those people...)
Computer vision late-stage startup, 80+ people now I think, of which 50 are devs. Of course not everyone does what I do, we still need people to work on the UI and packaging/licences etc. But at least 50% of the devs here do very research-oriented work.
In terms of business, I question whether most companies have the financial justification to implement math heavy software strategies, or novel strategies.
For many businesses, I wonder if their software requirements are generally boring with many parts of their problem already solved and implemented in the form of a framework, with a few libraries waiting to be glued together.
I also have the suspicion that for companies such as Cloudflare, where there is justification to implement either novel or math-heavy strategies, these kinds of companies trust very few people to make the business and technical judgment call to pursue a strategy aside from simply using off-the-shelf solutions.
But a lot of people may be screened on these matters without the company ever intending to take advantage of the abilities they test for. I really wonder how often Google takes advantage, or even trusts their employees, to make such decisions or exercise such abilities, as opposed to a few superstar Googlers.
Software in a nutshell. The 'can you invert a binary tree' coming of age ritual one studies so hard for. You know it will happen before you step into the interview room and there's no escaping it, but you go in nevertheless.
> This is why I'm trying hard to improve my problem solving skills by solving competitive programming problems almost everyday.
Here is another simple tip to improve your ability to recognize algorithms: Just look at the software you use every day and ask yourself how does it work.
When you make a click on your web browser, how does the browser know what element you clicked?
When you tell you StarCraft unit to move to a given point, how does the game engine know what path it should follow.
Are you using a Redis cache with an LRU eviction policy, how does that work? Why it's so fast? (hint: it's not only because it's written in C)
You know that adding indexes to your database columns makes them faster. Why? How does that work? What are the tradeoffs of the the different kinds of indexes.
When you type `ls -R` in the console, what's happening?
How is it that Google can give us the results of searching on trillions of webpages in just a fraction of a second?
It's sad to see a general sentiment here on HN against algorithms and data structures. In reality, most of the tools we use everyday use all those algorithms and data structures.
If you feel that you don't need to know about algorithms and data structures, you probably do very mechanic and simple things like CRUD software. The moment you do something slightly more difficult or at a bigger scale, you are going to need this knowledge. You simply can't be a good developer without understanding these concepts (I'm not saying that it's the only thing you need).
> You may learn pretty quickly how these algorithms work and implemented but it may take years of practice to earn ability to recognize them.
This is false. Just as you can learn pretty quickly how the algorithms work, you can also pretty quickly learn how to recognize which one to use for a given problem - it's basic pattern recognition. The problem for most people isn't that they can't develop this pattern recognition skill, it's that they don't realize they need to (and instead focus on just learning how the algorithms work).
A lot of the time when people say that you can't just "memorize" your way to passing a given test, they're just referring to situations where developing pattern recognition skills instead (or as well) will be more than sufficient. You can get pretty far in life by combining rapid memorization skills with the ability to rapidly develop pattern recognition for a new training set. The more types of inputs/outputs you can map between (muscular, visual, aural, etc.), the better.
I'm currently prepping for an interview at one of the Big 4. I can tell you that this site is quite useful.
They have tons of problems to help you with the recognition part as well. You don't have to be a genius to be able to do these problems. It just comes down to pattern matching.
That said I don't think this is the ideal way to interview people. However no one has as yet proposed a better alternative. I turned down an interview assignment recently because they wanted me to implement an app with :
- Syncing to a database
- UI Tests (with a mock API)
- Unit tests
- Functional reactive programming
- A really complex architectural design pattern
All this just to get a shot at the interview. I was too tired to do it at the time so I turned it down. So I would criticise programming interviews but I don't have a better alternative. Sane assignments are a reasonable middle ground (Perhaps they could have knocked off a few from the above list).
So if you want to work at a top employer and not be forever stuck doing CRUD then your only option is to learn algorithms and practice interviewing. I know it sucks but that is how the game is played.
The reason some people can do them is not because they're geniuses but they come from employers,schools where there is a culture of doing interview problems. They've been doing this for atleast a year if not more. So try doing them for a year and then tell me whether you still find them impossible.
I realised this when I took the help of a champion competitive coder for preparation. It was hard to find a question typically asked in these interviews which he hadn't heard of in some shape or form.
I have some tips I'm compiling which I might turn into a blogpost or book.
For recognition you need to practice abstract thinking . Thinking of something in terms of code should be completely avoided. Suppose I ask you to find the common ancestor of two divs.
In this case the DOM is a tree whose nodes have parent pointers.
Turn every question into a mathematical abstract form. Find a k such that , Find two numbers x & y such that and so on.
The next step is massive repetition. It feels like you're grinding with no understanding , but something happens when you repeat something 20+ times. Depending on how smart you are it happens sooner. Eventually it will become intuitive.
Always learn multiple solutions. Never settle for just one answer. Learn all possible answers and how it might be possible to go from a brute force to the optimal one.
Use Geeks4Geeks and Elements of Programming Interviews to build your pattern recognition.
Next read books and PDFs by Udi Manber on algorithm design.
This is a lot of effort. But that's just how it is. You don't HAVE to work at Google. You can work at other places and do quite well too. But if you want the top jobs then this the road you must take.
This site is EXTREMELY popular in India, and used a lot by students AND interviewers (I know many who simply ask questions from the front page of G4G on a given day). It's the inverted tree equivalent in India.
I'm someone who was actually interviewed by GeeksForGeeks because a junior from college connected them to me (They do interviews with people who have gotten placed in * dream * companies... not my terminology).
In the interview, which was done over email, I actually mentioned that resources like G4G are bad resources for studying because they over-simplify algorithms and reduce them to silly proportions, and also encourage rote learning. To my surprise, they directly published the same ON THEIR SITE. Speaks volumes of their editorial team (?).
This article too has little basis in reality, but more of one guy's list.
I strongly suggest you use much better resources for learning algortihms, rather than this site, which is (by and large) the W3Schools of algorithms/data structures.
I concur in India. I have 10+ years experience with a lot of work in embedded and I had this interviewer who when interviewing opened this page in his laptop and started asking questions from there.
Many of my colleague just learn the algorithm implementation by rote because in India it is very rare for companies to dig into algorithms or talk about its applications and optimizations.
I like the fact that this tests understanding of certain trade-offs. It can be improved in 2 ways though:
1. It doesn't allow the candidate to map out the available options for themselves, which is an equally important skill in software dev. When I'm working, I often have to spend a good chunk of time exploring the space of solutions, and only then can I move on to assess the trade-offs involved.
2. Another important skill is being able to question assumptions. You could (for example) intentionally under-specify the problem and let the candidate ask follow-up questions to root out assumptions/constraints. Example problem: You have an array of integers, how would you decide on an algorithm to sort it? Expected clarifying questions: (a) is there any relation/pattern in the integers stored? If they're all from a small set (say, 1-1000) then a simple counting sort works best, (b) how large is the array? If it doesn't fit in memory, a disk-based merge sort could be the best option.
Certainly. Of course, you should know how they work to the extent that you could write a (trivial) implementation if ever needed, but that very rarely happens.
However, occasionally you do need to write specialised implementations tailored to your particular usecase and chosen data structures. Hash tables in particular come to mind.
For example, I once had to write a statically allocated (fixed-size) hash table with O(1) lookups. A lot of tradeoffs enter the picture at that point so you had better know a dozen different types of hash tables to hash out a suitable implementation for the particular usecase.
It's a pretty pointless thing to ask something like solution for linked list and etc. Either you know it, or not, and if not, coming up with solution that took others many years to come up with is like asking to invent something on the spot - i.e. it's practically impossible. So it's a ridiculous kind of question and doesn't show anything useful about the candidate.
In my opinion, it's a settled question now. If you are looking for a job, you better cram these lists or you are dead meat. The screening tests and the interviews basically boil down to these set of questions for most of the companies.
I know where you are getting at and there's a subtle difference there.
Knowing the 'implementation' Vs Knowing the 'algorithm'.
I don't think I can 'know' something without actually doing it. Thereby, the road to knowing the algorithm goes through the rock climb of knowing its implementation.
Isn't the idea of preparing for software development interviews ridiculous?Instead of improving my algorithms skills to become a better developer I find myself memorizing a ton of problems just so I can answer similar ones during interviews. It feels like I'm preparing for the SATs again.
This list is very funny, straight out of the 90s, because we are in 2017 and most developers just spend their working days basically writing forms and storing/fetching data over the network/in a database.
I don't know if most developers still do an awful lot of that. At least not for the jobs I do - I do some but it's probably less than 25% of what I do.
And anyway if you have gotten the data you often need to do something with the data and sometimes that includes sorting it or other stuff.
When was the last time a front-end developer, or an app developer, or any developer actually, needed to implement a sort algorithm?
I started programming in the 90s, so I did a lot of it, implemented sorts, btrees, tries, you name it. When was the last time I need to implement it? Honestly, it's been a very long time, around 10 years, and it was just a bloom filter in c++ because it's not very used and few libraries have it.
Could I provide an implementation in an interview situation? Nope. And not interested in using my poor memory for it. If I ever need to implement a specific algorithm, say in a new language in which nobody did it before, I just need to make a search on google, take a few minutes to study it (for a sort), or hours (for more complex structures like btrees or algorithms I never used before), and use my knowledge/experience.
Of course, I don't need to implement those algorithms, but I use them a lot, everywhere. That's where interview questions should focus, where and when to use them appropriately, because that's the business case.
I think I've only ever had one of these algorithms come up in a hiring situation - unless I have brought them up myself in the normal flow of conversation.
I had to solve a problem for which a binary search was the correct solution (as well as some caching of results and stuff [although that part was fancy show-off stuff and not really necessary to solve the problem satisfactorily]) but I did the caching first and then sort of froze when it came to binary search because I was thinking 'uhm I should describe my thinking here first' and then the developer who was in charge of the exercise took my hesitation as not knowing the solution so he finished it and that was that (the test was also in Python a language I don't know that well - the theory was if you could figure your way through in Python despite not knowing it you would be able to handle new situations with aplomb. So I guess I failed the aplomb part.)
I sense the dire need for separate interviewing processes for anything that involves CRUD/WebApps with a database/Front End etc. and anything that is math/compute heavy.
Although I feel it is correct on the interviewer's part to expect me to know what these algorithms are and their general behaviour, expecting me to have it memorised to be considered eligible for writing CRUD apps and struggling with build tools and outdated test infrastructures is just infuriating. Hello 2017.
What a typical, uninspired, and pretentious list. I've recently started to opt out of interviewing people because I'm often teamed with someone that will Google one of these, think they're some sort of genius, and proceed to make some poor twenty-year-old feel like a doofus for not knowing the algorithm for a convex hull.
Speaking of which -- seriously? The only time I even had to LOOK at that algorithm was when I read a very old game programming book -- before I even went to college, mind you -- and generating pixel-perfect collisions for arbitrary polygons was one of the chapters (the game example was one of those meteor blaster clones).
I have strong feelings about this and I think this article is a complete waste of time, not to mention lazy (it looks auto-generated, anyway) because it perpetuates the idea(l) of making the software engineer interview process as arcane and difficult as possible.
For my part, I think the top few items on each group make for perfectly valid interview questions, but as we descend each list I agree with you more and more.
Things like DFS, BFS, linked list insertion, binary search, et. al. should be barely more than typing for a good experienced developer. They consist of basic skills, only slightly above fizzbuzz level. Implementing "Heap Sort" OTOH just tests whether you've recently reviewed the Heap Sort algorithm, which seems completely irrelevant to me.
maybe they want to skew their workforce to select for youngsters - recent grads would be best at these sort of things, cause as you say no-one writes these things in real life and if you do, you reach for the books. Glad those days are behind me, but it is a shame that this nonsense passes for interviewing.
I'm not sure if that is intentional or not, but these type of algorithms certainly favor someone who recently learned about them but hasn't had the experience to forget them. Because they are already incorporated into every framework that would use them, they are more "code trivia" for someone 10 years out of school.
But these questions should be a signal to you as an interviewee. Unless they are extremely salient to your proposed job (e.g., you are applying for a position teaching algorithms) they're a sign the recruiting effort at this workplace is not very healthy.
What that means is that talent and skill will be erratically dispersed throughout that organization. Requests for new staff will take a long time and may not fill needs, and that often times specific managers strongly influence who can get hired where for a variety of reasons.
Personally, I play along with these questions but make a game of pointing out how incredibly synthetic and unrealistic the conditions people put around them are. The goal of the game is to basically force the interviewer to come out and say exactly what algorithm they want, by way of how many other aspects of real-world software and systems they want to exclude from the conversation.
In my opinion, 80% of hiring decision is related to psicological terms. I.e. you can have the knowledge, but being discarded because resulting difficult to work with (anxious, narcissistic, undisciplined, uneducated, etc.).
In all my daily work OOP design skills always have battered much more significantly than knowledge of any of these algorithms. Yet I've never seen anyone ask about SOLID for example.
Nobody needs to be able to code these in an interview. Ever. For certain domains you should be aware of them and be able to look up decent implementations. But to think that level of knowledge is important in an interview is bogus. I could just as easily ask similar questions and weed out most CS grads that get into Google or Facebook with these:
Please implement a first order low pass IIR filter.
Tell me how the butterfly pattern in an FFT gets your from N^2 to N*logN. Oh, and implement an FFT.
Write a basic PID controller implementation.
Tell me how you'd handle a Field Oriented Control system that needs to run in voltage limit most of the time - what stability issues may occur?
Write a fixed-point implementation of the sin(x) function.
Implement a 2-pole 2-zero transfer function. For bonus points do it in fixed point without rollover or saturation problems.
Assuming you have a matrix library available, give me the boilerplate code for a Kalman Filter.
What kind of ODE solver should you use for long term stability when simulating planetary systems?
These are similar difficulty questions from a different domain, but many of them are likely to be used far more often in that domain than any of the interview questions in TFA are likely to be used in their domain.
The goal of an interview is to ascertain weather the candidate is capable of doing stuff and learning stuff, and if that's likely to carry over into the stuff you need done. It's not to see weather they can produce an answer to some specific problem on the spot. How you do that I'm not telling - it's hard enough without helping you find the people I need ;-)
"The goal of an interview is to ascertain weather the candidate is capable of doing stuff and learning stuff, and if that's likely to carry over into the stuff you need done. It's not to see weather they can produce an answer to some specific problem on the spot. "
I have uttered these words breathlessly so many times and we continue to hire disappointnent after disappointment. These questions are so foolishly beat into silicon valley culture it's absurd. I have zero CS background and rise to the top of every team I've been on, why? Because I'll just grind as hard as it takes to learn the relevant things to solve the problem at hand.
JFC, that's such bullshit. You want the mundane? Go for it. You actually want someone who can take a bunch of real operational data and solve the problem when the Person With The Money says, "We need to know what is actually happening with ____. And we've promised it in two days. You're it."
Who gives a flying fuck about writing the best sorting algorithm? "sort" works just fine, unless you're Google and microseconds matter. And then, you're really at the edge of R&D. You need to be able to manipulate data with aplomb. You need to be able to write an algorithm that works, and then refine it to make it go a hundred (or more) times faster once you understand why it is so slow.
I'm not a Googler, but I imagine memory usage would be a more meaningful constraint than speed per se on the mega-sorts they are doing. Completely speculative, but in service of a point valid even if the statement isn't: in those rare circumstances, the needs of the company are going to bizarre _anyway_. If you don't know what demands you'll face in the future, there's limited value in learning ahead of your needs.
I genuinely want to know where people use these algorithms in their code. I'm a non CS dev to begin with so may be I don't know where to use them since I didn't get formal CS education.
This way of interviewing is not what I prefer. I have been told I write better code than my CS grad peers but I have no clue about these algorithms and data structures. What do you guys think about this form of interview?
As a working developer for 20 years, the majority spent at Microsoft, I'd say that I have to understand data structures and algorithms in general, but I certainly do not need to know how to implement the ones that have names.
I've been a team lead and head geek for a small software company for a good number of years. I'd say that these questions matter a lot more than you'd think.
Using the wrong data structure or a data structure in the wrong scenario can make the difference between an application which can serve 1000 users per node or 100. That impacts the number of servers we recommend deploying in our cluster and in turn the hardware and maintenance costs for a customer buying a license for our software.
An understanding of Big-O and algos is very important and any good software eng or team lead should refresh themselves on the topics regularly since these really can make the difference between a performant app and one which brings the host device to its knees.
So really you're saying that actually you don't need to be able to implement these off-the-cuff, but you should understand big-O and based on the sort of data you have, pick the best algorithm from a table like this one: http://bigocheatsheet.com/ ?
Eh. I wouldn't put it that way. I'd say you need enough experience to know what you don't know. Which is hard and will vary based on the problem you're trying to solve. A simple cheat sheet won't be enough.
Do you really use Big-O at work? I don't know if I've ever heard it brought up outside of an interview. In my experience, when something is slow, people notice and start complaining about it.
"Why does it take 30 seconds to complete this seemingly simple request? Oh, it's making a database call for every element in the list, vs. efficiently sending a single request. I fixed it, and pull request submitted."
"What is this script taking so long? Oh, exec is being called on every command, so let's just pull that out and put it in a wrapper script."
"What performance tweak can we use to make this Rails app hellza faster, since we've maxed out low hanging fruit caching options? Rewriting this part in Elixir takes advantage of concurrency in a way that Ruby can't do all that well."
I guess real world discussions don't seem to incorporate Big O lingo.
I have encountered a few situations where time complexity matters during the normal course of work. The most notable one for me was where I did two DB queries to fetch a list of elements in one and another of the same length and related to the first one - to create a list of objects from the first list, I iterated on it, and it had to do another iteration inside to find the element in the second list. It turned out this approach showed some performance problems on larger datasets, so another coworker took a look at optimizing it - he ended up grouping the second list by id in one iteration so that it eliminated the need to iterate again inside the loop, transforming it from time complexity O(n^2) to O(n).
These situations don't come up too often, but when they do, it becomes important to at least be able to solve them in some fashion in a non-high pressure situation.
Comes up fairly regularly for us in code reviews. People will question the data structures used. E.g. This find operation in a tight loop is actually called on a vector not a map, meaning it's a linear search rather than a constant operation.
All other things being equal, someone who understands these algorithms/data structures and how/when to use them would be preferred over someone who hasn't put time in to get familiarized with them.
I think in many positions it probably isn't necessary to have knowledge of how to implement from scratch -- yet again, if the company could find someone that gets it, they may produce overall more efficient solutions. Whether that matters to the company or not is another story -- but things like finishing some scheduled task in 10secs instead of 2hrs can be really useful.
I used to have a mindset like "these algorithm quizzes are BS!" Yet when I have learned more about them, it is amazing to see how inefficient things can be produced, without the foundational knowledge to process/store things efficiently
EDIT: All that being said, I think the usual software engineer interview format is terrible. It's like an intellectual hazing gauntlet or something..
All other things being equal, someone who understands these algorithms/data structures and how/when to use them would be preferred over someone who hasn't put time in to get familiarized with them.
Correction: all other things being equal, the person who does better on an algorithms/data structures pop quiz is more likely to be a recent college graduate who you can pay less and treat worse than an established developer who's forgotten most of this stuff and just looks it up when/as needed.
In terms of simply getting hired/passed the interview, yes, either a recent grad or someone having studied the algorithms prior to the interviews will probably do best. I won't argue it's annoying to study for an interview.
I still think someone who understands these and has studied them will be in better shape to understand when/how to use such things in situations on the job (even if they can't be reproduced in a pop quiz scenario by the person). Maybe those situations will matter to the company, and maybe they won't.
Except you know this isn't how algorithm/data structure questions are used in interviews.
What you're talking about is primarily a function of experience: seeing various situations over time and learning what works well and what doesn't. But these questions are used, quiz-style, as a barrier to even entry-level positions. So even if I grant you the possibility of some effective criterion being developed from algorithm and data-structure questions, the fact would remain that hardly anyone (and more likely no-one) uses them as you advocate.
Getting these questions out of interviews and replacing them with metrics tailored to the desired job skills and responsibilities (rather than proxies for them, or even proxies for proxies for them, as is unfortunately usual in the industry), would be far more effective.
Or perhaps more bluntly: I know of no other field which A) drills students on low-level fundamental techniques in school/training, and B) largely replaces them with higher-level techniques on the job which discourage use and thus continued top-of-mind retention of the low-level techniques, and C) nonetheless requires instantaneous unassisted perfect recall of all details of any arbitrarily-chosen low-level technique as a mandatory qualification for employment even into late stages of the career.
Lawyers learn a lot about the law and its history and important cases, but they don't sit through pop quizzes of 15th-century English common-law rulings on every job interview for the rest of their lives, even though there probably are some such cases that would on occasion be useful to know. Doctors learn a lot of biology and chemistry, but if passing a closed-book organic-chem exam was a prerequisite for every job they'd take after med school we'd have a lot fewer employed doctors.
Only programmers do this to themselves. Only programmers relentlessly demand that it be preserved as a gatekeeping ritual. Only programmers insist that "well, it's fundamental so it must be useful sooner or later" is a sufficient justification for doing this.
It's time to stop doing this. It's time to stop supporting this. It's time to stop perpetuating this.
(and getting back to my initial comment: there's a reason why bootcamps now have a "how to pass code interviews" unit, and a reason why Cracking the Coding Interview sells so well, and it's because these things have stopped having any useful purpose -- if indeed they ever had useful purpose -- and now serve as artificial barriers and ways to perpetuate biases about background while claiming objective grounds to disqualify people the interviewer doesn't want to hire, thus making life miserable for both the hired, who are likely to be inexperienced and easy to take advantage of, and the unhired, who have to try again or give up and find another way to make a living)
You're right, and I totally agree with you on what you're saying about the interview/job obtaining process, and that replacing the way this is done with something far more effective for interviews would be ideal. I also agree that actual experience using these types of things seems much more important than seeing if someone has drilled on quiz questions.
The question then for me is, how does one assess if someone can use these things in practice to make a difference for the business? I don't have a good answer for that right now. If anyone here knows a nice approach to use to assess this type of skill, I'd like to know more (to stop perpetuating the usual 'algorithms gauntlet' approach).
As somebody who passed out of university last year, I remember how we had to mug up most of the questions on this website (and practice topcoder + codeforces), so that interviewers could consider us smart.
IMO, algorithmic interviews are maybe a good way to filter for motivation rather than anything else. Candidates who are likely to learn all this are more hardworking and career-consciuos (placements correlated pretty strongly with how much you 'knew').
That said, there was this one interview I had where the interviewer asked me how to design a distributed log collection service. Basically you have GBs of log files being generated on hundreds of servers and you want them sorted and stored on a single central database. What sort algo will you use, why? How to reduce transmitted over the network etc.
It was a fun round and tested a lot of disparate concepts.
To my inexperienced self, this seems like a good format:
- First round: Ask stuff like fizz-buzz, trees, file I/O or string processing stuff. Basically ensure that they know how to code. Another way could be asking them to code the same question in functional, OOP and procedural styles
- Second round: Discuss some project done by the candidate or ask them to design something from scratch. URL shorteners, databases, REST apis are normal candidates. Spreadsheets, DSLs etc might be good to make things harder.
- Third round (If applicable) : Dig into any one specific domain most relevant to your company/team and make them architect* the whole thing.
Ofcourse, any system, once its established and well-known, can be gamed. Banking on open source projects or past achievements is then what remains.
* Very few entry levels jobs really require such skills but (IMO) it will help you get better engineers instead of coders.
Engineer at one of the big four here. These specific algorithms don't necessarily come up all the time but my work would be impossible without strong algorithmic background. Is it better to use BDDs or Radix Trees to store abstract program state? What is the most efficient iteration strategy for computing fixed points? If I can't give a good answer to these questions then in all likelihood my system will never terminate.
Sometimes just moving a .find into a precomputed hashmap can be the difference between O(n^3) and O(n). The difference is important with n as low as 100.
It's that intuition which is valuable, not the implementing of algorithms by name.
It's enough to know the existence and properties (benefits, drawbacks, running time, memory use) and to be able to recognize when to use a specific algorithm or data structure. I have no use for a candidate that can implement every sort algorithm on a whiteboard. What I want is a candidate that can identify problems and identify the required algorithms.
So I want someone who says "this is analogous a dynamic convex hull problem" or "this can be solved greedily by branch and bound" etc.
That knowledge has to be learned it can't be Googled. Mergesort or an A* implementation is googleable once you know you need them (which was the important bit).
Let's look at it in a different way: I have a CS education, and have worked professionally since the 90s. In my resume there's things like:
- A code generator that took as input sources
- High performance RMI libraries for a phone company
- A entire retail system, from POS, to warehousing, reporting and PCI-DSS compliant key exchange systems
- Distributed systems that coordinate work between thousands of nodes
- A machine learning project that was recently mention in HN.
- Migrated most computing in a fortune 50 company to the cloud
There are far more storied careers than mine in HN, but this is not a career of someone that spent their days writing CRUD apps in visual basic: I worked on fun things. Some of that worked involved algorithms: many of them very complicated. However, since I left school, other than in interviews, I never had to touch a high percentage of the algorithms in that page. Let me go a section at a time:
- I have used graphs plenty of times, but I can't recall using any of those algorithms directly. Yes, not even BFS.
- I had to do linked list-like operations when I was writing in C at the beginning of my career. Not a single time since.
- Zero dynamic programming. Nada.
- Not a single manual sort algorithm, not a single manual search algorithm.
- There's been plenty of trees, but none of the operations covered there. They were either provided by the libraries underneath, or never came up.
- Number theory? Nothing from that list. I have implemented HyperLogLog though. Just don't ask me to do it from memory.
-Early in my career I had to deal with some bit manipulation. I've not had to touch it in years.
-Not a single one of those string/array manipulation ops
So my answer to the grandparent is that you can have a long, fun, not CRUD app career doing fun things without having to implement those algorithms once, because they are done for you. The algorithms those jobs need in practice are often harder, but you don't have to have them memorized: Some you go look for papers that solve your problems, others you develop yourself (and be afraid of that one, as I have seen a mathematician come up with a 5 page proof for an algorithm that only did what we needed in a parallel universe where latency is zero)
What almost every professional programmer has to understand what an array, a list, a set, a tree and a map are, and to go check the performance problems of specific implementations if it matters at the time. Almost every other interesting thing I have done was only relevant a small percentage of the time, and I could look up.
Interviews ask the questions they do because they match what is taught in a small subset of CS classes. We could teach other algorithms in those: Some of the ones I had to use would fit in said classes, instead of the ones we have. They can be implemented in under an hour too. However, nobody asks for them in interviews, because the people that come up with interview questions haven't solved them before.
So my point is not that you can ignore data structures and algorithms: You'll use some no matter what. But there is no subset of algorithms harder than a loop that every programmer uses in a regular basis, or data structures that we manually implement. We just ask for things that come from those same CS classes because we have no idea of how to assess if someone is any good, and the algorithm classes were some of the harder ones in college, so we assume that if you have them memorized, you must be pretty good. And we assume wrong.
> I have been told I write better code than my CS grad peers but I have no clue about these algorithms and data structures.
For a programer in the industry, the ability to write simple "legible" code is very important. An ideal interview process should spend some time evaluating those skills of a candidate - but this is very very hard to measure.
But I have to say that knowing these algorithms alone won't help you much during job interview with smart employer like Google.
The reason is simple but often overlooked by many people: the most important thing is not these algorithms themselves but ability to recognize them in problems.
You may learn pretty quickly how these algorithms work and implemented but it may take years of practice to earn ability to recognize them.
Google won't ask you directly to implement Dijkstra algorithm. They may give you a problem which on surface have nothing to do with graphs. It may take a while before you actually have a light-bulb/aha moment when you realize it's a graph problem.
In practical non-interview problems, ability to recognize algorithms is much more important than knowing their implementation. You can always find their implementation on the Internet after all.
This is why I'm trying hard to improve my problem solving skills by solving competitive programming problems almost everyday.