DSA interview questions and answers

It is LCS of the string and its reverse, or interval DP: dp[i][j] = 2+dp[i+1][j-1] if s[i]==s[j] else max of shrinking either end.

dp[i] is true if some word ends at i-1 and dp[i-len] is true.

Interval DP over the last balloon burst in a range: dp[l][r] = max over k of nums[l]*nums[k]*nums[r] + dp[l][k] + dp[k][r], after padding 1s.

DP on prefixes: '*' means zero copies of the previous token (skip two pattern chars) or one more match of the previous token if it fits.

dp[i][j] is the min cost of multiplying matrices i..j, trying every split k.

You cannot rob both first and last, so take the max of linear-rob on [0..n-2] and on [1..n-1], with a one-house base case.

State is (row, col1, col2) for two walkers moving in sync toward the end

Sort jobs by end time.

Greedy BFS-on-array: while in the current jump range, track the farthest you can reach, then increment jumps when the range ends.

Two passes: left-to-right enforce left neighbors, right-to-left enforce right neighbors, then take the max at each index.

Sort intervals by end and shoot at the current end

Repeatedly pop the two smallest-frequency trees from a min-heap and push a parent whose frequency is their sum

During merge sort, when you take a value from the right half, every remaining left-half value is a larger-before-smaller inversion.

Find the median with quickselect, then three-way partition virtual indices (Dutch flag on mapped positions) so the small half and large half interleave.

Compare f(n) to n^{log_b a}.

Backtrack row by row, skipping used columns and both diagonals (r-c and r+c bit sets or boolean arrays).

Find the next empty cell, try digits 1-9 that do not clash in row, column, or 3x3 box, and recurse

Build a binary trie of bit prefixes (or grow a prefix-xor set bit by bit from the high bit) and for each number greedily try the opposite bit.

Swap bits with masks in log steps (1,2,4,8,16) or loop 32 times shifting result left and feeding n's low bit.

While n > m, clear the lowest set bit of n with n &= n-1