Ask HN: What are the most requested algorithms during technical interviews?
What are some of the most requested algorithms during technical interviews?
When I was young and eager to please I would put up with this sort of thing. In fact, I used to think there must be something wrong with me, that I was a bad programmer for not having every data structure and sorting algorithm perfectly memorized at all times.
Now that I'm starting to get old and realize it's all BS, if you ask me to write quicksort on a whiteboard I'm going to roll my eyes and walk out.
When they are unable to answer "When was the last time someone implemented one from scratch" then I ask them "Why are you asking candidates questions that are not relevant to the job? Wouldn't it be better to evaluate the candidates against the role they will fill?"
Then if they give B.S. answers you can politely say "Thanks, but no thanks" and then go - I try and dig a bit deeper to establish whether there was a really cool and interesting story about why they had to implement one themselves, or whether they're just full of rubbish and literally have no idea what they're doing
Asking people to code a sort in an interview can be very useful as it shows whether they can actually code or not.
I've had people write horrible code in interviews many times and that is a major indicator that I shouldn't hire them for a coding position.
"I need to repeat this sequence of operations an indeterminate number of times... if only there were some programming construct that could help me out here..."
So I reached back to my Apple II BASIC days and whipped out the trusty GOTO. The look on the interviewer's face was priceless.
It really doesn't get much worse than forgetting how to write a select statement.
One needs to evaluate people. I would prefer to evaluate people using a metric close to what is required in the job -- coding.
If people have issues that they can not be evaluated properly, then what I am supposed to do? Just hire anyone no matter how they do?
Of course coding isn't the only metric but it is one of a couple. If you write an algorithm that has indexing errors or no stopping condition or just does't work, it isn't a good thing. I do rely on coding on whiteboards or paper a lot more when it is someone new in their career and do not have many past accomplishments to point to.
I like to write my algorithms on paper first before writing code, but doing it on a whiteboard in 45 minutes while explaining my work and checking for edge cases can be a bit unreasonable.
I don't think the contention is about testing a programmer's ability, but the way their ability is tested. Personally I think pair programming is a better method of testing someone's ability to code AND their ability to collaborate with others.
What does BS stand for?
I consider myself a good programmer. I have a PhD and about 10 years professional experience. But right now I can't remember the different sorting algorithms, and in the very unlikely situation that I would need them... well there's Google.
It's probably more about filtering rather than actually trying to seriously evaluate candidates.
Or shuffling an array - anyone can do it, but there's performance and correctness questions.
In practice I'm guessing so many candidates fail out much earlier. The number of people that can't, say, reverse a string, or words in a string (not even getting into Unicode) is staggering.
If they start writing a function and don't even mention the API, that's a significant red flag. I don't need code written from scratch unless necessary.
I interview developers. It depends a lot of how you ask the question. Asking "please write a quicksort on the whiteboard" is a pretty bad way of interviewing, you should not expect your candidates to memorize every algorithm invented.
However, if you explain how an algorithm works, and then ask them to write the code for it, you can check if the candidate is able to translate a description to code, which is an essential ability of any programmer.
For example: "In a quicksort, you take a random element of the list (pivot). Then you put all the elements greater than the pivot on the right part, and all the smaller or equal on the left part. Then you repeat the process on each part (left and right) of the list until you can't split anymore." Then based on this description write a simple quicksort in your favorite language, of course you can ask any clarifying questions about how the algorithm works.
I expect a competent programmer to be able to translate the description of the algorithm to code. Yes, it's true that in real world you never have to code a quicksort. But working with simple algorithm makes things easier at the earlier stages of interviewing at large companies, when you usually only have a few minutes to check if the candidate can write some code. Better, more real-world questions are asked at a later stage, when you have more time, typically on a face-to-face interview.
Fair point, but it seems like you'd be using the wrong filter ahead of time.
Sadly many people have little idea there exists a world of SQL beyond 'select * from table where foo = bar'.
That's what I'm trying to do - get the interviewee to ask more :)
I don't think complex algorithms are that common in interview questions, especially the ones that are well known.
But, I personally like to ask this one, cause it came up in my day to day job, and is quite deep:
http://stackoverflow.com/questions/127704/algorithm-to-retur...
Language features and "how do I"s can be googled, and can reasonably be learned in the first weeks on the job; a good understanding of algorithms generally requires study, and takes much longer to do well at. Further, even if the algorithm is completely new to them, you can still learn a lot from their problem solving methods.
Finally, it shows that they can code. You would be surprised how many people can interview well but cannot actually code. I learned this the hard (and expensive) way several years ago, and since have made coding a central part of the interview. Sure, I probably lose some candidates who think it's "beneath" them, but in all honesty with that kind of attitude they're probably not the ideal hire either.
Many people I interviewed managed to do it, and I passed many people who didn't. Usually I start the question by saying:
"this came up in my day to day job and I found it interesting. It seemed simple, but it took me a solid 2 hours to solve properly. I don't expect you to finish it during the interview, but I'd like to see what are you thoughts about how to solve this." For me it's a good question to assess:
1 If the person enjoys programming
2 If the person can articulate the problem to another person
3 If they are creative
4 To what degree they have a programming culture (how they talk about enumeration etc).
If they finish in 5 minutes using recursion, then you can ask how to make it so the enumeration can be enumerated in parallel, which is very useful, and involves ordering/gray codes and what not.
The point isn't to see if someone knows the answer (in fact, if they obviously do we'll move on to something else). The point is to see how they problem solve, and what their `toolbox' looks like.
To that end I never as "implement algorithm x", but rather "here is a problem [or set of requirements], how would you approach it".
The best versions of these are deep in the sense I think you are replying to. This means you can easily fill as much time as you want discussing different approaches or details.
http://ruby-doc.org/core-2.4.0/Array.html#method-i-combinati...
There's also `repeated_combination` (if elements can be used more than once) and you can even add `.lazy` on the end to avoid building the entire array of combinations if you're only interested in some.
1. Generate all subsets of 1-n using the proof of cardinality of the powerset
2. Filter to subsets of size k
3. If it's an array of letters, use the filtered subsets to index the array
https://github.com/divbit/tspm/blob/master/example-projectEu...
So interviewers rather then asking this bogus questions ask architectural questions, framework questions, coding things because this is what makes your product. For Sorting/Searching you will always use a library. Believe me, I hate being asked such questions during interview which can be found in a book. So please interviewers do ask relevant questions, we are there to develop your product not algo otherwise, if we are so talented, that definitely we wont' work for you.. :)
Often I read stories/comments and it feels as if questions of these sort are for the interviewer to prove a weird dominance of some sort and not to actually determine the competency of the interviewee.
This day in age I wish people would just say, "This job is mobile app development and simple REST APIs. If you want to ask about that go ahead, I'm not solving a problem which has a 1,000 solutions on Google."
Or alternatively, "Sure, give me a second. (Pulls out phone.) Here, this is the wikipedia entry on Insertion Sort."
For that kind of job, why would you ever roll your own rather than using tools that have libraries of standard algorithms and data structures?
You don't have to walk far from the beaten path at all before custom data structures start making lots of sense. Most interesting data structures in the literature are only implemented in a resuable, available way in one or two languages, if that.
More importantly, understanding this means you'll know the right questions to ask, or even be able to say upfront that a certain well-liked product some exec wants to use won't scale, even if the trial with a dataset less than RAM works "really fast!".
We do ask for an offline coding exercise featuring date math which is actually Mong the hardest problems known to man. :)
Now when I find a a candidate, usually via Github or their dev diary, I can usually tell from the work itself that they have the talent and skill.
But I can also employ a very simple screen: implement a basic image processing op using the Pixel Manipulation API on an HTML5 Canvas2d. Say Gaussian blur of an input bitmap. Not uncommon to get a "Javascript Expert" who can't even render a bitmap to a canvas. But a solid prospect with good engineering instincts will be able to wax poetic about low and high frequency noise in the image, convolution kernels versus Fourier analysis, and perhaps whether WebGL might not be more performant ;)
If the interviewer asks you an algo you know, and you bash it out super-quick, a prepared interviewer will just find another you _don't_ know the answer to. This thread's question is therefore somewhat missing the point.
Interview tests and questions which it's possible to swot up on aren't valuable. They only test your memory not your problem solving.
There are a few small tricks. Something that you can get in an interview even if you have never seen it before.
Given that we're mostly a large web application with a relational database, I think it's very appropriate for the job, and the question came almost straight out of real world experience.
Questions that depend on either leaps of insight or the interviewee having heard the question before make for dreadful interview questions. The former leads to too much variance to be a good measure; the latter makes the answer meaningless.