This post originally appeared on Arjun Rajkumar 's blog. Arjun is a web developer based in Bangalore, India.
Day 3: Question 1
Write a method for doing an in-place shuffle of an array.
The shuffle must be "uniform," meaning each item in the original array must have the same probability of ending up in each spot in the final array.
Assume that you have a method get_random(floor, ceiling) for getting a random integer that is >= floor and <= ceiling.
An in-place algorithm operates directly on its input and changes it, instead of creating and returning a new object. This is sometimes called destructive, since the original input is "destroyed" when it's edited to create the new output.
If you want to follow along, feel free to post your answers in the comment.
Top comments (1)
This was the logic for inplace shuffle..
Goes thru once so it has O[n] time and O space.