Advanced Problem Solving Techniques Questions

Master advanced techniques: binary search variants (finding boundaries, rotated arrays), greedy algorithms with justification for why greedy works, interval problems (merging, scheduling), and matrix problems (paths, rotations). Understand when each technique applies and when it doesn't. Know common gotchas: greedy doesn't always work (coin change is DP, not greedy), binary search requires specific properties, etc. Practice recognizing problem patterns that hint at specific techniques.

EasyTechnical

47 practiced

Implement binary search in Python: given a sorted ascending list of integers nums and an integer target, return the index of target or -1 if not found. Function signature: def binary_search(nums: List[int], target: int) -> int. Ensure O(log n) time and handle empty array and ordinary duplicates. Example: nums=[1,2,4,5,6], target=4 -> returns 2. Explain edge cases and show runtime and space complexity.

Sample Answer

Use an iterative binary search that keeps a left and right pointer and repeatedly halves the search range until target is found or range is empty. This is O(log n) time and O(1) space.

python

from typing import List

def binary_search(nums: List[int], target: int) -> int:
    """
    Returns index of target in sorted ascending nums, or -1 if not found.
    Handles empty list and duplicates (returns any matching index).
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2  # avoids overflow in other languages
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Key points:- Iterative approach avoids recursion overhead.- For duplicates this returns one valid index (the first/last occurrence requires slight modification).- mid calculation prevents potential overflow (habit from other languages).

Time complexity: O(log n) — each step halves the search space.Space complexity: O(1) — constant extra space.

Edge cases:- Empty list -> returns -1.- Single-element list -> correctly compares and returns 0 or -1.- Target smaller than all or larger than all -> returns -1.- All elements equal -> returns any index where value equals target (or -1 if different).

EasyTechnical

38 practiced

Check whether matrix B is a rotation of matrix A by a multiple of 90 degrees (Python): given two N x N matrices A and B, implement def is_rotation(A,B) -> bool that returns true if B equals A rotated by 0/90/180/270 degrees. Aim for clear code and O(n^2) time and O(1) extra space if possible.

Sample Answer

To solve this, compare B to A for each rotation (0°, 90°, 180°, 270°) using index mapping instead of creating rotated copies. Each check visits every element once → O(n^2) time total and O(1) extra space.

python

def is_rotation(A, B):
    """
    Return True if B equals A rotated by 0/90/180/270 degrees.
    A and B are lists of lists (N x N).
    """
    n = len(A)
    if n == 0:
        return True  # treat empty matrices as equal
    if any(len(row) != n for row in A) or any(len(row) != n for row in B):
        return False
    if n != len(B):
        return False

    def check_rotation(k):
        # k = 0,1,2,3 corresponding to 0°,90°,180°,270° clockwise
        for i in range(n):
            for j in range(n):
                if k == 0:
                    ai, aj = i, j
                elif k == 1:
                    ai, aj = n - 1 - j, i
                elif k == 2:
                    ai, aj = n - 1 - i, n - 1 - j
                else:  # k == 3
                    ai, aj = j, n - 1 - i
                if A[ai][aj] != B[i][j]:
                    return False
        return True

    for k in range(4):
        if check_rotation(k):
            return True
    return False

Key points:- Index mapping for each 90° step avoids extra arrays.- Time complexity: O(n^2) (4 checks but constant factor).- Space complexity: O(1) extra.Edge cases:- Empty matrix, non-square inputs, differing sizes, duplicate values — all handled.Alternative: Physically rotate A into temporary matrices and compare (simpler code but uses O(n^2) extra space).

MediumTechnical

47 practiced

Binary search on answer / Aggressive cows problem in Python: given stall positions (ints) and integer k (number of cows), place cows to maximize the minimum distance between any two cows. Implement def max_min_distance(stalls: List[int], k: int) -> int using binary search on distance and a feasible-check function. Explain correctness and complexity for up to 10^5 stalls.

Sample Answer

We can binary-search the maximum minimum distance D: for a candidate D, greedily place cows left-to-right (always put next cow at the earliest stall at least D away from last placed). If we can place >= k cows, D is feasible; otherwise not. Feasibility is monotonic in D so binary search works.

python

from typing import List

def max_min_distance(stalls: List[int], k: int) -> int:
    if k <= 1:
        return 0
    stalls.sort()
    n = len(stalls)

    def can_place(d: int) -> bool:
        # place first cow at stalls[0]
        count, last = 1, stalls[0]
        for i in range(1, n):
            if stalls[i] - last >= d:
                count += 1
                last = stalls[i]
                if count >= k:
                    return True
        return False

    lo, hi = 0, stalls[-1] - stalls[0] + 1  # hi is exclusive
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if can_place(mid):
            lo = mid
        else:
            hi = mid
    return lo

Correctness:- The predicate "feasible(d)" is monotonic: if distance d is feasible, any smaller d' < d is also feasible (easier to place).- Greedy is optimal: placing each cow as early as possible never reduces future options and thus maximizes count for given d.

Complexity:- Sorting O(n log n). Each feasibility check is O(n). Binary search over distance range W = max-min uses O(log W) iterations. Total O(n log n + n log W). For stalls ≤ 1e5 this is efficient; W ≤ 10^9 gives ~30 checks.

Edge cases:- k <= 1 return 0; identical stall positions handled by sort and check; ensure hi exclusive to avoid infinite loop.

MediumTechnical

77 practiced

Count number of intersecting interval pairs using sweep-line in C++: given N intervals, return the count of unordered pairs (i,j) that intersect. Implement an O(n log n) algorithm and discuss how to handle open vs closed interval endpoints and when the result may be very large.

Sample Answer

Approach (brief): Use a sweep-line over events: transform each interval into two events (start, end). Sort events by coordinate; at each start event the number of currently active intervals equals how many intervals this new interval intersects with. Add active to the answer, then increment active. At an end event decrement active. To handle open vs closed endpoints, break ties by event type: for closed intervals [l,r] process starts before ends at the same coordinate (so touching endpoints count); for open intervals (l,r) process ends before starts (so touching endpoints don't count).

C++ implementation:

cpp

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

struct Event {
    long long x;
    int type; // +1 = start, -1 = end
};
// type ordering depends on inclusive/exclusive behavior

long long countIntersections(vector<pair<long long,long long>>& intervals, bool endpointsClosed=true) {
    vector<Event> ev;
    ev.reserve(intervals.size()*2);
    for (auto &p : intervals) {
        long long l = p.first, r = p.second;
        // assume l <= r; if not, swap or ignore invalid
        ev.push_back({l, +1});  // start
        ev.push_back({r, -1});  // end
    }
    sort(ev.begin(), ev.end(), [&](const Event &a, const Event &b){
        if (a.x != b.x) return a.x < b.x;
        if (endpointsClosed) {
            // starts should come before ends so [l,r] touching counts
            return a.type > b.type; // +1 > -1 so starts first
        } else {
            // ends before starts so (l,r) touching doesn't count
            return a.type < b.type; // -1 < +1 so ends first
        }
    });

    long long active = 0;
    __int128 ans128 = 0; // guard against overflow
    for (auto &e : ev) {
        if (e.type == +1) {
            ans128 += active; // new start intersects all currently active intervals
            active++;
        } else {
            active--;
        }
    }
    // convert back safely
    long long maxLL = numeric_limits<long long>::max();
    if (ans128 > maxLL) return maxLL; // or throw/handle overflow as needed
    return (long long)ans128;
}

Key points:- Sorting events: O(n log n). Sweep: O(n). Total O(n log n) time, O(n) extra space.- Use 64-bit counters (or __int128 for accumulation) because pairs can be large (up to n*(n-1)/2).- Tiebreaker rule controls whether touching endpoints count: - closed [l,r]: process start before end at same coordinate → touching counts - open (l,r): process end before start → touching doesn't count- Edge cases: zero-length intervals (l==r), intervals with l>r (validate), empty input.- If result can exceed 64-bit, either clamp, return big-integer, or document overflow behavior.

MediumTechnical

42 practiced

Unique paths in a grid with obstacles (Python): given an m x n grid where 0 indicates empty and 1 indicates obstacle, compute number of unique paths from top-left to bottom-right moving only right or down. Implement def unique_paths_with_obstacles(grid: List[List[int]]) -> int and discuss time/space trade-offs and modulo when counts are large.

Sample Answer

To solve this, use dynamic programming: dp[i][j] = number of ways to reach cell (i,j). If a cell is an obstacle (1) its ways = 0. Transition (only right/down): dp[i][j] = dp[i-1][j] + dp[i][j-1]. We can optimize space to O(n) by keeping a single row.

python

from typing import List

def unique_paths_with_obstacles(grid: List[List[int]], mod: int = None) -> int:
    """
    Returns number of unique paths from top-left to bottom-right moving only right/down.
    If mod is provided, return count % mod to avoid large integers.
    """
    if not grid or not grid[0]:
        return 0

    m, n = len(grid), len(grid[0])
    # If start or end is blocked, no paths
    if grid[0][0] == 1 or grid[m-1][n-1] == 1:
        return 0

    # 1D dp for the current row: dp[j] = ways to reach cell in current row, column j
    dp = [0] * n
    dp[0] = 1  # start cell

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[j] = 0  # obstacle -> 0 ways
            else:
                if j > 0:
                    dp[j] = (dp[j] + dp[j-1]) if mod is None else (dp[j] + dp[j-1]) % mod
                # if j == 0, dp[j] remains as previous (only from top)
    return dp[-1]

Key points:- Time: O(m * n) — we visit each cell once.- Space: O(n) with the 1D dp; naive 2D dp is O(m * n).- Use modulo (e.g., 10**9+7) if counts may exceed integer limits or to match problem constraints; pass as mod argument.Edge cases:- Empty grid, single cell grid, start/end blocked, rows or columns of obstacles.Alternative:- 2D dp matrix for clarity (easier debugging), or use combinatorics only when no obstacles.

Unlock Full Question Bank

Get access to hundreds of Advanced Problem Solving Techniques interview questions and detailed answers.

Join thousands of developers preparing for their dream job.