Data Structures & Algorithms Interview Questions and Answers

Iterative (O(n) time, O(1) space):

def reverse(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt
    return prev

Recursive (O(n) time, O(n) stack space):

def reverse(head):
    if not head or not head.next:
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

Follow-ups: reverse a sublist between positions m and n, reverse in groups of k, and detect a cycle with Floyd's tortoise and hare.

• BFS explores level by level using a queue. It finds the shortest path in an unweighted graph, and is used for social-degree separation, maze shortest paths and level-order tree traversal. Space can be O(width) of the graph.
• DFS explores as deep as possible using a stack or recursion. It is used for cycle detection, topological sort, connected components, backtracking and path existence. Space is O(depth).

from collections import deque

def bfs(graph, start):
    seen, queue = {start}, deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)

Recursive DFS can overflow the stack on deep graphs; use an explicit stack when needed.

Options and trade-offs:

1. Sort then slice: O(n log n) time, simplest, fine for small n.
2. Min-heap of size k: O(n log k) time, O(k) space. Preferred when k is small relative to n.

import heapq

def k_largest(nums, k):
    return heapq.nlargest(k, nums)   # maintains a size-k heap internally

1. Quickselect: average O(n), worst O(n^2), mutates/partitions the array, good when k is close to n.

Follow-ups: streaming data (keep the heap across batches), finding the kth smallest, or using a bucket approach when values are bounded.