7 ms·

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

• aburan28 10y 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--b 10y 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-return-all-combinations-of-k-elements-from-n http://stackoverflow.com/questions/127704/algorithm-to-retur...
  • cantpassstepone 10y 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 10y 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--b 10y ago
        Once I was interviewed by a very seasoned developer. The only question he asked me was to write a C function that swaps the content of 2 pointers. He told me 90% of the people he saw screwed it up.
        • chaosite 10y ago
          This is, of course, the point of FizzBuzz. http://wiki.c2.com/?FizzBuzzTest http://wiki.c2.com/?FizzBuzzTest
    • d--b 10y 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 10y 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 10y 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-combination 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 10y ago
      <3 ruby -- I hope they add a `.fizzbuzz` method to the enumerable module in the next release.
  • divbit 10y 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-projectEulerNum51/EulerMath.ts#L51 https://github.com/divbit/tspm/blob/master/example-projectEu...
• raverbashing 10y ago
  Sorting, especially Quicksort or similar sorts. Insertion/Selection might be asked as well
• mynameisjody 10y 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. :)
• yread 10y 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 10y 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'.
    • yread 10y ago
      > A full outer join or left or right? That's what I'm trying to do - get the interviewee to ask more :)
  • Retric 10y 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.
    • Declanomous 10y 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 10y ago
  https://news.ycombinator.com/item?id=13294318 https://news.ycombinator.com/item?id=13294318
• henrik_w 10y 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.
• imron 10y ago
  Fizzbuzz and despite its popularity many people still get it wrong.
  • miguelrochefort 10y ago
    That is simply not true.
    • imron 10y ago
      Which of those two statements?
• jcadam 10y ago
  Pfft... I was once asked to build an R-tree (https://en.wikipedia.org/wiki/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 10y 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 10y 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 10y ago
      I asked that once and the reply was "we don't use freeware here". As their reason for coding everything themselves ...
  • 10y ago
• vinaygaba 10y ago
  I have been asked a lot of problems whose solution was a variation of Breadth First Search.
• startupdiscuss 10y 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.
  • MichaelGG 10y 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 10y 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.
  • knightofmars 10y 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 10y 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.
  • MichaelGG 10y 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.
    • bryanrasmussen 10y ago
      you definitely know some advanced 7 yr olds.
      • MichaelGG 10y ago
        Not if you explain it as a trick to guess someone's secret number between 1 and 100 in just 7 guesses.
    • 10y ago
• knightofmars 10y 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 10y 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?
    • knightofmars 10y 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.
    • barrkel 10y 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.
• alien3d 10y 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
  • alien3d 10y 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 10y 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 https://news.ycombinator.com/item?id=1277459
  • barrkel 10y 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 10y 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 10y 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 10y 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 10y 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 10y 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 10y ago
  FizzBuzz