Exercises — Deque

Exercise 4.6.1 Beginner

Implement a FIFO queue using a deque with three operations: enqueue(value), dequeue(), and is_empty().

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.dequeue()   # 1
q.dequeue()   # 2

▶ Try in Playground

Exercise 4.6.2 Beginner

Implement a LIFO stack using a deque with push(value), pop(), and peek() (returns top without removing).

s = Stack()
s.push("a")
s.push("b")
s.peek()    # "b"
s.pop()     # "b"
s.peek()    # "a"

▶ Try in Playground

Exercise 4.6.3 Intermediate

Given a list of numbers and a window size k, return a list of the maximum value in each window as it slides from left to right.

nums = [1, 3, -1, -3, 5, 3, 6, 7]
k    = 3
# expected: [3, 3, 5, 5, 6, 7]
# hint: use a deque with maxlen=k, or use it to track indices

▶ Try in Playground

Exercise 4.6.4 Intermediate

Use a deque to check whether a string is a palindrome (reads the same forwards and backwards).

is_palindrome("racecar")   # True
is_palindrome("hello")     # False
is_palindrome("madam")     # True
# hint: pop from both ends and compare

▶ Try in Playground

Exercise 4.6.5 Advanced

Implement a RecentHistory class backed by a deque(maxlen=n) that records the last n events and can answer: “did event X happen in the last n events?”

h = RecentHistory(3)
h.record("login")
h.record("view")
h.record("purchase")
h.record("logout")          # "login" is now out of the window

h.contains("purchase")      # True
h.contains("login")         # False

▶ Try in Playground