Pattern recognition:
"Sliding window" → deque or two pointers.
"Merge overlapping" → sort first, then linear scan.
"Without division" → prefix and suffix products.
"Minimum resources" → sort events, use a heap.
P 24Coding ProblemEasy
Flatten Nested List
Given an arbitrarily nested list like [1, [2, [3, 4]], 5], return a flat list [1, 2, 3, 4, 5].
The nesting can be any depth. Non-list items should appear in their original order.
recursionisinstance(item, list)list.extend()base case
Solution
from typing import List, Any
defflatten(nested: List[Any]) -> List[Any]:
result = []
for item in nested:
ifisinstance(item, list):
result.extend(flatten(item)) # recurse into sublistselse:
result.append(item)
return result
# Alternative: generator version (memory-efficient for huge inputs)defflatten_gen(nested):
for item in nested:
ifisinstance(item, list):
yield fromflatten_gen(item)
else:
yield item
Key ideas: Recursion is natural here — the problem has a self-similar structure (a nested list contains nested lists).
Use extend (not append) to add the flattened sublist directly.
The generator version uses yield from to delegate recursion — it produces items lazily so it never builds the full result list in memory.
Both are O(n) where n is the total number of non-list items.
P 25Coding ProblemMedium
Merge Intervals
Given a list of [start, end] intervals, merge all overlapping intervals and return the result.
Two intervals overlap if one starts before the other ends: [1,3] and [2,4] → [1,4].
sort by start timelinear merge scanin-place list[-1] updatemax() for end time
Solution
from typing import List
defmerge_intervals(intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
# Sort by start time — makes overlapping intervals adjacent
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
# Overlapping — extend the last interval's end if needed
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
Key insight: After sorting by start time, any overlapping intervals must be adjacent.
So a single linear scan suffices — compare each interval to the last one in the merged list.
Use max(merged[-1][1], end) because one interval may be fully contained inside another (e.g., [1,10] contains [2,5]).
Time: O(n log n) dominated by the sort.
P 26Coding ProblemHard
Sliding Window Maximum
Given a list and window size k, return a list where each element is the maximum
value in the sliding window of size k as it moves from left to right.
Must run in O(n) time — not O(n·k).
monotonic dequedeque stores indicesremove out-of-window from frontremove smaller from back
Solution
from collections import deque
from typing import List
defsliding_max(nums: List[int], k: int) -> List[int]:
dq: deque = deque() # stores indices; front = index of current max
result = []
for i, n inenumerate(nums):
# Remove indices that have left the windowwhile dq and dq[0] < i - k + 1:
dq.popleft()
# Remove indices whose values are smaller than current# (they can never be the max while current element is in the window)while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
# Window is full starting at index k-1if i >= k - 1:
result.append(nums[dq[0]])
return result
Key insight — monotonic deque: The deque stores indices in decreasing order of their values.
The front is always the index of the maximum in the current window.
Two maintenance steps: (1) remove expired indices from the front; (2) remove indices with smaller values from the back — they're useless because the new element is larger and will outlast them in the window.
Each index is added and removed at most once → O(n) total.
P 27Coding ProblemEasy
Rotate List by K Positions
Rotate the list k positions to the right. Elements shifted off the right end wrap around to the front.
Handle k larger than the list length. Return a new list.
modulo for k > lenlist slicingconcatenation: nums[-k:] + nums[:-k]
Solution
from typing import List
defrotate(nums: List[int], k: int) -> List[int]:
n = len(nums)
if n == 0:
return nums
k = k % n # normalise: k=7 on a list of 5 is the same as k=2if k == 0:
return nums[:]
# Take last k elements + first (n-k) elementsreturn nums[-k:] + nums[:-k]
Key ideas: The modulo operation handles k > n cleanly.
Slicing: nums[-k:] gives the last k elements (the "tail" that wraps around), nums[:-k] gives the rest.
The slice pattern nums[-k:] + nums[:-k] is the most concise Python way to rotate.
One subtlety: if k == 0 after modulo, nums[:-0] returns [] (not the full list!), so handle it explicitly.
P 28Coding ProblemHard
Product of Array Except Self
Given a list of integers, return a list where output[i] equals the product of all elements except nums[i].
Do not use division. Must run in O(n) time and O(1) extra space (output array doesn't count).
prefix product passsuffix product passO(1) extra spacetwo-pass linear scan
Solution
from typing import List
defproduct_except_self(nums: List[int]) -> List[int]:
n = len(nums)
result = [1] * n
# Forward pass: result[i] = product of all elements LEFT of i
prefix = 1for i inrange(n):
result[i] = prefix
prefix *= nums[i]
# Backward pass: multiply result[i] by product of all elements RIGHT of i
suffix = 1for i inrange(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
The trick: product_except_self[i] = (product of everything left of i) × (product of everything right of i).
Pass 1 (left to right): fill result[i] with prefix product up to but not including i.
Pass 2 (right to left): multiply each result[i] by the suffix product, accumulating as we go.
No division needed. No extra arrays needed — only two scalar variables (prefix, suffix).
Time: O(n). Space: O(1) extra.
P 29Coding ProblemHard
Minimum Meeting Rooms
Given a list of meeting intervals [start, end], find the minimum number of meeting rooms required
so that no two meetings in the same room overlap.
Example
min_rooms([[0,30],[5,10],[15,20]]) → 2
# At t=5: meetings [0,30] and [5,10] both running → need 2 rooms
min_rooms([[7,10],[2,4]]) → 1
# They don't overlap → 1 room suffices
sort by start timemin-heap of end timesheapq.heappush / heapreplacegreedy allocation
Solution
import heapq
from typing import List
defmin_rooms(intervals: List[List[int]]) -> int:
if not intervals:
return0
intervals.sort(key=lambda x: x[0])
heap = [] # min-heap of end times for rooms in usefor start, end in intervals:
if heap and heap[0] <= start:
# The earliest-ending room is free — reuse it
heapq.heapreplace(heap, end)
else:
# No free room — need a new one
heapq.heappush(heap, end)
returnlen(heap)
Key insight: Sort meetings by start time. Use a min-heap to track the end times of rooms in use.
When a new meeting starts, check if the earliest-ending room is free (its end time <= new start time).
If yes: reuse it (replace its end time with the new meeting's end).
If no: open a new room (push to heap).
The heap size at the end equals the peak number of simultaneous meetings.
Time: O(n log n).
P 30Coding ProblemMedium
Longest Consecutive Sequence
Given an unsorted list of integers, find the length of the longest sequence of consecutive integers.
Must run in O(n) time — no sorting allowed.
set for O(1) lookuponly start sequences at n-1 not in setwhile loop to extendO(n) overall
Solution
from typing import List
deflongest_consecutive(nums: List[int]) -> int:
num_set = set(nums) # O(1) lookup
best = 0for n in num_set:
# Only start a sequence if n is the true beginning (n-1 not in set)if n - 1not in num_set:
length = 1while n + length in num_set:
length += 1
best = max(best, length)
return best
The key trick: Only start counting a sequence from its smallest element.
Check n - 1 not in num_set — if true, n is the start of a streak.
Then extend the streak as far as possible using set lookups.
Why is this O(n)? Each number is only counted once — either it's a start and we count its streak, or it's visited during another number's streak extension. Total work across all starting points is still O(n).
P 31Coding ProblemHard
Merge Overlapping PII Spans, Then Redact
A PII API sometimes returns overlapping entities (e.g., one detector flags [0,20] as a NAME, another flags [10,30] as an ADDRESS).
Before redacting, merge all overlapping (start, end) spans into single spans.
Then redact the merged spans right-to-left. Assign the type of the first (leftmost) entity when merging.
Return the redacted text.
Example
text = "Hello Alice Johnson, please call 555-867-5309 for details."
entities = [
{"start_offset": 6, "end_offset": 18, "type": "NAME"},
{"start_offset": 13, "end_offset": 20, "type": "LAST_NAME"}, # overlaps NAME
{"start_offset": 33, "end_offset": 45, "type": "PHONE"},
]
# After merge: [{6,20,"NAME"}, {33,45,"PHONE"}]
→ "Hello [NAME] please call [PHONE] for details."
sort by startinterval merge (same as Merge Intervals)right-to-left replacementlist of dicts + sortingmax() for end during merge
Solution
from typing import List, Dict
defmerge_and_redact(text: str, entities: List[Dict]) -> str:
if not entities:
return text
# Step 1: Sort by start offset
entities = sorted(entities, key=lambda e: e["start_offset"])
# Step 2: Merge overlapping spans (keep the type of the leftmost entity)
merged: List[Dict] = [entities[0].copy()]
for entity in entities[1:]:
last = merged[-1]
if entity["start_offset"] <= last["end_offset"]:
# Overlapping: extend the end, keep existing type (leftmost entity wins)
last["end_offset"] = max(last["end_offset"], entity["end_offset"])
else:
merged.append(entity.copy())
# Step 3: Redact right-to-left (reversed merged list = right-to-left order)for entity inreversed(merged):
s = entity["start_offset"]
e = entity["end_offset"]
t = entity["type"]
text = text[:s] + f"[{t}]" + text[e:]
return text
Two-phase solution:
Phase 1 is exactly the Merge Intervals problem (Category D, P22) — sort by start, then scan linearly and extend overlapping spans.
Phase 2 is the PII Redaction right-to-left replacement (Category A, P09).
Combining these two classic patterns is what makes this a "hard" interview question — you need to recognise both sub-problems.
entity.copy() prevents mutation of the original input dicts.