5 ms·
Data structures and algorithms interview questions and their solutions
- tgarma1234 9y agoThat's a great list worthy of study in any context.
- deleted 9y ago[deleted]
- jhasbro 9y agoI agree. I studied these sorts of questions through hackerrank, leetcode, etc. and became a better programmer. That said, I wouldn’t want to work somewhere where they asked me to find a “zero sum sub array” in an interview
- pmoriarty 9y agoSadly, the code examples all seem to be in C++ ... not exactly the ideal language for pedagogy.
- hanoz 9y agoDidn't most of us get in to this mathsy line of work precisely because we didn't need to memorise a load of stuff and could just work things out from first principles as and when required?
- curiousgal 9y agoThank you! It's really sad seeing what this field has turned into.
- burkaman 9y agoI don't like coding interviews, but this list is for practice, not memorization. Ideally you could solve all of these from first principles.
- mathattack 9y agoThis is certainly why I enjoyed Calculus and Physics. :-)
- eesmith 9y agoI remember memorizing a load of stuff for my math degree. How did you write proofs without memorizing terms like "Method of Frobenius", "triangle inequality", "Zorn's lemma", "Bolzano–Weierstrass theorem", "Cantor diagonalization", and so on?
- munin 9y agoIf this isn't a metaphor for the programming interview I don't know what is: http://www.techiedelight.com/multiply-two-numbers-without-using-multiplication-operator-loops/ http://www.techiedelight.com/multiply-two-numbers-without-us... "Implement multiplication without using loops." "Uh, okay. What do you mean by loops?" "Don't use a conditional loop." "What do you mean by a conditional loop?" "Oh, you know, the standard definition." Time passes. "I'm stuck. What is the answer?" "Oh, you just have a loop on b dividing it by 2 using shift operators until it is zero." "Wait a minute, you said you couldn't use loops." "Did I? Ah, well." Hackerrank/leetcode exercises are written the same way. So many times that a problem asks "Output the indexes of two numbers in the array such that their sum is K" and you write your code and the website says "INCORRECT! You said [3,6] but the right answer was [6,3]". Addition is commutative! The two are equal! And both right!
- userbinator 9y agoThe real way to multiply without loops is to use a lookup table, or unroll the (fixed iteration) shift-and-add loop. That page is both hilarious and sad at the same time. Hilarious because the second "solution" clearly has a loop, and sad because sites like those don't really help anyone. Some of the pages on that site are downright WTFs: http://www.techiedelight.com/generate-binary-numbers-1-n/ http://www.techiedelight.com/generate-binary-numbers-1-n/
- vikiomega9 9y ago"What I told you the question was either or" haha
- bogomipz 9y ago>"or unroll the (fixed iteration) shift-and-add loop" Can you elaborate on this? I understand the shifting but didn't understand the "loop unrolling fixed iteration part"
- userbinator 9y agoThe shift-and-add algorithm for multiplication is usually implemented as a loop that iterates for the number of bits of the operand, so e.g. for an 8-bit x 8-bit multiplication, the loop runs 8 times. (An "early out" algorithm when one of the operands becomes 0 is also common, but let's not complicate things here.) It's trivial to unroll this loop into the 8 individual shift-and-add steps.
- bloaf 9y agoAm I stupid or do both of the solutions to the problem "Replace each element of array with product of every other element without using / operator" use the / operator? My solution would involve summing the log() of the values in the array.
- NiceGuy_Ty 9y agoThere was just a post on HN to a site that went over this exact problem. Essentially, you do two linear scans to calculate the product of every number before an index, and to calculate the product of every number after an index. Then, for each index, the answer is just multiplying those two numbers you found for that index.
- deleted 9y ago[deleted]
- sp527 9y agoMost interview questions are ridiculous and don’t test for the knowledge a candidate should have. When I interview, I ask a system design problem that involves using an inverted index, a bst, understanding how to normalize data, and then being a little clever when merging some data. It tests fundamental concepts in the context of building a working solution to a meaningful problem. I never understood why anyone would ask say DP questions in an interview. We don’t use that in 99.9% of software (I’ve never once in my career found a use case). What you’re really testing is whether or not the candidate had enough time to refresh that material. Worse still, it involves a very rigid solution pattern that’s over-specified to that class of problem and tells you nothing about what you want to know: can a candidate synthesize concepts to devise a solution to problems we actually encounter?
- ccleary00 9y agoI'd rather just not interview at companies that have these kinds of interviews and save myself the hassle.
- psergeant 9y agoFair enough, but you're not usually learning some deeper truth about the company based on whether or not they use these kinds of interviews. Interview processes are generally completely arbitrary, the interviewers chosen at the last minute by the hiring manager, and they're not changed because they're sort of good enough. If you dislike these types of interviews sufficiently on their own merits that you want to avoid them, fine. But don't think you're learning anything about companies just because they use them.
- manigandham 9y agoIf anyone asks these questions without a particular scenario to actually deal with in the course of the position you're interviewing for, you are in for some bullshit at that company. This has become all too common at the major corporations sadly.