Q012FreeFirmware
Implement and verify a bounded queue
Interview prompt
Question
Implement a fixed-capacity FIFO with O(1) push, pop, and peek, then briefly explain how you would verify its boundary and wraparound behavior. Capacity is an integer; values may be arbitrary Python objects, including None.
Candidate starting point
Implementation scaffold
class BoundedQueue:
def __init__(self, capacity):
"""TODO: implement this method."""
pass
def push(self, value):
"""TODO: implement this method."""
pass
def pop(self):
"""TODO: implement this method."""
pass
def peek(self):
"""TODO: implement this method."""
pass
def __len__(self):
"""TODO: implement this method."""
pass
def check_invariants(self):
assert 0 <= self.size <= self.capacity
assert 0 <= self.head < self.capacity
assert 0 <= self.tail < self.capacity
if self.size == 0:
assert self.head == self.tailReviewed example
Trace one case
Input
capacity=3; push(10), push(20), push(30), push(99), pop(), push(40)Expected output
push(99) reports overflow and changes no state; pop returns 10; final queue is [20, 30, 40]The failed overflow leaves the full queue intact, then the final push wraps the circular tail into the slot cleared by pop.
What to cover
Requirements
- Reject nonpositive capacity, overflow, and pop or peek underflow.
- Use a circular array with explicit head, tail, and size state.
- Clear a popped slot so the queue does not retain stale object references.
- Describe directed wraparound checks and a seeded randomized comparison against collections.deque.