Ask HN: What are the most requested algorithms during technical interviews?

https://news.ycombinator.com/item?id=13588993

by bsvalley • 9 years ago

68 66 9 years ago

news.ycombinator.com

What are some of the most requested algorithms during technical interviews?

aburan28• 9 years ago

Each interviewer in my experience has their own special algorithm they love to ask. For instance I was asked a question about the Boyer-Moore majority algorithm which is so obscure and rare and hence I messed that interview up. It is usually not the Splay Trees, AVL Trees, Merge Sort it's the logic behind your contextualization of the algo in the problem being asked to be solved

d--b3• 9 years ago

Fibonacci is very common, just to see if the person knows what complexity is about, and to see if the person understands the tradeoff between readability / conciseness and complexity.

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...

cantpassstepone• 9 years ago

Since it's "quite deep" and you might have spent hours looking for a solution on the Web, why would you ask this question to a candidate in a 45 min interview? Do you think it's fair? And how would you define success since everyone would fail on this question? Just curious...

flavor8• 9 years ago

You learn a lot more about a candidate by seeing them tackle a reasonably tough problem than you do by pop-quizzing them on language features.

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.

d--b3• 9 years ago

By quite deep, I meant that it's easily understandable, it's hard enough, and there are tons of different solutions. You can also see differences in recursion vs iterative, and talk about ordering and Gray codes, and all sorts of things.

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.

ska• 9 years ago

I typically wouldn't ask any "implement algorithm x" questions, but I do ask technical questions.

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.

al2o3cr• 9 years ago

I dunno about "deep" - it's literally available in the Ruby stdlib:

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.

josephorjoe• 9 years ago

<3 ruby -- I hope they add a `.fizzbuzz` method to the enumerable module in the next release.

divbit• 9 years ago

I am by no means good at programming interviews but

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...

raverbashing• 9 years ago

Sorting, especially Quicksort or similar sorts. Insertion/Selection might be asked as well

mynameisjody• 9 years ago

Fwiw, for our web/mobile device shop we ask 0 algorithm questions. I find those kinds of things rarely if ever come up in practice for our team and a person who makes it through the rest of our process would likely be up to the task.

We do ask for an offline coding exercise featuring date math which is actually Mong the hardest problems known to man. :)

yread2• 9 years ago

Not really an algorithm but I like to ask about the difference between inner and outer join. It can start a nice conversation about database design, normalization, performance, consistency,... I did get quite a few blank stares or "Yeah I do have SQL Server, MySQL, Oracle and PostgreSQL on my CV but I don't actually do it that much" answers, unfortunately.

matwood• 9 years ago

A full outer join or left or right? If you want to see how old someone is ask them about the * = syntax :)

Sadly many people have little idea there exists a world of SQL beyond 'select * from table where foo = bar'.

yread2• 9 years ago

A full outer join or left or right?

That's what I'm trying to do - get the interviewee to ask more :)

Retric• 9 years ago

One of the issues is you can easily go a year without using SQL just some ORM. In a job setting a few quick searches and it all comes back but interviews jump from topic to topic really fast.

Declanomous2• 9 years ago

Especially when it comes to things like inner and outer joins. I honestly can not remember the last time I needed a full outer join. Our database design doesn't really require it for anything that I can think of.

gspetr• 9 years ago

https://news.ycombinator.com/item?id=13294318

henrik_w• 9 years ago

At my one phone-screen with Google a long time ago: decide if all nodes in a binary tree fullfil the condition that elements in the left sub-tree are smaller than or equal to the node value, and all elements in the right sub-tree are greater than or equal. Good question I think, since you need to be able to use recursion + a tree is a simple and useful data structure.

imron2• 9 years ago

Fizzbuzz and despite its popularity many people still get it wrong.

miguelrochefort• 9 years ago

That is simply not true.

imron2• 9 years ago

Which of those two statements?

jcadam2• 9 years ago

