5 ms·

I generally don't mind whiteboard programming interviews but even so asking someone to implement merge sort is a bad question. My sanity check for any question

by avl999 5y ago

I generally don't mind whiteboard programming interviews but even so asking someone to implement merge sort is a bad question. My sanity check for any question I ask is- Is the question I'm asking something that someone in the past published a paper about? If so then that's probably not a good fit for a 45 minute whiteboarding interview. This question falls in that category. Generally those algorithms are complex enough that it is unrealistic to expect someone to get them right from first principles so at that point you are just selecting for people who just happened to have dealt with them, memorized them or implemented them recently. I have a co-worker who used to ask people to past to parse and evaluate infix notation expressions in interviews (and there are companies that ask that question). Always stuck me as weird as multiple papers have been written about that problem, are you really expecting someone to implement a solution to a problem that people spend weeks (months?) thinking about before publishing? Could even Djikstra have come up with the Shunting Yard Algorithm in a 45 minute interview (with implementation on whiteboard) if that was his first exposure to the problem of expression parsing?

lhorie 5y ago
Yep. I think it goes further than whether there's a published paper about. It boils down to "does the question have exactly one correct answer?" One important thing you learn in interviewer workshops is to avoid asking questions with "aha" components, i.e. things that can only be solved if a very specific insight is known. This type of question is problematic because it falls victim to the fallacious assumption that a candidate that excels in one specific problem must necessarily excel at others that are in actuality, at best, only marginally related. Instead, it is better to ask questions for which the solution can be arrived at with small increments in effort (e.g. maybe there's an obvious brute force solution and you start from there to discuss more optimal solutions, or maybe the candidate got stuck on some specific peculiarity and you can give a hint to unblock them and move on to another part of the problem to get more signal)
- azhenley 5y ago
  The "aha moment" is also known as the eureka effect. Psychologists call this "insight problem solving", which is terrible for interviewing since like you said since it isn't a problem that you can build up towards solving. As a teacher, I try to make sure my assignments/quizzes don't fall victim of this. For anyone interested, there are a lot of interesting studies on the topic if you search on Google Scholar. You've probably already seen matchstick arithmetic problems before (i.e., move a single matchstick to make the equation valid).
  - bradleyjg 5y ago
    It never ceases to amaze me that a profession full of people that studied something called “computer science” is also filled with people that refuse to read the literature when it comes to hiring and instead lean on gut feelings, anecdotes, and cargo cult-ing.
    - Cpoll 5y ago
      I've researched a lot about this since I've had to do hiring, but I haven't been lucky enough to find anything collectively definitive or comprehensive enough to describe as "the literature." Most of it leans towards "what not to do," which is helpful but leaves some gaps. What do you recommend?
    - gilmore606 5y ago
      > refuse to read the literature ... and instead lean on gut feelings, anecdotes, and cargo cult-ing I mean, if it works for programming...
