Practice DSA interview questions

Given an integer array `nums` and a positive integer `k`, return the most competitive subsequence of `nums` of size `k`. A subsequence `a` is more competitive than `b` (of the same length) if at the first position where `a` and `b` differ, `a`'s element is smaller. For example, `[1, 3, 5]` is more competitive than `[1, 3, 6]`. This is a classic monotonic stack problem. We want to build an increasing (as much as possible) subsequence.

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. Implement the `MovingAverage` class: `MovingAverage(size)` initializes the object with the window size. `double next(val)` adds `val` to the stream and returns the moving average of the last `size` elements. A queue is the perfect data structure to maintain the sliding window.

Design a hit counter which counts the number of hits received in the past 5 minutes (300 seconds). Implement the `HitCounter` class: `HitCounter()` initializes the object. `void hit(timestamp)` records a hit at `timestamp` (in seconds). `int getHits(timestamp)` returns the number of hits in the past 300 seconds from the given `timestamp`. All `timestamp` values are monotonically increasing. A queue is a natural fit for this problem.

You are given an `m x n` grid `rooms` initialized with three values: -1 (a wall or an obstacle), 0 (a gate), or INF (an empty room, which we can represent as 2^31 - 1). Fill each empty room with its distance to the *nearest* gate. If a room is unreachable, it should remain INF. This is a classic multi-source Breadth-First Search (BFS) problem, which is implemented with a queue.

You have a 4-wheel lock. Each wheel has 10 slots: '0' to '9'. The wheels rotate circularly. The lock starts at '0000'. You are given a list `deadends`, and if the lock displays any of these, it freezes. You are also given a `target` combination. Return the minimum total number of turns required to open the lock, or -1 if impossible. This is a shortest path problem on a graph, solvable with BFS.

Given an integer `n`, return the least number of perfect square numbers (e.g., 1, 4, 9, 16, ...) that sum to `n`. For example, `n = 12` returns 3 because `12 = 4 + 4 + 4`. `n = 13` returns 2 because `13 = 4 + 9`. This problem can be solved using dynamic programming, but it can also be modeled as a shortest path graph problem and solved with Breadth-First Search (BFS).

Given an undirected graph, return `true` if and only if it is bipartite. A graph is bipartite if we can partition its nodes into two independent sets, A and B, such that every edge in the graph connects a node in set A and a node in set B. This is a classic graph coloring problem. We can use BFS (with a queue) or DFS (with a stack) to attempt a 2-coloring.

Serialization is converting a data structure into a string. Deserialization is the reverse. Design an algorithm to serialize and deserialize a binary tree. A common method is to use a level-order traversal (BFS) with a queue. This method handles `null` children explicitly, often by adding a special marker (like 'N' or 'null') to the queue to represent an empty spot. This ensures the tree's structure is preserved.

You are given a list of airline tickets `[from, to]`. Reconstruct the itinerary in order, starting from 'JFK'. The itinerary must use all tickets once and only once. If there are multiple valid itineraries, return the one that has the smallest lexical order. This is a graph traversal problem. Specifically, it's about finding an Eulerian path. A stack-based iterative DFS (Hierholzer's algorithm) is a great approach.

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a `val` and a list of its `neighbors`. A deep copy means creating new nodes with the same values and connections. This is a classic graph traversal problem. A hash map is essential to map old nodes to their new copies, preventing infinite loops.

You are given a nested list of integers `nestedList`. Each element is either an integer or a list. Implement an iterator to flatten it. The `next()` method should return the next integer, and `hasNext()` should return `true` if there are more integers. This is a classic problem solved using a stack. The stack is used to 'unpack' the nested lists in a depth-first-search-like manner.

Write a function that takes a string as input and returns the string reversed. This is a foundational recursion problem that demonstrates the concept of a call stack. The function calls itself with a smaller subproblem (the rest of the string) and then appends the first character to the end of the result. This 'builds' the string in reverse as the call stack unwinds. It's a classic example of 'head' recursion.

