9 DSA interview questions and answers

O(log n) time and O(1) space for the iterative version. The data must be sorted, or the search space must be monotonic, which is what lets you 'binary search on the answer'.

Arrays give O(1) indexing and are cache-friendly. Linked lists give O(1) insertion and deletion when you already hold the node, but O(n) access by position.

In practice arrays win most of the time. Lists suit cases such as an LRU cache, where you remove and move nodes you already have pointers to.

A stack is last-in, first-out: think undo history, recursion and bracket matching. A queue is first-in, first-out: think BFS and task scheduling.

When the problem asks about a contiguous subarray or substring and the condition can be updated as the window grows or shrinks.

Example: longest substring without repeating characters. Expand the right end, shrink the left end when a character repeats, all in O(n).

Floyd's algorithm: move a slow pointer one step and a fast pointer two steps. If they meet there is a cycle; if fast reaches null there is none.

It runs in O(n) time and O(1) space. Resetting one pointer to the head and moving both one step at a time finds the start of the cycle.

BFS uses a queue and explores level by level, so it finds the shortest path in an unweighted graph.

DFS uses recursion or a stack and suits cycle detection, topological sort, connected components and backtracking.

A hash function maps a key to a bucket. Collisions are handled by chaining or open addressing, and the table resizes when the load factor gets too high.

Average lookup is O(1). The worst case is O(n), when many keys collide.

Look for optimal substructure, where the answer is built from answers to smaller subproblems, and overlapping subproblems, where the same subproblem is solved many times.

Then define the state, the recurrence, the base cases and the order of computation. Coin change is a classic: dp[x] = min over coins c of dp[x − c] + 1.

It repeatedly takes the unvisited node with the smallest known distance from a min-heap and relaxes its edges. With a binary heap it runs in O((V + E) log V).

It assumes a node's distance is final once it leaves the heap. A negative edge can later produce a shorter path and break that assumption. Use Bellman-Ford instead.