DSA Interview Questions

Think about how many times the input can be halved, and how much work happens per level.

The work grows like n × log n: slightly faster than linear. It typically comes from splitting the input in halves (log n levels) and doing O(n) work per level. Merge sort, heap sort, quick sort on average, and Python's sorted() are O(n log n). It is also the best possible worst case for any sort that only compares items.

Compare access by position with inserting next to an item you already hold.

Choose a linked list when you insert or delete often next to nodes you already have a reference to (O(1), no shifting), as in LRU caches, or when the size changes constantly and you never need item i directly. Choose an array for indexing (O(1) vs O(n)), memory efficiency and speed: arrays keep items together in memory, which processors handle much faster.

What happens if many keys land in the same bucket?

A lookup hashes the key to a bucket and searches only that bucket. With a good hash function and resizing, buckets hold about one item, so it is O(1) on average. If many keys collide (a poor hash function, or keys chosen by an attacker), one bucket holds most items and lookups degrade to O(n). Real implementations use well-mixed, often randomised hash functions to make that very unlikely.

One needs extra memory; the other needs sorted input.

With a dictionary of seen values, one pass is O(n) time and O(n) space and returns original indexes:

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i

print(two_sum([2, 7, 11, 15], 9))

(0, 1)

Two pointers need the list sorted (O(n log n), losing original positions unless you sort index pairs) but use O(1) extra space.

Two runners at different speeds on a circular track.

Floyd's algorithm: move slow one node and fast two nodes at a time. If there is a cycle, fast eventually laps slow and they meet; if fast reaches the end, there is none. O(n) time, O(1) space.

class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

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

a = Node(1, Node(2, Node(3)))
print(has_cycle(a))
a.next.next.next = a.next          # 3 points back to 2
print(has_cycle(a))

False
True

Anything where the most recent item must be handled first.

• The call stack that runs functions and recursion.
• Undo in editors and the browser Back button.
• Matching nested structures: brackets, HTML tags, expression evaluation.

Depth-first search also uses a stack, explicitly or through recursion.

Inorder visits the left subtree, then the node, then the right subtree.

The values in sorted order. In a BST every left-subtree value is smaller and every right-subtree value is larger than the node, and inorder visits exactly left, node, right, recursively. This is also a quick way to validate a BST: its inorder sequence must be strictly increasing.

Which operations does a priority queue actually need?

A heap. A priority queue needs only "insert" and "remove the minimum". A heap does those in O(log n) with O(1) peek, stored compactly in an array, and builds from a list in O(n). A balanced BST also manages O(log n) but is more complex; it is worth it only when you need extra operations such as ordered iteration, searching for any value, or finding the next larger key.

In what order does BFS reach vertices?

BFS visits vertices in order of their number of edges from the start: everything at distance 1, then 2, and so on. The first time it reaches a vertex is via a path with the fewest edges. With weights, fewest edges is not cheapest: two cheap edges can beat one expensive edge. Weighted graphs need Dijkstra (non-negative weights) or Bellman-Ford.

Dijkstra treats a vertex's distance as final when it is taken from the heap.

Dijkstra finalises the closest unfinished vertex, assuming no later path can be cheaper because adding edges only increases cost. A negative edge breaks that assumption: a longer route through it can arrive later and be cheaper, but the vertex is already finalised. Use Bellman-Ford, which relaxes every edge V − 1 times and also detects negative cycles.

Think of courses with prerequisites.

An ordering of a directed graph's vertices where every edge u → v puts u before v: a valid order for tasks with dependencies (build systems, course plans, spreadsheet recalculation). It is impossible when the graph has a cycle. Kahn's algorithm detects this: if it cannot place every vertex, a cycle remains.

Top-down versus bottom-up.

Both store subproblem answers so each is computed once. Memoization is top-down: the natural recursion plus a cache; it only computes subproblems that are actually needed but has recursion overhead and depth limits. Tabulation is bottom-up: a loop fills a table from the smallest subproblems; no recursion, and often easy to reduce to O(1) or one-row memory.

The last move came from step n − 1 or n − 2.

ways(n) = ways(n - 1) + ways(n - 2), the Fibonacci recurrence. Keep only the last two values:

def climb(n):
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

print([climb(n) for n in range(1, 8)])

[1, 2, 3, 5, 8, 13, 21]

Coin change with an unusual set of coins.

Fewest coins for amount 6 with coins 4: greedy takes the largest coin first, 4 + 1 + 1 = 3 coins, but 3 + 3 = 2 coins is better. Greedy works only when a local choice can be proven safe; otherwise use dynamic programming, here dp[a] = 1 + min(dp[a - c]).

Sorting works, but you only need part of the order.

• Sort and index: O(n log n).
• A min-heap of size k: the root is the kth largest at the end, O(n log k).
• Quickselect: partition like quick sort but recurse into one side only, O(n) on average.

import heapq

def kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]

print(kth_largest([3, 2, 1, 5, 6, 4], 2))

5

Remembering things costs memory but can save repeated work.

Using extra memory to save time, or the reverse. Examples: a set of seen values makes duplicate detection O(n) instead of O(n²) at the cost of O(n) memory; memoization stores subproblem answers to avoid exponential recomputation; prefix sums spend O(n) memory to answer any range sum in O(1).