I cheated on my Microsoft interview (2019)

Not disagreeing with your points.

> Preparing for this kind of question isn't cheating as long as you understood the answer.

TFA notes that because of lack of interview prep material in 2004, even when the author knew the question before-hand, it took them days to arrive at an optimal answer. And then it dawned on them that everyone else at the job fair, who may be seeing a question for the first time, only had 15 mins in a pressure-cooker situation to solve it.

TFA also notes that the author intentionally misled the interviewer as if they were solving the puzzle then and there: I casually explained how I could simply use a mathematical formula to calculate the sum of 1 to n (like, who doesn’t know the sum(1 to n) formula?) and compare that to the sum of the integers in the array. I slowly wrote out the solution I had come up with over days of thinking about the problem, being sure to pause periodically as if I was figuring it out for the first time. I talked through my thinking and made sure I had all the proper error checking in place. I double and triple checked my syntax. My handwritten code was perfect.

I don’t think this person would have done badly on the interview if they hadn’t practiced the question in advance. At least according to the narrative, when they first heard the problem they thought about summing the numbers: presumably they would also have gotten there during the interview.

It also begs the question that a direct path to “perfect code” is the intended goal. Admittedly this story takes place quite a while ago and there’s no one approach to interviewing in big tech, but I think it’s safe to say it’s generally a more nuanced evaluation. In a situation like this, the textbook approach is to start by proposing a quick and dirty naive solution, like storing all the seen values in an array, and telling the interviewer why or under what conditions you think it’s a bad solution. You could realize that there’s only one bit needed, so you could track eight values per byte. That’s probably the point at which the interviewer might prompt you to start coding, since there are a few details to get right to show that you know how to implement a simple algorithm, and there’s opportunity for followup about boundary conditions, scaling, big-O, etc.

At that point, you may have enough time for another prompt like “can you think of a way to do it without an array to store all the values?” If the candidate is still stuck, I’d offer them “what if I give you this formula for the sum of the numbers from 1 to N?” Similarly, if at some point earlier on they said “I think there’s a formula for this”, I’d probably give them a minute to think about it and then just tell them what it is. Because I want to move on to see if they can implement it.

Are a lot of FAANG interview questions math puzzles pretending to be programming questions? Unfortunately, yes. It’s hard to avoid when you have a people who are smart at math and not particularly skilled at interviewing. They tend to create questions based on something they’re impressed with themselves for knowing. I’m not suggesting anyone has solved the problem of how to decide, based on 45 minutes talking to someone, whether they’re going to be successful at the job.

what company is that?

Why so aggressive? What's the problem with the pen? The idea the OP proposes is to use it as a spring board to get a discussion going, I'm sure a pen, a keyboard or a interpretive dance would all work for what they're proposing

It might be the difficulty of actually getting it right (if by "right" we mean that all 52! permutations are equally likely. Or perhaps it is more accurate to say the ease of not getting it right.

Something like this:

  10 pick a number from 1 to 52
  20 if not already printed it
  30   print it
  40 if we have printed 52 numbers
  50   halt
  60 goto 10

works, but could take arbitrarily long time. Most people prefer bounded run time.

Most people seem to come up with something like this:

  array = [1, 2, ..., 52]
  for i = 0 to 51
    j = random(0,51)
    swap(array[i], array[j])
  print(array)

That has bounded time (constant time assuming random and swap are constant time). Unfortunately not all permutations are equally likely.

We can see that all permutations are equally likely by noting that there are 52 iterations of the loop, and each iteration has 52 possible outcomes. That gives us a total of 52^52 possible outcomes. 52! does not divide 52^52, so it is not possible for each of the 52! possible outcomes to be equally represented in the 52^52 outcomes.

To fix this, you can use the same basic idea of going through all 52 places in your array [1, 2, ..., 52] and swapping each with a random location, but instead of swapping the Nth location with a random location in the whole array, swap with a random location that is not earlier in the array.

Then you still have 52 iterations, but now the number of outcomes varies by iteration. The first iteration has 52 outcomes. The second has 51 outcomes. The third 50 outcomes and so on down to that last having only 1 outcome. That gives 52! possible outcomes, all equally likely. We just then have to show that every one of the 52! permutations is among those outcomes which is easy to do, and then we have shown that this is a correct shuffle.