Design a Queue — Implementation Trade-offs

A phone-screen OOD round: design a queue and discuss how different internal implementations (array vs. linked list, circular buffer, etc.) trade off against each other in performance. Requirements Design a queue data structure. Be ready to discuss multiple internal implementations and their performance trade-offs (e.g. dynamic array vs. linked list vs. ring buffer): amortized vs. worst-case enqueue/dequeue, memory locality, resizing cost. Notes The interviewer drives the discussion toward trade-offs ("what are the different ways to implement this internally, and what does each cost?") rather than a single correct answer. Relatedly, some screens push toward a circular-queue (ring-buffer) design via guided follow-ups — be comfortable converting a naive queue into a fixed-size circular buffer when prompted. Preparation Implement a queue two ways (linked list and circular array) and articulate the trade-offs out loud. Practice the circular-buffer index arithmetic (head/tail/size, full vs. empty) since it's a common follow-up.