DSA Interview Questions and Answers

An array stores elements in contiguous memory, so index access is O(1). A linked list stores nodes anywhere in memory, each pointing to the next, so reaching the k-th element takes O(k).

Choose an array for fast random access and iteration. Choose a linked list for frequent insertions and deletions at known positions, such as the nodes behind an LRU cache. In practice arrays (or dynamic arrays) win most benchmarks because of CPU cache locality.

What they are checking: Trade-offs, not just definitions

A stack is LIFO (last in, first out): push and pop at the same end. A queue is FIFO (first in, first out): enqueue at the rear, dequeue from the front.

• Stack uses: function call stack, undo, expression evaluation, balanced brackets, DFS.
• Queue uses: task scheduling, BFS, buffering, print jobs.

from collections import deque
stack = []
stack.append(1); stack.append(2); print(stack.pop())      # 2

queue = deque()
queue.append(1); queue.append(2); print(queue.popleft())  # 1

Use deque for queues in Python: list.pop(0) is O(n). All push, pop, enqueue and dequeue operations are O(1).

What they are checking: Core structures and where they are used

Big O describes how running time (or memory) grows with input size n in the worst case, ignoring constants. It lets you compare algorithms independent of hardware.

Rules: drop constants and lower terms (3n + 10 becomes O(n)), add sequential steps, multiply nested ones. Big O is an upper bound; Omega is a lower bound and Theta a tight bound.

What they are checking: Fluency in complexity language

A hash table stores key-value pairs. A hash function converts the key into an integer, which is reduced to an index (hash(key) % capacity) pointing at a bucket. Lookup, insert and delete are O(1) on average.

A collision happens when two keys map to the same bucket. Common fixes:

• Chaining: each bucket holds a list (or tree) of entries. Java HashMap does this.
• Open addressing: probe for another free slot (linear probing, quadratic probing, double hashing). Python dict uses this.

The load factor (entries / buckets) controls speed. When it passes a threshold (0.75 in Java), the table resizes and rehashes all keys. A bad hash function or an attacker choosing colliding keys can degrade operations to O(n).

Keys must be hashable and, if mutable, never changed while stored.

What they are checking: One of the most asked topics; checks you know the internals

Binary search finds a target in a sorted collection. It compares with the middle element again and again. Each time it throws away the half that cannot contain the target. Time is O(log n), extra space O(1) iterative.

Prerequisite: the data must be sorted and support O(1) random access (an array, not a linked list).

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2         # avoids overflow in fixed-width ints
        if a[mid] == target: return mid
        if a[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9], 7))   # 3

Python's bisect module provides it ready-made. The idea also applies to "binary search on the answer" problems.

What they are checking: Can you code it and get off-by-one details right

A BST is a binary tree with one rule for every node. All keys in the left subtree are smaller. All keys in the right subtree are larger. This allows search, insert and delete by comparing and going left or right.

Inserting sorted data into a plain BST makes it a linked list (worst case). Self-balancing trees (AVL, Red-Black) keep height O(log n) with rotations.

In-order traversal of a BST returns the keys in sorted order, which is also the standard way to validate one.

What they are checking: Tree fundamentals and degenerate case awareness

Both visit every node of a graph or tree in O(V + E).

Use BFS for shortest path in unweighted graphs, level-order traversal, "minimum steps" problems. Use DFS for cycle detection, topological sort, connected components, backtracking and path existence.

from collections import deque

def bfs(graph, start):
    seen, q = {start}, deque([start])
    order = []
    while q:
        n = q.popleft(); order.append(n)
        for nb in graph[n]:
            if nb not in seen:
                seen.add(nb); q.append(nb)
    return order

print(bfs({1: [2, 3], 2: [4], 3: [4], 4: []}, 1))   # [1, 2, 3, 4]

What they are checking: Graph traversal fundamentals

Comparison sorts cannot beat O(n log n). Insertion sort is good for small or nearly sorted data. This is why real libraries (Python's Timsort, Java's Arrays.sort for objects) mix merge sort and insertion sort.

What they are checking: Whether you know the table and the reasons behind it

Both are divide and conquer with O(n log n) average time.

• Merge sort: guaranteed O(n log n), stable, needs O(n) extra space, good for linked lists and external (disk) sorting.
• Quick sort: average O(n log n), worst O(n^2) with poor pivots (reduced by random or median-of-three pivots). It sorts in place with O(log n) stack. It is usually faster on arrays because of cache locality. It is not stable.

Choose merge sort when stability or worst-case guarantees matter (sorting records by multiple keys, large files). Choose quick sort for in-memory primitive arrays where speed and memory matter.

What they are checking: Reasoning about trade-offs

A binary heap is a complete binary tree stored in an array. Every parent is ordered against its children: in a min-heap the parent is smaller, in a max-heap larger. The root is always the min (or max).

Dynamic programming (DP) solves problems that have overlapping subproblems and optimal substructure by storing sub-results so each is computed once.

A dynamic array wraps a fixed array and grows when full: it allocates a bigger array (often 1.5x to 2x), copies the elements and continues. Append is O(1) amortized: occasional O(n) resizes are spread over many cheap appends, so the average cost per append stays constant.

For a binary tree:

• Preorder: node, left, right. Useful to copy a tree or serialise it.
• Inorder: left, node, right. Gives sorted order for a BST.
• Postorder: left, right, node. Useful to delete a tree or evaluate expression trees.
• Level-order: by depth, using a queue (BFS).

