Log Parsing Interview Practice: Streaming Aggregation and Bounded Memory

In a log parsing interview, “I will stream the file” is only the beginning of a memory argument. A single record can be enormous, a dictionary can accumulate millions of keys, and a set of event IDs can grow for the entire run. Bounded input buffering and bounded retained state are separate requirements. Explain both before promising that your solution fits the memory cap.

This guide uses an original NDJSON practice exercise, not a reported employer assessment. Official Python documentation supports the library behavior; the schema, expected outputs, and design recommendations are our own. Our local Python fixture and boundary checks passed. That verifies the stated example, not a production workload or a measured process-memory limit.

Define the contract before choosing a data structure

Our input is a binary file of UTF-8 JSON objects, one object per physical line. Each object has ts, service, status, and event_id. Extra fields are ignored; producers must not use duplicate field names. An absent final newline is allowed. Blank lines are invalid records.

For this exercise, timestamps are nonnegative integers below 2^63, and status is an integer from 100 through 599. Boolean values do not qualify as integers. The service domain is fixed to api and worker; event IDs are nonempty strings of at most 64 characters. A physical line is limited to 1,024 bytes, including its newline when present.

Count error records with status at least 500 whose timestamp falls in [100, 160). Repeated IDs count again because this version counts physical records, rather than unique business events. Input order can be arbitrary. Return both services ordered by descending error count, then alphabetically for ties, plus scalar diagnostic counts.

These choices answer different questions. Does 160 belong to the interval? No. Is a repeated ID a duplicate to suppress? No, under this contract. Does an unknown service extend the dictionary? No; it is invalid. If an interviewer specifies different behavior, change the contract and identify its state cost before changing the code.

Do not silently assume that a timestamp means seconds since epoch, that every malformed row should abort the run, or that a service name is trustworthy. A short clarification can prevent a correct algorithm from solving the wrong problem.

Trace nine records before implementing

The table abbreviates JSON fields for readability. The fixture file serializes the valid rows as JSON and includes the literal broken line.

Row	ts	service	status	event_id	Outcome
1	100	api	500	a	Count api
2	100	api	500	a	Count api again
3	100	worker	503	b	Count worker
4	150	worker	500	c	Count worker
5	99	api	500	d	Outside interval
6	160	api	500	e	Outside interval
7	120	api	200	f	Accepted, not an error
8	—	Broken JSON	—	—	Invalid
9	140	unknown	500	g	Invalid service

The result is [("api", 2), ("worker", 2)]. Diagnostics are five accepted, two outside, two invalid, and zero oversized records. The alphabetical tie rule puts api first. Accepted records include successful responses, so the accepted count is not the number of errors.

This trace is useful interview evidence because every row exercises a stated decision. Change the interval to [100, 160] and row 6 becomes eligible. Require unique IDs and row 2 no longer contributes. Change tie handling and the same counts can produce a different answer. Those are specification changes, rather than arbitrary implementation details.

Bound a physical line before decoding JSON

Official fact: Python's stream documentation provides readline(size) with a size limit; binary streams operate on bytes. A normal file iterator yields lines, but does not establish our chosen maximum record size. Python io documentation.

For a blocking binary file, this original reader bounds each read and discards the remainder of an oversized physical line without concatenating it:

MAX_LINE = 1024  # includes newline when present

def bounded_lines(stream):
    while True:
        chunk = stream.readline(MAX_LINE + 1)
        if not chunk:
            return
        if len(chunk) > MAX_LINE:
            while chunk and not chunk.endswith(b"\n"):
                chunk = stream.readline(MAX_LINE + 1)
            yield None  # one oversized physical record
        else:
            yield chunk

Reading one extra byte distinguishes a permitted maximum-length record from an oversized one. If the oversized chunk already ends in a newline, the next read starts a new record. Otherwise the loop drains bounded chunks until that newline or EOF. Count one oversized record, not one failure per chunk.

Do not decode an initial fragment and accidentally treat its remainder as another event. Do not append discarded chunks to an error message. Both mistakes defeat the purpose of the reader.

Official fact: Python warns that untrusted JSON can consume substantial CPU and memory, and recommends limiting parsed input size. Python json documentation. Our byte cap controls the size submitted to the decoder; it is not a complete hostile-input service design. A network parser also needs deadlines, cancellation, and a framing protocol appropriate to the connection.

UTF-8 decoding failures belong to the invalid-record category here. They must not shift framing for subsequent records. A final permitted line without a newline is still decoded once. These cases are more informative than testing only a neat file ending with a newline.

