DSA interview questions and answers

You grow a sorted prefix and insert the next element by shifting larger values right.

Big-O describes how runtime or memory grows as input size n grows, ignoring constants and lower-order terms.

On a sorted array, each step halves the search range, so time is O(log n) and extra space is O(1) iterative or O(log n) recursive.

Multiply independent iteration counts: an n-loop around an n-loop is O(n^2).

Time complexity is how the number of operations grows

The base case is the input that returns immediately without another recursive call, such as n == 0 for factorial.

Recurse on n-1 first, then print n, so the prints happen on the way back

Recursion matches tree and graph DFS, divide-and-conquer, and backtracking because the call stack stores the path.

A power of two has exactly one bit set, so n > 0 and (n & (n - 1)) == 0.

Brian Kernighan's trick repeatedly does n &= n - 1, clearing the lowest set bit until n is zero

Build prefix products to the left of i and suffix products to the right of i, then multiply those two for each index.

Kadane's algorithm keeps a running sum, resetting it to the current value when the running sum goes negative, and tracks the global max.

Sort intervals by start time, then scan and either extend the last merged interval when the next start is at most the current end, or push a new interval.

Find the rightmost ascent, swap it with the smallest larger successor on its right, then reverse the suffix to make it the next smallest order.

Treat values as indices: negate nums[abs(x)-1] on first visit and record x when you see a negative already.

Take the first string as a candidate and shrink it whenever a later string mismatches at some index.

Skip leading spaces, read an optional sign, then accumulate digits while checking overflow against INT_MAX/MIN before multiplying by 10.

Naive sliding comparison is O((n-m+1)*m).

Expand around each center (and each pair of centers for even length), tracking the longest window.

For each word, sort its characters or count letters as a hash key and append the word to a map of lists.