Practice DSA interview questions

You are given a list of non-overlapping, sorted `intervals` and a `newInterval`. Insert `newInterval` such that the list remains sorted and non-overlapping (merging if necessary). This is a common interval problem. It's a variation of 'Merge Intervals' but with a list that is already sorted, so we can do it in a single pass.

Given an integer array `nums` of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. This is a fundamental backtracking problem. The core idea is to make a decision for each element: either 'include' it in the current subset or 'exclude' it. This binary choice (include/exclude) for `n` elements naturally leads to 2^n possible subsets.

Given an array of distinct integers `candidates` and a `target`, return a list of all unique combinations of `candidates` where the numbers sum to `target`. The *same* number may be chosen an unlimited number of times. This is another classic backtracking problem where the 'state' includes the remaining sum needed.

Given two integers `n` and `k`, return all possible combinations of `k` numbers chosen from the range `[1, n]`. This is a classic backtracking problem where we explore the decision of either 'including' a number in our combination or skipping it. Unlike permutations, the order does not matter (so `[1,2]` is the same as `[2,1]`), which we handle by only choosing numbers in increasing order.

Given an array `nums` containing `n` distinct numbers in the range `[0, n]`, return the *only* number in the range that is missing from the array. This is a classic problem with several solutions. A hash set works (O(n) space). The optimal O(1) space solution uses the 'Cyclic Sort' pattern (placing numbers at their correct index) or a mathematical approach using Gauss's formula for the expected sum.

You are given a large integer represented as an array `digits`, where `digits[i]` is the `i`-th digit (most significant first). Increment the integer by one. For `[1,2,3]`, return `[1,2,4]`. The challenge is handling the 'carry', especially in cases like `[9,9,9]`, which must become `[1,0,0,0]`. This problem tests basic arithmetic and array manipulation.

Given a non-empty array of integers `nums`, every element appears *twice* except for one. Find that single one. This is a classic bit manipulation problem. The key is to use the XOR operation (`^`). The XOR of a number with itself is 0 (`a ^ a = 0`). The XOR of a number with 0 is itself (`a ^ 0 = a`). All pairs will cancel out.

Given an array of integers `nums`, find the 'pivot index'. This is the index where the sum of all numbers to the *left* of the index is equal to the sum of all numbers to the *right*. If no such index exists, return -1. This is a classic prefix sum problem. A naive O(n^2) solution (re-calculating sums) is too slow. The O(n) solution involves one pass to get the total sum, and a second to check the condition.

Given an integer array `nums`, handle multiple queries of this type: Calculate the sum of elements of `nums` between indices `left` and `right` inclusive. This is a classic problem to introduce **Prefix Sums**. A naive solution would re-calculate the sum for each query (O(n) per query). By pre-calculating a prefix sum array, we can answer each query in O(1) time.

Given an integer array `nums` and `k`, return the `k`th largest element. This is a classic selection problem. The optimal O(n) *average* case solution is **Quickselect**, which is a modification of Quicksort. We partition the array around a pivot, but unlike Quicksort, we only recurse on the *one* side that contains our target index.

Given an integer array `nums` sorted in non-decreasing order, return an array of the squares of each number, also sorted. A naive solution (square all, then sort) is O(n log n). The optimal O(n) solution uses a **two-pointer** approach, because the original array is sorted. The largest squared values will be at the *ends* of the original array.

Given an integer array `nums`, return the length of the longest strictly increasing subsequence (LIS). A subsequence can be non-contiguous. For `[10,9,2,5,3,7]`, the LIS is `[2,3,7]` (length 3). The classic DP solution is O(n^2). An optimal O(n log n) solution exists that uses an auxiliary array and Binary Search.

You are given an array of `coins` of different denominations and a total `amount`. Find the minimum number of coins that you need to make up that amount. If it cannot be made up, return -1. This is a classic 'unbounded knapsack' dynamic programming problem. We want to find the minimum for each sub-amount up to the target.

You have `n` jobs. You are given `startTime`, `endTime`, and `profit` arrays. Find the maximum profit you can take such that there are no overlapping jobs. This is a hard DP problem. `dp[i]` = max profit from job `i` onwards. The key is that after doing job `i`, you must find the *next non-overlapping* job. This search can be optimized from O(n) to O(log n) using Binary Search.

