Practice DSA interview questions

Given a doubly linked list and an integer `k`, reverse every `k` nodes. If the number of nodes is not a multiple of `k`, the remaining nodes at the end should be left as-is. This is a complex problem combining 'Reverse k-Group' with 'Reverse Doubly Linked List'. You must reverse a sub-list by swapping `prev`/`next` pointers, and then carefully re-link the head and tail of the reversed sub-list to the main list.

Given a sorted array of integers `nums` and an integer `target`, write a function to search for `target` in `nums`. If `target` exists, return its index. Otherwise, return -1. This is the most fundamental divide-and-conquer algorithm. It works by repeatedly dividing the search interval in half. It's a cornerstone of computer science, essential for its O(log n) time complexity, making it highly efficient for searching in large, sorted datasets.

Given a sorted array of distinct integers `nums` and a `target` value, return the index if the `target` is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. This is a classic variation of Binary Search. Instead of just finding the target, we are finding the *first element greater than or equal to* the target.

Given an array of integers `nums` sorted in non-decreasing order, find the starting and ending position of a given `target` value. If `target` is not found, return `[-1, -1]`. You must write an algorithm with O(log n) runtime complexity. This problem requires two modified Binary Searches: one to find the 'leftmost' occurrence (the first position) and one to find the 'rightmost' occurrence (the last position). This is a common pattern for 'lower bound' and 'upper bound' searches.

Given a non-negative integer `x`, compute and return the integer part of its square root. Since the return type is an integer, the decimal part is truncated. You are not allowed to use any built-in exponent function or operator (like `pow(x, 0.5)`). This is a classic Binary Search problem. We are searching for a number `k` such that `k*k <= x` and `(k+1)*(k+1) > x`. The search space is from 0 to `x`.

A peak element is an element that is strictly greater than its neighbors. Given an integer array `nums`, find a peak element, and return its index. The array may contain multiple peaks; in that case, return the index to any one. You may imagine that `nums[-1] = nums[n] = -infinity`. You must write an algorithm that runs in O(log n) time. This condition strongly hints at Binary Search.

You are given a sorted array of unique elements that has been rotated. For example, `[0,1,2,4,5,6,7]` might become `[4,5,6,7,0,1,2]`. Find the minimum element in this array. You must write an algorithm that runs in O(log n) time. The minimum element is the 'pivot' or 'inflection point' where the rotation happened. This is a modified Binary Search problem.

Write an efficient algorithm that searches for a `target` in an `m x n` matrix. This matrix has two properties: 1) Integers in each row are sorted from left to right. 2) The first integer of each row is greater than the last integer of the previous row. This structure allows us to treat the entire 2D matrix as a single, 1D sorted array, which can be searched with a standard Binary Search.

You are given an array of characters `letters` that is sorted in non-decreasing order, and a character `target`. There are at least two different characters in `letters`. Return the smallest character in `letters` that is strictly greater than `target`. If no such character exists (e.g., `target` is the largest), the characters 'wrap around', so you should return the first character in the array.

Koko loves to eat bananas. There are `n` piles, `piles[i]` bananas. The guards will return in `h` hours. Koko can choose an eating speed `k`. She eats `k` bananas from a pile. If a pile has less, she eats all and waits. Find the minimum integer `k` such that she can eat all bananas within `h` hours. This is a 'Binary Search on the Answer' problem. The answer (speed `k`) has a known range, and we can check if a given `k` is 'valid'.

A conveyor belt has packages with weights `weights[i]`. Ship all packages in `D` days. You must ship them in order. You can load at most `capacity` weight per day. Find the least weight `capacity` that will result in all packages being shipped within `D` days. This is another 'Binary Search on the Answer'. The 'answer' (capacity) has a clear range, and we can check if a given capacity is valid.

Given an array `nums` and an integer `m`, split the array into `m` non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these `m` subarrays. This is a classic 'Binary Search on the Answer' problem, identical in structure to 'Capacity to Ship Packages'. The answer (the max allowed sum) is what we binary search for.

Given two sorted arrays `nums1` and `nums2` of size `m` and `n`, return the median of the two combined sorted arrays. The overall run time complexity should be O(log (m+n)). This is a very difficult Binary Search problem. The key is to binary search for the correct 'partition' in the smaller array, which in turn defines the partition in the larger array. The median is then found using the elements at the partition boundaries.

Design a time-based key-value store class `TimeMap`. `set(key, value, timestamp)` stores the key with the value at the given timestamp. `get(key, timestamp)` returns a value such that `set` was called previously, with `timestamp_prev <= timestamp`. If there are multiple such values, return the one with the largest `timestamp_prev`. If no values exist, return `"`. This problem is solved by storing a list of `(timestamp, value)` pairs for each key and using Binary Search to find the correct timestamp.

You are given an array of positions `stalls` where `n` cows can be placed. You want to place `k` cows in these stalls such that the minimum distance between any two cows is maximized. Find the largest minimum distance. This is a classic 'Binary Search on the Answer' problem. We are not searching the `stalls` array; we are searching for the optimal 'distance', which has a known range.

