Linked Lists, Stacks, and Queues Questions
Pointer-based linear structures and the classic problems built on them: singly, doubly and circular linked lists (reversal whole, partial and in groups of k, cycle detection and cycle start with fast/slow pointers, intersection, middle and nth-from-end, merging two or k sorted lists, sorting a list, reordering, palindrome check, rotation, partitioning, duplicate removal, deep copy with random pointers, flattening child lists, sentinel nodes), implementing lists in C, C++ and Rust with attention to pointer handling, ownership and cleanup, array versus linked-list trade-offs including cache locality, stacks, queues and deques (array, linked and circular-buffer implementations, ring-buffer full versus empty, queue from two stacks, min stack, round-robin scheduling), monotonic stacks and queues (next greater element, largest rectangle in a histogram, sliding-window maximum), stack-based expression and bracket evaluation (balanced brackets, Reverse Polish Notation, infix to postfix, calculators), and structure-level builds such as an LRU cache from a hash map plus doubly linked list, undo/redo history, and variants like persistent or unrolled lists. Foundational for coding interviews and for understanding how higher-level structures are built. Concurrent and lock-free queues, memory allocators, general graph traversal, heaps and cache-eviction system design are covered elsewhere.
Design an iterator for a custom linked list that fails fast: it throws if the list is structurally modified during iteration by anything other than the iterator itself. Show how you detect the modification and what the iterator's remove does.
Sample Answer
The idea
An iterator walks a structure by holding a pointer into it. If the structure is rebuilt underneath it (a node is unlinked, one is appended), that pointer can refer to a node that is no longer in the list, and the loop silently visits stale data or skips elements. A fail-fast iterator refuses to continue instead: the next time you use it after such a change, it throws an error, so the bug shows up at the line that caused it.
The mechanism is a modification counter (Java's collections call it modCount):
- The list owns an integer that goes up by one on every structural modification, meaning a change to the number of nodes or their links (append, remove, clear), not a change to a value stored in a node.
- When an iterator is created it copies the counter into
expected. - Every
next()first comparesexpectedwith the list's current counter. If they differ, someone else changed the list: raise an error. - The iterator's own
remove()is the one allowed change, so after it unlinks a node it setsexpectedto the new counter value.
What the iterator's remove does
remove() deletes the node that the most recent next() returned, in O(1). To unlink a node in a singly linked list you need the node before it, so the iterator tracks four pointers: _cursor (the next node to return), _pred (the node just before the cursor, which is the same as the node just returned until a removal), _last (the node most recently returned, the one remove() will delete) and _last_pred (the node before _last, copied from _pred each time next() runs). _pred exists only so that next() can hand the right predecessor to _last_pred; after a removal it is reset to _last_pred so it still names the node behind the cursor. Removal does:
- check that
_lastexists (oneremove()pernext(), and not before the firstnext(); otherwise raise an illegal-state error), then that the counter still matches; - link
_last_pred(or the list head) to_last.next, and fix the tail pointer if_lastwas the tail; - bump the list counter, copy it into
expected, set_pred = _last_pred(the removed node is no longer behind the cursor), and clear_last.
Code
The iterator checks the counter before testing for the end, so a change made right after the last element is still reported. The program also contains a copy of the iterator without the check, used only to show what the check prevents.
class ConcurrentModificationError(RuntimeError):
pass
class IllegalStateError(RuntimeError):
pass
class _Node:
__slots__ = ("val", "next")
def __init__(self, val, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self, values=()):
self._head = None
self._tail = None
self._size = 0
self._mod_count = 0 # bumped by every structural change
for v in values:
self.append(v)
def __len__(self):
return self._size
def append(self, val):
node = _Node(val)
if self._tail is None:
self._head = node
else:
self._tail.next = node
self._tail = node
self._size += 1
self._mod_count += 1
def remove_value(self, val):
"""Remove the first node holding val (a structural change)."""
prev, cur = None, self._head
while cur is not None and cur.val != val:
prev, cur = cur, cur.next
if cur is None:
return False
self._unlink(prev, cur)
return True
def set_value(self, index, val):
"""Overwrite a value. Not structural, so it does not bump the counter."""
node = self._head
for _ in range(index):
node = node.next
node.val = val
def _unlink(self, prev, node):
if prev is None:
self._head = node.next
else:
prev.next = node.next
if node is self._tail:
self._tail = prev
self._size -= 1
self._mod_count += 1
def __iter__(self):
return FailFastIterator(self)
def __repr__(self):
vals, n = [], self._head
while n is not None:
vals.append(str(n.val))
n = n.next
return " -> ".join(vals + ["None"])
class FailFastIterator:
def __init__(self, lst):
self._list = lst
self._expected = lst._mod_count # snapshot taken at creation
self._cursor = lst._head # next node to return
self._pred = None # node just before the cursor
self._last = None # node most recently returned
self._last_pred = None # node just before _last
def _check(self):
if self._list._mod_count != self._expected:
raise ConcurrentModificationError(
f"list changed: iterator expected {self._expected}, list has {self._list._mod_count}")
def __iter__(self):
return self
def __next__(self):
self._check() # before the end test, so a late change is still caught
if self._cursor is None:
raise StopIteration
node = self._cursor
self._last, self._last_pred = node, self._pred
self._pred = node
self._cursor = node.next
return node.val
def remove(self):
"""Remove the node most recently returned by next()."""
if self._last is None:
raise IllegalStateError("remove() needs a preceding next(), and only one remove() per next()")
self._check()
self._list._unlink(self._last_pred, self._last)
self._expected = self._list._mod_count # the iterator's own change is allowed
self._pred = self._last_pred # the removed node is no longer before the cursor
self._last = None
class UncheckedIterator(FailFastIterator):
"""Same traversal with the modification check removed (shown only for contrast)."""
def _check(self):
pass
def attempt(label, action):
try:
print(f"{label}: {action()}")
except RuntimeError as e:
print(f"{label}: {type(e).__name__}: {e}")
def append_during_loop():
lst = LinkedList([1, 2, 3])
for v in lst:
if v == 2:
lst.append(99)
return lst
def remove_evens_through_iterator():
lst = LinkedList([1, 2, 4, 5, 6])
it = iter(lst)
for v in it:
if v % 2 == 0:
it.remove()
return lst
def two_iterators():
lst = LinkedList([1, 2, 3, 4])
a, b = iter(lst), iter(lst)
next(a)
next(a)
a.remove() # a removes 2: allowed for a
return (next(a), next(b)) # b still holds the old snapshot
def change_after_last_element():
lst = LinkedList([1, 2, 3])
it = iter(lst)
next(it); next(it); next(it)
lst.append(4) # change made after the last value was returned
return next(it)
def remove_twice():
lst = LinkedList([1, 2])
it = iter(lst)
next(it)
it.remove()
it.remove()
def remove_before_next():
return iter(LinkedList([1, 2])).remove()
def remove_after_outside_change():
lst = LinkedList([1, 2, 3])
it = iter(lst)
next(it)
lst.append(9) # a change the iterator did not make
it.remove()
def set_value_in_loop():
lst = LinkedList([1, 2, 3])
for i, v in enumerate(lst):
lst.set_value(i, v * 10) # not structural: allowed
return lst
attempt("append inside for-loop", append_during_loop)
attempt("it.remove() on evens of 1,2,4,5,6", remove_evens_through_iterator)
attempt("second iterator after the first removed", two_iterators)
attempt("append after the last next()", change_after_last_element)
attempt("remove() twice in a row", remove_twice)
attempt("remove() before any next()", remove_before_next)
attempt("remove() after an outside append", remove_after_outside_change)
attempt("set_value inside for-loop", set_value_in_loop)
print("--- trace: it.remove() on evens of 1 -> 2 -> 4 -> 5 -> 6 -> None")
lst = LinkedList([1, 2, 4, 5, 6])
it = iter(lst)
print(f"start: list = {lst}, list.mod_count={lst._mod_count}, it.expected={it._expected}")
while True:
try:
v = next(it)
except StopIteration:
print("next() -> StopIteration")
break
print(f"next() -> {v}")
if v % 2 == 0:
it.remove()
print(f" remove(): list = {lst}, list.mod_count={lst._mod_count}, it.expected={it._expected}")
print("--- why the check matters")
lst = LinkedList([2, 4, 6, 7])
visited = []
for v in UncheckedIterator(lst):
visited.append(v)
if v == 2:
lst.remove_value(4) # removes the node the iterator will return next
print(f"without the check: visited {visited}, list is now {lst}")
lst = LinkedList([2, 4, 6, 7])
visited = []
try:
for v in lst:
visited.append(v)
if v == 2:
lst.remove_value(4)
except ConcurrentModificationError:
print(f"with the check: visited {visited}, then ConcurrentModificationError")
def random_check():
import random
rng = random.Random(2024)
shapes = set()
removed_ok = changed_total = fail_fast_raised = unchecked_raised = 0
for _ in range(600):
values = [rng.randrange(10) for _ in range(rng.randrange(1, 9))]
shapes.add(tuple(values))
# (a) removal through the iterator equals filtering a Python list
lst = LinkedList(values)
it = iter(lst)
for v in it:
if v % 3 == 0:
it.remove()
model = [v for v in values if v % 3 != 0]
out, n = [], lst._head
while n is not None:
out.append(n.val)
n = n.next
assert out == model and len(lst) == len(model) and (lst._tail.val if lst._tail else None) == (model[-1] if model else None)
removed_ok += 1
# (b) an outside change after k values were returned must raise on the next call
k = rng.randrange(1, len(values) + 1)
for factory, counter in ((iter, "fast"), (UncheckedIterator, "unchecked")):
lst = LinkedList(values)
it = factory(lst)
for _ in range(k):
next(it)
if rng.random() < 0.5:
lst.append(rng.randrange(10))
else:
lst.remove_value(values[-1])
try:
next(it)
except ConcurrentModificationError:
if counter == "fast":
fail_fast_raised += 1
else:
unchecked_raised += 1
except StopIteration:
pass
changed_total += 1
print(f"{removed_ok} random lists ({len(shapes)} distinct): iterator.remove matches filtering")
print(f"{changed_total} outside changes: fail-fast raised {fail_fast_raised}, unchecked raised {unchecked_raised}")
random_check()
print("--- the same idea in Python's own dict")
d = {1: "a", 2: "b"}
try:
for key in d:
d[key + 10] = "new"
except RuntimeError as e:
print(f"RuntimeError: {e}")
Output (Python 3.12.15 in a python:3.12 container, aarch64):
append inside for-loop: ConcurrentModificationError: list changed: iterator expected 3, list has 4
it.remove() on evens of 1,2,4,5,6: 1 -> 5 -> None
second iterator after the first removed: ConcurrentModificationError: list changed: iterator expected 4, list has 5
append after the last next(): ConcurrentModificationError: list changed: iterator expected 3, list has 4
remove() twice in a row: IllegalStateError: remove() needs a preceding next(), and only one remove() per next()
remove() before any next(): IllegalStateError: remove() needs a preceding next(), and only one remove() per next()
remove() after an outside append: ConcurrentModificationError: list changed: iterator expected 3, list has 4
set_value inside for-loop: 10 -> 20 -> 30 -> None
--- trace: it.remove() on evens of 1 -> 2 -> 4 -> 5 -> 6 -> None
start: list = 1 -> 2 -> 4 -> 5 -> 6 -> None, list.mod_count=5, it.expected=5
next() -> 1
next() -> 2
remove(): list = 1 -> 4 -> 5 -> 6 -> None, list.mod_count=6, it.expected=6
next() -> 4
remove(): list = 1 -> 5 -> 6 -> None, list.mod_count=7, it.expected=7
next() -> 5
next() -> 6
remove(): list = 1 -> 5 -> None, list.mod_count=8, it.expected=8
next() -> StopIteration
--- why the check matters
without the check: visited [2, 4, 6, 7], list is now 2 -> 6 -> 7 -> None
with the check: visited [2], then ConcurrentModificationError
600 random lists (524 distinct): iterator.remove matches filtering
600 outside changes: fail-fast raised 600, unchecked raised 0
--- the same idea in Python's own dict
RuntimeError: dictionary changed size during iteration
Reading the trace
Starting with 1 -> 2 -> 4 -> 5 -> 6, building the list bumped the counter five times, so the list counter and it.expected start at 5. Reading 1 changes nothing. Reading 2 and calling remove() unlinks it: counter 6, and the iterator copies 6, so the next next() passes the check. The same happens for 4 (counter 7) and 6 (counter 8). The odd value 5 is only read. The result 1 -> 5 -> None is what filtering the even values gives.
The "why the check matters" lines show the failure it prevents. The loop removes node 4 while the iterator already holds a pointer to it; without the check the loop still visits 4, a node that is no longer in the list, and the list ends as 2 -> 6 -> 7. With the check the second next() raises.
The random check removes multiples of 3 through the iterator on 600 random lists (524 distinct) and compares the list with a filtered Python list, including the tail pointer. It then makes an outside append or remove after a random number of reads on the checked and the unchecked iterator: the checked one raised in all 600, the unchecked one in none, so the check separates the two.
Complexity
- Creating an iterator: O(1). Each
next(): O(1) with one integer comparison. A full pass is O(n) time and O(1) extra space per iterator. iterator.remove(): O(1), because the predecessor is tracked.LinkedList.remove_valueis O(n) because it must search.
Edge cases and common mistakes
- Which changes count: appends and removals bump the counter;
set_valuedoes not, which is why the last scenario succeeds. Decide this deliberately: if a value change would break your invariants, bump the counter there too. remove()runs the same counter check asnext(), so an outside change followed byit.remove()raises instead of unlinking from a stale position (the "remove() after an outside append" line).- Two iterators on the same list: when one removes, the other becomes invalid (the "second iterator" line). Only the iterator that made the change resyncs.
- The check before the end test: checking only when a next node exists would let a change slip through when it happens just before the end.
- Fail-fast is a debugging aid, not a lock. The Java documentation for
ConcurrentModificationExceptionstates that fail-fast behaviour "cannot be guaranteed" under unsynchronized concurrent modification, that it is thrown "on a best-effort basis", and that a program should not depend on it for correctness; use a lock or a concurrent collection for shared lists. Python's owndictbehaves the same way, as the last output line shows.
Running the code
python:3.12 container, standard library only
python failfast.py
Return the middle node of a singly linked list in one pass and O(1) space. For an even-length list, say which of the two middle nodes you return and why, and explain how your method lands on it.
Sample Answer
Direct answer
Use two pointers that both start at the head. slow moves one node per loop round and fast moves two. When fast can no longer move two steps, slow is standing on the middle. That is one trip over the list (a pass means one walk from the head to the end; each repetition of the loop is a round), O(n) time and O(1) extra space. For an even-length list I return the SECOND of the two middle nodes (index n // 2, counting from 0; // is whole-number division that drops any remainder, so 5 // 2 is 2 and 6 // 2 is 3), which is what the loop while fast and fast.next produces; the first middle (index (n - 1) // 2, which is 2 for 5 nodes and 2 for 6 nodes) needs a slightly earlier stop condition.
The idea in plain words
A singly linked list gives you no way to jump to position n // 2 because you do not know n and there is no index. The usual first answer is two passes over the list: count the nodes, then walk n // 2 steps. The one-pass trick is a speed difference. If one pointer moves twice as fast as the other, then at the moment the fast one reaches the end, the slow one has covered half the distance, so it is at the middle.
Why the pointers land where they do
Concretely, with the 5 nodes 1 2 3 4 5 (indexes 0 to 4): after 2 rounds slow is at index 2 and fast at index 4, the last node, so the loop stops and slow is on the 3. The general version follows. After k rounds, slow has moved k nodes (it is at index k) and fast has moved 2k nodes (index 2k).
- Odd length
n = 2k + 1: afterkroundsfastis at index2k, the last node, andfast.nextisNone. The loop stops withslowat indexk, the exact middle. - Even length
n = 2k: afterk - 1roundsfastis at index2k - 2and the last node (index2k - 1) is still after it, sofast.nextexists and the loop runs once more. AfterkroundsfastisNone(it stepped past the end) andslowis at indexk = n / 2, the second middle.
So the loop runs exactly n // 2 times and returns index n // 2.
Which middle to return for an even length, and why
I commit to the second middle (index n // 2) as the default, for two reasons: it is exactly what the simplest loop condition returns, and it equals nodes[len(nodes) // 2], the answer you would get by indexing into an array, so it is easy to explain and test. The first middle is the better choice when you need to CUT the list in half, as in merge sort of a list or a palindrome check: there slow must stop at the last node of the first half so you can set slow.next = None. The last lines of the program show it on 1 -> 2 -> 3 -> 4: cutting after the first middle gives two halves of 2 and 2, cutting after the second middle gives 3 and 1, and a palindrome check or a merge sort wants the balanced split. The code ships both. The first-middle version stops one round earlier by testing fast.next and fast.next.next instead.
Code
import random
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
def build(values):
head = None
for v in reversed(values):
head = ListNode(v, head)
return head
def to_list(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
def middle_second(head):
"""Second middle on even length (index n // 2)."""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def middle_first(head):
"""First middle on even length (index (n - 1) // 2)."""
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def show_middle(values):
"""Print slow and fast positions after each loop round, then the answer."""
head = build(values)
nodes = to_list(head)
print("list:", " -> ".join(map(str, nodes)), "-> None")
slow = fast = head
step = 0
while fast and fast.next:
slow = slow.next
fast = fast.next.next
step += 1
print(f" round {step}: slow at {slow.val}, fast at {fast.val if fast else None}")
print(f" returns {slow.val} (first middle would be {middle_first(head).val})")
show_middle([1, 2, 3, 4, 5])
show_middle([1, 2, 3, 4, 5, 6])
show_middle([7, 8])
show_middle([9])
# Why the first middle is the one to use for cutting a list in half
def cut_after(head, node):
"""Detach everything after node; return the second half."""
second, node.next = node.next, None
return second
for name, find_middle in (("first middle ", middle_first), ("second middle", middle_second)):
head = build([1, 2, 3, 4])
second = cut_after(head, find_middle(head))
print(f"cut after the {name}: {to_list(head)} and {to_list(second)}")
# Check against indexing, for every length from 1 to 40
rng = random.Random(3)
for n in range(1, 41):
values = [rng.randint(0, 99) for _ in range(n)]
head = build(values)
node = middle_second(head)
# walk from the head to find the position of the returned node
pos, cur = 0, head
while cur is not node:
cur, pos = cur.next, pos + 1
assert pos == n // 2
first = middle_first(head)
pos, cur = 0, head
while cur is not first:
cur, pos = cur.next, pos + 1
assert pos == (n - 1) // 2
print("lengths 1 to 40: second middle is index n // 2, first middle is index (n - 1) // 2")
Output:
list: 1 -> 2 -> 3 -> 4 -> 5 -> None
round 1: slow at 2, fast at 3
round 2: slow at 3, fast at 5
returns 3 (first middle would be 3)
list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
round 1: slow at 2, fast at 3
round 2: slow at 3, fast at 5
round 3: slow at 4, fast at None
returns 4 (first middle would be 3)
list: 7 -> 8 -> None
round 1: slow at 8, fast at None
returns 8 (first middle would be 7)
list: 9 -> None
returns 9 (first middle would be 9)
cut after the first middle : [1, 2] and [3, 4]
cut after the second middle: [1, 2, 3] and [4]
lengths 1 to 40: second middle is index n // 2, first middle is index (n - 1) // 2
Worked trace
Both pointers start on the head. For 1 -> 2 -> 3 -> 4 -> 5 -> None the printout shows round 1 with slow at 2 and fast at 3, round 2 with slow at 3 and fast at 5. fast.next is now None, so the loop stops and returns 3. For 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None there is a third round: slow moves to 4 and fast steps off the end to None, so the function returns 4 (the second middle) while the first-middle function returns 3. The two-node list 7 -> 8 takes one round and returns 8. The one-node list returns its only node after zero rounds. The two lines before the last show the cut. The final line is an assertion run over every length from 1 to 40, confirming the index formulas.
Complexity
- Time O(n):
fastvisits about every node once; the loop runsn // 2rounds. - Space O(1): two pointers, no recursion and no array.
Edge cases
- Empty list:
middle_second(None)returnsNone(the loop testfast and fast.nextis false at once).middle_first(None)would raiseAttributeErrorbecause it readsfast.next; guard withif head is None: return Nonewhen empty input is possible. - One node: both functions return it.
- Two nodes: second middle is the tail node, first middle is the head.
- Very long lists: the code is iterative, so Python's recursion limit (1000 frames by default) is not involved.
Common mistakes
- Writing
while fast.next and fast.next.nextand expecting the second middle: that returns the first middle for even lengths. - Writing
while fast.next:withfast = fast.next.next: on an even-length listfastbecomesNone, and the next test readsNone.next, which raisesAttributeError. The shipped conditions checkfastbefore readingfast.next. - Counting first, then walking: correct, but two passes over the list and it does not meet a "one pass" requirement.
Running the code
python middle_node.py
Python 3.12, standard library only.
Implement an LRU cache with a fixed capacity and O(1) get and put, without using a built-in ordered or LRU map. Explain which structures you combine and why one alone is not enough, and show how eviction and a get both update recency.
Sample Answer
The idea in plain words
An LRU cache (least recently used) holds at most capacity key-value pairs. When a new key arrives and the cache is full, it throws away the entry that has gone longest without being read or written. Both get(key) and put(key, value) must run in O(1).
No single structure gives both halves of that requirement:
- A hash map (Python
dict) finds a key in O(1) but has no notion of "how recently used". Finding the oldest entry would take a scan, O(n). - A list or array ordered by recency knows the oldest entry, but finding a key in it is O(n), and moving a hit to the front shifts elements.
So combine them. The map goes from each key to its node in a doubly linked list (each node points to both its neighbour toward the front and its neighbour toward the back) that is ordered from most to least recently used. The map gives O(1) access to a node. The list lets you cut a node out of the middle and re-insert it at the front in O(1), because a doubly linked node knows its own predecessor. In a singly linked list you would need to walk to find the predecessor, which is O(n). The least recently used entry is always at the back end, so eviction is also O(1).
Approach, step by step
- State:
nodes(the map), afrontsentinel and abacksentinel. A sentinel is a dummy node that never holds data; with one at each end, every real node always has aprevandnext, so inserting and removing never needs an "is this the first or last node?" branch. get(key): if the key is missing, return -1. Otherwise unlink the node and push it to the front (it is now the most recently used), and return its value. A read changes recency.put(key, value)for an existing key: update the value and move the node to the front.putfor a new key when the cache is full: take the node just before thebacksentinel (the least recently used), unlink it, and delete its key from the map. This is why each node stores its own key: the list node must be able to say which dictionary entry to delete. Then create the new node, add it to the map and push it to the front.- Every operation is a fixed number of pointer updates and dictionary operations.
The code
import random
from collections import OrderedDict # used only as a test reference, never by the cache itself
class Node:
def __init__(self, key=None, value=None):
self.key = key # kept so eviction can delete the dictionary entry
self.value = value
self.prev = None
self.next = None
self.expires_at = None # used only by the ExpiringCache extension
self.weight = 1 # used only by the ExpiringCache extension
class LRUCache:
def __init__(self, capacity):
if capacity < 1:
raise ValueError("capacity must be at least 1")
self.capacity = capacity
self.nodes = {} # key -> node, O(1) lookup
self.front = Node() # sentinel before the most recently used node
self.back = Node() # sentinel after the least recently used node
self.front.next, self.back.prev = self.back, self.front
def _unlink(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node):
node.prev, node.next = self.front, self.front.next
self.front.next.prev = node
self.front.next = node
def _remove(self, node):
self._unlink(node)
del self.nodes[node.key]
def get(self, key):
node = self.nodes.get(key)
if node is None:
return -1
self._unlink(node) # a hit makes the key most recently used
self._push_front(node)
return node.value
def put(self, key, value):
node = self.nodes.get(key)
if node is not None: # update in place and refresh recency
node.value = value
self._unlink(node)
self._push_front(node)
return
if len(self.nodes) == self.capacity: # full: evict the least recently used
self._remove(self.back.prev)
node = Node(key, value)
self.nodes[key] = node
self._push_front(node)
def order(self):
"""Keys from most to least recently used; also checks that prev and next agree."""
limit = len(self.nodes) # a healthy walk never takes more steps than there are keys
forward, node = [], self.front.next
while node is not self.back:
forward.append(node.key)
assert len(forward) <= limit, "forward walk never reaches the back sentinel"
node = node.next
backward, node = [], self.back.prev
while node is not self.front:
backward.append(node.key)
assert len(backward) <= limit, "backward walk never reaches the front sentinel"
node = node.prev
assert forward == backward[::-1] and len(forward) == len(self.nodes), "next and prev pointers disagree"
return forward
class ExpiringCache(LRUCache):
"""Capacity is a total weight budget (for example bytes). Each entry may also carry a time to live."""
def __init__(self, max_weight, clock):
super().__init__(max_weight)
self.clock = clock
self.total_weight = 0
def _remove(self, node):
super()._remove(node)
self.total_weight -= node.weight
def get(self, key):
node = self.nodes.get(key)
if node is None:
return -1
if node.expires_at is not None and self.clock() >= node.expires_at:
self._remove(node) # lazy expiry: only noticed when the key is read
return -1
self._unlink(node)
self._push_front(node)
return node.value
def put(self, key, value, weight=1, ttl=None):
if weight > self.capacity:
raise ValueError("entry is heavier than the whole cache")
if key in self.nodes:
self._remove(self.nodes[key])
node = Node(key, value)
node.weight = weight
node.expires_at = None if ttl is None else self.clock() + ttl
while self.total_weight + weight > self.capacity:
self._remove(self.back.prev) # evict from the cold end until the new entry fits
self.nodes[key] = node
self.total_weight += weight
self._push_front(node)
def demo():
cache = LRUCache(3)
steps = [("put", "a", 1), ("put", "b", 2), ("put", "c", 3), ("get", "a", None),
("put", "d", 4), ("get", "b", None), ("put", "c", 30), ("put", "e", 5), ("get", "a", None)]
print(f"{'operation':<12}{'result':<8}order, most recent first")
for op, key, value in steps:
if op == "put":
cache.put(key, value)
label, result = f"put({key},{value})", ""
else:
label, result = f"get({key})", cache.get(key)
print(f"{label:<12}{str(result):<8}{cache.order()}")
now = [0]
big = ExpiringCache(max_weight=10, clock=lambda: now[0])
big.put("x", "page-x", weight=4, ttl=5)
big.put("y", "page-y", weight=4)
print("weights 4+4:", big.order(), "total", big.total_weight)
big.put("z", "page-z", weight=4) # 12 > 10, so the coldest entry (x) goes
print("put z (weight 4):", big.order(), "total", big.total_weight)
big.put("w", "page-w", weight=2, ttl=5)
print("put w (weight 2, ttl 5):", big.order(), "total", big.total_weight)
now[0] = 5
print("clock=5, get(w) ->", big.get("w"), "| order", big.order(), "total", big.total_weight)
for label, fix_next, fix_prev in (("next pointers only", True, False), ("prev pointers only", False, True)):
broken = LRUCache(3)
for key in "abc":
broken.put(key, 0)
node = broken.nodes["b"]
if fix_next:
node.prev.next = node.next
if fix_prev:
node.next.prev = node.prev
broken._push_front(node) # then move the node to the front, as get("b") would
try:
broken.order()
except AssertionError as error:
print(f"half unlink, {label}: order() raises AssertionError: {error}")
def random_check():
rng = random.Random(24)
seen_hit = seen_miss = seen_evict = 0
for _ in range(500):
capacity = rng.randint(1, 5)
cache, ref = LRUCache(capacity), OrderedDict()
for _ in range(100):
key = rng.randint(0, 7)
if rng.random() < 0.5:
expected = -1
if key in ref:
ref.move_to_end(key, last=False) # front of the ordered dict = most recent
expected = ref[key]
got = cache.get(key)
assert got == expected
seen_hit += got != -1
seen_miss += got == -1
else:
value = rng.randint(0, 99)
if key not in ref and len(ref) == capacity:
ref.popitem(last=True) # drop the least recently used
seen_evict += 1
ref[key] = value
ref.move_to_end(key, last=False)
cache.put(key, value)
assert cache.order() == list(ref)
assert seen_hit and seen_miss and seen_evict
print("500 random runs match an OrderedDict reference (hits, misses and evictions all occurred)")
if __name__ == "__main__":
demo()
random_check()
Run, it prints:
operation result order, most recent first
put(a,1) ['a']
put(b,2) ['b', 'a']
put(c,3) ['c', 'b', 'a']
get(a) 1 ['a', 'c', 'b']
put(d,4) ['d', 'a', 'c']
get(b) -1 ['d', 'a', 'c']
put(c,30) ['c', 'd', 'a']
put(e,5) ['e', 'c', 'd']
get(a) -1 ['e', 'c', 'd']
weights 4+4: ['y', 'x'] total 8
put z (weight 4): ['z', 'y'] total 8
put w (weight 2, ttl 5): ['w', 'z', 'y'] total 10
clock=5, get(w) -> -1 | order ['z', 'y'] total 8
half unlink, next pointers only: order() raises AssertionError: next and prev pointers disagree
half unlink, prev pointers only: order() raises AssertionError: forward walk never reaches the back sentinel
500 random runs match an OrderedDict reference (hits, misses and evictions all occurred)
Worked trace
Capacity 3. The right-hand column is the list from most to least recently used.
- The three
putcalls build['c', 'b', 'a']:ais the oldest. get(a)returns 1 and movesato the front:['a', 'c', 'b']. Nowbis the oldest.put(d,4)finds the cache full, evicts the back nodeb, and addsd:['d', 'a', 'c'].get(b)is a miss (-1); nothing changes.put(c,30)updates an existing key: no eviction, andcmoves to the front:['c', 'd', 'a'].put(e,5)evicts the back nodea, giving['e', 'c', 'd'], so the finalget(a)is -1. Readingaearlier saved it from eviction exactly once; it was not protected forever.
Walking through the pointer updates
_unlink and _push_front are the lines that trip people up, so here is one move done one assignment at a time. The cache holds a, b, c (most recent first) and get(b) must move b to the front. Each node has two pointers, prev (toward the front) and next (toward the back). The one-line form x, y = p, q evaluates both right-hand sides first and only then assigns, left to right. In _unlink, b's own pointers are not changed by the two assignments, so the order does not matter there. The program below writes every step as a separate statement and prints every node's two pointers after each one.
class Node:
def __init__(self, label):
self.label = label
self.prev = None
self.next = None
front, back = Node("front"), Node("back")
a, b, c = Node("a"), Node("b"), Node("c")
chain = [front, a, b, c, back]
for left, right in zip(chain, chain[1:]):
left.next, right.prev = right, left
nodes = [front, a, b, c, back]
def show(step):
print(step)
cells = []
for n in nodes:
prev = n.prev.label if n.prev else "-"
nxt = n.next.label if n.next else "-"
cells.append(f"{n.label}[prev={prev} next={nxt}]")
print(" ", " ".join(cells))
def walk():
out, n = [], front.next
while n is not back and len(out) < 6:
out.append(n.label)
n = n.next
return out
show("start: front, a, b, c, back")
node = b
node.prev.next = node.next
show("unlink 1: b.prev.next = b.next (a.next skips b)")
node.next.prev = node.prev
show("unlink 2: b.next.prev = b.prev (c.prev skips b)")
print("walk after unlink:", walk())
node.prev = front
show("push 1: b.prev = front")
node.next = front.next
show("push 2: b.next = front.next (b.next = a)")
front.next.prev = node
show("push 3: front.next.prev = b (a.prev = b)")
front.next = node
show("push 4: front.next = b")
print("walk after push:", walk())
print()
print("Wrong order: setting front.next before front.next.prev")
for left, right in zip(chain, chain[1:]):
left.next, right.prev = right, left
node = b
node.prev.next, node.next.prev = node.next, node.prev
node.prev, node.next = front, front.next
front.next = node
front.next.prev = node
print("b.prev =", b.prev.label, "| b.next =", b.next.label, "| a.prev =", a.prev.label)
print("forward walk:", walk())
Run, it prints:
start: front, a, b, c, back
front[prev=- next=a] a[prev=front next=b] b[prev=a next=c] c[prev=b next=back] back[prev=c next=-]
unlink 1: b.prev.next = b.next (a.next skips b)
front[prev=- next=a] a[prev=front next=c] b[prev=a next=c] c[prev=b next=back] back[prev=c next=-]
unlink 2: b.next.prev = b.prev (c.prev skips b)
front[prev=- next=a] a[prev=front next=c] b[prev=a next=c] c[prev=a next=back] back[prev=c next=-]
walk after unlink: ['a', 'c']
push 1: b.prev = front
front[prev=- next=a] a[prev=front next=c] b[prev=front next=c] c[prev=a next=back] back[prev=c next=-]
push 2: b.next = front.next (b.next = a)
front[prev=- next=a] a[prev=front next=c] b[prev=front next=a] c[prev=a next=back] back[prev=c next=-]
push 3: front.next.prev = b (a.prev = b)
front[prev=- next=a] a[prev=b next=c] b[prev=front next=a] c[prev=a next=back] back[prev=c next=-]
push 4: front.next = b
front[prev=- next=b] a[prev=b next=c] b[prev=front next=a] c[prev=a next=back] back[prev=c next=-]
walk after push: ['b', 'a', 'c']
Wrong order: setting front.next before front.next.prev
b.prev = b | b.next = a | a.prev = front
forward walk: ['b', 'a', 'c']
Read it like this. After the two unlink steps nothing points at b from a or c, so the forward walk is ['a', 'c']; b still remembers its old neighbours, which is harmless because the next four steps overwrite them. In the push steps, front.next.prev = b must run before front.next = b: once front.next has been changed to b, the expression front.next means b itself. The wrong-order run shows the result: b.prev points at b, and a.prev still points at front instead of b. The forward walk still looks correct, which is why the bug hides until something walks backward; the order() helper in the main program checks both directions for exactly this reason.
Complexity
get and put are O(1) time: one dictionary operation and a fixed number of pointer assignments, with no loops. Space is O(capacity) for the nodes plus the map. (order() is a debugging helper that walks the list and is O(n); it is not part of the cache's operations.) Dictionary lookups are O(1) on average, not worst case, because two different keys can land in the same hash slot (a hash collision) and then need extra comparisons; interviewers accept that.
Edge cases and common mistakes
- Capacity 1: every new key evicts the previous one. The sentinels make this work without a special case.
putof an existing key must not evict, and it must refresh recency. Forgetting the refresh makes updated keys look old.- Forgetting that
getmust also move the node to the front. This is the most common bug: reads stop protecting an entry, so the cache evicts by the order of the last put (plain FIFO, first in first out, when no key is ever updated) instead of by recency of use. - Forgetting to delete the evicted key from the dictionary, which leaves a stale entry that points at an unlinked node.
- Updating
prevpointers but notnextpointers, or the reverse. Theorder()helper walks both directions, stops with an assertion if a walk does not end withinlen(self.nodes)steps, and asserts that the two directions agree; the run above shows both half-updates being caught, and the random test calls it after every operation. - Storing the value
-1and being unable to tell a hit from a miss; return a distinct sentinel orNoneif values can be -1.
Per-entry expiry and size-based eviction
A typical interview asks for the plain LRU above; entry expiry, size-based eviction and thread safety are the deeper follow-ups that come after it. Two extensions reuse the same list and map. The ExpiringCache class in the program shows both.
- Size-based eviction. Give each entry a weight (bytes, say) and treat
capacityas a total budget. Onput, evict from the cold end in a loop untiltotal_weight + weightfits. In the output the budget is 10: afterxandy(weight 4 each),z(weight 4) needs 12, sox, the coldest entry, is evicted and the total stays 8. - Per-entry TTL (time to live). Store
expires_at = now + ttlon the node.getcompares the clock withexpires_atand, if the entry has expired, removes it and reports a miss. This is lazy expiry: an expired entry that nobody reads still occupies space until eviction pushes it out, so a production cache adds a periodic sweep or checks the cold end on eachput. The clock is passed in as a function so the demo is deterministic: at clock 5,w(ttl 5) is gone and the weight total falls from 10 to 8.
Thread safety
A read reorders the list, so even get is a write. In Python, one thread can be switched out between the individual steps of the relinking, so two threads can leave the list half-updated. The simple correct fix is one lock held for the whole body of get and put. Sharded locks (splitting the keys across several independent caches, each with its own lock, so threads rarely wait on each other) and lock-free designs (updating shared data with atomic hardware operations instead of locks) trade complexity for throughput and belong to concurrency design. Interviews usually stop at naming the single lock.
Running the code
python lru_cache.py
python pointer_trace.py
Python 3.12, standard library only (pointer_trace.py is the pointer walk-through program). The main program imports OrderedDict only to check the cache against a reference; the cache itself uses a dict and its own doubly linked list.
Evaluate a Reverse Polish Notation expression given as a list of tokens, supporting integers and + - * /. For example ['2','1','+','3','*'] gives 9. Specify how division should truncate and how you handle malformed input.
Sample Answer
The idea in plain words
Reverse Polish Notation (RPN), also called postfix, writes the operator after its two operands: 2 1 + means 2 + 1. Its advantage is that it needs no parentheses and no precedence rules, because the order of the tokens already says what to compute first. A stack (last-in, first-out) evaluates it in one left-to-right pass: a number is pushed; an operator pops the two newest values, computes, and pushes the result back. When the tokens run out, the stack holds exactly one value, the answer.
The detail interviewers watch is operand order. The value popped first is the right operand and the one popped second is the left one. For - and / this matters: 5 2 - is 3, not -3.
The decisions the question asks you to state
- Division truncates toward zero.
-7 / 2is-3. This matches C, C++ and Java integer division (the Java run below confirms it). Python's//is different: it floors (rounds toward minus infinity), so-7 // 2is-4. The code therefore divides absolute values and fixes the sign. - Do not use
int(a / b)for this./produces a float, and floats carry only 53 bits of integer precision (see the explanation below), so large values are silently wrong; the output shows2**53 + 1coming back as...992. - Division by zero is reported as an error rather than crashing with an obscure message.
- Malformed input is reported with a clear error: an operator when fewer than two values are on the stack (
+alone), a token that is neither an integer nor an operator (x), and a finished expression that leaves anything other than exactly one value (1 2, or the empty list). - Negative numbers.
'-7'is a number and'-'is the operator. Testing "is the token in the operator set" first and parsing everything else withintdistinguishes them; testingtoken[0] == '-'would not.
The code
import random
from fractions import Fraction
from math import trunc
OPERATORS = {"+", "-", "*", "/"}
def divide_truncating(a, b):
"""Integer division that rounds toward zero (like C, C++ and Java), not toward minus infinity."""
if b == 0:
raise ZeroDivisionError("division by zero")
quotient = abs(a) // abs(b)
return quotient if (a < 0) == (b < 0) else -quotient
def eval_rpn(tokens, trace=False):
stack = []
for token in tokens:
if token in OPERATORS:
if len(stack) < 2:
raise ValueError(f"operator {token!r} needs two operands, stack has {len(stack)}")
right = stack.pop() # the operand that was pushed last is on the right
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
stack.append(divide_truncating(left, right))
else:
try:
stack.append(int(token)) # accepts '-3' as a number, '-' alone is the operator
except ValueError:
raise ValueError(f"bad token {token!r}") from None
if trace:
print(f" token {token!r:>6}: stack={stack}")
if len(stack) != 1:
raise ValueError(f"expression left {len(stack)} values on the stack")
return stack[0]
def demo():
for tokens in (["2", "1", "+", "3", "*"], ["4", "13", "5", "/", "+"], ["-7", "2", "/"]):
print(tokens)
print(" ->", eval_rpn(tokens, trace=True))
print("floor vs truncate for -7 / 2:", -7 // 2, "vs", divide_truncating(-7, 2))
print("int(a / b) with a = 2**53 + 1, b = 1:", int((2**53 + 1) / 1), "vs", divide_truncating(2**53 + 1, 1))
for bad in (["+"], ["1", "2"], ["1", "0", "/"], ["1", "x", "+"], []):
try:
eval_rpn(bad)
except (ValueError, ZeroDivisionError) as error:
print(f"{bad!r:<16} -> {type(error).__name__}: {error}")
def random_expression(rng, depth):
"""Return (tokens, value) built from a random expression tree, using exact Fractions."""
if depth == 0 or rng.random() < 0.3:
n = rng.randint(-9, 9)
return [str(n)], n
lt, lv = random_expression(rng, depth - 1)
rt, rv = random_expression(rng, depth - 1)
op = rng.choice("+-*/")
if lv is None or rv is None:
v = None # a division by zero inside a subtree poisons the whole expression
elif op == "+":
v = lv + rv
elif op == "-":
v = lv - rv
elif op == "*":
v = lv * rv
else:
v = None if rv == 0 else trunc(Fraction(lv, rv))
return lt + rt + [op], v
def random_check():
rng = random.Random(5)
ok = errors = 0
for _ in range(3000):
tokens, expected = random_expression(rng, 4)
if expected is None:
try:
eval_rpn(tokens)
except ZeroDivisionError:
errors += 1
continue
assert eval_rpn(tokens) == expected
ok += 1
print(f"{ok} valid expressions match an exact-Fraction reference; {errors} zero-division cases raised")
if __name__ == "__main__":
demo()
random_check()
Run, it prints:
['2', '1', '+', '3', '*']
token '2': stack=[2]
token '1': stack=[2, 1]
token '+': stack=[3]
token '3': stack=[3, 3]
token '*': stack=[9]
-> 9
['4', '13', '5', '/', '+']
token '4': stack=[4]
token '13': stack=[4, 13]
token '5': stack=[4, 13, 5]
token '/': stack=[4, 2]
token '+': stack=[6]
-> 6
['-7', '2', '/']
token '-7': stack=[-7]
token '2': stack=[-7, 2]
token '/': stack=[-3]
-> -3
floor vs truncate for -7 / 2: -4 vs -3
int(a / b) with a = 2**53 + 1, b = 1: 9007199254740992 vs 9007199254740993
['+'] -> ValueError: operator '+' needs two operands, stack has 0
['1', '2'] -> ValueError: expression left 2 values on the stack
['1', '0', '/'] -> ZeroDivisionError: division by zero
['1', 'x', '+'] -> ValueError: bad token 'x'
[] -> ValueError: expression left 0 values on the stack
2652 valid expressions match an exact-Fraction reference; 348 zero-division cases raised
Worked trace
For ['2', '1', '+', '3', '*'], which is (2 + 1) * 3:
2and1are pushed: stack[2, 1].+pops 1 (right) and 2 (left), pushes 3: stack[3].3is pushed: stack[3, 3].*pops 3 and 3, pushes 9: stack[9]. One value is left, so the answer is 9.
For ['4', '13', '5', '/', '+'], the / pops 5 (right) and 13 (left), computes 13 / 5 = 2 (truncated), pushes it, and + gives 4 + 2 = 6. For ['-7', '2', '/'] the result is -3, where Python's // would give -4.
The same rule in Java
Java's / on integers truncates toward zero and Math.floorDiv floors, so a Java version uses / directly.
public class TruncDemo {
public static void main(String[] args) {
System.out.println("-7 / 2 = " + (-7 / 2));
System.out.println("-7 % 2 = " + (-7 % 2));
System.out.println("Math.floorDiv(-7, 2) = " + Math.floorDiv(-7, 2));
}
}
Compiled and run on OpenJDK 21 (the Docker image eclipse-temurin:21-jdk), it prints:
-7 / 2 = -3
-7 % 2 = -1
Math.floorDiv(-7, 2) = -4
The % result -1 follows the same truncating rule: (-7 / 2) * 2 + (-7 % 2) is -6 + -1 = -7.
Why floats and fixed-width integers break
Three of the decisions above rest on number facts, and the program below prints each one.
# 1. A float stores 53 significant binary digits, so integers above 2**53 get gaps.
limit = 2**53
print("2**53 =", limit)
for n in (limit + 1, limit + 2, limit + 3):
print(f"int(float({n})) = {int(float(n))}")
print("every integer from 2**53 - 5 up to 2**53 survives the round trip:",
all(int(float(n)) == n for n in range(limit - 5, limit + 1)))
# 2. Floor and truncate are two ways to keep a == q * b + r. They differ in the sign of r.
a, b = -7, 2
q_floor, r_floor = divmod(a, b)
q_trunc = int(a / b)
r_trunc = a - q_trunc * b
print(f"floor: {a} = {q_floor} * {b} + {r_floor}")
print(f"truncate: {a} = {q_trunc} * {b} + {r_trunc}")
# 3. A signed 32-bit integer holds -2**31 .. 2**31 - 1, so -2**31 / -1 does not fit.
lowest, highest = -2**31, 2**31 - 1
result = lowest // -1
print(f"32-bit range: {lowest} to {highest}")
print(f"{lowest} / -1 = {result}, fits in 32 bits: {lowest <= result <= highest}")
2**53 = 9007199254740992
int(float(9007199254740993)) = 9007199254740992
int(float(9007199254740994)) = 9007199254740994
int(float(9007199254740995)) = 9007199254740996
every integer from 2**53 - 5 up to 2**53 survives the round trip: True
floor: -7 = -4 * 2 + 1
truncate: -7 = -3 * 2 + -1
32-bit range: -2147483648 to 2147483647
-2147483648 / -1 = 2147483648, fits in 32 bits: False
- 53 bits. A 64-bit float keeps 53 binary digits of precision for the number itself. Up to
2**53every integer fits exactly. Above it the spacing between storable numbers becomes 2, so2**53 + 1has no slot of its own and rounds to2**53, and2**53 + 3rounds to...996. That is whyint(a / b)returns a wrong integer for big operands even though it looks fine on small ones. - Floor versus truncate. Both rules satisfy
a == q * b + r, so a language must pick one. Truncating toward zero (C, C++, Java) gives-7 = -3 * 2 + -1, so the remainder takes the sign of the dividend. Flooring (Python's//anddivmod) gives-7 = -4 * 2 + 1, so the remainder takes the sign of the divisor. The question asks you to state which one you implement, and the code above implements truncation. - 32-bit overflow. A signed 32-bit integer holds
-2147483648to2147483647, one more negative value than positive ones. Dividing the lowest value by-1should give2147483648, which is one past the top of the range, so the result cannot be stored. Python integers grow as needed and never hit this; in Java or C the result must be handled on purpose.
Complexity
Time O(n) for n tokens: each token is handled once, with O(1) stack work and one int parse. Space O(n) in the worst case, when all the numbers come before any operator, as in 1 2 3 4 + + +, where the stack peaks at 4 values. Python integers have arbitrary precision, so there is no overflow; in Java or C a 32-bit result needs an explicit overflow decision (for example -2147483648 / -1 overflows int).
Edge cases and common mistakes
- Swapping the operand order for
-and/. - Using floor division for negative results (
-4instead of-3). - Parsing with
floatorint(a / b)and losing precision on large values. - Treating the token
'-'as the start of a negative number, or'-3'as an operator. - Not checking that exactly one value remains.
1 2finishes without any error from the loop, but it is not a valid expression. - Letting
ZeroDivisionErroror anIndexErrorfrom an emptypopescape without a message.
Running the code
python rpn.py # Python 3.12
python number_limits.py # the float, floor and 32-bit facts
javac TruncDemo.java && java TruncDemo # JDK 21, file saved as TruncDemo.java
Standard library only.
A non-negative integer is stored in a singly linked list with the most significant digit at the head. Add one to it and return the new head, without converting the list to a number.
Sample Answer
The idea
Adding one to a decimal number on paper starts at the last digit. A digit below 9 just goes up by one and the work stops. A 9 becomes 0 and passes a carry (a 1 handed to the next digit on the left) along. So the carry travels left over a run of trailing 9s and stops at the first digit that is not 9. That digit goes up by one, and every digit to its right (all 9s) becomes 0.
The trouble is that a singly linked list only moves left to right, and the most significant digit is at the head. The fix: in one left-to-right pass, remember the rightmost node that is not 9. That is the node that absorbs the carry. If every digit is 9 (as in 999), there is no such node, so you put a spare leading 0 (a sentinel: a dummy node added to remove a special case) in front, and that 0 becomes the 1 of 1000.
The brute force and the other standard approaches
- Convert to an integer, add 1, convert back. The question forbids it; it also needs the digits in memory twice, and in a fixed-width language the number can overflow.
- Reverse, add with carry, reverse back. Correct, O(n) time and O(1) space, but it rewrites all the pointers twice and temporarily breaks the list.
- Recursion that adds 1 on the way back out of the deepest call. Clean, but it uses O(n) stack, and CPython stops at 1000 nested calls by default, so a list longer than about that fails with
RecursionError. - Stack of nodes pushed during the walk, popped to propagate the carry: O(n) extra space.
The rightmost-non-9 method needs no reversal, no stack and no recursion.
Approach
- Create a sentinel node holding 0 that points at the head. Set
rightmost_non_nineto the sentinel. - Walk the list once. Every time a node's digit is not 9, record it as
rightmost_non_nine. - Add 1 to that node's digit.
- Set every node after it to 0 (they were all 9s).
- If the sentinel became 1, return it as the new head; otherwise return the original head.
Code
import random
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
def build(digits):
head = None
for d in reversed(digits):
head = Node(d, head)
return head
def to_digits(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
def show(head):
return " -> ".join(map(str, to_digits(head) + ["None"]))
def plus_one(head, trace=False):
sentinel = Node(0, head) # a spare leading 0 absorbs a carry out of the top digit
rightmost_non_nine = sentinel
node = head
while node:
if node.val != 9:
rightmost_non_nine = node
node = node.next
if trace:
print(f" rightmost non-9 node holds {rightmost_non_nine.val}")
rightmost_non_nine.val += 1 # this digit absorbs the carry
node = rightmost_non_nine.next
while node: # every digit after it was a 9 and becomes 0
node.val = 0
node = node.next
return sentinel if sentinel.val else head # keep the sentinel only if it became 1
for digits in ([1, 2, 3], [1, 2, 9, 9], [9, 9, 9], [0], [4, 9, 8]):
head = build(digits)
print(f"{digits}:")
print(" before:", show(head))
result = plus_one(head, trace=True)
print(" after: ", show(result))
rng = random.Random(68)
for trial in range(2000):
n = rng.randint(1, 8)
digits = [rng.choice([0, 9, 9, 1, 5]) for _ in range(n)] # lots of 9s on purpose
if digits[0] == 0 and n > 1:
digits[0] = 3
expected = [int(c) for c in str(int("".join(map(str, digits))) + 1)]
assert to_digits(plus_one(build(digits))) == expected, digits
print("2000 random digit lists match int arithmetic")
Output:
[1, 2, 3]:
before: 1 -> 2 -> 3 -> None
rightmost non-9 node holds 3
after: 1 -> 2 -> 4 -> None
[1, 2, 9, 9]:
before: 1 -> 2 -> 9 -> 9 -> None
rightmost non-9 node holds 2
after: 1 -> 3 -> 0 -> 0 -> None
[9, 9, 9]:
before: 9 -> 9 -> 9 -> None
rightmost non-9 node holds 0
after: 1 -> 0 -> 0 -> 0 -> None
[0]:
before: 0 -> None
rightmost non-9 node holds 0
after: 1 -> None
[4, 9, 8]:
before: 4 -> 9 -> 8 -> None
rightmost non-9 node holds 8
after: 4 -> 9 -> 9 -> None
2000 random digit lists match int arithmetic
Worked trace
On 1 -> 2 -> 9 -> 9 the walk sees 1, 2, 9, 9 and the last non-9 it saw was the node holding 2. That node becomes 3; the two nodes after it become 0:
before: 1 -> 2 -> 9 -> 9 -> None
^ rightmost non-9
after: 1 -> 3 -> 0 -> 0 -> None
On 9 -> 9 -> 9 no node is a non-9, so rightmost_non_nine stays on the sentinel (printed as holding 0). The sentinel becomes 1, the three 9s become 0, and the sentinel is returned: 1 -> 0 -> 0 -> 0 -> None. On 4 -> 9 -> 8 the last digit 8 is not 9, so it becomes 9 and nothing after it changes: 4 -> 9 -> 9 -> None.
The last lines of the output show that the method matches ordinary integer arithmetic on 2000 seeded random digit lists (about two in five digits are 9, so long runs of 9s are common). Integer conversion appears only in that test, as the reference; the solution never converts.
Complexity
One pass to find the node and a second walk over only the trailing 9s: O(n) time for n nodes. Extra space is a sentinel node and two pointers, O(1). It changes digits in place and allocates at most the one sentinel node, and nothing recurses.
Edge cases and common mistakes
- All 9s (
999): needs the new leading node. Forgetting it gives000. - A single 0 (
0): the digit is not 9, so it becomes 1. - A 9 in the middle (
1 -> 9 -> 8): the answer is1 -> 9 -> 9. Tracking "the last node that is less than 9" and bumping it is right; tracking "the last 9" is not. - Resetting too much: only the nodes after the bumped one are zeroed. Zeroing from the head loses digits.
- Leading zeros in the input are not expected (the number is non-negative and written normally), so
0is the only list whose head digit is 0.
Follow-ups
Adding an arbitrary number k (not just 1) needs real carry propagation, so reverse both lists or use stacks. Adding two such numbers is the same idea; if the lists are stored least significant digit first, the problem becomes a single forward walk with a carry variable.
Running the code
Save as plus_one_list.py, then run: python plus_one_list.py
Needs Python 3.12 and the standard library only.
Unlock Full Question Bank
Get access to all Linked Lists, Stacks, and Queues interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.