Premium

#391 Counting Active Users in a Sliding Window

Companies:
Yandex
Themes:
AlgorithmsHash TablesPractice

There is a sequence of user requests, where each request is a pair of time and userId. Requests always arrive sorted by time.

The system must quickly answer: “How many users made at least limit requests during the last k milliseconds?”, where k > 0 and limit > 0. 

class UserStatistics {
    private long limit = 0;
    private long k = 0;

    public void event(long now, long userId) {
        // place your code here
    }

    public int robotCount(long now) {
        // place your code here
    }
}

Question review

Mentor
Answer as you would in a real interview. I’ll ask follow-up questions, then compare your answer with the reference answer and show your accuracy as a %.
Sign in to start the dialogue The mentor keeps the context of the current question and your previous messages.
Sign in