Following Up on Your Solution: Huge Inputs and Streams
35 min · Advanced
Need help? Ask a tutor on WhatsApp (opens in a new tab)Your first solution is rarely the last question. Interviewers ask what happens if the input is huge, arrives as a stream, is already sorted, or is queried many times. This lesson gives you a short reply for each. Use the Python DSA 150 sheet at /learn/python/dsa-sheet to find problems and try a follow-up on each one.
Follow-up questions are part of the test
A follow-up question is a change to the original problem, such as bigger input, a stream, no extra memory or repeated queries. The answer names what breaks and what you would change.
After your solution works, the interviewer changes one thing and asks what happens. This tests whether you understand your own code, not whether you memorised it.
Stay calm: restate the new condition, say which part of your solution breaks, then adjust that part.
- Input too big for memory: read it in pieces or as a stream.
- Data arrives one item at a time: keep a small running state.
- Many queries on the same data: preprocess once, answer fast.
- Less memory, sorted input, duplicates or negative numbers: say how each changes your choice of tool.
When the input is huge
A streaming algorithm reads its input one item at a time and keeps memory small, often O(1) or O(k), no matter how long the input is. A generator is Python's tool for this.
A list of ten million lines may not fit in memory. Read one line at a time and keep only what the answer needs. In Python, a file object and a generator both give items lazily.
def count_errors(lines): total = 0 for line in lines: # a file object gives one line at a time if "ERROR" in line: total += 1 return total
# with open("server.log") as log:# print(count_errors(log))Example 1 · Count matching lines without loading the file
import io
def count_errors(lines): total = 0 for line in lines: if "ERROR" in line: total += 1 return total
log = io.StringIO("start\nERROR disk\nok\nERROR network\ndone\n")print(count_errors(log))lines = (f"row {i}" for i in range(1_000_000))print(sum(1 for line in lines if line.endswith("7")))2 100000
What this code does
- The first call reads a file-like object line by line. The second uses a generator expression, so one million strings are never held together.
- Memory stays O(1). Time is O(n), because every item must be seen at least once.
Say: "Time is O(n) and extra space is O(1), because I never store the lines." A list of all lines would cost O(n) memory.
Streams: keep a small running state
A running state is the small amount of data you keep between items of a stream, such as a total, a heap of size k or a window of the last k items. It must be enough to answer after every item.
For a stream you cannot go back, so decide what to remember. Count, sum, minimum and maximum need O(1) memory. The top k needs a heap of size k. A median needs two heaps. Revise: Running median with two heaps (opens in a new tab)
import heapq
class TopK: def __init__(self, k): self.k = k self.heap = []
def add(self, value): heapq.heappush(self.heap, value) if len(self.heap) > self.k: heapq.heappop(self.heap)
def kth(self): return self.heap[0]Example 2 · Top k of a stream with a size-k heap
import heapq
k = 3heap = []for value in [5, 1, 9, 3, 7, 8, 2]: heapq.heappush(heap, value) if len(heap) > k: heapq.heappop(heap) print(value, "->", sorted(heap, reverse=True))5 -> [5] 1 -> [5, 1] 9 -> [9, 5, 1] 3 -> [9, 5, 3] 7 -> [9, 7, 5] 8 -> [9, 8, 7] 2 -> [9, 8, 7]
What this code does
- The heap holds the k largest values so far. Its smallest item is the k-th largest, and it is the one dropped when a bigger value arrives.
- Time is O(n log k) and memory is O(k), so it works for a stream of any length.
Example 3 · Moving average of the last 3 readings
from collections import deque
class MovingAverage: def __init__(self, size): self.window = deque(maxlen=size) self.total = 0
def add(self, value): if len(self.window) == self.window.maxlen: self.total -= self.window[0] self.window.append(value) self.total += value return self.total / len(self.window)
avg = MovingAverage(3)for reading in [1, 10, 3, 5]: print(round(avg.add(reading), 2))1.0 5.5 4.67 6.0
What this code does
deque(maxlen=3)drops the oldest item by itself. The code subtracts it from the total first, so each update is O(1).- Recomputing
sum(window)each time would be O(size) per reading.
Example 4 · Running median with two heaps
import heapq
low = [] # max-heap of the smaller half (stored negated)high = [] # min-heap of the larger halffor value in [5, 15, 1, 3]: heapq.heappush(low, -value) heapq.heappush(high, -heapq.heappop(low)) if len(high) > len(low): heapq.heappush(low, -heapq.heappop(high)) median = -low[0] if len(low) > len(high) else (-low[0] + high[0]) / 2 print(median)5 10.0 5 4.0
What this code does
lowkeeps the smaller half andhighthe larger half, so the median sits at their tops. Every value goes throughlowfirst so the halves stay in order.- Each value costs O(log n). Reading the median is O(1). Python's heapq is a min-heap, which is why
lowstores negated values.
Each add costs O(log k) and the memory is O(k), however long the stream is.
Repeated queries, sorted input and less memory
Preprocessing is doing work once before answering queries, such as building prefix sums or sorting, so each later query is fast. It trades memory and setup time for query time.
If the same data answers many queries, do the work once before the queries. If the input is sorted, two pointers or binary search often replace a dict and its memory. If data does not fit in memory, sort pieces and merge them. Revise: Prefix sums and range queries (opens in a new tab)
Example 5 · Answer many range sums after one setup
from itertools import accumulate
scores = [4, 8, 1, 6, 3, 9]prefix = [0] + list(accumulate(scores))queries = [(0, 2), (1, 4), (3, 5)]for left, right in queries: print(prefix[right + 1] - prefix[left])13 18 18
What this code does
- Building
prefixis one O(n) pass. Each query is then O(1), instead of O(n) for adding up the slice every time. - With q queries the cost drops from O(n times q) to O(n + q).
Example 6 · Merge sorted chunks that do not fit in memory
import heapq
chunk_a = [1, 4, 9]chunk_b = [2, 3, 10]chunk_c = [0, 5, 6]merged = heapq.merge(chunk_a, chunk_b, chunk_c)print(list(merged))[0, 1, 2, 3, 4, 5, 6, 9, 10]
What this code does
heapq.mergetakes already sorted inputs and yields one item at a time, keeping only one item per input in memory.- For k sorted chunks with n items in total, the merge costs O(n log k). This is the second half of an external sort.
Next step
Check your understanding
12 quick questions