Waze: a road report can be accurate and still become outdated
Waze lets drivers report hazards and uses later feedback to adjust how long reports remain visible. The design treats freshness as part of the information service rather than leaving every once-correct report on the map forever.
Break down the problem and try your own design and implementation first. Then explore the reasoning to check states, edge cases, trade-offs, and ways to test your approach. The guide offers a reasoning path, not a complete implementation.
Expire a report from when it was observed
Implement a local road-notice module. Each notice has a unique ID, observation time, and text; times are integer minutes. Its initial expiry is observation time plus 10. A “no longer there” response shortens expiry to the earlier of its current expiry and feedback time plus 2, never extending it. A notice is already invisible at its expiry time.
- Support receiving notices, recording feedback, and reading visible notices at a supplied current time. Received IDs are unique; feedback only concerns received notices. Current time only advances or stays equal, and feedback time equals that call’s current time. Notices may arrive late, but their lifetime must still start at observation. Feedback cannot reactivate an expired notice. Return notices sorted by ID.
- At time 2, receive R1 observed at 0, expiring at 10. Feedback at 4 moves expiry to 6; more feedback at 5 must not move it to 7. A query at 5 includes R1; at 6 it is empty. R2, observed at 1 but received at 12, is invisible immediately on receipt.
- Deliver a runnable module and these calls. Explain where the time rules live and how to verify results without actually waiting. No map, network, or background cleanup is required.
Explore the reasoning
Keep observation and receipt times distinct and consider which determines the age of the information. Make feedback move expiry only earlier. Check the exact-expiry and delayed-arrival examples; determining visibility need not depend on a timer deleting data.