Google On-Site: Design alerting system for a server (sliding window)

Found this question here. Specifically, I'm looking for help with the solution to the follow-up:

We would like to design an alerting system for a server. The input to the system is error rates of the server over time. For example, 5, 10, 7, 15, 0, 60, 55, 60, 60, 60, 0, 5, 5 will be interpreted as the server having error rate of 5% during the 1st second, 10% during the 2nd second, 7% during the 3rd second, and so on.

You are given a threshold t. Write a function that returns true iff there is an interval where s * r > t, where s is the size of the interval (in seconds) and r represents the lowest error rate in the interval.

Can someone help me understand how to attack this question? Reading online, it seems like the optimal solution uses a stack, but I can't seem to understand how to use the stack to identify the areas where s * r exceeds the threshold. Been banging my head on this one for two days....

Comments (9)