Interview Guides

Debounce Search Suggestions Stream | Dataford Interview Questions - Dataford - Ace your Interview

Debounce Search Suggestions Stream

Medium

Coding

StringsDynamic ProgrammingRecursionMath

Problem

You’re building the typeahead search bar for a large e-commerce marketplace (millions of DAUs). Every keystroke can trigger a backend suggestion request, but sending a request per keypress increases cost and hurts P99 latency. To protect the system, the frontend uses debouncing: only fire a request after the user has stopped typing for delay_ms.

Given a chronological stream of input events, simulate a debouncer and return the list of requests that would actually be sent.

Formal Task

Implement debounce_requests(events, delay_ms).

Each event is a tuple (t_ms, text):
- t_ms is an integer timestamp in milliseconds (non-decreasing order).
- text is the full current input value after that keystroke.
Debounce behavior:
1. When an event arrives, it schedules a request for time t_ms + delay_ms with that event’s text.
2. If another event arrives before the scheduled time, the previous schedule is canceled and replaced.
3. A scheduled request fires exactly at its scheduled time if it hasn’t been canceled.
After the final event, the last scheduled request (if any) should still fire.

Return a list of fired requests as tuples (fire_time_ms, text) in chronological order.

Examples

Example 1

Input:

events = [(0, "h"), (50, "he"), (120, "hel"), (400, "hell")]
delay_ms = 200

Output:

[(320, "hel"), (600, "hell")]

Explanation:

Events at 0, 50, 120 keep canceling until the user pauses; after 120 there’s a 280ms gap, so the request fires at 120+200=320 with text "hel".
Then the event at 400 schedules a request for 600, which fires after the stream ends.

Example 2

Input:

events = [(0, "a"), (200, "ab")]
delay_ms = 200

Output:

[(200, "a"), (400, "ab")]

Explanation: The second event arrives exactly at 200ms, so the first request has already fired at 200ms (it is not canceled).

Constraints

0 <= len(events) <= 2 * 10^5
0 <= t_ms <= 10^9, timestamps are non-decreasing
0 <= delay_ms <= 10^9
text length <= 200 and contains printable ASCII

Notes

Treat “arrives before scheduled time” as strictly < scheduled_time.
Your solution should be efficient for large event streams.

Examples

Example 1

Inputevents = [(0, "h"), (50, "he"), (120, "hel"), (400, "hell")], delay_ms = 200Output[(320, "hel"), (600, "hell")]WhyThe first three events keep canceling until a pause after 120ms; it fires at 320ms. The last event fires at 600ms.

Example 2

Inputevents = [(0, "a"), (200, "ab")], delay_ms = 200Output[(200, "a"), (400, "ab")]WhyAn event at exactly the scheduled fire time does not cancel; the earlier request fires at 200ms, then the new one is scheduled.

Constraints

0 <= len(events) <= 2 * 10^5
0 <= t_ms <= 10^9 and timestamps are non-decreasing
0 <= delay_ms <= 10^9
0 <= len(text) <= 200
Cancel only when next event time is strictly less than the scheduled fire time

Function Signature

def debounce_requests(events: list[tuple[int, str]], delay_ms: int) -> list[tuple[int, str]]:

Problem

Given a chronological stream of input events, simulate a debouncer and return the list of requests that would actually be sent.

Formal Task

Implement debounce_requests(events, delay_ms).

Each event is a tuple (t_ms, text):
- t_ms is an integer timestamp in milliseconds (non-decreasing order).
- text is the full current input value after that keystroke.
Debounce behavior:
1. When an event arrives, it schedules a request for time t_ms + delay_ms with that event’s text.
2. If another event arrives before the scheduled time, the previous schedule is canceled and replaced.
3. A scheduled request fires exactly at its scheduled time if it hasn’t been canceled.
After the final event, the last scheduled request (if any) should still fire.

Return a list of fired requests as tuples (fire_time_ms, text) in chronological order.

Examples

Example 1

Input:

events = [(0, "h"), (50, "he"), (120, "hel"), (400, "hell")]
delay_ms = 200

Output:

[(320, "hel"), (600, "hell")]

Explanation:

Events at 0, 50, 120 keep canceling until the user pauses; after 120 there’s a 280ms gap, so the request fires at 120+200=320 with text "hel".
Then the event at 400 schedules a request for 600, which fires after the stream ends.

Example 2

Input:

events = [(0, "a"), (200, "ab")]
delay_ms = 200

Output:

[(200, "a"), (400, "ab")]

Explanation: The second event arrives exactly at 200ms, so the first request has already fired at 200ms (it is not canceled).

Constraints

0 <= len(events) <= 2 * 10^5
0 <= t_ms <= 10^9, timestamps are non-decreasing
0 <= delay_ms <= 10^9
text length <= 200 and contains printable ASCII

Notes

Treat “arrives before scheduled time” as strictly < scheduled_time.
Your solution should be efficient for large event streams.

Examples

Example 1

Example 2

Constraints

