Practice DSA interview questions

Given an integer `n` (as a string), find the smallest 'good base' `k >= 2`. A base `k` is 'good' if the representation of `n` in base `k` consists of only the digit '1'. For example, for `n = 13`, the base `k = 3` is good because `13 = 111` in base 3. This is a very hard math problem. The number `n` in base `k` with `m` ones is `1 + k + k^2 + ... + k^(m-1) = (k^m - 1) / (k - 1)`. We can binary search for `k`.

Given a function `f(x, y)` which is monotonically increasing in both `x` and `y`, and an integer `z`, find all pairs `(x, y)` such that `f(x, y) == z`. The function is hidden behind an API `customfunction.f(x, y)`. This problem can be solved in O(x+y) using a two-pointer approach, but it can also be solved in O(x log y) by iterating through `x` and using Binary Search for `y`.

Given two sorted arrays, `arr1` of size `m` and `arr2` of size `n`, and an integer `k`, find the `k`-th smallest element in the merged sorted array. This is a classic divide-and-conquer problem, similar to 'Median of Two Sorted Arrays'. The goal is to find the element in O(log(m+n)) or O(log m + log n) time. We recursively 'discard' parts of the arrays that cannot contain the k-th element.

You are given an array `arr` which is a permutation of `[1, ..., n]`. You have a binary string of `n` zeros. At step `i`, you set the bit at position `arr[i]` to 1. Find the *latest step* at which there exists a group of *exactly* `m` consecutive ones. This is a hard problem. It can be solved by tracking intervals, but a 'Binary Search on the Answer' (the *step*) is also possible, though complex. A simpler O(n log n) solution uses a sorted data structure.

You are given two arrays `nums1` and `nums2`. The 'sum difference' is `sum(|nums1[i] - nums2[i]|)`. You can replace *at most one* element in `nums1` with *any other* element in `nums1` to minimize this sum. Find the minimum sum. The key is to find the *best possible replacement* for each index `i`. This search for the best replacement can be optimized with Binary Search.

You are given an array `obstacles`. You are building an obstacle course. For each position `i`, find the length of the *longest valid obstacle course* ending at `i`. A valid course must be increasing. This is a variation of the Longest Increasing Subsequence (LIS) problem. We need to find the LIS *ending at each index*. The O(n log n) LIS algorithm can be adapted for this.

Given the `root` of a *complete* binary tree, return the number of nodes. A 'complete' tree is filled at every level, except possibly the last, which is filled left-to-right. A naive traversal is O(n). An O((log n)^2) solution exists by leveraging the 'complete' property. We can find the height in O(log n). If the left and right subtrees have the same height, the left is a perfect tree. If not, the right is a perfect tree.

Given an `m x n` matrix where each row is sorted, find the overall median of the matrix. Assume `m * n` is odd. This is a classic 'Binary Search on the Answer' problem. The median is the element that has `(m*n) / 2` elements smaller than it. We can binary search for the *value* of the median in the range of possible values (min to max in the matrix).

Implement the `bisect_left` function. Given a sorted array `nums` and a `target`, find the *first index* `i` such that `nums[i] >= target`. If no such element exists, return `len(nums)`. This is the classic 'lower bound' Binary Search. It's a fundamental building block for many other BS problems. The key is how you adjust the pointers.

Implement the `bisect_right` function. Given a sorted array `nums` and a `target`, find the *first index* `i` such that `nums[i] > target`. If no such element exists, return `len(nums)`. This is the classic 'upper bound' Binary Search. It finds the correct insertion point to maintain sorted order if duplicates are inserted to the right. The logic is subtly different from `bisect_left`.

Implement a Trie data structure. A Trie (or prefix tree) is a tree-like data structure used to efficiently store and retrieve keys in a string dataset. Your implementation should support an `insert` method, which adds a `word` to the trie. This is a foundational problem for many string-based questions, as it allows for O(L) time complexity for string operations, where L is the length of the string.

As a follow-up to implementing a Trie, add a `search` method. This method should take a `word` and return `true` if the *entire* word exists in the trie (i.e., it was previously inserted) and `false` otherwise. This means we must traverse the trie and, at the end, check the `isEndOfWord` flag of the final node. This tests the core retrieval logic of the prefix tree.

As a final follow-up to the Trie implementation, add a `startsWith` method. This method should take a `prefix` and return `true` if there is any word in the trie that starts with the given `prefix`, and `false` otherwise. This is different from `search` because we *don't* need to check the `isEndOfWord` flag. We just need to successfully traverse the trie for all characters in the prefix.

Given the `root` of an N-ary tree, return the *preorder* traversal of its nodes' values. An N-ary tree is a tree where each node can have an arbitrary number of children. Preorder traversal visits the root, then recursively visits all of its children from left to right. This is a common traversal for hierarchical data, like file systems. The `Node` class usually has a `val` and a `list` of `children`.

