Opengist

Explore

  • All gists
  • Topics
  • Users
Give feedback on the new UI Powered by Opengist ⋅ 10ms

user:thomas gists created by user

title:mygist gists with given title

description:sync gists with given description

filename:myfile.txt gists having files with given name

extension:yml gists having files with given extension

language:go gists having files with given language

topic:homelab gists with given topic

all:systemctl search all fields

Login Register
i

interview

Recently created Least recently created Recently updated Least recently updated

linkjobai / Coding Interview: Top K Frequent Words with a Count-Min Sketch (Streaming Variant)

Last active 5 days ago interview

Interview prep notes

0 0 1

Coding Interview: Top K Frequent Words with a Count-Min Sketch (Streaming Variant)

A common follow-up to "top K frequent words" is: what if the stream is too large to keep an exact count for every word? The answer interviewers look for is an approximate counter plus a small heap.

Exact version first

For a list that fits in memory: count with a hash map, then keep a min-heap of size K keyed by (count, word). O(n log K) time, O(n) space. Say this first so the interviewer knows you have the baseline.

Count-Min Sketch