Practice DSA interview questions

Implement a Min-Heap. A Binary Heap is a complete binary tree that satisfies the heap property (in a min-heap, every parent is smaller than or equal to its children). It's usually implemented as an array. Implement the `insert` operation, which adds a new element while maintaining the heap property. This operation is O(log n) because it involves 'bubbling up' the new element.

Implement the `extractMin` (or `pop`) operation for a Min-Heap. This operation removes and returns the smallest element in the heap (the root). To maintain the heap's 'complete tree' shape, we swap the root with the *last* element, pop the old root, and then 'sift-down' or 'bubble-down' the new root to its correct position. This operation is O(log n).

Design a class to find the `k`th largest element in a stream of numbers. This class should have a constructor that takes `k` and an initial array, and an `add(val)` method that adds `val` to the stream and returns the *current* `k`th largest element. This is a classic application for a Min-Heap.

Given an array of `points` where `points[i] = [x, y]`, return the `k` closest points to the origin `(0, 0)`. The distance is the Euclidean distance. This is a common sorting/selection problem. The most efficient solution uses a Max-Heap of size `k` (or a Min-Heap with all `n` points, which is less efficient if `k << n`). A Max-Heap allows us to keep track of the `k` *smallest* distances seen so far.

You are given an array `stones` of positive integers. In each turn, you choose the two *heaviest* stones. If `x == y`, both are destroyed. If `x < y`, `x` is destroyed and `y` becomes `y - x`. This continues until at most one stone is left. Return the weight of this last stone. This problem is a direct simulation that can be made efficient by using a Max-Heap to quickly find the two heaviest stones.

Given an integer array `nums` and an integer `k`, return the `k`th largest element. This is a classic selection problem. While it can be solved with sorting (O(n log n)) or Quickselect (O(n) average), a common and easy-to-implement solution uses a Min-Heap of size `k`. This approach has an O(n log k) time complexity, which is very efficient.

The median is the middle value in a sorted list. Design a data structure that supports `addNum(num)` (adds `num` from a stream) and `findMedian()` (returns the median of all numbers added so far). This is a classic hard design problem. The key is to realize we don't need the *whole* list sorted, only the *middle* elements. This is solved efficiently using two heaps: a Max-Heap and a Min-Heap.

Given an N-ary tree, convert it to a Binary Tree. This is a classic tree transformation problem. The standard conversion is: the `left` child of a `BinaryTree` node becomes the *first child* of the `N-ary` node. The `right` child of the `BinaryTree` node becomes the *next sibling* of the `N-ary` node. This is also known as the 'left-child, right-sibling' representation.

A 'star graph' is a graph with `n` nodes where one 'center' node is connected to all other `n-1` nodes. You are given an `edges` list. Find the center. This is a simple graph problem on a tree. The center is the only node that appears in every single edge. A simpler check is to just check the first two edges.

Given the `root` of a binary tree, return the *zigzag level order traversal*. This means the first level is left-to-right, the second is right-to-left, the third is left-to-right, and so on. This is a common FAANG interview question that modifies the standard BFS. It tests your ability to manage level-specific logic and data structures (like a `deque`) to reverse the order of elements efficiently.

Given the `root` of a binary tree, return the length of the diameter. The diameter is the *longest* path between any two nodes, which may or may not pass through the root. This is a very common interview question. It's solved with a post-order DFS where the recursive function returns the *height* of a node, but *updates* a global max diameter variable by checking `left_height + right_height` at each node.

Given a binary tree, find the maximum path sum. The path may start and end at *any* two nodes in the tree and does not need to pass through the root. This is a famously hard FAANG question. The logic is similar to 'Diameter of a Binary Tree'. The recursive function returns the max 'gain' path downwards, but updates a global max for paths that 'split' at the current node.

Given the roots of two binary trees, `p` and `q`, write a function to check if they are structurally identical and have the same node values. This is a fundamental tree problem, often used as a helper function in other problems (like 'Subtree of Another Tree'). It's solved with a simple simultaneous recursion.

Given two binary trees `root` and `subRoot`, return `true` if `subRoot` is a subtree of `root` (i.e., it has the same structure and node values). A subtree must consist of a node in `root` and *all* of its descendants. This problem is solved by traversing the `root` tree and, at each node, checking if the tree rooted there is identical to `subRoot`.