Pfft... I was once asked to build an R-tree (https://en.wikipedia.org/wiki/R-tree).

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.

y0y• 9 years ago

Yeah, I'm getting to be the same. I'll happily talk to you about various algorithms with as much technical depth as I can muster given the algorithm of choice, but I've no interest in coding on your whiteboard. If you can't glean my level of understanding from a conversation, that's your problem. If you want to know if I can code, that's what my github is for.

malux85• 9 years ago

I woudln't roll my eyes and walk out, but I would ask them when the last time somebody in their organization implemented an R-Tree from scratch, then if they actaully answered the question, they better have a really good answer for the next question: why not use a mature, well tested, perforamnce enhanced library?

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

mrfusion• 9 years ago

I asked that once and the reply was "we don't use freeware here". As their reason for coding everything themselves ...

bhouston2• 9 years ago

if you ask me to write quicksort on a whiteboard I'm going to roll my eyes and walk out.

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.

bryanrasmussen2• 9 years ago

or it's an indicator that they get flustered coding in front of people. I definitely underperform when pair coding, coding on a whiteboard instead of a computer I'm familiar with? Probably not my best work.

0x54MUR41• 9 years ago

...realize it's all BS

What does BS stand for?

Gargol• 9 years ago

BS stands for - Bull St

vinaygaba• 9 years ago

I have been asked a lot of problems whose solution was a variation of Breadth First Search.

startupdiscuss• 9 years ago

Determine if a linked list is a loop or not.

There are a few small tricks. Something that you can get in an interview even if you have never seen it before.

MichaelGG4• 9 years ago

To start: "given two liked lists, determine if they share any nodes". Even if you've only read about linked lists it should be something to get in a few minutes by stepping through it. No tricks.

rowanseymour• 9 years ago

Is regurgitating an algorithm actually a useful way to interview?

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.

knightofmars5• 9 years ago

No, it isn't. The problem is that interviewing from the side of the interviewer is an incredibly difficult skill and it's an easy short-cut to thinking you've got a way of separating the wheat from the chaff.

arethuza• 9 years ago

I suspect these question are asked because they are easy to ask and give clear binary answers.

It's probably more about filtering rather than actually trying to seriously evaluate candidates.

MichaelGG4• 9 years ago

I think the point is that they're simple. Like binary search, which a 7 yr old can grasp. Or writing a simple hash table, at least in psuedo code.

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.

bryanrasmussen2• 9 years ago

you definitely know some advanced 7 yr olds.

calenti• 9 years ago

Or that know you can do this with the API. One of my questions for developers is to ask for things like date format or string reversal.

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.

ceronman• 9 years ago

Is regurgitating an algorithm actually a useful way to interview?

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.

kiliancs• 9 years ago

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.

Fair point, but it seems like you'd be using the wrong filter ahead of time.

knightofmars5• 9 years ago

I believe it should depend on the domain of the job you're interviewing for. If the job is heavy in large data sets and number crunching, then it makes sense to ask an algorithm question. If the job is integrating disparate APIs, then it makes sense to ask about how to define an easily consumable API. And while there are definitely positions that could require both pieces of knowledge it doesn't mean every position should expect encyclopedic knowledge of algorithms.

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."

SideburnsOfDoom• 9 years ago

If the job is heavy in large data sets and number crunching, then it makes sense to ask an algorithm question.

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?

knightofmars5• 9 years ago

I certainly hope you wouldn't "roll your own" but you do need to understand how to identify the type of data and the correct algorithm to use in processing it based on the requirements provided.

barrkel2• 9 years ago

Pre-packaged libraries are generally optimized for being composable and generic. When trying to get more performance, it can make sense to e.g. create an index or lookup that can be used in multiple steps, or fold multiple iterative steps into a single iteration, or take advantage of the data's distribution to use a more specific approach, etc.

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.

MichaelGG4• 9 years ago

You will almost certainly not be writing your own, until you do.

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!".

vonmoltke• 9 years ago

The problem is the companies who ape Google's process, since the domain Google hires for is "the entirety of software engineering" due to their req-blind hiring philosophy.

knightofmars5• 9 years ago

Google, is well Google. The problem is companies who copy Google blindly without taking a moment to think about what the actual problems their engineers are solving. (You said, "ape" so I'm not sure what that meant. I may have just re-commented your original comment.)

alien3d2• 9 years ago

i just ask hello world in language they know.No point for me asking basseyen formula,or what ever formula.We solve problem client only

alien3d2• 9 years ago

for those whom downvote. Im sad for them. As interviewer,what point i ask specific formula while the basic cannot deliver?Each client have their own way doing thing.If the person can do hello world very quick ,for sure he can do any other thing with proper guidance.Some candidate quite scare first time and unable to solve big formula question. Stick with simple and stress level will reduce and i prefer too see what they do how they talk . Its just not about code formula but on how much easier interaction in the future.

amelius• 9 years ago

I'm not sure if it is "binary search", but it certainly would be an interesting test, see [1].

[1] https://news.ycombinator.com/item?id=1277459

barrkel2• 9 years ago

Binary search is a terrible interview question because there's a handful of gotchas in the implementation.

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.

danpalmer• 9 years ago

We ask a question that is roughly a little bit of database entity design, and a bit of scaling.

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.

foreigner• 9 years ago

Nortel once asked me to write "Hello World" in C++ when I was fresh out of school. You can't make this stuff up.

xcession• 9 years ago

Algorithm questions are not about the interviewer discovering what algos you know off the top of your head, but rather discovering how you solve a problem.

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.

gridworld2017• 9 years ago

Gamedev here and one thing I've noticed amongst peers is an emphasis on good practice over algo knowledge. Mastery of debugging for example is something to look for.

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 ;)

panbhatt• 9 years ago

Interviewers especially at the startup (where they think they would money by selling product) ask the questions like we developers need to use them daily by hand. These freaky people do not understand there is a difference between a DEVELOPER n a Dijkstra kind of developer. If I am a Dijkstra kind of developer i won't be working at your startup for some peanuts (either I will be at google/mfst or some other big company). Its not like you shouldn't know it there isn't any use of this. Illustrate a simple example through your career (<1% of all developers) where you have to innovate a SORTING/SEARCHING algo. This works happens in PHD where your sole goal/aim is to find/do something.

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.. :)

camilin87• 9 years ago

FizzBuzz

Ask HN: What are the most requested algorithms during technical interviews?

Related Stories