• Adjacency list: a map from each vertex to its neighbours. Space O(V + E). Iterating neighbours is fast. Best for sparse graphs (most real ones).
• Adjacency matrix: a V x V grid where cell (i, j) marks an edge. Space O(V^2). Edge check is O(1). Best for dense graphs or when you need constant-time edge lookups.

Both avoid recomputing subproblems.

Time complexity measures how the number of operations grows with input size. Space complexity measures how extra memory grows with input size (usually excluding the input itself, called auxiliary space).

A singly linked list node has data and next. A doubly linked list node also has prev.

A sort is stable if elements with equal keys keep their original relative order.

Recursion is when a function calls itself on a smaller version of the problem. It needs:

1. A base case that returns without recursing.
2. A recursive case that moves toward the base case.

HashMap is an array of buckets. For put(key, value):

1. Compute key.hashCode() and spread its bits.
2. Find the bucket index (hash & (capacity - 1); capacity is a power of two).
3. If the bucket is empty, store a node. Otherwise compare keys with equals; replace the value if equal, else append to the chain.
4. Since Java 8, a chain longer than 8 (with table size at least 64) turns into a red-black tree. So the worst-case lookup is O(log n) instead of O(n).
5. When size exceeds capacity * 0.75, the table doubles and entries are redistributed.

Consequences: keys need matching equals/hashCode. If you change a key after inserting it, you lose it. The iteration order is not guaranteed. It is not thread-safe (use ConcurrentHashMap). A null key is allowed (bucket 0). Initial capacity matters if you know the size, to avoid rehashing.

What they are checking: Internals knowledge that interviewers love

Both are self-balancing BSTs that keep height O(log n) so every operation stays O(log n).

Dijkstra finds the shortest path from one source to all vertices in a graph with non-negative edge weights. It greedily picks the unvisited vertex with the smallest known distance (using a min-heap), then relaxes its outgoing edges.

Options:

1. Sort: O(n log n). Simple, fine for small inputs.
2. Min-heap of size k: push each element, pop when size exceeds k. Result is the heap root. O(n log k) time, O(k) space. Best for streams.
3. Quickselect: partition around a pivot like quick sort but recurse into one side only. Average O(n), worst O(n^2) (random pivot makes this unlikely). Modifies the array.

Two pointers: two indices move through a sequence (often one from each end, or a slow one and a fast one). This avoids a nested loop. Typical for sorted arrays: pair sum, removing duplicates, reversing, partitioning. Turns O(n^2) into O(n).

LRU needs O(1) lookups and O(1) "move to most recent" and "evict oldest". One structure cannot do both:

• A hash map gives O(1) lookup by key.
• A doubly linked list keeps usage order; moving or removing a known node is O(1).

A topological order of a directed acyclic graph (DAG) lists the vertices so that for every edge u -> v, u comes before v. It exists only if the graph has no cycle.

Uses: build systems, course prerequisites, task scheduling, package dependency resolution.

Undirected graph: DFS or BFS and look for a visited neighbour that is not the node's parent. Or use Union-Find: if an edge joins two vertices already in the same set, there is a cycle.

A trie (prefix tree) stores strings character by character: each node is a character and a path from the root spells a prefix. Lookup, insert and prefix search take O(L), where L is the string length, independent of how many words are stored.

Union-Find tracks a partition of elements into disjoint sets. Operations: find(x) returns the set representative, union(a, b) merges two sets. With path compression and union by rank, each operation is almost O(1) (inverse Ackermann).

Given items with weights and values and a capacity W, choose a subset with maximum total value. The total weight must not exceed W. Each item is used at most once.

State: dp[w] = best value with capacity w. Iterate items, and iterate capacity downward so each item is used once.

Heap sort: build a max-heap from the array. Then swap the root (largest) with the last unsorted element, make the heap one smaller, and sift down. Repeat. Result is ascending, in place: O(n log n) time in all cases, O(1) extra space, not stable.

Amortized analysis spreads the cost over a sequence of operations, even in the worst case. A rare expensive operation is shared by many cheap ones. It is not probabilistic.

Load factor = number of entries / number of buckets. A high load factor means more collisions: chains get longer (or probe sequences grow), pushing operations from O(1) toward O(n).

A minimum spanning tree (MST) connects all vertices of a weighted undirected graph. It has the smallest total edge weight and no cycles.

Disk and SSD reads fetch whole pages, so the cost is the number of page reads, not comparisons. A binary tree has height log2(n), which means many reads. A B-tree node holds hundreds of keys (one page), so the tree is very wide and shallow. With 500 keys per node, 100 million rows need only about 3 or 4 levels.

A trie keyed by characters supports prefix lookup in O(L). Store a small list of top suggestions at each node (worked out in advance by frequency). Then a query returns results without walking the whole subtree.

Exact counting needs memory proportional to distinct items. Options:

Model users as vertices and friendships as edges (unweighted, undirected). Use BFS from the source: the first time you reach the target is the shortest path, in O(V + E).

A sorted array gives O(log n) search but O(n) insert/delete because of shifting. A plain linked list gives O(1) insert but O(n) search.

Inserting keys in sorted order into a plain BST creates a lopsided tree. Every node has only a right child, so it behaves like a linked list. Height becomes n and operations degrade from O(log n) to O(n).

Options by constraint:

1. External sort: sort chunks that fit in memory, write them out, k-way merge, and compare neighbours. O(n log n) with sequential disk I/O, exact.
2. Hash partitioning: split IDs into buckets on disk by hash(id) % B, so duplicates fall in the same bucket. Then check each bucket in...

Use two stacks of commands (Command pattern).

A priority queue implemented with a binary heap: insert and pop-highest are both O(log n), peek is O(1). A sorted list would make inserts O(n).