Given an array `nums` and `k`, find the length of the longest subarray whose sum is divisible by `k`. This is a classic 'Prefix Sum' problem combined with a hash map. The key insight is that if `(prefix_sum[j] % k) == (prefix_sum[i] % k)`, then the sum of the subarray `nums[i+1...j]` must be divisible by `k`.

Given an integer `numRows`, generate the first `numRows` of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. This is a straightforward DP or simulation problem. Each new row can be built from the previous row.

Given an integer `rowIndex`, return the `rowIndex`-th (0-indexed) row of Pascal's triangle. This is a follow-up to the previous problem. The challenge is to do this with only O(k) extra space, where `k` is the `rowIndex`. This means we can't store the whole triangle. We must compute the row iteratively, modifying a single list in place.

Given a binary array `nums`, you must delete *exactly one* element. Return the size of the longest subarray of `1`s in the resulting array. If there is no such subarray, return 0. This is a sliding window problem. We are looking for the longest window that contains at most *one* zero.

Given a binary array `nums`, return the maximum number of consecutive `1`s in the array. This is a simple one-pass traversal problem. We just need to keep track of the current 'streak' of 1s and update a global maximum.

Given a binary array `nums` and an integer `k`, return the maximum number of consecutive `1`s in the array if you can flip at most `k` `0`s to `1`s. This is a classic sliding window problem. The 'window' is the subarray, and the 'validity' constraint is that the window contains at most `k` zeros.

You are given an `m x n` integer grid `accounts` where `accounts[i][j]` is the amount of money the `i`-th customer has in the `j`-th bank. Return the wealth of the richest customer. The wealth is the sum of all money they have. This is a simple 2D array traversal problem, often used as a warm-up.

Given a 2D integer array `matrix`, return the transpose of `matrix`. The transpose is formed by flipping the matrix over its main diagonal, switching the row and column indices. For an `m x n` matrix, the transpose is an `n x m` matrix. This is a fundamental matrix operation.

Determine if a `9 x 9` Sudoku board is valid. Only the filled cells need to be validated. A Sudoku is valid if: 1. Each row contains digits 1-9 without repetition. 2. Each column contains digits 1-9 without repetition. 3. Each of the nine 3x3 sub-boxes contains digits 1-9 without repetition. This is a classic hash set problem that tests careful indexing.

There are `n` gas stations on a circular route. `gas[i]` is the amount of gas at station `i`, and `cost[i]` is the cost to travel from `i` to `i+1`. Find the starting station's index if you can complete a full circle, otherwise return -1. This is a classic, hard greedy problem. The key insight is that if the `total_gas >= total_cost`, a solution is *guaranteed* to exist.

You have `points` where `points[i] = [x_start, x_end]`. You shoot arrows vertically. An arrow at `x` will burst all balloons where `x_start <= x <= x_end`. Find the minimum arrows to burst all. This is a greedy interval problem. It's equivalent to finding the maximum number of *non-overlapping* intervals, but the overlap logic is slightly different.

Given an array of `intervals`, find the minimum number of intervals to remove to make the rest non-overlapping. This is a classic greedy interval problem. It's the *inverse* of finding the *maximum number of non-overlapping intervals*. We sort by end time and greedily pick the next valid interval.

You are given two lists of *disjoint* and *sorted* intervals, `firstList` and `secondList`. Return the intersection of these two lists. For `A = [[0,2]]` and `B = [[1,5]]`, the intersection is `[[1,2]]`. This is solved using a two-pointer (or 'merge'-like) approach, moving through both lists simultaneously.

You are a robber. The houses are in a line. `nums[i]` is the money in house `i`. You cannot rob two adjacent houses. Find the maximum amount you can rob. This is the quintessential 1D Dynamic Programming problem. At each house, you have two choices: rob it (and take profit from `i-2`) or skip it (and take profit from `i-1`).

This is a follow-up to 'House Robber'. The houses are now in a *circle*, meaning the first and last houses are adjacent. This means you cannot rob *both* `nums[0]` and `nums[n-1]`. This is solved by breaking the problem into two sub-problems: 1) Rob houses `0` to `n-2` (excluding the last). 2) Rob houses `1` to `n-1` (excluding the first). The answer is the max of these two.

You are climbing a staircase. It takes `n` steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb? This is a classic DP problem that is identical in structure to the Fibonacci sequence. The number of ways to reach step `n` is the sum of the ways to reach step `n-1` (and taking one step) and the ways to reach step `n-2` (and taking two steps).