Mock Interview
BCG X

Step 1 — Clarify Assumptions

• Is k always valid? (1 ≤ k ≤ number of unique elements) → assume yes
• Can there be negative numbers? → yes, hashmap handles it fine
• What if multiple elements tie in frequency? → sort them ascending by value (good edge case to raise proactively)
• Should the output preserve original order? → no, sort by frequency descending

Step 2 — Brute Force

Count frequencies naively with a loop, then sort all unique elements by frequency, take the first k.

def top_k_brute(nums, k):
    freq = {}
    for n in nums:
        freq[n] = freq.get(n, 0) + 1  # build manually

    # sort all unique elements by freq descending
    sorted_keys = sorted(freq.keys(),
                          key=lambda x: -freq[x])
    return sorted_keys[:k]
# Time: O(n + u log u)  u = unique elements  Space: O(u)

Step 3 — Optimize: HashMap + Sorted with Tuple Key

Use collections.Counter to build the frequency map in O(n), then sort with a tuple key to handle ties — (-freq, value) sorts by frequency descending, then value ascending.

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    # Step 1: build frequency map — O(n)
    freq = Counter(nums)
    # freq = {1: 3, 2: 2, 3: 1} for [1,1,1,2,2,3]

    # Step 2: sort by (-freq, value) — handles ties cleanly
    sorted_elements = sorted(freq.keys(),
                              key=lambda x: (-freq[x], x))

    # Step 3: return top k
    return sorted_elements[:k]
# Time: O(n + u log u)  Space: O(u)

Step 4 — Dry Run

nums = [4,4,2,2,3], k = 2

freq = {4: 2, 2: 2, 3: 1}

sort key (-freq, value):
  4 → (-2, 4)
  2 → (-2, 2)
  3 → (-1, 3)

sorted: [2, 4, 3]   ← 2 before 4 because (-2,2) < (-2,4)

return [:2] → [2, 4]  ✓  (tie broken by ascending value)

Step 5 — Complexity

u = number of unique elements. In the worst case u = n (all elements distinct).

Step 6 — Edge Cases

• k = 1 → returns the single most frequent element ✓
• All elements identical → freq = {x: n}, k = 1 → [x] ✓
• All elements unique → every freq = 1, sort ascending by value, return first k ✓
• Negative numbers → hashmap handles, tuple sort still works ✓

Interviewer Follow-up Questions

import heapq

def top_k_heap(nums, k):
    freq = Counter(nums)
    # heap of (freq, value) — min-heap on freq
    heap = []
    for val, cnt in freq.items():
        heapq.heappush(heap, (cnt, val))
        if len(heap) > k:
            heapq.heappop(heap)  # remove least frequent
    return [val for cnt, val in
            sorted(heap, reverse=True)]
# Time: O(n + u log k)  — better when k << u

# Ascending frequency, ascending value on tie
sorted_elements = sorted(freq.keys(),
                          key=lambda x: (freq[x], x))

# Descending frequency, descending value on tie
sorted_elements = sorted(freq.keys(),
                          key=lambda x: (-freq[x], -x))

Step 1 — Clarify Assumptions

• Can the list be empty? → yes, return 0
• Can there be zeros in the list? → problem says non-zero, but worth asking — if yes, 0 is trivially the closest
• Tie-breaking rule: if two values have the same absolute value, return the positive one
• What's the return type? Same type as input (int)
• Single element? → return it directly

Step 2 — Brute Force

Sort by absolute value, pick the first. But sorting loses control over the tie-breaking rule — need to handle that explicitly.

def closest_to_zero_brute(temps: list[int]) -> int:
    if not temps: return 0
    temps.sort(key=lambda x: (abs(x), -x))  # abs asc, positive first on tie
    return temps[0]
# Time: O(n log n)  Space: O(1)

Step 3 — Optimize: Single Pass O(n)

Track the best candidate. Update when we find a strictly closer value, or an equally close but positive value.

