Compute Top-K word frequencies under a path
Company: Box
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given a filesystem path that may contain nested subdirectories and files, compute the top K most frequent words across all files. Describe an in-memory solution and its complexity. Follow-up: when the corpus is too large to fit in memory, propose scalable approaches (e.g., external sorting/partitioning, MapReduce-style sharding and merge) and an approximate heavy-hitters approach (e.g., Count–Min Sketch with Space-Saving), including accuracy/latency/storage trade-offs.
Quick Answer: This question evaluates understanding of text parsing and frequency-counting algorithms, external-memory and distributed processing techniques, and streaming/approximate heavy-hitter methods with attention to accuracy/latency/storage trade-offs.