Design out-of-order windowed stream processor
Company: Box
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Design an event processor for an unbounded stream where each event has id, timestamp, payload string, and checksum. Events may arrive out of timestamp order; late events beyond a 60-second window are dropped. Validate events by checksum, then maintain and report the average payload length over the latest 60 seconds. Ensure total time complexity is no worse than O(n log n) across n events and support continuous updates as new events arrive. Describe data structures and late/duplicate handling.
Quick Answer: This question evaluates understanding of stream processing concepts such as out-of-order event handling, sliding 60-second windows, checksum validation, deduplication, and maintaining rolling aggregates under time and space constraints.