def closest_to_zero(temps: list[int]) -> int:
    if not temps:
        return 0

    closest = temps[0]

    for t in temps[1:]:
        # strictly closer → update
        if abs(t) < abs(closest):
            closest = t
        # equally close → prefer positive
        elif abs(t) == abs(closest) and t > 0:
            closest = t

    return closest
# Time: O(n)  Space: O(1)

Step 4 — Dry Run

temps = [-5, 5, 3]

closest = -5

t = 5: abs(5)==abs(-5) and 5>0 → closest = 5
t = 3: abs(3) < abs(5)         → closest = 3

return 3  ✓

---
temps = [-5, 5]

closest = -5
t = 5: abs(5)==abs(-5) and 5>0 → closest = 5

return 5  ✓  (tie → positive)

Step 5 — Complexity

Step 6 — Edge Cases

• Empty list → return 0 ✓
• Single element → returned immediately ✓
• All negative → returns the one with smallest absolute value ✓
• Tie between -x and +x → positive wins via elif t > 0 ✓
• Multiple ties (e.g. [-3, 3, -3, 3]) → first 3 encountered wins, then re-updated to 3 → still 3 ✓

Step 1 — Clarify Assumptions

• Should spaces be ignored? → yes (BCG example: "bad credit" / "debit card")
• Case-sensitive? → no, lowercase before comparing
• Only ASCII letters? → assume yes
• Empty strings: are they anagrams of each other? → yes (both empty after stripping)

Step 2 — Brute Force (sorted)

Sort both cleaned strings and compare. Simple but O(n log n).

def is_anagram_sort(s1: str, s2: str) -> bool:
    clean = lambda s: sorted(s.lower().replace(" ", ""))
    return clean(s1) == clean(s2)
# Time: O(n log n)  Space: O(n)

Step 3 — Optimize: HashMap O(n)

Build a frequency map for s1, decrement for s2. If all counts reach 0, they're anagrams.

def is_anagram(s1: str, s2: str) -> bool:
    # normalize: lowercase, remove spaces
    s1 = s1.lower().replace(" ", "")
    s2 = s2.lower().replace(" ", "")

    if len(s1) != len(s2):
        return False  # early exit

    count = {}
    for ch in s1:
        count[ch] = count.get(ch, 0) + 1

    for ch in s2:
        count[ch] = count.get(ch, 0) - 1
        if count[ch] < 0:
            return False  # s2 has more of this char than s1

    return True
# Time: O(n)  Space: O(1) — bounded by 26 letters

Step 4 — Dry Run

s1 = "bad credit" → "badcredit"
s2 = "debit card" → "debitcard"

Build count from s1: {b:1, a:1, d:2, c:1, r:1, e:1, i:1, t:1}

Decrement with s2:
  d→1, e→0, b→0, i→0, t→0, c→0, a→0, r→0, d→0

All counts ≥ 0 → True ✓

Step 5 — Complexity

*O(1) because alphabet is fixed size (26). O(k) if unicode.

Step 6 — Edge Cases

• Different lengths after normalization → early return False ✓
• Empty strings → len check passes (0==0), both loops skip → True ✓
• "bad credit" / "debit card" → spaces stripped before comparison ✓
• Same string twice → always True ✓

Step 1 — Clarify Assumptions

• Return indices or values? → indices
• Can the same element be used twice? → no (but two different indices with same value are OK — e.g. [3,3])
• Is the array sorted? → do not assume
• Exactly one solution guaranteed → no need to handle "not found"

Step 2 — Brute Force

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
# Time: O(n²)  Space: O(1)

Step 3 — Optimize: HashMap O(n)

For each number, check if its complement (target - num) is already in the hashmap. Store value → index as we go.

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # value → index

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i  # store AFTER check to avoid self-use

# Time: O(n)  Space: O(n)

Step 4 — Dry Run

nums=[3,2,4], target=6

i=0, num=3: complement=3, not in seen={} → seen={3:0}
i=1, num=2: complement=4, not in seen={3:0} → seen={3:0,2:1}
i=2, num=4: complement=2, 2 in seen → return [1, 2] ✓

