## 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. ```hint 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 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 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 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. ``` ### 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? ### What a Strong Answer Covers - **Clean class decomposition:** an immutable card value object (rank + suit, with sensible equality and a readable string form) and a deck that owns the card collection plus its randomness source. - **Justified data structure:** a list/array with one end as the "top," explaining why pop-from-end gives $O(1)$ draw and supports in-place shuffling, and why other choices are worse. - **Correct unbiased shuffle:** Fisher–Yates stated precisely, with a probability argument that all $n!$ orderings are equally likely, and explicit mention of the biased anti-patterns to avoid. - **Correct uniform draw:** either "draw the top after an unbiased shuffle" with a uniformity argument, or the random-index swap-and-pop technique that is uniform without a prior shuffle. - **Complexity targets:** $O(n)$ time / $O(1)$ extra space for `shuffle()`; $O(1)$ time and space for `draw()`. - **Edge cases & API design:** explicit, documented behavior for an empty deck; testability via an injectable PRNG; awareness of thread-safety and secure-randomness trade-offs raised at the right altitude. ### 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?