Given the `root` of an N-ary tree, return the *postorder* traversal of its nodes' values. Postorder traversal recursively visits all children from left to right, and *then* visits the root node. This 'bottom-up' approach is useful for problems where children must be processed before the parent, such as calculating the total size of sub-directories in a file system.

Given the `root` of an N-ary tree, return the *level order* traversal of its nodes' values. This is a Breadth-First Search (BFS) and is identical in logic to the binary tree version. The only difference is that when you dequeue a node, you must enqueue *all* of its children from the `children` list, not just `left` and `right`. This is used to explore the tree layer by layer.

Given the `root` of an N-ary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root to the farthest leaf node. This is a classic recursive DFS problem, similar to the binary tree version, but requires finding the max depth among *all* children, not just two.

Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement `addWord(word)` and `search(word)`. The `search` method can contain dots (`.`) as wildcards, where `.` can match any single letter. This problem is a direct application of a Trie (Prefix Tree), but the `search` function must be modified to be a recursive DFS to handle the wildcard.

Given an `m x n` `board` of characters and a list of `words`, return all words that can be built from the board. A word is built from adjacent cells (horizontal/vertical) and cannot use the same cell more than once. This is a very hard problem that combines Trie and Backtracking/DFS. A naive DFS for every word will time out. The optimal solution is to add all `words` to a Trie, then perform a single DFS on the board that *prunes* paths that don't exist in the Trie.

Serialization is the process of converting a data structure to a string, and deserialization is the reverse. Design an algorithm to serialize and deserialize an N-ary tree. This is a common interview question that tests your understanding of tree traversals and string manipulation. Unlike a binary tree, a node can have a list of children, so we need a way to encode this list structure.

You are given *all* the nodes of an N-ary tree as a list. Each node has a `val` and a `children` list. However, you are not given the `root` node. Your task is to find the `root`. The root is the only node in the entire tree that is not a child of any other node. This problem can be solved by finding the one node that never appears in any `children` list.

A tree is an undirected graph. The 'root' of a tree can be any node. The height is the longest path to a leaf. Find all nodes that, when chosen as the root, result in a *minimum* height tree (MHT). These nodes are the 'centers' of the tree. This is a graph theory problem on a tree that can be solved with a topological-sort-like BFS. The idea is to 'peel' the tree from its leaves, layer by layer, until only the center(s) remain.

Design a 'MagicDictionary' that supports `buildDict(dictionary)` and `search(word)`. `search` should return `true` if there is *exactly one* character difference between the `word` and any word in the dictionary. This is a great Trie problem. We can build a normal Trie, but the `search` function must be a modified DFS that 'allows' for one mismatch.

Given an N-ary tree, return all root-to-leaf paths. A leaf is a node with no children. This is a classic backtracking problem. We must perform a Depth-First Search (DFS) and keep track of the current path of nodes. When we reach a leaf, we add a copy of the current path to our result list.

Given the roots of two N-ary trees, `rootA` and `rootB`, write a function to check if they are identical. Two trees are identical if they have the same structure and the same values at corresponding nodes. This is a straightforward recursive comparison problem. We must check the root values and then recursively check that all children are also identical.

Given the `root` of an N-ary tree, find the diameter. The diameter is the length of the longest path between *any two nodes* in the tree. This path may or may not pass through the root. This is a classic recursive DFS problem. For any node, the longest path passing through it is the sum of its two *deepest* children, plus 2 (for the edges).

Given the `root` of an N-ary tree and two nodes `p` and `q` in the tree, find their Lowest Common Ancestor (LCA). The LCA is the lowest node that has both `p` and `q` as descendants. This is the N-ary version of the classic 'LCA of a Binary Tree' problem. The recursive logic is similar: a node is the LCA if it finds `p` in one subtree and `q` in another, or if it *is* `p` or `q` and finds the other in a subtree.

Given an N-ary tree, check if it is symmetric (a mirror image of itself). For an N-ary tree, this means the *first* child must be a mirror image of the *last* child, the *second* child must be a mirror of the *second-to-last* child, and so on. This is a recursive problem similar to the binary tree version, but it requires comparing multiple pairs of children.

Given a generic tree (N-ary tree), count the total number of root-to-leaf paths. A leaf is a node with no children. This is a simple recursive DFS problem. We just need to traverse all paths, and when we hit a leaf, we count it as 1. The total count is the sum of counts from all subtrees.

Describe how a B-Tree works, focusing on its properties and how `insert` and `search` are performed. B-Trees are self-balancing tree data structures that maintain sorted data and are optimized for storage systems (like databases and file systems) that read/write large blocks of data. They are not binary trees; nodes can have many children and many keys.