Coding Puzzle Interview Playbook

Given an array of non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Example: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Constraints: - n == height.length - 1 <= n <= 2 * 10^4 - 0 <= height[i] <= 10^5

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input. Two intervals [a, b] and [c, d] overlap if there is any point shared between them (e.g., [1, 2] and [2, 3] overlap). Constraints: - 1 <= intervals.length <= 10^4 - intervals[i].length == 2 - 0 <= start_i <= end_i <= 10^4

You are given an $n \times n$ binary matrix `grid`. You are permitted to change at most one `0` to a `1`. An island is defined as a group of `1`s connected 4-directionally (up, down, left, right). Find and return the size of the largest possible island that can be formed after performing this operation at most once. Constraints: - $n == grid.length$ - $n == grid[i].length$ - $1 \le n \le 500$ - $grid[i][j]$ is either $0$ or $1$.

You are given an integer array `instructions`. You need to build a sorted collection by inserting elements from `instructions` one by one in the given order. The cost of inserting an element `instructions[i]` into the current collection is defined as the minimum of: 1. The number of elements currently in the collection that are strictly less than `instructions[i]`. 2. The number of elements currently in the collection that are strictly greater than `instructions[i]`. Calculate the total cost of inserting all elements from `instructions`. Since the total cost can be very large, return the result modulo $10^9 + 7$. Constraints: - `1 <= instructions.length <= 10^5` - `1 <= instructions[i] <= 10^5`

You are given an array of $k$ linked-lists `lists`, where each linked-list is sorted in ascending order. Your task is to merge all the linked-lists into a single sorted linked-list and return its head. Example: Input: `lists = [[1,4,5],[1,3,4],[2,6]]` Output: `[1,1,2,3,4,4,5,6]` Constraints: - `k == lists.length` - `0 <= k <= 10^4` - `0 <= lists[i].length <= 500` - `-10^4 <= lists[i][j] <= 10^4` - The total number of nodes in all lists does not exceed $10^4$.

You are given an integer array `prices` where `prices[i]` is the price of a given stock on the $i^{th}$ day, and an integer `k` representing the maximum number of transactions allowed. A single transaction consists of one purchase and one subsequent sale. You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Return the maximum profit you can achieve with at most `k` transactions.

You are given an `m x n` matrix `grid` of non-negative integers. Each `grid[row][col]` represents the minimum time required to enter that cell. You start at `(0, 0)` at time `t = 0`. In each second, you can move to an adjacent cell (up, down, left, right). You can only enter a cell if the current time plus one second is greater than or equal to the value at that cell. If you cannot reach a cell at the required time, you may move back and forth between previously visited cells to wait. Return the minimum time to reach the bottom-right cell `(m-1, n-1)`. If it is impossible, return -1. Constraints: - `m == grid.length`, `n == grid[i].length` - `2 <= m, n <= 1000` - `0 <= grid[i][j] <= 10^5` - `grid[0][0] == 0`

Given a string `s` and an array of strings `words` where all strings in `words` are of the same length, find all starting indices of substring(s) in `s` that represent a concatenation of every string in `words` exactly once, in any order, without any intervening characters. Example: Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively, which are permutations of ["foo","bar"]. Constraints: - 1 <= s.length <= 10,000 - 1 <= words.length <= 5,000 - 1 <= words[i].length <= 30 - s and words[i] consist of lowercase English letters.

You are given $n$ members and a set of $m$ potential crimes. Each crime $i$ requires $group[i]$ members and produces $profit[i]$ profit. A member can participate in at most one crime. A 'profitable scheme' is a subset of crimes such that the total number of members required does not exceed $n$, and the total profit generated is at least $minProfit$. Return the total number of distinct profitable schemes possible. As the result can be large, return it modulo $10^9 + 7$. Constraints: - $1 \le n, minProfit \le 100$ - $1 \le group.length = profit.length \le 100$ - $0 \le group[i], profit[i] \le 100$

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the `LRUCache` class: - `LRUCache(int capacity)`: Initialize the LRU cache with positive size `capacity`. - `int get(int key)`: Return the value of the `key` if the key exists, otherwise return -1. - `void put(int key, int value)`: Update the value of the `key` if the `key` exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the `capacity` from this operation, evict the least recently used key. The functions `get` and `put` must each run in $O(1)$ average time complexity.

Given two sorted arrays `nums1` and `nums2` of size `m` and `n` respectively, return the median of the combined sorted arrays. The solution must provide an overall run-time complexity of O(log(m+n)). Example: Input: nums1 = [1, 3], nums2 = [2] Output: 2.00000 Explanation: Combined array = [1, 2, 3] and median is 2. Input: nums1 = [1, 2], nums2 = [3, 4] Output: 2.50000 Explanation: Combined array = [1, 2, 3, 4] and median is (2 + 3) / 2 = 2.5. Constraints: - 0 <= m, n <= 1000 - 1 <= m + n <= 2000 - -10^6 <= nums1[i], nums2[i] <= 10^6

Given an M x N binary matrix `mat`, return the number of special positions in the matrix. A position (i, j) is defined as 'special' if `mat[i][j] == 1` and all other elements in the i-th row and j-th column are 0 (i.e., it is the only 1 in its respective row and column). Constraints: - m == mat.length - n == mat[i].length - 1 <= m, n <= 500 - mat[i][j] is either 0 or 1.