Top algorithms in interview questions
geeksforgeeks.org
geeksforgeeks.org
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.
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.
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.
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...)
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.
Pick a math intensive and performance sensitive domain and interesting algorithmic problems like these pop up all the time.
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.
http://akira.ruc.dk/~keld/teaching/CSS_e10/Manber88.pdf
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 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.
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).
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.
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.
1) I have an array of 1000 integers, which of these would be the best way to sort them a) quicksort b) bubblesort...
2) what sort of structure would you use to store a list of numbers and strings 1) dictionary/hash 2) two arrays ...
and so on. These would give you the certainty that they know which is which, you could ask give reasons to see if they mention O() and so on.
IRL it's very seldom that you write one of these structures, but you use them all the time and need to know which one to use when.
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.
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.
Knowing the running time of merge sort or A* is interesting. Knowing its implementation by heart is not.
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.
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 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.)
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.
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.
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.
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.
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 ;-)
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.
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.
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.
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).
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..
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.
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.
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)
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).
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.
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.
"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.
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.
It's that intuition which is valuable, not the implementing of algorithms by name.
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 good familiarity with the basics of CS is also important to be able to perform many of these jobs. Here is a good blog post about this form of interview and the rationale behind it: http://www.goodmath.org/blog/2015/11/19/technical-interviews...