Advanced

Mock Exam 5: Full Difficulty

The real interview gauntlet. One Medium and two Hard problems that regularly appear at FAANG companies. If you can solve all three under time pressure, you are interview-ready. Target time: 75 minutes total.

Problem 1: Merge Intervals (Medium)

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.

Examples

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap, merge to [1,6]

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: [1,4] and [4,5] are considered overlapping

Constraints

• 1 ≤ intervals.length ≤ 10⁴
• intervals[i].length == 2
• 0 ≤ start_i ≤ end_i ≤ 10⁴

Solution: Brute Force

def merge_brute(intervals):
    """Brute force: repeatedly merge overlapping pairs.

    Time: O(n^2) - scan for overlaps, repeat until none
    Space: O(n)

    Keep scanning for any two overlapping intervals,
    merge them, and repeat until no more overlaps.
    """
    intervals = [list(i) for i in intervals]
    merged = True
    while merged:
        merged = False
        i = 0
        while i < len(intervals):
            j = i + 1
            while j < len(intervals):
                a, b = intervals[i], intervals[j]
                if a[0] <= b[1] and b[0] <= a[1]:
                    intervals[i] = [min(a[0], b[0]), max(a[1], b[1])]
                    intervals.pop(j)
                    merged = True
                else:
                    j += 1
            i += 1
    return intervals

Solution: Optimal (Sort + Merge)

def merge(intervals):
    """Optimal: sort by start, then merge in one pass.

    Time: O(n log n) - sorting dominates
    Space: O(n) - output array

    After sorting, overlapping intervals are adjacent.
    Compare each interval with the last merged interval:
    - If overlapping: extend the end of the last merged
    - If not: start a new merged interval
    """
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            # Overlapping: extend the end
            merged[-1][1] = max(merged[-1][1], end)
        else:
            # Non-overlapping: add new interval
            merged.append([start, end])

    return merged

# Trace for [[1,3],[2,6],[8,10],[15,18]]:
# Sorted: [[1,3],[2,6],[8,10],[15,18]]
# Start: merged = [[1,3]]
# [2,6]: 2 <= 3 -> merge -> [[1,6]]
# [8,10]: 8 > 6 -> add -> [[1,6],[8,10]]
# [15,18]: 15 > 10 -> add -> [[1,6],[8,10],[15,18]]

# Test
print(merge([[1,3],[2,6],[8,10],[15,18]]))  # [[1,6],[8,10],[15,18]]
print(merge([[1,4],[4,5]]))                  # [[1,5]]

Problem 2: Trapping Rain Water (Hard)

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Examples

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Visual:
        #
    # . . # #
  # . # # # # # .
# # # # # # # # # #
0 1 0 2 1 0 1 3 2 1 2 1

Water (.) fills gaps between taller bars.

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints

• n == height.length
• 1 ≤ n ≤ 2 × 10⁴
• 0 ≤ height[i] ≤ 10⁵

Solution: Brute Force

def trap_brute(height):
    """Brute force: for each bar, find water above it.

    Time: O(n^2) - for each bar, scan left and right
    Space: O(1)

    Water above bar[i] = min(max_left, max_right) - height[i].
    For each bar, scan left to find max and right to find max.
    """
    n = len(height)
    water = 0
    for i in range(n):
        left_max = max(height[:i+1])
        right_max = max(height[i:])
        water += min(left_max, right_max) - height[i]
    return water

Solution: Prefix Max Arrays

def trap_prefix(height):
    """Precompute left and right max arrays.

    Time: O(n) - three passes
    Space: O(n) - two arrays

    Pre-compute the maximum height to the left
    and right of each position, then calculate
    water at each position.
    """
    n = len(height)
    if n == 0:
        return 0

    left_max = [0] * n
    right_max = [0] * n

    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], height[i])

    right_max[n-1] = height[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], height[i])

    water = 0
    for i in range(n):
        water += min(left_max[i], right_max[i]) - height[i]

    return water

