8 ms·
Top algorithms in interview questions
- known 10y agoGood list; Please add Containers to the list http://www.cplusplus.com/reference/stl/ http://www.cplusplus.com/reference/stl/
- andrewvijay 10y agoI 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?
- anomk5050 10y agoDo you really find you can ignore data structures and algorithms in your work (and if so, what sort of work do you do)?
- hibikir 10y agoLet'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.
- emodendroket 10y agoI feel like recursively descending some object isn't some obscure thing and there is DFS for you.
- andrewvijay 10y agoIm a frontend dev by day. Golang/rust by night where Im in the need of learning DS/Algo anyway.
- alkonaut 10y agoIt'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).
- jupiter90000 10y agoAll 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..
- ubernostrum 10y agoAll 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.
- jupiter90000 10y agoIn 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.
- ubernostrum 10y ago
- leonroy 10y agoI'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.
- abstractbeliefs 10y agoSo 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/ http://bigocheatsheet.com/ ?
- burntsushi 10y agoEh. 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.
- amorphid 10y agoDo 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.
- crdoconnor 10y agoYou typically don't. This form of interviewing is cargo culting Google's interview process.
- psyc 10y agoAs 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.
- Swizec 10y agoSometimes 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.
- mavelikara 10y ago> 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 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-more-than-a-brain-teaser/ http://www.goodmath.org/blog/2015/11/19/technical-interviews...
- UncleMeat 10y agoEngineer 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.
- tzs 10y agoConvex hull is in the number theory category?
- dvt 10y agoWhat 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.
- chadcmulligan 10y agomaybe 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.
- Clubber 10y agoI'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.
- DavidWoof 10y agoFor 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.
- chadcmulligan 10y agoWould a better way to interview be questions like: 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.
- Clubber 10y agoI second that. It's good to know what tools to use and why, but not necessary to know how to make the tools.
- yason 10y agoCertainly. 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.
- vickychijwani 10y agoI 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.
- phkahler 10y agoNobody 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 ;-)
- noponpop 10y ago"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.
- bezzi 10y agoIsn'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.
- axiom92 10y agoIn 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.
- alkonaut 10y agoThat might be true in Silicon Valley, I would never ever ask for an implementation of a known algorithm from a candidate, it's beyond stupid. Knowing the running time of merge sort or A* is interesting. Knowing its implementation by heart is not.
- sh87 10y agoI 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.
- madmax108 10y agoThis 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.
- mindentropy 10y agoI 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.
- jules 10y agoThe couple of explanations of algorithms that I looked at were good. Much more concise than a textbook, but with links to additional material.
- mathogre 10y agoJFC, 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.
- hawkice 10y agoI'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.
- shmerl 10y agoIt'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.
- invaliduser 10y agoThis 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.
- bryanrasmussen 10y agoI 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.
- invaliduser 10y agoBesides calling Array.sort()? 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.
- KirinDave 10y agoBut 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.
- hal9000xp 10y agoThis 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.
- cle 10y agoAnd 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.
- snovv_crash 10y agoThat, 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.
- bryanrasmussen 10y agoI 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.)
- faragon 10y agoIn 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.).
- ajmurmann 10y agoIn 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.
- sh87 10y agoI 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.