Step 5 — Complexity

Step 6 — Edge Cases

• [3,3] target=6 → i=0 stores 3:0, i=1 complement=3 found at index 0 → [0,1] ✓ (store after check prevents self-use)
• Negative numbers → complement still works (e.g. target=0, num=-3 → complement=3) ✓
• Single element → no valid pair, but problem guarantees one exists ✓

Step 1 — Clarify Assumptions

• Is [1,4] and [4,5] overlapping? → yes, touching counts (end == start)
• Is [1,4] and [2,3] one interval? → yes, fully contained → merge to [1,4]
• Are intervals sorted on input? → do not assume, sort first
• Can the list be empty? → yes, return []

Step 2 — Brute Force sketch

Compare every pair of intervals. O(n²) — too slow for large inputs. Mention and move on.

Step 3 — Optimal: Sort + Linear Merge

Sort by start time. Iterate and either extend the current interval or start a new one.

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []

    # Sort ascending by start — O(n log n)
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for start, end in intervals[1:]:
        last_end = merged[-1][1]

        if start <= last_end:
            # overlapping → extend the current interval
            merged[-1][1] = max(last_end, end)
        else:
            # gap → start a new interval
            merged.append([start, end])

    return merged
# Time: O(n log n)  Space: O(n)

Step 4 — Dry Run

intervals = [[1,3],[2,6],[8,10],[15,18]]

After sort: [[1,3],[2,6],[8,10],[15,18]]  (already sorted)

merged = [[1,3]]

[2,6]: 2 ≤ 3 → overlap → max(3,6)=6 → merged=[[1,6]]
[8,10]: 8 > 6 → new → merged=[[1,6],[8,10]]
[15,18]: 15 > 10 → new → merged=[[1,6],[8,10],[15,18]]

return [[1,6],[8,10],[15,18]] ✓

---
Edge: [[1,4],[2,3]]
After sort: [[1,4],[2,3]]
[2,3]: 2 ≤ 4 → max(4,3)=4 → merged=[[1,4]] ✓  (contained)

Step 5 — Complexity

*Python sort is in-place (Timsort), O(log n) stack space.

Step 6 — Edge Cases

• Empty input → return [] ✓
• Single interval → returned as-is ✓
• [1,4],[4,5] → 4 ≤ 4 → merged to [1,5] ✓ (touching)
• [1,4],[2,3] → contained → max(4,3)=4 → [1,4] ✓
• All overlapping → one big interval ✓
• None overlapping → original list returned ✓

Step 1 — Clarify Assumptions

• Can I assume n is a positive integer greater than 1? → yes
• Return a list of factors or a formatted string like "2 × 2 × 3"? → list (easier to test)
• Should the list be sorted? → yes, naturally sorted by the algorithm
• What about n = 1? → 1 has no prime factors → return [] (good edge case to raise)

Step 2 — Brute Force Intuition

Try every divisor from 2 up to n. For each one, divide as many times as possible. Works but is O(n) in the worst case (e.g. n is prime).

Step 3 — Optimize: Stop at √n

Key insight: if n has no prime factor ≤ √n, then n itself is prime. So we only need to test divisors up to √n — which gives O(√n) time.

def prime_factorization(n: int) -> list[int]:
    factors = []
    divisor = 2

    while divisor * divisor <= n:  # only up to √n
        while n % divisor == 0:     # divide out all copies
            factors.append(divisor)
            n //= divisor
        divisor += 1

    if n > 1:                      # remaining n is prime
        factors.append(n)

    return factors
# Time: O(√n)  Space: O(k) — k = number of prime factors

Step 4 — Dry Run

n = 60

divisor=2: 60%2==0 → append 2, n=30
           30%2==0 → append 2, n=15
           15%2≠0 → stop
divisor=3: 15%3==0 → append 3, n=5
           5%3≠0  → stop
divisor=4: 4*4=16 > 5 → loop exits

