Practice DSA interview questions

Given two strings `s` and `t`, return the number of distinct subsequences of `s` which equal `t`. For `s = 'rabbbit', t = 'rabbit'`, the answer is 3. This is a hard 2D Dynamic Programming problem. `dp[i][j]` will store the number of distinct subsequences of `s[0...i]` which equal `t[0...j]`.

Given `s1` and `s2`, determine if `s2` is a 'scrambled' version of `s1`. A scramble is formed by recursively partitioning a string into two non-empty parts and (optionally) swapping them. E.g., `great` -> `gr` + `eat` -> `gr` + `e` + `at`. This can be 'rgeat'. This is a hard 3D Dynamic Programming or recursion with memoization problem.

Given a string `s`, determine if it is a 'valid number'. This includes integers, decimals, and scientific notation (e.g., '95.5e+3'). This is a notoriously difficult, edge-case-heavy parsing problem. It's best solved by creating a deterministic finite automaton (DFA) or a very strict set of rules. It tests your ability to handle a large number of specific edge cases meticulously.

Given a string `s`, find the length of the *longest substring* without repeating characters. This is a classic 'sliding window' problem, a fundamental technique in FAANG interviews. We use two pointers, `left` and `right`, to define a 'window' and a hash set (or map) to keep track of the characters currently in that window. We expand the window with `right` and shrink it with `left` when a duplicate is found.

Given an array of integers `nums` and an integer `target`, return the indices of the two numbers such that they add up to `target`. You may assume that each input would have exactly one solution, and you may not use the same element twice. This is the most common 'icebreaker' question to check for a basic understanding of hash maps. A naive O(n^2) solution is obvious, but the O(n) hash map solution is the expected answer.

You are given an array `prices` where `prices[i]` is the price of a given stock on the `i`-th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit. This is a classic problem that can be solved in a single pass. It's a test of finding a minimum value and a maximum difference concurrently.

