Katkat
Back

Design top-K tracker with linked lists

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Design top-K tracker with linked lists evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Design a data structure that tracks the top-K most frequent keys in a stream. Support operations increment(key), decrement(key), and topK(k) -> list of k keys with highest frequencies. Achieve O(

  1. amortized updates by combining a hash map with a doubly linked list of frequency buckets. Specify tie-breaking, deletion behavior when counts drop to zero, memory usage, and complexity.