n=5 > 1 → append 5

return [2, 2, 3, 5] ✓

---
n = 13 (prime)

divisor=2: 2*2=4 ≤ 13, 13%2≠0
divisor=3: 3*3=9 ≤ 13, 13%3≠0
divisor=4: 4*4=16 > 13 → loop exits

n=13 > 1 → append 13

return [13] ✓

Step 5 — Complexity

k is very small — at most log₂(n) factors (e.g. 2^30 has 30 factors but n ≈ 10^9).

Step 6 — Edge Cases

• n = 1 → loop doesn't execute, n=1 not > 1 → return [] ✓
• n is prime (e.g. 13) → inner loop never appends, remaining n > 1 → appended at end ✓
• n is a perfect square (e.g. 4) → divisor=2, appended twice, n=1 → return [2,2] ✓
• n is a large prime (e.g. 999983) → outer loop runs only √999983 ≈ 1000 times, not 999983 ✓

Interviewer Follow-up Questions

return " × ".join(str(f) for f in factors)
# [2, 2, 3] → "2 × 2 × 3"

def prime_factorization_opt(n: int) -> list[int]:
    factors = []
    while n % 2 == 0:          # handle 2 separately
        factors.append(2)
        n //= 2
    divisor = 3
    while divisor * divisor <= n:
        while n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        divisor += 2           # odd numbers only
    if n > 1: factors.append(n)
    return factors
# Still O(√n) but ~2x faster in practice

Step 1 — Clarify

• Can the string be empty? → yes, empty string is valid (return True)
• Only those 6 characters guaranteed? → assume yes
• What about whitespace or other chars? → not in this problem

Step 2 — Intuition

Classic stack problem. Push opening brackets. On closing bracket, check it matches the top of the stack.

Step 3 — Solution

def is_valid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping:             # closing bracket
            top = stack.pop() if stack else '#'
            if mapping[char] != top:
                return False
        else:
            stack.append(char)          # opening bracket

    return len(stack) == 0
# Time: O(n)  Space: O(n)

Step 4 — Complexity

Step 5 — Edge Cases

• Empty string → stack empty → True ✓
• Starts with closing bracket → stack empty → pop returns '#' → mismatch → False ✓
• Odd-length string → can never be valid → early return optimization
• "(((" → loop ends, stack not empty → return False ✓

Step 1 — Clarify

• Can the string be empty? → yes, return 0
• Only ASCII? → assume yes for simplicity
• Is the answer the length or the substring itself? → length

Step 2 — Brute Force

Check all O(n²) substrings, verify each in O(n). Total O(n³) — too slow. Not worth coding, just mention it.

Step 3 — Sliding Window (Optimal)

Maintain a window [left, right] with a set of current characters. Expand right; when a duplicate appears, shrink from left.

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in char_set:   # shrink until no duplicate
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len
# Time: O(n)  Space: O(k) — k = charset size

Step 4 — Complexity

Step 5 — Edge Cases

• Empty string → loop never runs → returns 0 ✓
• All same chars ("aaaa") → window always resets to size 1 ✓
• All unique → window expands to full length ✓
• Single char → returns 1 ✓

