Event and log processing problems, step by step: per-key state, sorts and heaps

In this article

1. Before you start
2. Why interviewers ask this
3. Event and log processing from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Every problem on this page is one step of the industry coding rounds guide, where the format of these rounds is explained.

Why interviewers ask this

Event and log processing problems appear because real systems are mostly records arriving and someone asking a summary question about them. Candidates report versions of this task from loops at Atlassian, Amazon, Microsoft, Reddit and Apple: top words in sentences, average rating per support agent, users who broke an entry and exit sequence, and a streaming top-k.

The task is short, so interviewers look at habits. A weak answer starts typing before asking what a tie means, sorts inside a loop, or averages the wrong thing. A strong answer states the input and the output, names the state kept per key, gives the time cost in the number of records and the number of distinct keys, and says what changes when the data no longer fits in memory. A Staff-level answer also states the tie rule and the error of any approximate method.

Event and log processing from first principles

Event and log processing problem

An event and log processing problem is a coding task that gives you a list of records, such as sentences, ratings or attendance rows, and asks for a summary computed per key, such as a word count, an average per agent or the users who broke a rule.

Per-key state

Per-key state is the small piece of memory a program keeps for each distinct key while it reads records, such as a count, a running sum and count, or an inside-or-outside flag, so each record updates one entry and no second pass over earlier records is needed.

Top-k query

A top-k query is a request for the k keys with the largest values, such as the k most frequent words, answered by sorting all keys or by keeping a min-heap that never holds more than k of them.

In plain words

Picture a ballot count with a tally sheet. Each ballot is read once. You find the candidate's row and add a mark. At the end you read the sheet and announce the winners. You never reread old ballots. The analogy breaks when there are very many candidates, because the sheet itself no longer fits on the table.

That is the whole family of problems. A log is a list of ballots. The key is the row of the sheet. The state is the marks in that row. In one precise sentence, you stream over the records once, update one state per key, and then turn the states into the requested answer.

Step 1: Turn each record into a key and a value

Each record becomes a key and a value: the key is the thing you group by, and the value is the thing you accumulate. The input is one raw record and the output is a pair. For a sentence the records are words, the key is the lower-cased word and the value is one. For a rating the key is the agent and the value is the score. For an attendance row the key is the user and the value is the action.

Ask three questions before coding: what is the key, what is a legal value, and what should happen to a bad record. Words may need punctuation stripped and a single case, so "The" and "the" are one key. Decide the rule aloud, because the interviewer cannot read your assumption.

You now know what to group by. The next step decides what to remember for each group, and that choice is where most wrong answers start.

Step 2: Keep one small state per key

Per-key state is the smallest thing from which the answer can be rebuilt. For a frequency question the state is one counter. For an average the state is a pair, the running sum and the running count, never an average without its count. For a rule such as entry then exit then entry then exit, the state is one flag per user: inside or outside.

The common error is averaging averages. If you average each day's average rating for an agent, a day with one rating counts as much as a day with four. The true average is the total of all ratings divided by the number of ratings, so keep both totals and divide once at the end. The worked example below shows an agent ranking that flips because of this.

Input: a key and a value. Output: the updated state of that key only. Each record touches one entry, so the work is linear in the number of records.

Step 3: Turn the state into an answer with a sort or a heap

The final answer is a function of the states, usually ordered. To list all agents by average, sort every entry by value descending. To get only the top k, either sort all entries or keep a min-heap of size k, where a new entry replaces the smallest only if it is larger. Sorting costs about the number of distinct keys times its logarithm. The heap costs about the number of distinct keys times the logarithm of k, which is smaller when k is small.

Ties need a rule. Python's Counter.most_common orders elements with equal counts by first encounter. A stable sort is a sort that keeps equal items in their input order. A plain heap built with heappush and heappop does not keep equal items in insertion order (the heapq docs list sort stability as a priority-queue challenge), so put the tie rule inside the key and the result no longer depends on input order.

from collections import Counter
import heapq
import string

def top_words(sentences, n):
    # lower-case and strip surrounding punctuation so "The," and "the" are one key
    words = (w.strip(string.punctuation) for s in sentences for w in s.lower().split())
    counts = Counter(w for w in words if w)
    # key: highest count first, then alphabetical, so ties follow a rule you chose
    return heapq.nsmallest(n, counts.items(), key=lambda kv: (-kv[1], kv[0]))

The function builds the counts in one pass, then lets the heap keep the best n entries under the key.

Step 4: Cap the memory when the stream is too large

Exact counting needs one counter for every distinct key, so a stream with more keys than memory needs an approximate summary. The Space-Saving paper by Metwally, Agrawal and El Abbadi (2005) targets both top-k and frequent elements in data streams.

A bounded summary called Space-Saving keeps a fixed number of counters. In the version computed on this page, a key already tracked is incremented, a new key takes a free counter, and when none is free the key with the smallest count is evicted and the newcomer inherits its count plus one. Each estimate can only be too high, and the inherited count is the largest possible error.

Say the limit aloud: the heaviest keys are reliable, the light tail is not, and the memory is fixed by the number of counters you choose. This is the same bounded-memory thinking as the eviction in a least recently used (LRU) cache in Python and the expiry, called time to live (TTL), in time-based key-value stores.

1 · Parse2 · State per key3 · Answer4 · Cap memoryReplay

Step-by-step description

1. Each record becomes a key and a value.
2. Each key keeps one small state.
3. A sort or a heap turns the states into the answer.
4. When keys outgrow memory, a bounded summary with fixed counters replaces exact state.

