Practice DSA interview questions

Given a binary tree (not a BST), find the lowest common ancestor (LCA) of two given nodes `p` and `q`. This is much harder than the BST version because we cannot use value properties to guide our search. We must search both subtrees. The recursive solution is brilliant but can be hard to grasp. It relies on 'bubbling up' the result.

Given a string containing digits from `2-9` inclusive, return all possible letter combinations that the number could represent, in any order. A mapping of digits to letters (just like on a telephone keypad) is provided. This is a classic backtracking problem. The core idea is to explore a decision tree. For each digit, we have 3 or 4 choices (letters). We pick one letter, then recursively call the function for the next digit. The recursion builds up a combination, and when we've processed all digits, we add the result.

Given an `m x n` grid of characters `board` and a string `word`, return `true` if `word` exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where 'adjacent' means horizontally or vertically neighboring. The same letter cell may not be used more than once. This is a classic backtracking problem on a 2D matrix. We must perform a Depth-First Search (DFS) from every cell to see if we can find the word.

Write a program to solve a Sudoku puzzle by filling the empty cells. A Sudoku solution must satisfy all of the following rules: Each of the digits `1-9` must occur exactly once in each row, each column, and each of the nine `3x3` sub-boxes. The `.` character indicates empty cells. This is a quintessential backtracking problem. We try placing a number in an empty cell and recursively see if it leads to a solution.

Given a string `s`, partition `s` such that every substring in the partition is a palindrome. Return all possible palindrome partitionings. This is a backtracking problem where we need to decide where to 'cut' the string. At each step, we check if the substring from the current start to a new endpoint is a palindrome. If it is, we add it to our current partition and recurse on the rest of the string.

You are climbing a staircase. It takes `n` steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? This is a classic dynamic programming 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).

There is a robot on an `m x n` grid. The robot is initially at the top-left corner (`grid[0][0]`) and tries to move to the bottom-right corner (`grid[m-1][n-1]`). The robot can only move either down or right at any point in time. Given `m` and `n`, return the number of possible unique paths. This is another fundamental DP problem solvable with recursion and memoization.

Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times. This is a DP problem that can be solved with top-down memoization. We recursively check if prefixes of the string are in the dictionary.

Given the `root` of a binary tree and an integer `targetSum`, return `true` if the tree has a root-to-leaf path such that adding up all the values along the path equals `targetSum`. A leaf is a node with no children. This is a classic tree DFS problem. We traverse the tree, subtracting the node's value from the target sum as we go.

Given the `root` of a binary tree and an integer `targetSum`, return all root-to-leaf paths where the sum of the node values equals `targetSum`. This is a backtracking problem. We need to not only check for the sum, but also keep track of the *path* (the nodes) that led to that sum. When we find a valid path, we add a copy of it to our result list.

Given the `root` of a binary tree, flatten the tree into a 'linked list' in-place. The 'linked list' should use the same `TreeNode` class, where the `right` child pointer points to the next node in the list and the `left` child pointer is always `null`. The list should be in pre-order traversal order. This can be solved with a clever recursive, post-order traversal.

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is one in which the left and right subtrees of every node differ in height by no more than one. This problem requires a recursive solution. A naive solution that calls `maxDepth` at every node is O(n log n). The optimal O(n) solution combines the height calculation and the balance check into one recursive function.

Given the `root` of a binary tree, return the length of the diameter of the tree. The diameter is the length of the *longest* path between any two nodes. This path may or may not pass through the root. The length is the number of edges. This is a classic post-order traversal problem. For any node, the longest path *passing through it* is `height(left) + height(right)`.

Given the `root` of a binary search tree (BST) and an integer `k`, return the `k`th smallest element (1-indexed) in the tree. The key property of a BST is that an **in-order traversal** visits the nodes in ascending order. We can perform an in-order traversal and stop when we've visited `k` elements.

Given an integer array `nums` where the elements are sorted in ascending order, convert it to a height-balanced binary search tree (BST). A height-balanced tree is one where the depths of the two subtrees of every node never differ by more than one. This is a classic divide-and-conquer problem. To keep it balanced, we should pick the middle element of the array as the root.

Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal and `inorder` is the inorder traversal, construct and return the binary tree. You may assume duplicates do not exist. The key insight is: the first element of `preorder` is *always* the root. The position of this root in the `inorder` array tells us which elements belong to the left subtree and which belong to the right.

