Write better code: Day 3 - In-Place Shuffle

#challenge

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.

My answers are in the comments.

Question from InterviewCake

Top comments (1)

Arjun Rajkumar • Dec 7 '18

This was the logic for inplace shuffle..

Go thru the entire array
Initially with index 0, pick a random number between (0...array.size) and interchange the two numbers at [0] and [random]
Then with index 1, pick a random number between (1...array.size) and interchange them.
Then with index 2, pick a random number between (2...array.size) and interchange them.
Repeat...

def inplace_shuffle(shuffle_me)
  shuffle_me.each.with_index do |val, index|
    random = rand(index..(shuffle_me.length-1))
    shuffle_me[index], shuffle_me[random] = shuffle_me[random], shuffle_me[index]
  end
end

Goes thru once so it has O[n] time and O[1] space.

DEV Community

Write better code: Day 3 - In-Place Shuffle

Day 3: Question 1

My answers are in the comments.

Question from InterviewCake

Top comments (1)

Read next

Unlock Ultimate Security: How to Use YubiKey (or Any Security Key) for Passwordless Access in Azure Virtual Machines!

GBASE数据库 | GBase 8c 500 Primary-Standby Maintenance: Common Issues and Solutions

What is Wireless Communication?

Mastering Blockchain: A Hands-On Journey with Go