Category D · 8 Problems

List & Sequence Problems

Flatten, merge, slide, rotate, transform. These problems test array manipulation, two-pointer technique, and the monotonic deque pattern.

Problems: 8
Difficulty: Easy – Hard
Key techniques: two-pointer · monotonic deque · prefix product · heapq
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 24 Coding Problem Easy
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.
Example
flatten([1, [2, [3, 4]], 5]) → [1, 2, 3, 4, 5] flatten([[1, 2], [3, [4, [5]]]]) → [1, 2, 3, 4, 5] flatten([]) → [] flatten([1]) → [1]
recursionisinstance(item, list) list.extend()base case
Solution
from typing import List, Any def flatten(nested: List[Any]) -> List[Any]: result = [] for item in nested: if isinstance(item, list): result.extend(flatten(item)) # recurse into sublists else: result.append(item) return result # Alternative: generator version (memory-efficient for huge inputs) def flatten_gen(nested): for item in nested: if isinstance(item, list): yield from flatten_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 25 Coding Problem Medium
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].
Example
merge_intervals([[1,3],[2,6],[8,10],[15,18]]) → [[1,6],[8,10],[15,18]] merge_intervals([[1,4],[4,5]]) → [[1,5]] merge_intervals([[1,4],[0,4]]) → [[0,4]]
sort by start timelinear merge scan in-place list[-1] updatemax() for end time
Solution
from typing import List def merge_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 26 Coding Problem Hard
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).
Example
sliding_max([1,3,-1,-3,5,3,6,7], k=3) → [3, 3, 5, 5, 6, 7] # windows: [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]
monotonic dequedeque stores indices remove out-of-window from frontremove smaller from back
Solution
from collections import deque from typing import List def sliding_max(nums: List[int], k: int) -> List[int]: dq: deque = deque() # stores indices; front = index of current max result = [] for i, n in enumerate(nums): # Remove indices that have left the window while 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-1 if 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 27 Coding Problem Easy
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.
Example
rotate([1,2,3,4,5], k=2) → [4,5,1,2,3] rotate([1,2,3,4,5], k=7) → [4,5,1,2,3] # 7 % 5 = 2 rotate([1,2,3], k=0) → [1,2,3]
modulo for k > lenlist slicing concatenation: nums[-k:] + nums[:-k]
Solution
from typing import List def rotate(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=2 if k == 0: return nums[:] # Take last k elements + first (n-k) elements return 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 28 Coding Problem Hard
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).
Example
product_except_self([1,2,3,4]) → [24,12,8,6] # output[0] = 2*3*4 = 24 # output[1] = 1*3*4 = 12 product_except_self([0,0]) → [0,0]
prefix product passsuffix product pass O(1) extra spacetwo-pass linear scan
Solution
from typing import List def product_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 = 1 for i in range(n): result[i] = prefix prefix *= nums[i] # Backward pass: multiply result[i] by product of all elements RIGHT of i suffix = 1 for i in range(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 29 Coding Problem Hard
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 times heapq.heappush / heapreplacegreedy allocation
Solution
import heapq from typing import List def min_rooms(intervals: List[List[int]]) -> int: if not intervals: return 0 intervals.sort(key=lambda x: x[0]) heap = [] # min-heap of end times for rooms in use for 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) return len(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 30 Coding Problem Medium
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.
Example
longest_consecutive([100,4,200,1,3,2]) → 4 # sequence: 1,2,3,4 longest_consecutive([0,3,7,2,5,8,4,6,0,1]) → 9 # 0-8
set for O(1) lookuponly start sequences at n-1 not in set while loop to extendO(n) overall
Solution
from typing import List def longest_consecutive(nums: List[int]) -> int: num_set = set(nums) # O(1) lookup best = 0 for n in num_set: # Only start a sequence if n is the true beginning (n-1 not in set) if n - 1 not in num_set: length = 1 while 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 31 Coding Problem Hard
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 + sorting max() for end during merge
Solution
from typing import List, Dict def merge_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 in reversed(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.
← Category C: Dict & Counting Category E: Nested JSON →