Random Flip Matrix

Random Flip Matrix

What is this problem about?

The Random Flip Matrix problem asks you to design a class that randomly flips a 0-entry in an m×n binary matrix (initially all zeros) to 1, uniformly at random among all remaining zeros. It must support reset to all zeros. This coding problem uses virtual index mapping to avoid O(mn) space. The math, hash table, reservoir sampling, and randomized interview pattern is demonstrated.

Why is this asked in interviews?

Google asks this to test space-efficient random sampling. The naive approach stores all zero positions in a list; the elegant solution uses a hash map to virtually rearrange remaining indices, similar to Fisher-Yates shuffle without materializing the full array.

Algorithmic pattern used

Fisher-Yates shuffle with hash map. Maintain remaining = total zeros = m*n. For each flip: pick a random index r in [0, remaining-1]. Map r to an actual (row, col) pair using r → map.get(r, r). Record the flipped position. Swap this slot with the last slot: map[r] = map.get(remaining-1, remaining-1). Decrement remaining.

Example explanation

m=2, n=3. Total=6. Map starts empty.

• flip(): r=2 (random 0..5). map[2]=2 (unset). Row=0, col=2. map[2]=map.get(5,5)=5. remaining=5.
• flip(): r=3 (random 0..4). map[3]=3. Row=1, col=0. map[3]=map.get(4,4)=4. remaining=4. Returns valid distinct random (row,col) pairs.

Common mistakes candidates make

• Storing all zero positions (O(mn) space — wasteful).
• Not using virtual remapping (causes repeated selections).
• Incorrect row/col computation from flat index.
• Not cleaning up map on reset.

Interview preparation tip

Random Flip Matrix teaches the "virtual Fisher-Yates" technique: sample from a shrinking range without materializing all elements. The hash map stores only elements that have been remapped. This approach is O(1) space (excluding hash map entries) per operation. Practice: "random sampling without replacement," "reservoir sampling for k elements." Virtual array techniques are essential for memory-constrained random sampling.