4 ms·
> Then they proceed to ask candidates to derive a card shuffling algorithm on a whiteboard in 30 minutes and fail them from the interview if the running time co
by tzs 8y ago
> Then they proceed to ask candidates to derive a card shuffling algorithm on a whiteboard in 30 minutes and fail them from the interview if the running time complexity would be too high or if they can’t mathematically prove the result would be a uniform draw from the space of permutations of the cards.
I'd actually expect a surprisingly large fraction of programmers to be able to do reasonably OK on that particular problem--and I don't mean just those with CS degrees. I'm including the ones that are entirely self taught. In fact, especially those.
That's because so many of us, even those with CS degrees or other common degrees that programmers get instead of CS [1], started out trying to write games or other things that needed to shuffle, were sure that the obvious approach we took was right, and then found out it wasn't and why. It was our first personal encounter with the idea that you can analyze and reason about algorithms and their correctness.
In other words, shuffling was one of the first algorithmic "aha!" moments for many of us, and you don't really forget those.
[1] Mine is math, not CS, for example. Partly that's because when I got my degree, in the early '80s at Caltech, Caltech did not have an undergraduate CS degree. The CS department only offered graduate degrees. They had all the necessary undergraduate coursework available--they just had not yet put together a formal degree program.
- SamReidHughes 8y agoYep. I encountered the problem of shuffling while writing QBASIC code as a teenager. I couldn't prove that random swapping wasn't uniform, in those days, but was able to come up with the uniform algorithm everybody uses now and feel comfortable with its correctness. Granted, the interview question is pretty bad if it's just a test of if you've seen the problem already.
- nicoburns 8y agoIt possibly depends when you started programming. When I was making those kind of games and such things my environment had a built in shuffle call that worked fine...
- tzs 8y agoFor those who haven't seen it, here is how you can show with a counting and divisibility argument that a common algorithm many come up with to shuffle is not a fair shuffle. Here's the algorithm, in pseudo code (yes, with 1-based arrays!): let a = [1, 2, 3, ...., N] # the items to shuffle for i = 1 to N j = random_in(1, N) swap(a[i], a[j]) Imagine that random_in() makes a log of all its return values. In this program every time it is called it returns an integer >= 1 and <= N. It is called N times. Thus, the log consists of N integers with N possible values for each integer. In what follows we shall call such a log a trace of the program (because log could be confused for logarithm). (Trace has a meaning in linear algebra, but that should not cause a problem here). That means that there are N^N distinct possible traces. Each of these traces is equally likely. We can associate with each of the traces a shuffle, namely the shuffle that results from the run of the program that produced that trace. This gives us a list of N^N shuffles. This list will contain duplicates, because there are only N! distinct shuffles, and N! < N^N. The shuffle is fair if and only if each possible shuffle occurs the same number of times in the list of N^N shuffles. For it to be even possible for that to happen, we must have N! divides N^N. But if N > 2, that cannot happen. To show this note that if N! divides N^N, then every divisor of N! must divide N^N. Pick a prime P such that (1) p < N and (2) P does not divide N. Then p is a divisor of N! but is not a divisor of N^N, which shows that N! does not divide N^N, and so the shuffle is not fair. Can we really always pick such a prime? Yes. If N is divisible by every prime p < N, then N-1 must be prime, but then N-1 is a prime < N that does not divide N. Note that you cannot save this class of algorithm by doing more passes. Those just change the size of the trace from N^N to N^(kN) for some integer N. Nor can you save it by changing it to pick both indices at random for the swap instead of picking only one at random. That just changes N^N to (N^2)^N = N^(2N). As long as the random number generator is always asked for a number in {1, 2, ..., N} and it is called the same number of times every time the program is run, the trace size is going to be a power of N, and cannot be divide evenly by N! Now we can see why Fisher-Yates might work. It asks for a random number up to N the first iteration, up to N-1 the second iteration, and so on. That means its trace is N! long. There is no problem dividing N! by N!. Since N!/N! = 1, if we can show that each shuffle is included, that will also show that each is included the same number of times, and hence that Fisher-Yates is fair. All we have to do now to see that Fisher-Yates is fair is show that each shuffle can be produced by it. Given a desired shuffle, it is easy to construct the trace that results in it, and we are done.
- tzs 8y ago> Can we really always pick such a prime? Yes. If N is divisible by every prime p < N, then N-1 must be prime, but then N-1 is a prime < N that does not divide N. We don't actually need a prime. We just need something that divides N! but does not divide N. N-1 will do nicely.
- stcredzero 8y agoI just thought of it this way: You're implementing "n P n" which just reduces to n factorial. So you just have to show that your 1st iteration is choosing from n items, your 2nd iteration is choosing from (n - 1) items, ... the (n - 1)th iteration is choosing from 2 items. (Choosing from 1 item is a noop, of course.) All we have to do now to see that Fisher-Yates is fair is show that each shuffle can be produced by it. Given a desired shuffle, it is easy to construct the trace that results in it, and we are done. You mean: Given a desired shuffle, you show you can construct the only trace that results in it.