A coding interview that never happened

I've conducted hundreds of interviews that involve some kind of problem solving and most of them involved writing the solution in code. And most candidates make the same mistake so I figured it was time to share a simple strategy that seems to have worked for me over the years when I was the candidate.

The strategy is simple - solve the problem and write the code the same way you would solve a problem outside an interview. What it means is; if the problem seems too large/complex and you don't know how to solve it, then you need to break the problem down in smaller parts. Similarly when you write your code you should not write a single large function with a solution but rather split the code up in a number of functions that make sense.

Let me use an example to show you what I mean. I have never solved the Tower of Hanoi in any way and when I started thinking about this problem, at first I had no idea to how I would solve the problem. So I started thinking about the simple cases:

  1. If I only need to move one disk - I know how to do that.
  2. If I only need to move two disks - I know how to do that since I can use the extra pin as temporary storage for the first disk until I get the second one in place.
So the second statement made me think that the essence of the algorithm to solve Tower of Hanoi is to move N-1 disks to temporary storage since that will allow me to move N disks do the desired location.

In other words the essence of the algorithm is (pseudo code):

move(n, from, to) { 
   if (n <= 0) { 
   move(n-1, from, temp) 
   move(1, from, to) 
   move(n-1, temp, to)  

At this point I frankly have no idea if there is a corner case where this does not work, but trying the algorithm with three disks also works so let's give it a try...

In an interview setting I would now start implementing the main function and leave any helpers out. Those can be implemented if there is time as needed. When I sat down and actually implemented this I realized a stack would be good to have so I created one. A helper function to figure out the temporary pin would also be nice to have so I added one of those too. I was also very paranoid that my solution would violate the disk size rule so I added a check in my stack to make sure I never put a disk larger than the previous disk in any stack. I was honestly surprised when I could see my implementation working for any number of disks. I really expected there to be some corner case this simple algorithm would not handle. And the resulting code can be found here: https://go.dev/play/p/CLm-oPmyfi5

Bottom line; breaking down the problem into smaller manageable chunks and solve each of those tends to always work. And breaking down your implementation by using helper functions tends to let you keep moving without getting stuck on implementation details.

I realize this advice may seem generic and not helpful, but still I've seen so many candidates over the years that fail because they do not break the problem down and start simple. So this is still my best advice.

No comments:

Post a Comment