Given an integer array `nums`, return `true` if any value appears at least twice in the array, and return `false` if every element is distinct. This is a fundamental problem used to test for O(n) hash set usage. A sorting-based solution is also possible (O(n log n)) but is less efficient. It's a common warm-up question.

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. This is a classic problem solved efficiently using **Kadane's Algorithm**, which is a O(n) time and O(1) space dynamic programming approach. The algorithm is a very common pattern in array-based problems.

Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`. You must solve this in O(n) time and without using the division operation. This is a very common FAANG question that tests your ability to use prefix and postfix calculations in a clever way to achieve an O(1) space solution (excluding the output array).

Given an integer array `nums`, move all `0`'s to the end of it while maintaining the relative order of the non-zero elements. This must be done in-place without making a copy of the array. This is a classic two-pointer problem ('fast' and 'slow') that tests in-place modification and minimizing the total number of operations. It's a common screening question.

Given an integer array `nums`, find all unique triplets `[nums[i], nums[j], nums[k]]` such that `i != j`, `i != k`, `j != k`, and their sum is zero. The solution set must not contain duplicate triplets. This is a very common and classic interview question. The optimal O(n^2) solution involves sorting the array first, then using a 'two-pointer' approach on the sub-arrays to find the other two numbers.

You are given an integer array `height` of length `n`. There are `n` vertical lines drawn such that the two endpoints of the `i`-th line are `(i, 0)` and `(i, height[i])`. Find two lines that, together with the x-axis, form a container that holds the most water. Return the maximum amount of water. This is a classic two-pointer problem that uses a greedy approach.

Given an array `nums`, rotate the array to the right by `k` steps, where `k` is non-negative. For example, `[1,2,3,4,5]` with `k=2` becomes `[4,5,1,2,3]`. This must be done in-place with O(1) extra space. This problem tests in-place manipulation. The most clever solution involves three 'reverse' operations.

You are given two sorted integer arrays, `nums1` (of size `m+n`) and `nums2` (of size `n`). `nums1` has `m` initialized elements and `n` zeros at the end. Merge `nums2` into `nums1` as one sorted array. The final sorted array should be stored in `nums1`. This is a classic two-pointer problem. The key is to fill `nums1` from the *back* to avoid overwriting elements.

Given an array `nums` of `n` integers where `nums[i]` is in the range `[1, n]`, and each integer appears once or twice, return an array of all the integers that appear twice. You must solve this in O(n) time and O(1) extra space. This is a classic "Cyclic Sort" or "in-place hash" problem. We use the array indices themselves to store information.

Given an array `nums` of `n + 1` integers where each is in `[1, n]`, there is only one repeated number. Find it. You must not modify `nums` and use O(1) space. This is a very common FAANG question. It can be solved by mapping it to a 'Linked List Cycle Detection' problem. The array indices are nodes, and the values are pointers. The duplicate number creates a cycle.

Given an unsorted integer array `nums`, return the smallest missing positive integer (e.g., 1, 2, 3...). You must solve this in O(n) time and O(1) extra space. This is a famously hard FAANG problem. The key is to use the array *itself* as a hash map. We try to place the number `x` at index `x-1`.

Given `n` non-negative integers representing an elevation map (`height`), compute how much water it can trap. This is a classic hard problem. A DP solution uses O(n) space. The optimal O(n) time, O(1) space solution uses a clever two-pointer approach. We maintain the max height seen from the left (`left_max`) and from the right (`right_max`).

You are given an `n x n` 2D `matrix` representing an image. Rotate the image by 90 degrees (clockwise). You must do this in-place, without allocating another 2D matrix. This is a very common matrix problem. The solution is a clever two-step process: 1) Transpose the matrix. 2) Reverse each row.

Given an `m x n` matrix, if an element is 0, set its entire row and column to 0. You must do this in-place. A naive solution using O(m*n) space is easy. An O(m+n) space solution is also simple. The optimal O(1) space solution is tricky. It uses the *first row* and *first column* of the matrix itself as storage to mark which rows/cols need to be zeroed.

Given an `m x n` matrix, return all elements of the matrix in spiral order. For example, a 3x3 matrix `[1,2,3],[4,5,6],[7,8,9]` should return `[1,2,3,6,9,8,7,4,5]`. This is a classic simulation problem that tests your ability to manage boundaries. You need to simulate the traversal by 'peeling' the outer layer of the matrix.

Given an array of `intervals` where `intervals[i] = [start, end]`, merge all overlapping intervals and return an array of the non-overlapping intervals. For example, `[[1,3],[2,6],[8,10]]` becomes `[[1,6],[8,10]]`. This is a very common problem that tests sorting and greedy logic. The key is to sort by the start time.

Given an integer array `nums` and `k`, return the `k`th largest element. This is a classic selection problem. The O(n log n) solution is to sort. The O(n log k) solution is to use a min-heap of size `k`. The optimal O(n) average-case solution is **Quickselect**, which is a modification of Quicksort.

Given an array `nums` of `n` integers where `nums[i]` is in `[1, n]`, return an array of all integers in `[1, n]` that do *not* appear in `nums`. You must solve this in O(n) time and O(1) extra space (excluding the output). This is another 'in-place hash' problem, similar to 'Find All Duplicates'. We use the array's indices and the sign of the numbers to mark which are seen.

Given an array of integers `nums` and an integer `k`, find the total number of continuous subarrays whose sum equals `k`. This is a very common and important problem. A naive O(n^2) solution (checking all subarrays) will time out. The optimal O(n) solution uses a hash map to store the frequencies of *prefix sums*.

Given an array of integers `nums`, find the next lexicographically greater permutation. If no such permutation exists, rearrange it to the lowest (sorted ascending). This must be in-place with O(1) space. This is a classic algorithm problem. It requires finding the first 'dip' from the right, swapping it, and then reversing the rest.

You are given an array `nums` where `nums[i]` is the maximum jump length from that position. You start at index 0. Return `true` if you can reach the last index. This is a classic 'greedy' array problem. We don't need to know *how* we get to the end, just *if* we can. We can track the 'farthest' reachable index.

Given an array `nums` where `nums[i]` is the max jump length, find the *minimum* number of jumps to reach the last index. This is the follow-up to 'Jump Game' and is also a greedy problem. This is a common and clever O(n) solution that is a form of Breadth-First Search.

Given an array `nums` of size `n`, return the majority element. The majority element is the element that appears more than `floor(n / 2)` times. You may assume one always exists. The hash map solution is O(n) time and O(n) space. The optimal O(n) time, O(1) space solution is the **Boyer-Moore Voting Algorithm**.

Given an integer array `nums` of size `n`, find all elements that appear more than `floor(n / 3)` times. This is a follow-up to the 'Majority Element' problem. At most, there can be *two* such elements. This is solved with a modified Boyer-Moore Voting Algorithm that tracks two candidates and two counters.