def length_of_longest_substring_opt(s: str) -> int:
    last_seen = {}
    left = 0
    max_len = 0
    for right, char in enumerate(s):
        if char in last_seen and last_seen[char] >= left:
            left = last_seen[char] + 1  # jump directly
        last_seen[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len
# Still O(n) but no inner while loop — single clean pass

Step 1 — Clarify

• Can the grid be empty? → yes, return 0
• Diagonal connections count? → no, only horizontal/vertical
• Can we modify the grid in place? → yes (if not, use a visited set)

Step 2 — Approach: DFS flood fill

Iterate the grid. When we find a '1', increment counter and DFS to mark all connected land as visited (set to '0'). This "floods" the island so we don't count it again.

def num_islands(grid: list[list[str]]) -> int:
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1': return
        grid[r][c] = '0'           # mark visited
        dfs(r+1, c); dfs(r-1, c)
        dfs(r, c+1); dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count
# Time: O(m×n)  Space: O(m×n) call stack worst case

Step 4 — Complexity

Step 5 — Edge Cases

• Empty grid → return 0 ✓
• All water → count stays 0 ✓
• All land → entire grid is one island → return 1 ✓
• Single cell '1' → return 1 ✓

from collections import deque
def bfs(r, c):
    queue = deque([(r, c)])
    grid[r][c] = '0'
    while queue:
        row, col = queue.popleft()
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = row+dr, col+dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                grid[nr][nc] = '0'
                queue.append((nr, nc))

Step 1 — Clarify

• Can input be empty? → yes, return []
• Lowercase only? → assume yes
• Sort groups by first word ascending? → yes

Step 2 — Key Insight

Two words are anagrams iff their sorted version is identical. Use that sorted string as a hashmap key to group all anagrams in one pass.

from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for word in strs:
        key = "".join(sorted(word))   # "eat" → "aet"
        groups[key].append(word)

    result = [sorted(g) for g in groups.values()]
    result.sort(key=lambda g: g[0])  # sort groups by first word
    return result
# Time: O(n·k log k)  Space: O(n·k)

Step 3 — Complexity

Step 4 — Edge Cases

• Empty list → return [] ✓
• Single char strings → sorted("a")="a" → works ✓
• All words are anagrams → one group returned ✓

def group_anagrams_ok(strs):
    groups = defaultdict(list)
    for word in strs:
        count = [0] * 26
        for ch in word:
            count[ord(ch) - ord('a')] += 1
        groups[tuple(count)].append(word)
    return [sorted(g) for g in groups.values()]
# Key building O(k) instead of O(k log k)

Step 1 — Clarify

• Array is sorted and contains distinct integers → confirmed
• Return index or value? → index
• Can array be empty? → yes, return -1

Step 2 — Solution

def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

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

    return -1
# Time: O(log n)  Space: O(1)

Step 3 — Why O(log n)?

Each iteration halves the search space. After k steps, remaining elements = n / 2^k. When n / 2^k = 1 → k = log₂(n). For n = 1,000,000: only ~20 comparisons.

Step 4 — Edge Cases

• Empty array → left=0, right=-1 → while condition false → -1 ✓
• Target smaller than all elements → right keeps shrinking → -1 ✓
• Target is first or last element → found on first or last iteration ✓
• Single element array → mid=0, check once ✓

def first_occurrence(nums, target):
    left, right, result = 0, len(nums)-1, -1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            result = mid
            right = mid - 1   # keep searching left
        elif nums[mid] < target: left = mid + 1
        else: right = mid - 1
    return result

Step 1 — Clarify

• Do we need to sort the output? → no, any order is fine
• Do we need the actual distance or just compare? → just compare → we can skip √ (monotone)
• k guaranteed ≤ len(points)? → assume yes

Step 2 — Key Insight: skip sqrt

√(x²+y²) is monotonically increasing, so we can compare x²+y² directly — no need to compute the square root. Saves computation and avoids floats.

Step 3 — Approach A: Sort (simple)

def k_closest_sort(points, k):
    points.sort(key=lambda p: p[0]**2 + p[1]**2)
    return points[:k]
# Time: O(n log n)  Space: O(1)

Step 4 — Approach B: Max-Heap of size k (optimal)

import heapq

def k_closest_heap(points: list, k: int) -> list:
    heap = []
    for x, y in points:
        dist = -(x*x + y*y)          # negate → max-heap via min-heap
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)      # remove farthest
    return [[x, y] for _, x, y in heap]
# Time: O(n log k)  Space: O(k)

Step 5 — Complexity Comparison

Step 6 — Edge Cases

• k = len(points) → return all points ✓
• Points at origin [0,0] → dist=0, always closest ✓
• Negative coordinates → x²+y² handles them correctly ✓
• k = 1 → return the single closest point ✓