Preparing your design workspace

Loading the problem and your saved attempt…

Design and Implement a Random-Access FIFO Queue

Design a conceptually unbounded FIFO queue with constant-time enqueue, dequeue, and uniform random inspection, then extend it for equality, concurrency, and run-length encoding.

For this exercise, assume an in-memory generic queue supports `add(value)`, FIFO `poll()`, and non-removing `getRandom()`. `poll` and `getRandom` must be worst-case O(1), while `add` may be amortized O(1) as storage grows.

`getRandom` returns each currently queued occurrence with equal probability, so duplicate values occupy separate random slots. Empty `poll` and `getRandom` return an explicit empty result.

Derive an object model and storage representation that meet these contracts, walk through removal, growth, sampling, and equality, implement the single-threaded core, and write focused unit tests for add, poll, and getRandom.

Then discuss linearizable thread safety, equality by logical FIFO contents, deadlock-free comparison, and how equality changes when queues are represented as variable-length run-length encoded runs. Persistence and a distributed queue are outside scope.