0 <= len(events) <= 2 * 10^5
0 <= t_ms <= 10^9 and timestamps are non-decreasing
0 <= delay_ms <= 10^9
0 <= len(text) <= 200
Cancel only when next event time is strictly less than the scheduled fire time

Function Signature

def debounce_requests(events: list[tuple[int, str]], delay_ms: int) -> list[tuple[int, str]]:

Practice Python

Python 3.10

Open on desktop for the full Python editor with syntax highlighting and autocomplete.

Up next

Debounced Local Search FilterEasy

Next question

Debounce Search Suggestions Stream

Medium

Coding

StringsDynamic ProgrammingRecursionMath

Problem

Given a chronological stream of input events, simulate a debouncer and return the list of requests that would actually be sent.

Formal Task

Implement debounce_requests(events, delay_ms).

Each event is a tuple (t_ms, text):
- t_ms is an integer timestamp in milliseconds (non-decreasing order).
- text is the full current input value after that keystroke.
Debounce behavior:
1. When an event arrives, it schedules a request for time t_ms + delay_ms with that event’s text.
2. If another event arrives before the scheduled time, the previous schedule is canceled and replaced.
3. A scheduled request fires exactly at its scheduled time if it hasn’t been canceled.
After the final event, the last scheduled request (if any) should still fire.

Return a list of fired requests as tuples (fire_time_ms, text) in chronological order.

Examples

Example 1

Input:

events = [(0, "h"), (50, "he"), (120, "hel"), (400, "hell")]
delay_ms = 200

Output:

[(320, "hel"), (600, "hell")]

Explanation:

Events at 0, 50, 120 keep canceling until the user pauses; after 120 there’s a 280ms gap, so the request fires at 120+200=320 with text "hel".
Then the event at 400 schedules a request for 600, which fires after the stream ends.

Example 2

Input:

events = [(0, "a"), (200, "ab")]
delay_ms = 200

Output:

[(200, "a"), (400, "ab")]

Explanation: The second event arrives exactly at 200ms, so the first request has already fired at 200ms (it is not canceled).

Constraints

0 <= len(events) <= 2 * 10^5
0 <= t_ms <= 10^9, timestamps are non-decreasing
0 <= delay_ms <= 10^9
text length <= 200 and contains printable ASCII

Notes

Treat “arrives before scheduled time” as strictly < scheduled_time.
Your solution should be efficient for large event streams.

Examples

Example 1

Example 2

Constraints

0 <= len(events) <= 2 * 10^5
0 <= t_ms <= 10^9 and timestamps are non-decreasing
0 <= delay_ms <= 10^9
0 <= len(text) <= 200
Cancel only when next event time is strictly less than the scheduled fire time

Function Signature

def debounce_requests(events: list[tuple[int, str]], delay_ms: int) -> list[tuple[int, str]]:

Problem

Given a chronological stream of input events, simulate a debouncer and return the list of requests that would actually be sent.

Formal Task

Implement debounce_requests(events, delay_ms).

Each event is a tuple (t_ms, text):
- t_ms is an integer timestamp in milliseconds (non-decreasing order).
- text is the full current input value after that keystroke.
Debounce behavior:
1. When an event arrives, it schedules a request for time t_ms + delay_ms with that event’s text.
2. If another event arrives before the scheduled time, the previous schedule is canceled and replaced.
3. A scheduled request fires exactly at its scheduled time if it hasn’t been canceled.
After the final event, the last scheduled request (if any) should still fire.

Return a list of fired requests as tuples (fire_time_ms, text) in chronological order.

Examples

Example 1

Input:

events = [(0, "h"), (50, "he"), (120, "hel"), (400, "hell")]
delay_ms = 200

Output:

[(320, "hel"), (600, "hell")]

Explanation:

Events at 0, 50, 120 keep canceling until the user pauses; after 120 there’s a 280ms gap, so the request fires at 120+200=320 with text "hel".
Then the event at 400 schedules a request for 600, which fires after the stream ends.

Example 2

Input:

events = [(0, "a"), (200, "ab")]
delay_ms = 200

Output:

[(200, "a"), (400, "ab")]

Explanation: The second event arrives exactly at 200ms, so the first request has already fired at 200ms (it is not canceled).

Constraints

0 <= len(events) <= 2 * 10^5
0 <= t_ms <= 10^9, timestamps are non-decreasing
0 <= delay_ms <= 10^9
text length <= 200 and contains printable ASCII

Notes

Treat “arrives before scheduled time” as strictly < scheduled_time.
Your solution should be efficient for large event streams.

Examples

Example 1

Example 2

Constraints

0 <= len(events) <= 2 * 10^5
0 <= t_ms <= 10^9 and timestamps are non-decreasing
0 <= delay_ms <= 10^9
0 <= len(text) <= 200
Cancel only when next event time is strictly less than the scheduled fire time

Function Signature

def debounce_requests(events: list[tuple[int, str]], delay_ms: int) -> list[tuple[int, str]]:

Practice Python

Python 3.10

Open on desktop for the full Python editor with syntax highlighting and autocomplete.

Up next

Debounced Local Search FilterEasy

Next question