Compute top-N items from log stream

Q: Compute top-N items from log stream

This question evaluates the ability to aggregate frequencies and compute top-N results from logs, covering competencies in frequency counting, top-k algorithms, and streaming data handling within the Coding & Algorithms domain at a practical application level.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem

You are given application logs containing events with an itemId. Each log line may contain extra fields, but you can extract the itemId from each line.

Parse the logs, count how many times each itemId appears, then output the top N most frequent items.

Input

logs : a list of strings, each representing one log line.
N : an integer.
Each log line contains an item identifier (assume it can be extracted deterministically; e.g., a token like item=<id> or the first whitespace-separated field).

Output

Return a list of the top N itemIds with their counts, sorted by:

descending count
for ties, ascending itemId (or specify and implement a deterministic tie-break).

Constraints (reasonable assumptions)

1 <= len(logs) <= 10^6
Item IDs are strings or integers.
1 <= N <= number of distinct itemIds

Follow-ups

How would you handle streaming logs (unbounded input)?
How would you handle very large distinct counts (memory constraints)?