rectang 5y ago
I was just watching a Jon Gjengset "Crust of Rust" stream on sorting, and when his quicksort implementation kept going sideways, I was like "haha how nostalgic".
w0mbat 5y ago
I got asked to whiteboard the Dijkstra Shunting Yard Algorithm at TripAdvisor in Palo Alto. I didn't get the job, which I could have done in my sleep. It's way too complicated to code on a whiteboard. I would never have asked somebody that question at Google.
908B64B197 5y ago
> My sanity check for any question I ask is- Is the question I'm asking something that someone in the past published a paper about? If so then that's probably not a good fit for a 45 minute whiteboarding interview. Also, is it a widely known algorithm? Because then I'm not measuring for programming ability; I'm measuring for rote memorization (there are people that will rote memorize all the sorting algos to be able to spit them out during interviews!). Asking for a simply program like wc, in my opinion, gives a much better idea if someone can code (hint: there's not a single way of writing it and to define a word). > I have a co-worker who used to ask people to past to parse and evaluate infix notation expressions in interviews That's a cool problem to use. I wouldn't expect a perfect parser or even a working one but I would be curious to see how they approach the problem and what they end up writing.
cowmoo728 5y ago
My impression of the facebook interview experience was that it is specifically selecting people that were calm under pressure and well rehearsed. They are testing for people that put in the effort to crank out a bunch of algorithms practice because they want to ace an interview. FB and Amazon were also explicit that they were looking for people with a particular "get things done and promote myself" attitude. Whether or not those people make good employees, I don't know. When I interviewed at FB, every round was something that I had drilled on leetcode or similar sites. Yes, the wording was changed and the problems were altered a bit, but they were the same algorithms. And there were also two "lightning" rounds of 15 minutes each to solve two simpler algorithms problems (maybe easy/medium difficulty on leetcode). This experience gave me the impression that facebook's goals in hiring were to select people who really wanted the job and could pass quizzes well.
- kazinator 5y ago
  If you can crank out some moderately complicated algorithms, even having rehearsed them, and get all the little details right, like all the cases that occur, that does show you kind of know what you're doing. Someone without the proper CS/programming background who is just trying to rote memorize will screw up the details, and not be able to explain anything if asked about it: like what is the purpose of that line of code? Only problem is, even if this interview question is good at testing that which it is testing, it might not be selecting people along the right dimensions in terms of being suited for the job. It's not probing all the attributes of a software engineer. Five candidates, A, B, C, D and E have done equally well on the exercise, excellent in fact, and are hired. Yet, in actual work, things go funny. A doesn't seem to believe in testing. Deliveries are sloppy and break things all the time. A is proud of her skills and treats criticism of their code as an insult. B has never heard the words "version" and "control" in one sentence. B works on an out-of-date version of the code to make a change, and then follows the Wiki instructions for getting a fresh checkout (which pulls the latest baseline) and then just copies their previously changed files into the new checkout. Their code submission therefore reverts numerous changes from other people (incompletely: just in those files), while asserting their own changes. On top of that, B makes gratuitous whitespace changes, doesn't follow any consistent coding standard (never mind the prescribed one), and randomly fixes things he sees wrong that do not relate to the topic of the change. C cannot handle changes in requirements. Even after code base has undergone many changes, C keeps thinking in the same concepts from when the code was two months old and C had been mostly working alone on that code, knowing everything about it. C's ideas about making changes no longer fit the new code. E.g. C cannot remember that some logic is now distributed, running in several places at once, because that's not how it once was, and consistently forgets that aspect. D cannot say no to any new task. Whenever someone talks to D, D gets distracted and excited and starts looking into what that person was talking about, and doing work on it. Whenever D gets stuck on something, D easily finds something else, and forgets about being stuck, or to report having been stuck. D leaves numerous tickets in an in-progress state, and that list just grows over time. E is simply lost in any large project. E has done nothing but programming challenges under 1000 lines of code. E has no skills with regard to navigating a large code tree and understanding the structure of something made of tends of thousands of lines (or orders of magnitudes more). E gets paralyzed when faced with making a change to a large system that will involve making some small changes to eight or nine files. But have you seen E's Tetris in five lines of code?
yodsanklai 5y ago
> Always stuck me as weird as multiple papers have been written about that problem, are you really expecting someone to implement a solution to a problem that people spend weeks (months?) thinking about before publishing except that these things aren't research material anymore and are now taught at undergraduate level.
- underwater 5y ago
  That's the point. No one is solving the problem, they're regurgitating knowledge. If you care is someone has completed a Computer Science degree, ask to see their resume. If you care if they actually learned the material, ask to see their GPA.
  - imoverclocked 5y ago
    Neither one of those things are reliable sources of information across candidates or universities.
    - yodsanklai 5y ago
      Especially when you consider applications from all over the world.
    - underwater 5y ago
      But a 45m technical interview is?
gh0std3v 5y ago
I don't think whiteboard programming is really a good metric for measuring someone's skills for a normal software engineering job. However, assuming that extensive knowledge of certain algorithms (like merge sort), data structures, or computational methods are necessary for a particular job, I think a better question to ask isn't "how do you implement merge sort" but instead to present the merge sort algorithm and then ask the interviewee how it works based on the code given. Obviously still not the best way to assess someone's skills, but I think it's better than just memorizing a bunch of algorithms without being able to explain how they work.
WalterBright 5y ago
> parse and evaluate infix notation expressions Wirth's "Pascal User Manual and Report" has a listing of a program on pg 75 that does just that. Except it emits the expressions in postfix form rather than evaluating them. It's 31 lines of code, including declarations and `end` statements. K+R "The C Programming Language" has a desk calculator that evaluates postfix form on pages 74-75 which is about 60 lines of code including lines with just a {, and handles +-*/= including user interface and error checking.
kazinator 5y ago
Say that it's a binary merge sort over a singly linked list. A binary merge sort, if written recursively, is straightforward divide-and-conquer. The input list is divided into two halves, which are separately sorted via recursion, and then the sorted halves are merged to produce the sorted output. The algorithm pops out of the definition. If you know the above definition (or the interviewer has provided it, which they should!) the rest is just an exercise which demonstrates that you can: - completely analyze a problem's cases, including figuring out the existence of cases that are not spelled out in the description (like how to terminate the recursion) - manipulate pointers - decompose a problem into small, simple functions that you can separately reason about: (merging two lists, chopping a list in half, and such). It's not such a bad interview question. I would actually tell all the candidates at least a day ahead of time that they will be implementing merge sort in C using a singly linked list during the interview, so they can study it all they want and rehearse coding it. It's complicated enough that it can't just be regurgitated from memory by someone who doesn't know what the are doing. (Say, someone who had someone else write the code, and then tried to rote memorize it.) The memory has to be accompanied by understanding if the candidate is to reconstruct it with few or no flaws.
rrjanbiah 5y ago
FWIW, I have created a tracker under the Open Market Research repo to track such broken hiring and fake job posts https://github.com/OpenMarketResearch/Labs/issues/new?labels=0001+Broken+Companies+Hiring&template=report_broken_companies.yml&title=%5B0001%5D%3A+ https://github.com/OpenMarketResearch/Labs/issues/new?labels...

by avl999 5y ago

lhorie 5y ago

Yep. I think it goes further than whether there's a published paper about. It boils down to "does the question have exactly one correct answer?" One important thing you learn in interviewer workshops is to avoid asking questions with "aha" components, i.e. things that can only be solved if a very specific insight is known. This type of question is problematic because it falls victim to the fallacious assumption that a candidate that excels in one specific problem must necessarily excel at others that are in actuality, at best, only marginally related. Instead, it is better to ask questions for which the solution can be arrived at with small increments in effort (e.g. maybe there's an obvious brute force solution and you start from there to discuss more optimal solutions, or maybe the candidate got stuck on some specific peculiarity and you can give a hint to unblock them and move on to another part of the problem to get more signal)

azhenley 5y ago
The "aha moment" is also known as the eureka effect. Psychologists call this "insight problem solving", which is terrible for interviewing since like you said since it isn't a problem that you can build up towards solving. As a teacher, I try to make sure my assignments/quizzes don't fall victim of this. For anyone interested, there are a lot of interesting studies on the topic if you search on Google Scholar. You've probably already seen matchstick arithmetic problems before (i.e., move a single matchstick to make the equation valid).
- bradleyjg 5y ago
  It never ceases to amaze me that a profession full of people that studied something called “computer science” is also filled with people that refuse to read the literature when it comes to hiring and instead lean on gut feelings, anecdotes, and cargo cult-ing.
  - Cpoll 5y ago
    I've researched a lot about this since I've had to do hiring, but I haven't been lucky enough to find anything collectively definitive or comprehensive enough to describe as "the literature." Most of it leans towards "what not to do," which is helpful but leaves some gaps. What do you recommend?
  - gilmore606 5y ago
    > refuse to read the literature ... and instead lean on gut feelings, anecdotes, and cargo cult-ing I mean, if it works for programming...

rectang 5y ago

I was just watching a Jon Gjengset "Crust of Rust" stream on sorting, and when his quicksort implementation kept going sideways, I was like "haha how nostalgic".

w0mbat 5y ago

I got asked to whiteboard the Dijkstra Shunting Yard Algorithm at TripAdvisor in Palo Alto. I didn't get the job, which I could have done in my sleep. It's way too complicated to code on a whiteboard. I would never have asked somebody that question at Google.

908B64B197 5y ago

> My sanity check for any question I ask is- Is the question I'm asking something that someone in the past published a paper about? If so then that's probably not a good fit for a 45 minute whiteboarding interview. Also, is it a widely known algorithm? Because then I'm not measuring for programming ability; I'm measuring for rote memorization (there are people that will rote memorize all the sorting algos to be able to spit them out during interviews!). Asking for a simply program like wc, in my opinion, gives a much better idea if someone can code (hint: there's not a single way of writing it and to define a word). > I have a co-worker who used to ask people to past to parse and evaluate infix notation expressions in interviews That's a cool problem to use. I wouldn't expect a perfect parser or even a working one but I would be curious to see how they approach the problem and what they end up writing.

cowmoo728 5y ago

My impression of the facebook interview experience was that it is specifically selecting people that were calm under pressure and well rehearsed. They are testing for people that put in the effort to crank out a bunch of algorithms practice because they want to ace an interview. FB and Amazon were also explicit that they were looking for people with a particular "get things done and promote myself" attitude. Whether or not those people make good employees, I don't know. When I interviewed at FB, every round was something that I had drilled on leetcode or similar sites. Yes, the wording was changed and the problems were altered a bit, but they were the same algorithms. And there were also two "lightning" rounds of 15 minutes each to solve two simpler algorithms problems (maybe easy/medium difficulty on leetcode). This experience gave me the impression that facebook's goals in hiring were to select people who really wanted the job and could pass quizzes well.

kazinator 5y ago
If you can crank out some moderately complicated algorithms, even having rehearsed them, and get all the little details right, like all the cases that occur, that does show you kind of know what you're doing. Someone without the proper CS/programming background who is just trying to rote memorize will screw up the details, and not be able to explain anything if asked about it: like what is the purpose of that line of code? Only problem is, even if this interview question is good at testing that which it is testing, it might not be selecting people along the right dimensions in terms of being suited for the job. It's not probing all the attributes of a software engineer. Five candidates, A, B, C, D and E have done equally well on the exercise, excellent in fact, and are hired. Yet, in actual work, things go funny. A doesn't seem to believe in testing. Deliveries are sloppy and break things all the time. A is proud of her skills and treats criticism of their code as an insult. B has never heard the words "version" and "control" in one sentence. B works on an out-of-date version of the code to make a change, and then follows the Wiki instructions for getting a fresh checkout (which pulls the latest baseline) and then just copies their previously changed files into the new checkout. Their code submission therefore reverts numerous changes from other people (incompletely: just in those files), while asserting their own changes. On top of that, B makes gratuitous whitespace changes, doesn't follow any consistent coding standard (never mind the prescribed one), and randomly fixes things he sees wrong that do not relate to the topic of the change. C cannot handle changes in requirements. Even after code base has undergone many changes, C keeps thinking in the same concepts from when the code was two months old and C had been mostly working alone on that code, knowing everything about it. C's ideas about making changes no longer fit the new code. E.g. C cannot remember that some logic is now distributed, running in several places at once, because that's not how it once was, and consistently forgets that aspect. D cannot say no to any new task. Whenever someone talks to D, D gets distracted and excited and starts looking into what that person was talking about, and doing work on it. Whenever D gets stuck on something, D easily finds something else, and forgets about being stuck, or to report having been stuck. D leaves numerous tickets in an in-progress state, and that list just grows over time. E is simply lost in any large project. E has done nothing but programming challenges under 1000 lines of code. E has no skills with regard to navigating a large code tree and understanding the structure of something made of tends of thousands of lines (or orders of magnitudes more). E gets paralyzed when faced with making a change to a large system that will involve making some small changes to eight or nine files. But have you seen E's Tetris in five lines of code?

yodsanklai 5y ago

> Always stuck me as weird as multiple papers have been written about that problem, are you really expecting someone to implement a solution to a problem that people spend weeks (months?) thinking about before publishing except that these things aren't research material anymore and are now taught at undergraduate level.

underwater 5y ago
That's the point. No one is solving the problem, they're regurgitating knowledge. If you care is someone has completed a Computer Science degree, ask to see their resume. If you care if they actually learned the material, ask to see their GPA.
- imoverclocked 5y ago
  Neither one of those things are reliable sources of information across candidates or universities.
  - yodsanklai 5y ago
    Especially when you consider applications from all over the world.
  - underwater 5y ago
    But a 45m technical interview is?

gh0std3v 5y ago

I don't think whiteboard programming is really a good metric for measuring someone's skills for a normal software engineering job. However, assuming that extensive knowledge of certain algorithms (like merge sort), data structures, or computational methods are necessary for a particular job, I think a better question to ask isn't "how do you implement merge sort" but instead to present the merge sort algorithm and then ask the interviewee how it works based on the code given. Obviously still not the best way to assess someone's skills, but I think it's better than just memorizing a bunch of algorithms without being able to explain how they work.

WalterBright 5y ago

> parse and evaluate infix notation expressions Wirth's "Pascal User Manual and Report" has a listing of a program on pg 75 that does just that. Except it emits the expressions in postfix form rather than evaluating them. It's 31 lines of code, including declarations and `end` statements. K+R "The C Programming Language" has a desk calculator that evaluates postfix form on pages 74-75 which is about 60 lines of code including lines with just a {, and handles +-*/= including user interface and error checking.

kazinator 5y ago

Say that it's a binary merge sort over a singly linked list. A binary merge sort, if written recursively, is straightforward divide-and-conquer. The input list is divided into two halves, which are separately sorted via recursion, and then the sorted halves are merged to produce the sorted output. The algorithm pops out of the definition. If you know the above definition (or the interviewer has provided it, which they should!) the rest is just an exercise which demonstrates that you can: - completely analyze a problem's cases, including figuring out the existence of cases that are not spelled out in the description (like how to terminate the recursion) - manipulate pointers - decompose a problem into small, simple functions that you can separately reason about: (merging two lists, chopping a list in half, and such). It's not such a bad interview question. I would actually tell all the candidates at least a day ahead of time that they will be implementing merge sort in C using a singly linked list during the interview, so they can study it all they want and rehearse coding it. It's complicated enough that it can't just be regurgitated from memory by someone who doesn't know what the are doing. (Say, someone who had someone else write the code, and then tried to rote memorize it.) The memory has to be accompanied by understanding if the candidate is to reconstruct it with few or no flaws.

rrjanbiah 5y ago

FWIW, I have created a tracker under the Open Market Research repo to track such broken hiring and fake job posts https://github.com/OpenMarketResearch/Labs/issues/new?labels=0001+Broken+Companies+Hiring&template=report_broken_companies.yml&title=%5B0001%5D%3A+ https://github.com/OpenMarketResearch/Labs/issues/new?labels...