You are given an array `arr` of `n` books, where `arr[i]` is the number of pages in the `i`-th book. You have to allocate these books to `m` students such that the maximum number of pages assigned to a student is minimized. Each book must be allocated contiguously. This is another classic 'Binary Search on the Answer' problem, identical in structure to 'Split Array Largest Sum'.

Given an array that is sorted, but each element may have been shifted by at most one position to the left or right (i.e., `arr[i]` could be at `arr[i-1]`, `arr[i]`, or `arr[i+1]` in the final sorted array). Find a `target` element in O(log n) time. This requires a modified Binary Search that checks not just `mid`, but also its neighbors.

Given a sorted array `nums` and a value `x`, find the 'floor' and 'ceil' of `x`. The 'floor' is the largest element in the array that is less than or equal to `x`. The 'ceil' is the smallest element in the array that is greater than or equal to `x`. If they don't exist, return -1. This is a classic application of Binary Search, similar to finding 'lower bound' and 'upper bound'.

You are given a sorted array of unknown size (effectively infinite). You do not have a `length` property. You can only access it with an `array.get(index)` method, which returns the value or an error if the index is out of bounds. Find the position of a `target` in O(log n) time. This problem is solved in two parts: first, find the 'bounds' for the Binary Search, and second, perform the search.

Given an array `nums` and a `threshold`, find the smallest positive integer `divisor` such that the sum of `math.ceil(num / divisor)` for all elements in `nums` is less than or equal to `threshold`. This is a 'Binary Search on the Answer' problem. The answer (the divisor) is within a predictable range, and we can check if any given divisor is 'valid'.

Write an efficient algorithm that searches for a `target` in an `m x n` matrix. This matrix has properties: Integers in each row are sorted left-to-right. Integers in each column are sorted top-to-bottom. This is different from the 'Search a 2D Matrix I' as the matrix cannot be treated as a single sorted array. The optimal O(m+n) solution starts at a corner (e.g., top-right) and 'staircase' searches, which is a common and clever technique.

You are given a sorted array that has been rotated and *may contain duplicates*. For example, `[2,5,6,0,0,1,2]`. Given this array and a `target`, return `true` if `target` is in `nums`, or `false` otherwise. The presence of duplicates affects the time complexity. In the worst case (e.g., `[1,1,1,1,1]`), the runtime degrades to O(n), as we can no longer guarantee which half is sorted.

You are given a sorted array of elements that has been rotated and *may contain duplicates*. Find the minimum element in this array. For example, `[3,3,1,3]` or `[10,1,10,10,10]`. The presence of duplicates means we can't always determine the location of the pivot in O(log n) time. The worst-case complexity can degrade to O(n) when many elements are the same, but the average case is still O(log n).

Given an array `citations` of a researcher's citations (sorted in ascending order), compute the h-index. The h-index is defined as the maximum value `h` such that the researcher has at least `h` papers with at least `h` citations each. For example, `[0,1,3,5,6]` means 5 papers. The h-index is 3, because there are 3 papers with at least 3 citations (3, 5, 6). This can be solved in O(log n) time.

Given a positive integer `num`, write a function which returns `true` if `num` is a perfect square, and `false` otherwise. You are not allowed to use any built-in library functions like `sqrt`. This is a straightforward application of Binary Search, very similar to the 'Sqrt(x)' problem. We are searching for an integer `k` in the range `[1, num]` such that `k * k == num`.

Given a sorted integer array `arr`, two integers `k` and `x`, return the `k` closest integers to `x` from the array. The result should also be sorted. An integer `a` is closer to `x` than `b` if `|a - x| < |b - x|` or `|a - x| == |b - x|` and `a < b`. This problem can be solved by using Binary Search to find the 'starting point' of the k-sized window. We are essentially searching for the *left bound* of the optimal window.

Given a sorted array of integers `nums` and a `target`, search for `target` using a recursive Binary Search. If `target` exists, return its index, otherwise return -1. This is the recursive formulation of the classic algorithm. It uses the function call stack to manage the `left` and `right` boundaries, which are passed as arguments to the helper function. This demonstrates a clear divide-and-conquer pattern.

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element. You must solve it in O(log n) time and O(1) space. The key insight is that the array has a property: before the single element, all pairs are at `(even, odd)` indices. After the single element, all pairs are at `(odd, even)` indices.

Given an `n x n` matrix where each row and column is sorted in ascending order, return the `k`th smallest element in the matrix. Note that it is the `k`th smallest element *in the sorted order*, not the `k`th distinct element. This is a classic 'Binary Search on the Answer' problem. The answer (the value) is within the range `[matrix[0][0], matrix[n-1][n-1]]`. We can efficiently count how many elements are smaller than a `mid` value.

Given two positive integers `n` (the root) and `m` (the number), find the `n`-th root of `m`. If the root is not an integer, return the integer 'floor' of the root (or -1 if no integer root). For example, `n=3, m=27` should return 3. `n=3, m=30` should return -1 (or 3, depending on problem spec). This is a 'Binary Search on the Answer' problem. We are searching for an integer `k` in the range `[1, m]` such that `k^n <= m`.