Given two integer arrays `inorder` and `postorder` where `inorder` is the inorder traversal and `postorder` is the postorder traversal, construct and return the binary tree. You may assume duplicates do not exist. This is the reverse of the previous problem. The key insight is: the *last* element of `postorder` is *always* the root. Its position in `inorder` splits the tree into left and right subtrees.

Given an array of integers `nums`, sort the array in ascending order using Merge Sort. Merge Sort is a classic divide-and-conquer algorithm. It works by recursively splitting the array into two halves, sorting each half, and then merging the two sorted halves back together. Its time complexity is O(n log n) and it is a stable sort. It requires O(n) auxiliary space for the merge step.

Given an array of integers `nums`, sort the array in ascending order using Quick Sort. Quick Sort is another classic divide-and-conquer algorithm. It works by selecting a 'pivot' element and partitioning the array around it, such that all elements smaller than the pivot are to its left and all elements larger are to its right. It then recursively sorts the two sub-arrays. Average time is O(n log n), but worst-case is O(n^2).

Given a sorted array `nums` that has been rotated at some unknown pivot, and a `target`, return the index of `target` if it's in `nums`, or -1. For example, `[4,5,6,7,0,1,2]` was rotated from `[0,1,2,4,5,6,7]`. You must solve this in O(log n) time. This implies a modified Binary Search. The key is to determine which half (left or right) of the array is still sorted.

Given an integer array `nums` and an integer `k`, return the `k`th largest element. This can be solved by sorting (O(n log n)) or a min-heap (O(n log k)). However, a more advanced O(n) average-case solution uses **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.

Given an input string `s` and a pattern `p`, implement regular expression matching with support for `'.'` (matches any single character) and `'*'` (matches zero or more of the preceding element). This is a very common and difficult problem often asked in interviews. It is a perfect candidate for recursion with memoization (top-down dynamic programming). We have to make decisions based on the current characters in `s` and `p`.

Given an input string `s` and a pattern `p`, implement wildcard pattern matching with support for `?'` (matches any single character) and `'*'` (matches any sequence of characters, including the empty sequence). This is similar to Regular Expression Matching but with different rules for `'*'`. This problem is also a classic recursion with memoization (Dynamic Programming) problem, testing your ability to handle multiple recursive pathways and optimize them.

Given an `m x n` 2D binary grid `grid` which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. This is a classic graph traversal problem. We iterate through the grid, and every time we find a '1' (land), we increment our island count and then use a recursive Depth-First Search (DFS) to 'sink' the entire island (turn all its '1's to '0's) so we don't count it again.

You are given an `m x n` binary matrix `grid`. An island is a group of '1's connected 4-directionally. The area of an island is the number of cells with a value '1' in the island. Return the maximum area of an island in `grid`. If there is no island, return 0. This is a variation of the 'Number of Islands' problem. Instead of just sinking the island, our recursive DFS function needs to *return* the size of the island it just explored.

Given an integer `x`, return `true` if `x` is a palindrome, and `false` otherwise. A palindrome reads the same forwards and backward. This can be solved by converting the number to a string, but a recursive solution without string conversion is also possible, though more complex. The string conversion approach is the most common and easily understood.

We build a table of `n` rows. We start with `0` in row 1. For every subsequent row, we replace `0` with `01` and `1` with `10`. Given `n` and `k`, return the `k`-th (1-indexed) character in the `n`-th row. This is a classic divide-and-conquer problem. We can observe a pattern: the second half of any row `n` is the bitwise NOT of the first half. The first half is identical to row `n-1`.

Given an integer `n`, return the number of structurally unique binary search trees (BSTs) that have exactly `n` nodes with unique values from 1 to `n`. This is a famous dynamic programming problem related to Catalan numbers. The core idea is to iterate through all possible root nodes (`i` from 1 to `n`). For each `i` as the root, the number of unique left subtrees is `G(i-1)` and the number of right subtrees is `G(n-i)`.

Given an integer `n`, return all the structurally unique binary search trees (BSTs) which have exactly `n` nodes of unique values from 1 to `n`. This is the follow-up to the previous problem. Instead of just *counting* the trees, we must *generate* all of them. This requires a recursive function that returns a list of all possible subtrees.

Given two strings `word1` and `word2`, return the minimum number of operations (insert, delete, or substitute) required to convert `word1` to `word2`. This is a classic and very common dynamic programming problem. The recursive solution explores the three possible operations at each character comparison.