Katkat
Back

Scale Word-Frequency Processing Beyond One Machine

RobinhoodBackend Engineer · Technical Screen
MediumBackend EngineerTechnical ScreenSystem Design

Last updated

This question tests the ability to design a distributed data processing pipeline that handles large-scale text files by balancing memory constraints, horizontal scalability, and data integrity.

Problem Statement

Design a distributed system that calculates the exact word frequency for a set of massive text files (petabyte scale) stored in an immutable object store (e.g., S3). The output should be a ranked list of the top 1,000 most frequent words across all files.

Functional Requirements

  • Process input files of arbitrary size.
  • Provide an exact word count (no approximate algorithms like Count-Min Sketch).
  • Support idempotent processing to handle node failures.

Non-Functional Requirements

  • Ensure deterministic output regardless of parallel execution order.
  • Design for horizontal scalability across a cluster.
  • Handle "hot keys" (e.g., extremely frequent stop words like 'the') that might cause memory pressure on specific reduce tasks.

Deliverables

  1. High-level architecture: Describe the stages (e.g., ingestion, tokenization, aggregation, reduction).
  2. Partitioning strategy: How do you partition data to avoid losing partial words split across file boundaries?
  3. Data model: What does the communication look like between your worker nodes and the aggregator/storage layer?
  4. Fault tolerance: How do you handle a worker node crashing midway through processing a file segment?

Hints

Hint 1

Consider implementing a MapReduce-style architecture where local word counts are computed per segment before being shuffled to global reducers.

Hint 2

Address the word-boundary issue by having workers read a slight overlap between file chunks or by using an index file that maps offsets to complete lines.

Hint 3

Mitigate hot keys by introducing a secondary aggregation step (combiner) or by hashing tokens into buckets to distribute the load across multiple reducers.

Follow-up questions

  • How would you modify your design if the system needed to support real-time word frequency updates as new files are uploaded to the object store?
  • If the 'top 1000' list needs to be updated incrementally as each file is processed, what data structures would you use?
  • How would you monitor the system for skewed partitions that might indicate a hot-key issue in real-time?