• Each record becomes a key and a value.
• Each key keeps one small state.
• A sort or a heap turns the state into an answer.
• A bounded summary replaces exact per-key state when keys outgrow memory.

Worked example

The data is a tiny illustrative set so you can redo every number by hand. Four sentences contain 22 words and 11 distinct words, and "the" appears 6 times.¹ With Counter.most_common(3) the top three are the, cat and sat, because cat, sat, on, dog, log and a all have count 2 and the docs order ties by first encounter. If the rule is "count descending, then name", the top three are the, a and cat.¹ Same data, two defensible answers, so state the rule.

For ratings, three agents have illustrative ratings over two days. Asha has a sum of 21 over 5 ratings, Ben 17 over 5, Chen 8 over 2.¹ Dividing once gives Asha 4.2, Chen 4.0 and Ben 3.4. Averaging each day first gives Asha 4.5, Ben 4.0 and Chen 4.0. Ben now ties Chen and wins the tie on name, so the sorted list reads Asha, Ben, Chen instead of the correct Asha, Chen, Ben.¹

Text description of the diagram

• Dividing the total by the count gives Asha 4.2, Chen 4.0 and Ben 3.4.
• Averaging daily averages gives Asha 4.5, Ben 4.0 and Chen 4.0.
• Ben then ties Chen and wins the tie on name.

For the entry and exit flow, the state per user is inside or outside. In an illustrative log of ten rows, an entry while inside or an exit while outside is a violation. The violators are u3 and u2: u3 exits before entering and u2 enters twice.¹ The ids u2 and u4 end the log inside, which is not a violation unless the interviewer says so, so ask.

The stream shows the cost of fixed memory: item a is exact, but items g and h are each reported as 4 when the true count is 1, and item b with a true count of 2 is not tracked at the end.¹

Trade-offs and edge cases

The three methods for top-k trade memory against exactness. Counter then sort keeps one count per distinct word and is exact. Counter then heap has the same memory and the same exact answer and is cheaper when k is small. A bounded summary uses a fixed number of counters and gives estimates, so it is the right answer only when the stream outgrows memory.

Text description of the diagram

• Counter then sort keeps one count per distinct word and is exact.
• Counter then heap has the same memory and is cheaper when k is small.
• A bounded summary uses a fixed number of counters and gives estimates.

Edge cases to raise. Out-of-order logs: sort by timestamp before running a per-user state machine, or the flow check gives false violations. Ambiguous wording: "loyal users who viewed different unique products on each day" can mean the two product sets differ or share nothing, so ask which. Empty input and a user with no ratings need a defined output. Very large k: when k is close to the number of distinct keys, the heap saves nothing over a sort. When state per key grows beyond a counter, the design resembles the in-memory database assessment levels, where you pick a structure per query.

How to answer it in an interview

The spoken structure: clarify the key and the tie rule, name the state per key, give the cost, then say what changes when memory runs out.

Common mistakes

• "I'll average each day's average." (wrong) A day with one rating then counts as much as a day with four. (right) "I keep a sum and a count per agent and divide once at the end."
• "Ties are fine in any order." (wrong) The output can differ between runs and between methods. (right) "I'll order by count descending, then alphabetically, and state that."
• "I'll sort the whole log first." (wrong) For a counting question, sorting the records costs more than counting them and adds nothing. (right) "I count in one pass, then sort only the distinct keys." Sorting by timestamp is still right when a rule depends on order.
• "A streaming top-k can be exact in tiny memory." (wrong) Exact counts need a counter per distinct key. (right) "With fixed memory the counts are estimates, and the light tail is the unreliable part."
• "The log is already in time order." (wrong) A state machine on shuffled rows invents violations. (right) "I'll confirm the order, or sort by timestamp first."

Follow-up questions

How do you handle capitalization and punctuation when counting words?

Lower-case each word and strip surrounding punctuation before counting, so "The," and "the" share one key. Decide aloud what to do with apostrophes and hyphens, and keep the tie rule in the sort key, because each choice can change the top n.

How would you build an agent rating system that returns every agent with the average rating, sorted descending?

Keep a sum and a count per agent as ratings arrive, divide when queried, and sort the entries by average descending, then by name. Do not store an average without its count, and do not average per-day averages.

How do you design a streaming solution for the top-k most frequent words from a large corpus?

Count exactly if the distinct words fit in memory, with a heap for the top k. If not, use a bounded summary such as Space-Saving with a fixed number of counters, and report each count as an estimate with its error bound.

How do you find users who broke the entry and exit flow in an attendance log?

Sort rows by time, keep an inside flag per user, and flag an entry while inside or an exit while outside. Ask whether ending inside counts as a violation.

How do you find loyal users who viewed different products on two days?

Keep a set of product ids per user per day, then keep the users present on both days whose two sets differ, or share nothing, depending on how the interviewer reads the wording. Ask which reading is meant before coding.

Which other industry coding problems should I practice next?

Try tasks that mix state and recursion, such as nested list weight sum, and the design-flavored questions in low level design interview questions.

Sources

1. collections: Counter objects (most_common and tie order) — Python Software Foundation (documentation, accessed 2026-10-26), 26 Oct 2026
2. heapq: Heap queue algorithm (nlargest, nsmallest, stability note) — Python Software Foundation (documentation, accessed 2026-10-26), 26 Oct 2026
3. Efficient Computation of Frequent and Top-k Elements in Data Streams — Springer, ICDT 2005, LNCS 3363 (Metwally, Agrawal, El Abbadi), 1 Jan 2005