Police Alert Waze App

Aug 28, 2021

Purpose

The purpose of this document is to implement the police alert feature in the Waze app.

Use Case

You might have seen this pop up on your screen and wondered how it works.

Who sends the data?

Pretty sure the drivers do.

Now, there are 5 kinds of drivers:

a. those who report cops with a “thumbs up”.

b. those who report “not there”.

c. those who use the information but don't report.

d. those who use google maps or don't use any navigation.

e. those who have a wife sitting right next to them.

Let's only focus on the folks who send in the data (i.e a and b).

How should this feature behave?

Simply put, it should show police ahead when there is one. Nothing, if there isn't.

Thought process and Implementation

We need a way to store the data and make a decision.

Store the data

Let's maintain a list that keeps all the data with a timestamp.

List : [1 at 10am, 1 at 10:01am, 1, 1, 0, 0, 0, 0, 0, … ]

Time : - - - - - >

1-> thumbs up, 0 -> not there and fresh data kees getting appended.

Make a decision

Average the list for the last 15 mins. Decided on 15 mins for freshness.

If it is over 0.2, show police ahead.

If it is under 0.2, don't show anything.

Well, the above numbers can be tweaked.

Implementation Problems

The list can keep growing forever, that

a. could lead to memory issues and

b. as we only have the head pointer, need to write code to look back 15 minutes. nobody, nobody, nobody wants to do that.

Iteration 1

Another thread that cleans up data older than 15 mins <- yuck!

Iteration 2

Let's keep a fixed-sized array that captures the last 15 mins, ok - but what size?

size estimation: Suppose Waze gets around 3 data points (i.e thumbs up/not there) a second. Subject to location for sure but let's assume. Means list size = 2700.

Ok, 2700 size list with no timestamps.

List: [1, 1, 1, 1, 0, 0, 0, 0, 0, … , 1, 1]

What happens once the list is full? Start overwriting from the beginning since it is the oldest and store this index for next time. Also switch to arrays, it will be easier. :)

+ves:

  1. No cleanup thread is needed.
  2. At any given point in time, the array average helps us make a decision

Excellent.

Conclusion

We learned how to implement the police alert feature in the Waze app.

You could use this windowing technique for:

  1. calculating instance CPU average, create an endpoint for it and stick it in AWS health checks.
  2. find the median from a stream of data on leetcode. Amazon asked me this and I told him the yucky thread way.

I hope you enjoyed this newsletter.