This problem was asked by Facebook.

Given a function that generates perfectly random numbers between 1 and k (inclusive), where k is an input, write a function that shuffles a deck of cards represented as an array using only swaps.

It should run in O(N) time.

Hint: Make sure each one of the 52! permutations of the deck is equally likely.

My Solution(Python):


"""
Fisher-Yates Algorithm
https://www.geeksforgeeks.org/shuffle-a-given-array-using-fisher-yates-shuffle-algorithm/
"""
import numpy as np

def randK(k: int) -> int:
    return np.random.randint(0, k+1)

def shuffleDeck(cards: list, k: int) -> list:
    n = len(cards)
    for i in range(n-1, 0, -1):
        j = randK(i)
        cards[i], cards[j] = cards[j], cards[i]
    return cards

print(shuffleDeck(cards=list(range(1, 53)), k=10))