Re:My worst tech interview experience
by kazinator on Wednesday December 01, 2021 @09:14PM
(#29411723)
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.
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.