How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Roblox.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Roblox during technical interviews.

Implement a Log Rate Limiter | Roblox Coding Question

Implement a Log Rate Limiter

Company: Roblox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are building a backend logging service. Implement a class that decides whether an incoming log message should be emitted. Each request provides: - `timestamp`: an integer timestamp in seconds, arriving in nondecreasing order - `message`: a string message key Return `true` if the message should be emitted at that timestamp, and `false` otherwise. A message may be emitted only if the same message has not been emitted during the previous 10 seconds. Different messages are tracked independently. Example: - `(1, "foo") -> true` - `(2, "bar") -> true` - `(3, "foo") -> false` - `(11, "foo") -> true` Discuss the time and space complexity of your approach.

Quick Answer: This question evaluates a candidate's ability to design and implement time-based rate limiting and stateful event tracking using appropriate data structures and algorithmic analysis.

You are building a backend logging service. Implement logic that decides, for each incoming log message, whether it should be emitted. Each request is a pair `[timestamp, message]`: - `timestamp`: an integer number of seconds, with requests arriving in nondecreasing timestamp order. - `message`: a string message key. A message may be emitted only if the same message has not been emitted during the previous 10 seconds. Concretely, a message is emitted at time `t` if it has never been emitted before, or if at least 10 seconds have elapsed since it was last emitted (i.e. `t - lastEmitted >= 10`). Different message keys are tracked independently. Given the full ordered list of requests, return a list of booleans where the i-th value is `true` if the i-th message is emitted and `false` otherwise. Example: - `[1, "foo"] -> true` - `[2, "bar"] -> true` - `[3, "foo"] -> false` (only 2s since "foo" was emitted) - `[11, "foo"] -> true` (10s elapsed since "foo" at t=1) Discuss the time and space complexity of your approach.

Constraints

Timestamps arrive in nondecreasing order.
0 <= timestamp <= 10^9
1 <= number of requests <= 10^5
Each message is a non-empty string.
The cooldown window is exactly 10 seconds: re-emit allowed when timestamp - lastEmitted >= 10.

Examples

Input: ([[1, "foo"], [2, "bar"], [3, "foo"], [11, "foo"]],)

Expected Output: [True, True, False, True]

Explanation: "foo" at t=1 and "bar" at t=2 are firsts (emit). "foo" at t=3 is only 2s later (suppress). "foo" at t=11 is 10s after t=1 (emit).

Input: ([],)

Expected Output: []

Explanation: No requests -> empty result list.

Input: ([[1, "a"]],)

Expected Output: [True]

Explanation: First and only occurrence of "a" is always emitted.

Input: ([[1, "x"], [10, "x"], [11, "x"], [21, "x"]],)

Expected Output: [True, False, True, True]

Explanation: x@1 emits. x@10 is 9s later (suppress). x@11 is 10s after t=1 (emit, window resets to 11). x@21 is 10s after t=11 (emit).

Input: ([[1, "foo"], [1, "foo"], [1, "bar"]],)

Expected Output: [True, False, True]

Explanation: Duplicate "foo" at the same timestamp: second is suppressed (0s gap). "bar" is a different key, so it emits.

Input: ([[0, "m"], [9, "m"], [10, "m"]],)

Expected Output: [True, False, True]

Explanation: Boundary check: m@9 is only 9s after m@0 (suppress); m@10 is exactly 10s after m@0 (emit).

Hints

Track, for each distinct message, the last timestamp at which it was emitted.
A message is allowed when it has never been seen, or when current_ts - last_ts >= 10.
Only update the stored timestamp on the requests you actually emit — a suppressed request does not reset the 10-second window.
A hash map keyed by message gives O(1) amortized work per request.

Quick Overview

This question evaluates a candidate's ability to design and implement time-based rate limiting and stateful event tracking using appropriate data structures and algorithmic analysis.