Given an integer array `nums` and `k`, return the `k`th largest element. This is a classic selection problem, frequently asked by FAANG. While Quickselect is O(n) average, a very common and expected solution is to use a Min-Heap of size `k`. This approach is O(n log k) and is simple and robust. A heap is a form of a tree, so this is often grouped with tree questions.

Design a data structure that supports `addNum(num)` and `findMedian()`. This is a classic hard design problem from Google/Facebook. It's solved by using two heaps: a Max-Heap to store the smaller half of the numbers and a Min-Heap to store the larger half. This keeps the median(s) available at the roots in O(1) time. `addNum` is O(log n).

You are given an array of `k` sorted linked lists. Merge all of them into one sorted linked list and return its head. This is a very common FAANG question. A naive divide-and-conquer is O(nk log k). The optimal O(nk log k) solution (where `nk` is total nodes) uses a Min-Heap. The heap stores the *next* node from each of the `k` lists, allowing us to find the smallest overall node in O(log k) time.

Given the `root` of a *complete* binary tree, return the number of nodes. A naive O(n) traversal is too slow. The key is to use 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. This allows us to use a formula for one subtree and only recurse on the other.

Given the `root` of an N-ary tree, find the diameter (longest path between any two nodes). This is a common N-ary tree question. The logic is similar to the binary tree diameter, but for any node, the path could be between its two *deepest* children. The recursive function must return its *height*, but also update a global max diameter.

Given the `root` of a Binary Search Tree (BST), convert it to a Greater Sum Tree (GST). The value of *every* node should be changed to be the original value *plus* the sum of all values *greater than* it in the BST. This is a classic BST traversal problem. The key is to realize that a **Reverse In-order Traversal** (Right, Root, Left) visits the nodes in descending order.

Given a binary tree, return the vertical order traversal. This involves scanning the tree from left-to-right (column by column). If two nodes are in the same row and column, they should be sorted by value. This is a very common Google and Facebook question that requires a BFS (to ensure top-to-bottom order) and a map (to store nodes by column).

Given the `root` of a binary tree, determine if it is a valid Binary Search Tree (BST). This is a fundamental tree problem. A naive check of just the immediate parent and child is incorrect. The *entire* left subtree must be less than the root, and the *entire* right subtree must be greater. This is solved by passing min/max constraints down the tree.

You are given the `root` of a Binary Search Tree (BST) and a `val` to insert. Insert `val` into the BST, maintaining the BST property. Return the `root` of the modified tree. It is guaranteed that `val` does not exist in the original BST. This is a fundamental BST operation, solvable recursively or iteratively.

Given a `root` of a BST and a `key`, delete the node with `key` from the BST. Return the `root`. This is the most complex of the basic BST operations. It has three cases: 1) Node is a leaf (easy). 2) Node has one child (easy). 3) Node has two children (hard: must find the node's in-order successor or predecessor to replace it).

Given a `root`, a `target` node, and `k`, return a list of values of all nodes that are at distance `k` from the `target` node. This is a common Google question. It's tricky because you must traverse *away* from the target (downwards) and also *upwards* towards the root and into other branches. This requires augmenting the tree (e.g., with parent pointers) or doing two passes.

Given a binary tree `root`, a node `X` is 'good' if the path from the root to `X` contains no nodes with a value *greater than* `X`. Return the number of 'good' nodes. This is a very common FAANG question that is solved with a straightforward DFS. We just need to pass the *maximum value encountered so far* down the recursive path.

Given the `root` of a binary tree, determine if it is a *complete binary tree*. In a complete tree, all levels are filled except *possibly* the last. If the last level is not full, all its nodes must be as far left as possible. A `null` node cannot be followed by a non-null node in a level-order (BFS) traversal. This is the key insight.

Design an autocomplete system. For a given `prefix` (as the user types), return the top 3 'hot' (most frequent) sentences that start with that prefix. This is a very common FAANG system design / DSA problem. It's solved by combining a Trie (to store sentences and frequencies) with a Min-Heap (to find the top `k=3` results).

Given the `root` of a binary tree, return the *maximum width* of the tree. The width of one level is the distance between the two endmost non-null nodes. This is a tricky BFS problem. The key is to index the nodes as if they are in a complete binary tree (like a heap). A left child is `2*i` and a right child is `2*i + 1`. The width is then `max_index - min_index + 1` at each level.

Given two nodes `p` and `q` in a binary tree, find their LCA. Here, each node has an additional pointer to its *parent*. This is a variation of the standard LCA problem, frequently asked by FAANG. With parent pointers, the problem is no longer about tree traversal, but about finding the intersection of two linked lists.