Keep the aggregate's key domain explicit

Initialize two counters from the fixed domain and never add a key discovered in the stream. Decode each permitted line, require an object, validate the four fields, then apply the interval and status conditions. Reject wrong types before comparing values.

The essential update is deliberately small:

counts = {"api": 0, "worker": 0}
# After decoding and validating the complete record:
if start <= ts < end:
    if status >= 500:
        counts[service] += 1

ranked = sorted(counts.items(), key=lambda item: (-item[1], item[0]))
answer = ranked[:2]

Our locally tested reference implementation adds schema validation and diagnostics. This excerpt shows the aggregate invariant: each counter equals the number of valid eligible error records seen for that service. A record outside the interval changes the outside diagnostic, but no error counter.

With maximum record size L and K allowed services, the retained object count is O(L + K), apart from fixed stream-buffer overhead. Python integer counters need O(log N) bits as N records accumulate; therefore a literal fixed-byte guarantee also needs a bounded input count or defined overflow behavior. We did not benchmark process RSS or claim a particular megabyte cap.

Scanning costs O(B) for B input bytes under the fixed record-size contract, followed by O(K log K) sorting. Oversized records still take time to drain their bytes. Streaming saves retained input memory; it does not make reading unwanted bytes free.

Why does a top-k heap not fix an unbounded dictionary?

Suppose the service field is now arbitrary and there are U distinct services. A counting dictionary retains O(U) keys even if only two winners are returned. A size-two heap used after counting reduces ranking work or ranking storage, but leaves the dictionary intact.

Official fact: Python documents heap-based nlargest and nsmallest selection, including when sorting is preferable. That describes selection behavior, not an exact bounded-state frequency algorithm. Python heapq documentation.

An exact one-pass solution for unrestricted key cardinality cannot simply discard every current nonleader. A currently rare service might later become the most frequent. Choose an explicit alternative: a bounded key domain, external aggregation, additional passes over replayable input, or an approximation with stated error and candidate-retention behavior.

Do not announce “Count-Min Sketch gives the exact top two.” A frequency sketch and identifying candidate keys are separate concerns, and collisions affect estimates. For an interview, explaining the requirement conflict clearly is stronger than attaching an approximate structure to an exact-output promise.

If external storage is permitted, discuss how you partition keys, limit each partition's memory, and merge counts. A disk-backed answer changes the resource budget; it does not satisfy an instruction that forbids external state. Confirm that trade-off with the problem setter.

What changes for deduplication and live windows?

Exact deduplication across the entire input requires remembering enough information to recognize previously seen IDs. Our physical-record counter intentionally has no such set. A bounded recent-ID cache offers a different promise: duplicates outside the retention period can count again.

Clarify ID scope and collisions. Is an ID unique globally, within a service, or only within a producer session? If the same ID arrives with different content, define whether to reject, retain the first, or treat it as an update. An ID set alone cannot implement a content-conflict policy.

The batch exercise selects a fixed timestamp interval, so input ordering does not affect its counts. A continuously moving window is different. Evicting events from the front of a queue assumes an ordering contract; late events can invalidate a simple arrival-ordered eviction rule.

Ask whether the window uses event time or arrival time, what lateness is accepted, and when a result becomes final. A bounded time span does not automatically bound the number of retained events when event rate is unrestricted. Aggregated buckets reduce state only under stated bucket granularity and key constraints, and can change boundary precision.

For restart recovery, record how far input was processed and how aggregate state relates to that position. Replaying records after restoring a counter can double count them. This is a follow-up design discussion, not a claim that the small local parser provides exactly-once processing.

Verify boundaries with an independent oracle

Our executed fixture compares the nine-row output with an independently enumerated set of valid facts. It also checks exact byte limits, oversized-line draining followed by a valid record, invalid UTF-8, Boolean timestamps, missing fields, nonobject JSON, empty input, blank lines, and a final unterminated record.

The important independence is semantic: the oracle calculates counts from known fixture facts rather than calling the parser's validator again. Otherwise a shared boundary bug could make both outputs agree.

Add a counterexample whenever a requirement changes. Unique-ID mode needs a repeated-ID test; live-window mode needs late arrival and eviction tests. Report limitations honestly: a passed fixture proves its checked cases, while peak-memory and throughput claims require separate measurement under the intended runtime and input distribution.

Sources and Further Reading

• Python: io — Core tools for working with streams
• Python: json — JSON encoder and decoder
• Python: heapq — Heap queue algorithm