Katkat
Back

Design a deck of cards with shuffle/draw

AppleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This question evaluates object-oriented design skills, understanding of randomness and probability in algorithms, and analysis of time/space complexity for data structures and operations.

Object-Oriented Design + Randomness: A Deck of Cards

Design an in-memory model of a standard 52-card playing deck. Your design will be exercised by client code that builds a fresh deck, shuffles it, and draws cards one at a time until the deck is exhausted.

Create classes to represent at least:

  • A card holding a rank (Ace through King) and a suit (Clubs, Diamonds, Hearts, Spades).
  • A deck that owns a collection of cards.

The deck must support two operations:

  1. shuffle() — randomizes the order of the cards currently remaining in the deck.
  2. draw() — removes one card from the deck and returns it.

Your design must also satisfy two correctness/probability requirements:

  • After shuffle(), every ordering (permutation) of the remaining cards is equally likely — i.e., the shuffle is unbiased.
  • Each draw() returns each currently-remaining card with equal probability at that moment.

Walk through your class design, justify your data-structure choice, give the algorithm for shuffle() and draw(), argue why the probability requirements hold, and state the time/space complexity of each operation. Sketch the core methods in your language of choice.

Constraints & Assumptions

  • A standard deck has exactly 52 distinct cards (4 suits × 13 ranks); no jokers unless you choose to support them.
  • The deck holds no duplicates; a drawn card is gone until the deck is rebuilt/reset.
  • A good pseudo-random number generator is available (e.g., a Random-style API that yields a uniform integer in a half-open range).
  • The deck is small and fully in memory; persistence, networking, and multi-deck shoes are out of scope unless you raise them.

Clarifying Questions to Ask

  • Should shuffle() shuffle only the remaining cards, or always reset to a full 52 and then shuffle?
  • What is the desired behavior of draw() on an empty deck — exception, sentinel/null, or an Optional-style empty value?
  • Does the deck need to be thread-safe (drawn from multiple threads concurrently), or is single-threaded use acceptable?
  • Should the PRNG be injectable (for deterministic, seedable tests), or is a built-in default acceptable?
  • Are duplicate cards or multi-deck "shoes" (e.g., blackjack's 6-deck shoe) ever required?
  • Do we need card equality/ordering (e.g., for comparing hands), or only identity and printing?

Hints

Hint 1

Where to start: Separate the *value* (an immutable card) from the *container* (a mutable deck). Build the full 52-card deck by taking the cross product of the 4 suits and 13 ranks. Pick the deck's internal representation by asking which operation has to be fast: removing a card.

Hint 2

Data structure: A dynamic array / list backs both operations cheaply if you treat one *end* as the "top." Removing from the end (pop) is $O(1)$ amortized; removing from the front forces an $O(n)$ shift. Avoid a structure (like a singly linked list) that makes random index access $O(n)$ — the shuffle needs random indexing.

Hint 3

Unbiased shuffle: The standard correct algorithm is the **Fisher–Yates (Knuth) shuffle**: iterate $i$ from $n-1$ down to $1$, pick $j$ uniformly in $[0, i]$, and swap positions $i$ and $j$. Beware the two classic traps — picking $j$ from the full range $[0, n-1]$ on every step, or "sort by a random key" — both produce biased orderings.

Hint 4

Uniform draw without relying on shuffle: If you want `draw()` to be uniform on its own (not depending on a prior shuffle), pick a random index $k \in [0, n-1]$, swap that card with the last card, then pop the last. This keeps `draw()` at $O(1)$ and never invalidates the deck.

Follow-up questions

  • How would you unit-test that `shuffle()` is unbiased and `draw()` is uniform, given that the output is random? (Hint: seed the PRNG for determinism; use a chi-square / frequency test over many trials for the distribution.)
  • Extend the design to a multi-deck "shoe" (e.g., 6 decks) and a "burn/discard" pile, then a `reshuffle()` that folds the discards back in. What changes?
  • If two players draw concurrently from the same deck, how do you guarantee no card is dealt twice and the draw stays uniform? Compare a coarse lock vs. a single-threaded dealer.
  • Suppose you must support an "infinite" stream of uniformly random cards with replacement (a card can repeat). How does the data structure and `draw()` change?