Q: When would you choose a circular buffer, and what are the implementation subtleties?

Answer when I'd choose it with concrete scenarios: When bounded memory is a guarantee I need — a ring buffer never grows, so memory use is known in advance. In embedded systems, real-time audio/video processing and sensor data this is a hard requirement. When I need the last N items — circular logs, the last N measurements, metric windows. When full, the oldest is overwritten automatically and you write no cleanup code. High-frequency producer-consumer — contiguous memory and no reallocation means no latency spikes. For queues generally — an ArrayDeque is exactly this. Implementation subtleties — this part shows experience: Telling "full" from "empty": head == tail holds in both cases. Two standard fixes — keep a separate size counter (clear, uses the full capacity) or always leave one slot free (no counter, one slot lost). Wrap arithmetic: (head + i) % capacity. If the capacity is a power of two, & (capacity - 1) is faster — used in performance-critical code. The policy when full: reject the new element (backpressure) or overwrite the oldest (ring buffer)? That is a product decision and must be explicit in the code — silently dropping data is dangerous. GC: if you don't null out the vacated slot, the object stays reachable from the buffer and can't be collected — a hidden memory leak. Concurrency: a single-producer/single-consumer buffer can be implemented lock-free; with multiple threads you need synchronisation. Wrap up: "In practice I reach for the library's ArrayDeque/Queue first; I hand-roll a circular buffer only for specific requirements like fixed capacity, an overwrite policy, or lock-free behaviour."

Question 1

What is a queue and how does it differ from a stack?

Accepted Answer

State the difference precisely in one sentence: both are abstract data types that manage the order of elements; the only difference is which end you remove from. A stack is LIFO (add and remove at the same end), a queue is FIFO (opposite ends). Give the operations with complexity: enqueue, dequeue, peek — all O(1) in a correct implementation. Then answer why the difference matters in practical terms — that's the line between a definition and a strong answer: swap the stack for a queue in the same graph-traversal code and DFS becomes BFS. A stack expresses "close the most recently opened first" (undo, brackets, recursion); a queue expresses "fair ordering" (task queues, printer spools, BFS). Close with an implementation note: don't use an array plus shift() as a queue — shift is O(n); the right choice is an ArrayDeque (circular buffer) or a linked list. That note ties the answer from theory to practice.

Question 2

How would you implement an efficient queue in JavaScript?

Accepted Answer

Start by showing the problem — that's the real checkpoint here: array.push() + array.shift() is the most common solution, but shift() is O(n), because arrays are contiguous and removing the first element shifts everything else. Pushing n elements through gives O(n²). Then list the fixes: An array with two indices (the simplest correct fix): append with push, and dequeue by advancing a head index (queue[head++]) — O(1) removal. To stop the array growing forever, compact periodically (e.g. when head passes half the length) with slice(head) — still amortized O(1). A circular buffer: a fixed-capacity array with head/size fields and wrapping via (head + size) % capacity. Memory is bounded and cache locality is good. The fixed capacity is actually a feature wherever you want backpressure. A linked list: remove at the head, append at the tail — guaranteed O(1), but an object allocation per node and poor cache locality. Choice and justification: for small queues it doesn't matter; under load I'd take the two-index array or the circular buffer, since both stay in contiguous memory. End with the measuring habit: "This is something to measure — at 100 elements shift() is a non-issue, at 100,000 it's plainly visible."

Question 3

What is the difference between BFS and DFS? When do you choose each?

Accepted Answer

Start from the structure — it's the clearest explanation: BFS uses a queue (FIFO), DFS uses a stack (LIFO, or recursion). The code is nearly identical; only the end you take from changes. Behavioural difference: BFS expands level by level in order of distance from the start; DFS follows one branch to the end and then backtracks. I pick BFS when I need the shortest path in an unweighted graph (its most important property), the nearest match, or level-wise processing (printing each tree level separately), or when the tree is very deep but the answer is near. Memory: at worst the width of one level — which can be large in wide graphs. I pick DFS when I need to explore all paths or configurations (backtracking: sudoku, permutations), for cycle detection, topological sorting, or finding connected components. Memory: at worst the depth — which can be large in deep graphs. Recursion makes it shorter to write but risks a stack overflow; an explicit stack fixes that. Complexity is the same for both: O(V + E) time. The difference is memory and which answer they find first. End with the most common bug: in BFS, mark "visited" on enqueue, not on dequeue — otherwise the same node enters the queue repeatedly.

