Menu
CoddyTech
Start learning
Learn Python step by stepOnline Python compiler

Linked List, Stack and Queue Interview Questions

Linked list pointer work, stacks and queues, heaps as priority queues, and the LRU cache.

By Kevin Spektor, Co-founder & CTO

13 questions

  1. How do you reverse a singly linked list?

    Walk with prev and curr: save curr.next, point curr.next at prev, then move both forward. When curr is None, prev is the new head. O(n) time, O(1) space.

    Python
    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 reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    return prev

print(to_list(reverse(build([1, 2, 3, 4, 5]))))

    The recursive version is shorter but uses O(n) stack, which matters on long lists.

    Practice it: Reverse Linked List

  2. How do you detect a cycle in a linked list?

    Use Floyd's tortoise and hare: slow moves one node, fast two. With a cycle they meet; if fast reaches None, there is none. O(n) time, O(1) space.

    Python
    class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

nodes = [ListNode(i) for i in range(5)]
for a, b in zip(nodes, nodes[1:]):
    a.next = b
print(has_cycle(nodes[0]))
nodes[4].next = nodes[2]   # the tail points back into the list
print(has_cycle(nodes[0]))

    Follow-up: where does the cycle start? After they meet, reset one pointer to the head and step both by one; they meet at the cycle's first node.

    Practice it: Linked List Cycle, Find the Duplicate Number

  3. How do you find the middle of a linked list in one pass?

    Move slow one step and fast two; when fast reaches the end, slow is at the middle. For an even length it returns the second middle node.

    Python
    class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.val

five = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
six = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6))))))
print(middle(five), middle(six))

    It is the first step of merge sort on a linked list.

    Practice it: Middle of the Linked List, Remove Nth Node From End of List

  4. What is the difference between singly, doubly and circular linked lists?

    A singly linked node points to the next node; a doubly linked node also points to the previous one; in a circular list the last node points back to the first. Only a doubly linked list can delete a node you hold in O(1), which is why LRU caches use one. A circular traversal must stop when it returns to the start.

    Practice it: Reverse Linked List

  5. How do you check if a string of brackets is balanced?

    Push every opening bracket; each closing bracket must match the popped top; at the end the stack must be empty. O(n) time and space.

    Python
    def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

for s in ["()[]{}", "([)]", "{[]}", "(("]:
    print(s, is_valid(s))

    Test a closer on an empty stack, a mismatch (([)]) and leftover openers ((().

    Practice it: Valid Parentheses, Generate Parentheses

  6. What is left in a Python list stack after three pushes, a pop and a push?

    Python
    stack = []
for x in [1, 2, 3]:
    stack.append(x)
stack.pop()
stack.append(4)
print(stack)

    After the loop the stack is [1, 2, 3]. pop() removes the top, 3, then 4 goes on top: [1, 2, 4]. Picking [2, 3, 4] means you treated it as a queue.

    Practice it: Baseball Game

  7. What does a Python deque hold after append, popleft and appendleft?

    Python
    from collections import deque

q = deque([1, 2, 3])
q.append(4)
q.popleft()
q.appendleft(0)
print(list(q))

    append(4) gives [1, 2, 3, 4], popleft() removes 1, and appendleft(0) puts 0 in front: [0, 2, 3, 4]. Both ends are O(1), which is why BFS uses deque.popleft() and not list.pop(0), an O(n) shift.

  8. How do you implement a queue using two stacks?

    Push onto an inbox stack and pop from an outbox stack; when the outbox is empty, move everything from the inbox onto it, reversing the order. Each item moves at most twice, so operations are amortized O(1).

    Python
    class Queue:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def push(self, x):
        self.inbox.append(x)

    def pop(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

q = Queue()
for x in [1, 2, 3]:
    q.push(x)
print(q.pop())
q.push(4)
print(q.pop(), q.pop(), q.pop())

    Moving items back to the inbox after every pop is the common wrong version, O(n) per operation.

    Practice it: Implement Queue Using Stacks

  9. How do you design a stack that returns its minimum in O(1)?

    Push each value together with the minimum of it and everything below it. The top then always holds the current minimum, and popping restores the previous one. Every operation is O(1).

    Python
    class MinStack:
    def __init__(self):
        self.items = []   # (value, minimum so far)

    def push(self, x):
        low = min(x, self.items[-1][1]) if self.items else x
        self.items.append((x, low))

    def pop(self):
        return self.items.pop()[0]

    def get_min(self):
        return self.items[-1][1]

s = MinStack()
for x in [5, 3, 7, 1]:
    s.push(x)
print(s.get_min())
s.pop()
print(s.get_min())
s.pop()
s.pop()
print(s.get_min())

    It prints 1, then 3, then 5. A leaner version keeps a second stack pushed only when the value is <= its top; with <, popping one of two equal minimums would lose the other.

    Practice it: Min Stack

  10. What is a monotonic stack, and how does it find the next greater element?

    A monotonic stack keeps its elements in order by popping anything that would break it before pushing. For next greater element, keep indexes still waiting; a bigger value answers every smaller one it pops. Each index is pushed and popped once: O(n).

    Python
    def next_greater(nums):
    result = [-1] * len(nums)
    stack = []  # indexes whose values never increase
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

print(next_greater([2, 1, 2, 4, 3]))
print(next_greater([73, 74, 75, 71, 69, 72, 76, 73]))

    The same loop solves daily temperatures and the largest rectangle in a histogram.

    Practice it: Next Greater Element I, Daily Temperatures, Largest Rectangle in Histogram

  11. What is a heap, and how do you use it as a priority queue?

    A binary heap is a complete binary tree in an array where every parent is at most its children (a min heap). The smallest item sits at index 0, push and pop are O(log n), and building one is O(n). Python's heapq is a min heap; negate values for a max heap.

    Python
    import heapq

tasks = [(3, "write tests"), (1, "fix prod bug"), (2, "review PR")]
heapq.heapify(tasks)
while tasks:
    priority, name = heapq.heappop(tasks)
    print(priority, name)

# max heap trick: push negated values
nums = [5, 1, 8, 3]
max_heap = [-x for x in nums]
heapq.heapify(max_heap)
print(-max_heap[0])

    Top k uses a min heap of size k, O(n log k). Watch heap insert and remove.

    Practice it: Kth Largest Element in an Array, Last Stone Weight, Merge k Sorted Lists

  12. What does h[0] show before and after a heappop in Python?

    Python
    import heapq

h = []
for x in [5, 1, 8, 3]:
    heapq.heappush(h, x)
print(h[0], heapq.heappop(h), h[0])

    h[0] is always the smallest item, so the first value is 1. Arguments are evaluated left to right: heappop returns 1, then h[0] is the new smallest, 3. Only index 0 is guaranteed; the rest of the list is not sorted.

  13. How would you design an LRU cache with O(1) get and put?

    Combine a hash map with a doubly linked list. The map finds a key's node in O(1); the list keeps nodes in order of use, so moving one to the front and evicting the tail are O(1). OrderedDict is that pair:

    Python
    from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)  # least recently used

cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")
cache.put("c", 3)   # evicts "b"
print(cache.get("b"), cache.get("a"), cache.get("c"))

    Expect to write the list by hand; sentinel head and tail nodes remove the None checks. See a doubly linked list.

Coddy programming languages illustration

Learn to code with Coddy

Get started