You need to find the maximum value in every window of size k as it slides across an array of n elements. Which approach correctly uses a deque to solve this in O(n)?
AStore all k elements in the deque for each window and scan for the max — O(k) per window
BMaintain a deque of indices in decreasing value order, removing expired indices from the front and smaller indices from the back as each new element arrives
CUse the deque as a sorted set, inserting in order at each step
DPush all elements onto the deque and pop the front k times per window
The key insight is that the deque's bidirectional O(1) access enables a clever invariant: the front always holds the index of the current maximum. When a new element arrives, you remove from the back any index whose value is ≤ the new element (they can never be a future maximum), and remove from the front any index that has slid out of the window. This processes each element at most twice — once pushed, once popped — giving O(n) total. Option A is the naive O(nk) approach; options C and D misuse the deque.
Question 2 Multiple Choice
A deque is implemented with a circular array. Which statement best describes the trade-off compared to a doubly linked list implementation?
AThe circular array is slower because it must check for wraparound on every operation
BThe doubly linked list has better cache locality because elements are stored sequentially in memory
CThe circular array has better cache locality and avoids per-element pointer overhead, but requires occasional resizing
DBoth implementations have identical performance characteristics
Cache locality is the key difference. A circular array stores elements contiguously in memory, so sequential access benefits from CPU cache lines. A doubly linked list scatters nodes across the heap; each pointer dereference may cause a cache miss. The linked list trades this for no resizing overhead and simpler wraparound logic, but the circular array's cache efficiency typically wins in practice. The wraparound check in a circular array is a single modulo or branch — negligible compared to cache misses.
Question 3 True / False
A deque can simulate both a stack (LIFO) and a queue (FIFO) by choosing which ends to use for insertion and removal.
TTrue
FFalse
Answer: True
This is precisely the deque's defining property. Use push-back and pop-back exclusively and it behaves as a stack. Use push-back and pop-front exclusively and it behaves as a FIFO queue. Use both ends freely and you get a structure neither a pure stack nor queue can express — for example, adding high-priority items to the front and normal items to the back (as in 0-1 BFS).
Question 4 True / False
A deque's O(1) performance at both ends makes it strictly slower than a dedicated stack or queue for applications that mainly need one-ended access.
TTrue
FFalse
Answer: False
This is a common misconception. A deque with the right implementation (circular array or doubly linked list) performs single-ended operations in O(1) — identical to a stack or queue. There is no overhead for 'having' the extra capability if you don't use it. In practice, standard library deques (Python's collections.deque, Java's ArrayDeque) are often used even when only stack or queue behavior is needed.
Question 5 Short Answer
Explain why a deque, rather than a simple queue or stack, is the right data structure for the sliding window maximum problem.
Think about your answer, then reveal below.
Model answer: The sliding window maximum requires removing expired elements from the front (the old maximum's index has left the window) and removing dominated elements from the back (any index with a value smaller than the new element can never become the maximum). These are two distinct removal operations at opposite ends — exactly what a deque supports in O(1). A queue only removes from one end; a stack from the other. Neither alone can express 'maintain a decreasing sequence while expiring old elements from the front.'
The algorithm's elegance comes from the deque enforcing an invariant: elements are in decreasing order of value, and the front is always the current window's maximum. Both ends are actively used during every element insertion — the back is cleaned of dominated elements, and the front is checked for expiry. This is a pattern that appears in many sliding-window optimization problems and is the canonical demonstration of why deques are 'fundamental to many algorithms,' not niche.