Question 4

How would you design a rate limiter? Which structure would you use?

Accepted Answer

Start by clarifying the requirement — the first step in any design question: how is the limit expressed (N requests per minute?), keyed by what (user, IP, API key?), single server or distributed? Then compare the algorithms: Fixed window: a counter per minute. Simplest, O(1), minimal memory. Its flaw: twice the load can slip through at a window boundary (N at second 59, N again at second 61). Sliding window log (deque): store each request's timestamp in a deque. On a new request, drop expired timestamps from the front, check size < limit, then append the new one at the back. Accurate; O(limit) memory, amortized O(1) per operation. A deque is chosen precisely because appends go to the back and removals come from the front — a textbook FIFO pattern. Token bucket: a bucket refilled at a fixed rate; each request consumes a token. Allows short bursts, O(1) memory. The most widely used approach in practice. Leaky bucket: smooths the output at a constant rate — when you need to even out traffic. The choice: "If accuracy matters and the limit is small, the sliding window log with a deque; for high-frequency, memory-sensitive scenarios, token bucket." Production details — the part that strengthens the answer: in a distributed system the state must live somewhere central like Redis (with a Lua script or INCR + EXPIRE for atomicity); set a TTL on stale keys or you leak memory; return 429 with a Retry-After header when the limit is hit; and vary limits by user tier.

Question 5

When would you choose a circular buffer, and what are the implementation subtleties?

Accepted Answer

Answer when I'd choose it with concrete scenarios: When bounded memory is a guarantee I need — a ring buffer never grows, so memory use is known in advance. In embedded systems, real-time audio/video processing and sensor data this is a hard requirement. When I need the last N items — circular logs, the last N measurements, metric windows. When full, the oldest is overwritten automatically and you write no cleanup code. High-frequency producer-consumer — contiguous memory and no reallocation means no latency spikes. For queues generally — an ArrayDeque is exactly this. Implementation subtleties — this part shows experience: Telling "full" from "empty": head == tail holds in both cases. Two standard fixes — keep a separate size counter (clear, uses the full capacity) or always leave one slot free (no counter, one slot lost). Wrap arithmetic: (head + i) % capacity. If the capacity is a power of two, & (capacity - 1) is faster — used in performance-critical code. The policy when full: reject the new element (backpressure) or overwrite the oldest (ring buffer)? That is a product decision and must be explicit in the code — silently dropping data is dangerous. GC: if you don't null out the vacated slot, the object stays reachable from the buffer and can't be collected — a hidden memory leak. Concurrency: a single-producer/single-consumer buffer can be implemented lock-free; with multiple threads you need synchronisation. Wrap up: "In practice I reach for the library's ArrayDeque/Queue first; I hand-roll a circular buffer only for specific requirements like fixed capacity, an overwrite policy, or lock-free behaviour."

Structure	Add/remove at the front	Add/remove at the back	Index access	Typical use
Stack	—	O(1) / O(1) (same end)	No	Undo, DFS, brackets
Queue (FIFO)	— / O(1)	O(1) / —	No	BFS, task queues
Deque	O(1) / O(1)	O(1) / O(1)	Usually yes (`ArrayDeque`)	Sliding window, undo+redo, work stealing
Array (with push/shift)	O(n) / O(n)	amortized O(1) / O(1)	O(1)	Unsuitable as a queue
Circular buffer	O(1) / O(1)	O(1) / O(1)	O(1) (with an offset)	Fixed-size buffers, audio, logs
Priority queue (heap)	Removal O(log n)	Insertion O(log n)	No	Scheduling, Dijkstra

Queue, Deque and Circular Queue

📚 Sources and documentation