Solution: Optimal (Two Pointers)

def trap(height):
    """Optimal: two pointers, O(1) space.

    Time: O(n) - single pass
    Space: O(1) - only pointers and max trackers

    Key insight: water at position i depends on
    min(left_max, right_max). We don't need both
    arrays - if left_max < right_max, water is
    determined by left_max (and vice versa).

    Move the pointer with the smaller max inward,
    accumulating water along the way.
    """
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

# Test
print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # 6
print(trap([4,2,0,3,2,5]))               # 9

Problem 3: Minimum Window Substring (Hard)

Given two strings s and t, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return "".

Examples

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: "BANC" contains A, B, and C.

Input: s = "a", t = "a"
Output: "a"

Input: s = "a", t = "aa"
Output: ""
Explanation: "a" has only one 'a', but t needs two.

Constraints

• 1 ≤ s.length, t.length ≤ 10⁵
• s and t consist of uppercase and lowercase English letters

Solution: Brute Force

from collections import Counter

def min_window_brute(s, t):
    """Brute force: check all substrings.

    Time: O(n^2 * m) where n = len(s), m = len(t)
    Space: O(n + m)

    Generate all substrings of s and check if each
    contains all characters of t.
    """
    if not s or not t:
        return ""

    t_count = Counter(t)
    min_len = float('inf')
    result = ""

    for i in range(len(s)):
        for j in range(i + len(t), len(s) + 1):
            window = s[i:j]
            w_count = Counter(window)
            if all(w_count[c] >= t_count[c] for c in t_count):
                if len(window) < min_len:
                    min_len = len(window)
                    result = window

    return result

Solution: Optimal (Sliding Window)

from collections import Counter

def min_window(s, t):
    """Optimal: sliding window with character counting.

    Time: O(n) where n = len(s), each char visited twice
    Space: O(m) where m = len(t), for the frequency map

    Expand right to include chars. When all t chars
    are covered, shrink left to find minimum window.
    Track "formed" count to know when window is valid.
    """
    if not s or not t or len(s) < len(t):
        return ""

    t_count = Counter(t)
    required = len(t_count)  # Unique chars needed

    window_count = {}
    formed = 0  # How many unique chars have enough count
    left = 0

    min_len = float('inf')
    min_left = 0

    for right in range(len(s)):
        # Add right character to window
        char = s[right]
        window_count[char] = window_count.get(char, 0) + 1

        # Check if this char's frequency matches requirement
        if char in t_count and window_count[char] == t_count[char]:
            formed += 1

        # Try to shrink window from left
        while formed == required:
            # Update minimum window
            window_size = right - left + 1
            if window_size < min_len:
                min_len = window_size
                min_left = left

            # Remove left character
            left_char = s[left]
            window_count[left_char] -= 1
            if left_char in t_count and window_count[left_char] < t_count[left_char]:
                formed -= 1

            left += 1

    return "" if min_len == float('inf') else s[min_left:min_left + min_len]

# Trace for s="ADOBECODEBANC", t="ABC":
# Expand until we have A,B,C -> "ADOBEC" (0-5)
# Shrink -> can't remove A -> min window = "ADOBEC"
# Expand further, find another valid window "CODEBA" etc.
# Eventually find "BANC" (9-12) as minimum

# Test
print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"
print(min_window("a", "a"))                 # "a"
print(min_window("a", "aa"))                # ""

Score Your Performance

Result	Score	Next Step
All 3 solved optimally in < 75 min	⭐ Exceptional	You are interview-ready. Move to Mock Exam 6.
2 solved (any approach) in < 75 min	👍 Strong	Review the missed problem pattern, then Mock Exam 6
1 solved + partial on others	🔄 Developing	Good partial credit. Practice more Hard problems.
0-1 solved	📚 Keep Practicing	Review two pointers and sliding window, retry in 5 days