Problem

/** 
 * @param array the array from which we 
 * @return a uniform random derangement
 */
export function derange<T>(array: T[]): T[] {

}

Solution

import { randomInt } from '../random/random';

/** 
 * @param array the array from which we 
 * @return a uniform random derangement
 */
export function derange<T>(array: T[]): T[] {
  array = array.slice();

  for (let i = 0; i < array.length - 1; i++) {
    const randomIndex = randomInt(i + 1, array.length - 1);
    [array[i], array[randomIndex]] = [array[randomIndex], array[i]];
  }

  return array;
}

Transcript

00:00

Today's coding interview question is called derangement. And this comes from a request on a lesson on shuffling. And as we will see, it is actually quite easy to end up with derangement just by a slightly poor implementation of shuffling. Now, derangement does have real world applications, for example, in peer reviewing assignments, but we want to take each individual's assignment and randomly assign it to someone else. So this algorithm is useful to have in your toolbox. So let's go. Now, we're going to try something different for this particular lesson. And I think the best way to explain this particular algorithm is to write the test first.

00:33

A arrangement is an arrangement of the original array such that none of the items remain in their original place. And that is exactly what our test is ensuring within an array of a hundred items. We want to make sure that after we invoke the range, the item at an individual index is not equal to the item that was present there before. So with the test out of the way, let's jump into our implementation and build a skeleton for the function that we are looking for. We take an array of items T and then return a uniform random derangement of that input array. Now to help us along in our journey,

01:05

we will bring in the random integer function, which we have a lesson dedicated to so that we don't have to recap that over here. And then within the function body, the first thing that we will do is we will create a copy of the input array because we do not want to be mutating someone else's own array. And the way the algorithm is going to work is that we will loop through the items in the array one by one. And for each iteration we'll pick a random index from the remaining number of items and put that into the current position. That is what this swap line is doing. And then finally, we will return this arranged version.

01:38

Now, picking items from a random index, excluding the current one, ensures that the item that ends up at the current index is not going to be the item that was there before. And in terms of analysis, this is going to be a uniform derangement where each item is going to have the probability of one over N minus one for ending up at the position where it does end up. Now, even though we are carrying out the algorithm in place, it might be helpful for you to visualize it as two arrays and input array and an output array where we are placing items.

02:10

And the probability of the first item that ends up at position A is going to be one over N minus one, because we are going to pick it up from the remaining array. And then for the second item, the probability will be that it doesn't end up in the first place, which means that it is unlucky. That is N minus two divided by N minus one. And then it does get picked up for the second iteration. That is, it gets picked up with the probability of one over and minus two. And if you multiply these two, we end up with the probability of the item in the second place to be one over and minus one.

02:42

And then you can repeat this analysis for the remaining items as well. Very similar to how we did for shuffling. In shuffling the probability of each item at a particular place was one over N. And over here it is one over N minus one. So in a sense, shuffling is more random than the arrangement because there are lesser positions for the item to end up because we know that it's not going to be in its original position. And if you take a look back at this algorithm, this is exactly the same as what we implemented was shuffling except for the one key difference where we pick up a random item at I plus one to make sure

03:16

that the item that we get for the current index is not the same as what is sitting at the index right now. One more thing to watch out for is that we have to make sure that we terminate the loop when we only have one item remaining, as there is going to be no item to pick from the remaining array to put into the current position. And in terms of space and time complexity, it is going to be constant space as we are doing the swaps in place. And in terms of time complexity, we are only looping through the input array once, so it is going to be OFN.

Pro Members Only

This lesson is available if you have an active subscription.

Alternatively, some member might be able to gift it to you.

Coding Interview Lessons

Derangement

Subscription Required

Problem

Solution

Transcript

Coding Interview