What is a Deque (Double-Ended Queue)?

0-2 years experience

1. 1We are building a simple 'Undo/Redo' feature for a text editor where users can perform actions, undo them, or redo them. If we want to limit the history to the last 50 actions to save memory, how would you use a double-ended queue to manage this history buffer?
2. 2Imagine you are implementing a sliding window average for a real-time sensor stream where you need to constantly add new readings to the end and discard old readings from the front. Why might you choose a deque over a standard array or list for this?

2-5 years experience

1. 1We have a service that processes incoming customer requests. We recently switched our queue implementation from a standard linked-list queue to a circular-array-based deque to support a 'priority bypass' where urgent tasks are pushed to the front. However, during peak traffic, we're seeing sudden latency spikes and high memory allocation overhead. What could be causing this, and how would you debug it?
2. 2You're building a browser history component that needs to support back/forward navigation (which behaves like two stacks) but also needs to cap the total history size at 10,000 entries to prevent memory leaks. How would you design this using a single deque, and what are the tradeoffs compared to using two separate stacks?

5-8 years experience

1. 1We are designing a high-throughput work-stealing scheduler for a multi-core execution engine. Each worker thread has its own task queue. We need threads to push/pop tasks from their own queue quickly, but also allow idle threads to 'steal' tasks from other threads' queues to balance the load. How would you design the underlying data structure using a deque, and how do you handle concurrency/locking to minimize contention?
2. 2In a low-latency trading application, we need to maintain a sliding window of the maximum stock price over the last 10 seconds, processing millions of ticks per second. If we use a monotonic deque to solve this in O(N) time, what are the cache-locality implications of using a pointer-based deque versus a contiguous-memory circular buffer, and how would you optimize it?

8+ years experience

1. 1Our platform's core event-broker client library currently uses a custom-built, linked-list-based deque for local buffering before flushing to the network. As we scale to support ultra-low latency IoT telemetry, garbage collection pauses from node allocations in this deque are becoming our primary bottleneck. How would you lead the migration to a zero-allocation or ring-buffer-backed deque architecture without breaking backward compatibility for the dozens of product teams consuming this library?
2. 2We are designing a distributed, replicated log system similar to Kafka, where each partition needs an in-memory cache of the most recent segments to serve fast reads, while older segments are flushed to disk. How would you architect the in-memory buffer layer using a distributed deque-like abstraction, and how do you handle the trade-offs between memory pressure, disk I/O, and consistency during a node failover?