Databricks·Software Engineer·Technical Phone Screen
- Implement run-length encoding over a stream of tokens, outputting (value, run_length) pairs for consecutive equal tokens. Your implementation must also handle backpressure from a slow downstream consumer.
- Now imagine the token stream is extremely high volume and you can't keep all encoded pairs in memory. How do you redesign the RLE to only retain the last K encoded pairs, emit earlier ones to a downstream sink, and still guarantee correctness at the boundary between flushed and in-memory state?
“The core RLE part was fine, just track current token and count, emit when it changes.”