Python Deque and Collections Practice Problems & Exercises
Practice: Deque and Collections
← Back to lessonBuild a deque by processing a sequence of directional append operations. Each operation is a tuple of ('left', value) or ('right', value).
Constraints:
- 0 to 1000 operations
- Values can be any integer
Solution
from collections import deque
def build_deque(operations):
dq = deque()
for direction, value in operations:
if direction == 'left':
dq.appendleft(value)
else:
dq.append(value)
return list(dq)
# Tests
print(build_deque([('right', 1), ('left', 2), ('right', 3), ('left', 4)]))
print(build_deque([('right', 20), ('left', 10), ('right', 30)]))
print(build_deque([]))
Time: O(n) -- each append is O(1). Space: O(n) for the deque.
from collections import deque
def build_deque(operations):
"""
Given a list of (direction, value) tuples where direction is
'left' or 'right', build a deque by appending each value to
the specified end. Return the deque as a list.
Example:
operations = [('right', 1), ('left', 2), ('right', 3), ('left', 4)]
Result: [4, 2, 1, 3]
"""
# TODO: implement
passExpected Output
[4, 2, 1, 3]
[10, 30, 20]
[]Hints
Hint 1: Create an empty deque, then loop through the operations list.
Hint 2: Use dq.append(val) for 'right' and dq.appendleft(val) for 'left'.
Hint 3: Return list(dq) at the end.
Simulate a log buffer that retains only the most recent k messages. Use deque(maxlen=k) so old messages are automatically discarded.
Constraints:
- 0 to 100,000 messages
- 1 <= k <= len(messages)
Solution
from collections import deque
def recent_messages(messages, k):
buffer = deque(maxlen=k)
for msg in messages:
buffer.append(msg)
return list(buffer)
# Tests
print(recent_messages(["boot", "init", "connect", "auth", "query", "close"], 3))
print(recent_messages(["a", "b", "c", "d", "e"], 1))
print(recent_messages(["a", "b", "c", "d", "e"], 5))
Time: O(n) where n is the number of messages. Space: O(k) -- the deque never holds more than k elements.
from collections import deque
def recent_messages(messages, k):
"""
Given a list of log messages and an integer k, return the
last k messages. Use deque(maxlen=k) so memory never exceeds
k entries, even if millions of messages stream in.
Example:
messages = ["boot", "init", "connect", "auth", "query", "close"]
k = 3
Result: ["query", "close"] -- wait, that's only 2... nope:
Result: ["auth", "query", "close"]
"""
# TODO: implement
passExpected Output
['auth', 'query', 'close']
['e']
['a', 'b', 'c', 'd', 'e']Hints
Hint 1: Create a deque with maxlen=k.
Hint 2: Append each message -- the deque auto-evicts the oldest when full.
Hint 3: Return list(dq) at the end.
Use a deque to check whether a string is a palindrome. Load characters into a deque, then compare from both ends simultaneously using popleft() and pop().
Constraints:
- Ignore spaces and case
- Empty string and single character are palindromes
Solution
from collections import deque
def is_palindrome(s):
cleaned = s.lower().replace(" ", "")
dq = deque(cleaned)
while len(dq) > 1:
if dq.popleft() != dq.pop():
return False
return True
# Tests
print(is_palindrome("racecar"))
print(is_palindrome("Race Car"))
print(is_palindrome("hello"))
print(is_palindrome("A"))
print(is_palindrome(""))
Time: O(n) -- each character is popped exactly once. Space: O(n) for the deque.
from collections import deque
def is_palindrome(s):
"""
Check if a string is a palindrome using a deque.
Compare characters from both ends, moving inward.
Ignore spaces and case.
Example:
is_palindrome("racecar") -> True
is_palindrome("Race Car") -> True
is_palindrome("hello") -> False
"""
# TODO: implement
passExpected Output
True
True
False
True
TrueHints
Hint 1: Convert to lowercase and remove spaces before loading into the deque.
Hint 2: While the deque has more than 1 element, popleft and pop -- compare them.
Hint 3: If any pair differs, return False. If the loop finishes, return True.
Use deque.rotate() to rotate a list by k positions. Positive k rotates right, negative k rotates left.
Constraints:
- k can be positive, negative, or zero
- The list can have 0 to 100,000 elements
Solution
from collections import deque
def rotate_list(nums, k):
dq = deque(nums)
dq.rotate(k)
return list(dq)
# Tests
print(rotate_list([1, 2, 3, 4, 5], 2))
print(rotate_list([1, 2, 3, 4, 5], -1))
print(rotate_list([1, 2, 3], 0))
print(rotate_list([1], 100))
Time: O(k) for the rotation + O(n) for deque construction. Space: O(n) for the deque.
Note: deque.rotate(k) is O(k), not O(n). It performs k individual popleft/append (or pop/appendleft) operations internally, each O(1).
from collections import deque
def rotate_list(nums, k):
"""
Rotate a list to the right by k positions using deque.rotate().
Return the rotated list.
Example:
rotate_list([1, 2, 3, 4, 5], 2) -> [4, 5, 1, 2, 3]
rotate_list([1, 2, 3, 4, 5], -1) -> [2, 3, 4, 5, 1]
"""
# TODO: implement
passExpected Output
[4, 5, 1, 2, 3]
[2, 3, 4, 5, 1]
[1, 2, 3]
[1]Hints
Hint 1: Load the list into a deque.
Hint 2: Call dq.rotate(k) -- positive rotates right, negative rotates left.
Hint 3: Return list(dq).
Implement a MovingAverage class that computes the average of the last k values in a stream. Each call to next(val) adds a value and returns the current average. Use deque(maxlen=k) to maintain the window efficiently.
Constraints:
- 1 <= k <= 10,000
- Values can be any integer or float
Solution
from collections import deque
class MovingAverage:
def __init__(self, k):
self.window = deque(maxlen=k)
self.window_sum = 0
def next(self, val):
if len(self.window) == self.window.maxlen:
self.window_sum -= self.window[0]
self.window.append(val)
self.window_sum += val
return self.window_sum / len(self.window)
# Tests
ma = MovingAverage(3)
print(ma.next(1))
print(ma.next(10))
print(ma.next(3))
print(ma.next(5))
Time: O(1) per next() call.
Space: O(k) for the deque window.
Key insight: Maintaining a running sum avoids recalculating the sum every time. When the deque is full and a new element arrives, the leftmost element is about to be evicted -- subtract it from the sum before the append.
from collections import deque
class MovingAverage:
"""
Calculate the moving average of a data stream over
the last k values.
Example:
ma = MovingAverage(3)
ma.next(1) -> 1.0 (only [1])
ma.next(10) -> 5.5 (average of [1, 10])
ma.next(3) -> 4.667 (average of [1, 10, 3])
ma.next(5) -> 6.0 (average of [10, 3, 5], 1 evicted)
"""
def __init__(self, k):
# TODO: initialize
pass
def next(self, val):
# TODO: implement — return the current moving average
passExpected Output
1.0
5.5
4.666666666666667
6.0Hints
Hint 1: Use a deque(maxlen=k) to hold the window and a running sum variable.
Hint 2: Before appending, if the window is full, subtract the element about to be evicted (window[0]).
Hint 3: Append the new value, add it to the sum, then return sum / len(window).
Implement the classic sliding window maximum algorithm using a monotonic deque. The deque stores indices in decreasing order of their corresponding values. This achieves O(n) total time because each index is pushed and popped at most once.
Constraints:
- 1 <= k <= len(nums)
- 1 <= len(nums) <= 100,000
Solution
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing by value
result = []
for i, val in enumerate(nums):
# Remove indices outside the current window
while dq and dq[0] <= i - k:
dq.popleft()
# Remove indices whose values are smaller than current
while dq and nums[dq[-1]] < val:
dq.pop()
dq.append(i)
# Record the max once the first window is complete
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Tests
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(max_sliding_window([1], 1))
print(max_sliding_window([1, 3, 1, 2, 0, 5, 3, 6], 4))
Time: O(n) -- each element enters and leaves the deque at most once. Space: O(k) for the deque.
Why this works: The deque maintains a decreasing order of values. When a new value is larger than the back of the deque, those smaller elements can never be the window maximum while the new element is in the window, so they are discarded. The front always holds the index of the current maximum.
from collections import deque
def max_sliding_window(nums, k):
"""
Given a list of integers and a window size k, return a list
of the maximum value in each sliding window of size k.
Use a monotonic deque to achieve O(n) time.
Example:
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Result: [3, 3, 5, 5, 6, 7]
"""
# TODO: implement
passExpected Output
[3, 3, 5, 5, 6, 7]
[1]
[3, 3, 3, 5, 5, 6]Hints
Hint 1: Store indices (not values) in the deque. The front always holds the index of the current window max.
Hint 2: For each new index i: remove from front any index outside the window (index <= i - k).
Hint 3: Remove from back any index whose value is less than nums[i] -- they can never be the max.
Hint 4: Append i. Once i >= k - 1, the window is full -- record nums[dq[0]] as the max.
Implement a fully functional LRU cache using collections.OrderedDict. Both get and put must run in O(1) time. This is a classic interview problem (LeetCode 146).
Constraints:
- 1 <= capacity <= 1000
- Keys and values are integers
Solution
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
# Tests
cache = LRUCache(2)
cache.put(1, 10)
cache.put(2, 20)
print(cache.get(1)) # 10 -- key 1 moved to most recent
cache.put(3, 30) # evicts key 2
print(cache.get(2)) # -1 -- evicted
print(cache.get(3)) # 30
print(cache.get(1)) # 10
Time: O(1) for both get and put. Space: O(capacity).
Why OrderedDict: move_to_end(key) is O(1) because OrderedDict maintains a doubly-linked list of keys alongside the hash table. Plain dict preserves insertion order but has no way to move an existing key to the end in O(1).
from collections import OrderedDict
class LRUCache:
"""
Implement a Least Recently Used (LRU) cache with O(1) get and put.
- get(key): return the value if it exists, otherwise -1.
Marks the key as most recently used.
- put(key, value): insert or update. If the cache exceeds
capacity, evict the least recently used key.
Example:
cache = LRUCache(2)
cache.put(1, 10)
cache.put(2, 20)
cache.get(1) -> 10 (key 1 is now most recent)
cache.put(3, 30) -> evicts key 2 (least recently used)
cache.get(2) -> -1 (evicted)
"""
def __init__(self, capacity):
# TODO: initialize
pass
def get(self, key):
# TODO: implement
pass
def put(self, key, value):
# TODO: implement
passExpected Output
10
-1
30
10Hints
Hint 1: Use an OrderedDict where the rightmost entry is the most recently used.
Hint 2: On get: if the key exists, call self.cache.move_to_end(key) to mark it as recent.
Hint 3: On put: if the key exists, move it to end. Set the value. If over capacity, call self.cache.popitem(last=False) to evict the leftmost (least recent) entry.
Build a three-layer configuration system using ChainMap. Command-line arguments override environment variables, which override defaults. Return a lookup function.
Constraints:
- All three input dicts can be empty
- Keys are strings, values can be any type
Solution
from collections import ChainMap
def build_config(defaults, env, cli):
chain = ChainMap(cli, env, defaults)
return lambda key: chain.get(key)
# Tests
defaults = {'debug': False, 'timeout': 30, 'retries': 3}
env = {'timeout': 60}
cli = {'debug': True}
get = build_config(defaults, env, cli)
print(get('debug'))
print(get('timeout'))
print(get('retries'))
print(get('missing'))
Time: O(m) per lookup where m is the number of maps in the chain (here 3 -- effectively O(1)). Space: O(1) additional -- ChainMap is a view, not a copy.
Key insight: ChainMap does not merge the dicts. It walks them in order at lookup time. This means changes to the original dicts are reflected immediately through the ChainMap -- useful when environment variables or config files can reload at runtime.
from collections import ChainMap
def build_config(defaults, env, cli):
"""
Build a layered configuration using ChainMap.
Priority: cli > env > defaults.
Return a function get_config(key) that looks up the key
through the chain, returning None if not found anywhere.
Example:
defaults = {'debug': False, 'timeout': 30, 'retries': 3}
env = {'timeout': 60}
cli = {'debug': True}
get = build_config(defaults, env, cli)
get('debug') -> True (from cli)
get('timeout') -> 60 (from env)
get('retries') -> 3 (from defaults)
get('missing') -> None
"""
# TODO: implement
passExpected Output
True
60
3
NoneHints
Hint 1: Create a ChainMap with cli as the first map, then env, then defaults.
Hint 2: Return a function (or lambda) that calls chain.get(key) -- .get() returns None for missing keys.
Build a scope chain simulator using ChainMap.new_child() and .parents. This is how Python itself resolves variable names through nested scopes.
Constraints:
pop_scope()on a single-scope chain should raise an error or be a no-op- Variable names are strings
Solution
from collections import ChainMap
class ScopeChain:
def __init__(self):
self.chain = ChainMap()
def push_scope(self):
self.chain = self.chain.new_child()
def pop_scope(self):
if self.chain.parents.maps:
self.chain = self.chain.parents
else:
raise RuntimeError("Cannot pop the global scope")
def set(self, name, value):
self.chain[name] = value # writes to the first (innermost) map
def get(self, name):
return self.chain[name] # walks the chain; raises KeyError if not found
# Tests
sc = ScopeChain()
sc.set('x', 10)
sc.push_scope()
sc.set('y', 20)
print(sc.get('x')) # 10 -- found in outer scope
print(sc.get('y')) # 20 -- found in inner scope
sc.pop_scope()
print(sc.get('x')) # 10
try:
sc.get('y')
except KeyError:
print("Caught KeyError for y")
Time: O(d) per lookup where d is the scope depth. Space: O(n) total across all scopes for n variables.
Why ChainMap here: new_child() creates a new scope layer in O(1). .parents removes it in O(1). Variable lookup automatically walks outward through all scopes. This is exactly how Python resolves names through local, enclosing, global, and builtin scopes.
from collections import ChainMap
class ScopeChain:
"""
Simulate nested variable scopes (like Python's LEGB rule).
- push_scope(): create a new inner scope
- pop_scope(): remove the innermost scope
- set(name, value): set variable in the current (innermost) scope
- get(name): look up variable, walking outward through scopes
Raise KeyError if not found in any scope.
Example:
sc = ScopeChain()
sc.set('x', 10) # global scope
sc.push_scope()
sc.set('y', 20) # inner scope
sc.get('x') -> 10 # found in outer scope
sc.get('y') -> 20 # found in inner scope
sc.pop_scope()
sc.get('x') -> 10
sc.get('y') -> KeyError
"""
def __init__(self):
# TODO: initialize
pass
def push_scope(self):
# TODO: implement
pass
def pop_scope(self):
# TODO: implement
pass
def set(self, name, value):
# TODO: implement
pass
def get(self, name):
# TODO: implement
passExpected Output
10
20
10
Caught KeyError for yHints
Hint 1: Store the chain as a ChainMap. Start with one empty dict as the global scope.
Hint 2: push_scope: self.chain = self.chain.new_child() -- adds a new empty dict at the front.
Hint 3: pop_scope: self.chain = self.chain.parents -- removes the front dict.
Hint 4: set writes to self.chain.maps[0] (the innermost scope). get uses self.chain[name].
Use typing.NamedTuple to define a Student record. Filter and sort students by GPA, then convert to dicts for JSON serialization using _asdict().
Constraints:
- 0 to 10,000 students
- GPA is a float between 0.0 and 4.0
Solution
from typing import NamedTuple, List
class Student(NamedTuple):
name: str
grade: int
gpa: float
def top_students(students: List[Student], min_gpa: float) -> List[dict]:
filtered = [s for s in students if s.gpa >= min_gpa]
filtered.sort(key=lambda s: s.gpa, reverse=True)
return [dict(s._asdict()) for s in filtered]
# Tests
students = [
Student("Alice", 12, 3.9),
Student("Bob", 11, 3.2),
Student("Carol", 12, 3.95),
Student("Dave", 10, 2.8),
]
print(top_students(students, 3.5))
print(top_students(students, 4.0))
Time: O(n log n) for sorting. Space: O(n) for the filtered list.
Why NamedTuple over dict: NamedTuples are immutable (no accidental mutation), use less memory than dicts, are hashable (can be used in sets), and provide attribute access for readable code. The _asdict() method gives you a dict when you need one for serialization.
from typing import NamedTuple, List
class Student(NamedTuple):
name: str
grade: int
gpa: float
def top_students(students: List[Student], min_gpa: float) -> List[dict]:
"""
Filter students with GPA >= min_gpa, sorted by GPA descending.
Return a list of dicts (using _asdict()) for JSON serialization.
Example:
students = [
Student("Alice", 12, 3.9),
Student("Bob", 11, 3.2),
Student("Carol", 12, 3.95),
Student("Dave", 10, 2.8),
]
top_students(students, 3.5)
-> [{'name': 'Carol', 'grade': 12, 'gpa': 3.95},
{'name': 'Alice', 'grade': 12, 'gpa': 3.9}]
"""
# TODO: implement
passExpected Output
[{'name': 'Carol', 'grade': 12, 'gpa': 3.95}, {'name': 'Alice', 'grade': 12, 'gpa': 3.9}]
[]Hints
Hint 1: Filter with a list comprehension: [s for s in students if s.gpa >= min_gpa].
Hint 2: Sort the filtered list by gpa descending: sorted(..., key=lambda s: s.gpa, reverse=True).
Hint 3: Convert each Student to a dict using s._asdict(). In Python 3.8+, _asdict returns a regular dict.
Design a key-value store where entries automatically expire after a fixed time-to-live (TTL). This combines dict-based O(1) lookup with time-based eviction -- a pattern used in DNS caches, session stores, and rate limiters.
Constraints:
- Timestamps are monotonically increasing integers
- TTL is a positive integer
- Keys are strings, values are integers
Solution
from collections import deque
class ExpiringCache:
def __init__(self, ttl):
self.ttl = ttl
self.store = {} # key -> (value, expiry_time)
self.expiry_queue = deque() # (expiry_time, key) for lazy cleanup
def _cleanup(self, current_time):
"""Remove expired entries from the front of the queue."""
while self.expiry_queue and self.expiry_queue[0][0] <= current_time:
exp_time, key = self.expiry_queue.popleft()
# Only delete if the stored expiry matches (key may have been overwritten)
if key in self.store and self.store[key][1] == exp_time:
del self.store[key]
def put(self, key, value, timestamp):
self._cleanup(timestamp)
expiry = timestamp + self.ttl
self.store[key] = (value, expiry)
self.expiry_queue.append((expiry, key))
def get(self, key, timestamp):
self._cleanup(timestamp)
if key not in self.store:
return -1
value, expiry = self.store[key]
if timestamp >= expiry:
del self.store[key]
return -1
return value
# Tests
cache = ExpiringCache(ttl=5)
cache.put("a", 100, timestamp=1)
print(cache.get("a", timestamp=3)) # 100 (expires at 6, 3 < 6)
print(cache.get("a", timestamp=5)) # 100 (expires at 6, 5 < 6)
print(cache.get("a", timestamp=7)) # -1 (expired: 7 >= 6)
cache.put("b", 200, timestamp=10)
print(cache.get("b", timestamp=14)) # 200 (expires at 15, 14 < 15)
print(cache.get("b", timestamp=15)) # -1 (expired: 15 >= 15)
Time: O(1) amortized for both get and put. Cleanup is amortized O(1) because each entry enters and leaves the deque exactly once. Space: O(n) where n is the number of non-expired entries.
Design insight: The deque serves as a lazy expiration queue. Since timestamps are monotonic, expired entries are always at the front. We clean them up on each operation, spreading the cost across calls. This is the same pattern used by Redis for key expiration.
from collections import deque, OrderedDict
class ExpiringCache:
"""
A key-value store where each entry expires after a given time.
- put(key, value, timestamp): store a key-value pair at the given time
- get(key, timestamp): return the value if the key exists AND has not
expired. Return -1 if missing or expired.
- Each entry lives for self.ttl time units from its insertion timestamp.
Example (ttl=5):
cache.put("a", 100, timestamp=1)
cache.get("a", timestamp=3) -> 100 (1+5=6 > 3, not expired)
cache.get("a", timestamp=7) -> -1 (1+5=6 < 7, expired)
"""
def __init__(self, ttl):
# TODO: initialize with a time-to-live value
pass
def put(self, key, value, timestamp):
# TODO: implement
pass
def get(self, key, timestamp):
# TODO: implement
passExpected Output
100
100
-1
200
-1Hints
Hint 1: Store entries as (value, expiry_time) in a dict. expiry_time = timestamp + ttl.
Hint 2: On get, check if the key exists and if timestamp < expiry_time.
Hint 3: Bonus: use a deque to track insertion order and lazily clean up expired entries for memory efficiency.