The Fibonacci sequence, denoted `F(n)`, is a series of numbers in which each number is the sum of the two preceding ones, starting from 0 and 1. That is, `F(0) = 0`, `F(1) = 1`, and `F(n) = F(n - 1) + F(n - 2)` for `n > 1`. Write a function to compute `F(n)`. While this has a straightforward recursive solution, it's famously inefficient due to redundant calculations. It's often the first example used to introduce memoization (top-down dynamic programming).

Implement `pow(x, n)`, which calculates `x` raised to the power `n`. This problem can be solved with a simple recursive loop, but the optimal solution uses a technique called **exponentiation by squaring** or binary exponentiation. This divide-and-conquer approach reduces the number of multiplications from O(n) to O(log n) by repeatedly squaring the base `x` and handling the exponent `n` based on whether it's even or odd.

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 `nums` of distinct integers, return all the possible permutations. You can return the answer in any order. Like the subsets problem, this is a classic backtracking problem. The key difference is that instead of just deciding to include/exclude, we are deciding the *order*. We must ensure that each element is used exactly once in each permutation. This is often managed with a `visited` set or by swapping elements.

Given an integer array `nums` that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. This is a variation of the 'Subsets' problem. The challenge is to avoid generating duplicate subsets. This is achieved by sorting the input array and then, within the recursive loop, skipping over any duplicates to ensure each number is only used once at a particular position in the subset.

Given a collection of numbers `nums` that might contain duplicates, return all possible unique permutations in any order. This problem combines the ideas from 'Permutations I' and 'Subsets II'. We need to generate all permutations while skipping duplicates. Sorting the array and using a `visited` array is a common and effective way to manage this.

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

Given a collection of `candidates` (which might have duplicates) and a `target` integer, find all unique combinations in `candidates` where the numbers sum to `target`. Each number in `candidates` may only be used once in each combination. This problem is a mix of 'Combination Sum' and 'Subsets II'. We must handle duplicates in the input and are not allowed to reuse elements.

Given `n` pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, if `n = 3`, the output is `["((()))","(()())","(())()","()(())","()()()"]`. This is a classic recursive backtracking problem where the 'state' we track is the number of open and closed parentheses used so far. The constraints for a valid state are key.

The N-Queens puzzle is the problem of placing `n` chess queens on an `n x n` chessboard so that no two queens attack each other. Given an integer `n`, return all distinct solutions. Each solution must contain the board configuration. This is the quintessential backtracking problem. We place queens row by row, and for each row, we try placing a queen in each column. We must check if the placement is 'safe' (not attacked by queens in previous rows).

You are given the heads of two sorted linked lists, `list1` and `list2`. Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list. This problem has a simple and elegant recursive solution. It's a classic divide-and-conquer approach.

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed). For example, `1->2->3->4` becomes `2->1->4->3`. This can be solved iteratively, but the recursive solution is very clean. We solve the problem for the sub-list and then attach the head.

Given the `head` of a singly linked list, reverse the list, and return the reversed list's head. This is another fundamental linked list problem with a classic recursive solution. The idea is to recursively reverse the *rest* of the list (everything after the head) and then attach the head to the end of that reversed list.

Given the `root` of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. This is a very common and simple tree recursion problem. The depth of a tree is defined by the depth of its subtrees.

Given the `root` of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). For example, a tree with root 1, left child 2, and right child 2 is symmetric. This problem is solved by a modified tree traversal. We need a helper function that compares two nodes at a time: the left child and the right child.

Given the `root` of a binary tree, invert the tree, and return its root. Inverting a tree means that for every node, its left and right children are swapped. This is a famous problem and a perfect example of a simple, top-down recursive solution. We solve the problem for the current node and then recursively tell its children to do the same.

Given the `root` of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be BSTs. A simple in-order traversal won't work. The key is to pass down min/max constraints.

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes `p` and `q` in the BST. The LCA is defined as the lowest node that has both `p` and `q` as descendants. Because this is a BST, we can use the BST properties to find the LCA efficiently. The LCA is the node where `p` and `q` split into different subtrees.