Debounce

Medium

Asked by:

20 views

Given a function fn and a time in milliseconds t, return a debounced version of that function.

A debounced function is a function whose execution is delayed by t milliseconds and whose execution is cancelled if it is called again within that window of time. The debounced function should also receive the passed parameters.

For example, let's say t = 50ms, and the function was called at 30ms, 60ms, and 100ms.

The first 2 function calls would be cancelled, and the 3rd function call would be executed at 150ms.

If instead t = 35ms, The 1st call would be cancelled, the 2nd would be executed at 95ms, and the 3rd would be executed at 135ms.

Debounce Schematic

The above diagram shows how debounce will transform events. Each rectangle represents 100ms and the debounce time is 400ms. Each color represents a different set of inputs.

Please solve it without using lodash's _.debounce() function.

Example 1:

Input: 
t = 50
calls = [
  {"t": 50, inputs: [1]},
  {"t": 75, inputs: [2]}
]
Output: [{"t": 125, inputs: [2]}]
Explanation:
let start = Date.now();
function log(...inputs) { 
  console.log([Date.now() - start, inputs ])
}
const dlog = debounce(log, 50);
setTimeout(() => dlog(1), 50);
setTimeout(() => dlog(2), 75);

The 1st call is cancelled by the 2nd call because the 2nd call occurred before 100ms
The 2nd call is delayed by 50ms and executed at 125ms. The inputs were (2).

Example 2:

Input: 
t = 20
calls = [
  {"t": 50, inputs: [1]},
  {"t": 100, inputs: [2]}
]
Output: [{"t": 70, inputs: [1]}, {"t": 120, inputs: [2]}]
Explanation:
The 1st call is delayed until 70ms. The inputs were (1).
The 2nd call is delayed until 120ms. The inputs were (2).

Example 3:

Input: 
t = 150
calls = [
  {"t": 50, inputs: [1, 2]},
  {"t": 300, inputs: [3, 4]},
  {"t": 300, inputs: [5, 6]}
]
Output: [{"t": 200, inputs: [1,2]}, {"t": 450, inputs: [5, 6]}]
Explanation:
The 1st call is delayed by 150ms and ran at 200ms. The inputs were (1, 2).
The 2nd call is cancelled by the 3rd call
The 3rd call is delayed by 150ms and ran at 450ms. The inputs were (5, 6).

Constraints:

0 <= t <= 1000
1 <= calls.length <= 10
0 <= calls[i].t <= 1000
0 <= calls[i].inputs.length <= 10

Try coding it in LeetCode

Debounce

Medium

Asked by:

20 views

Given a function fn and a time in milliseconds t, return a debounced version of that function.

A debounced function is a function whose execution is delayed by t milliseconds and whose execution is cancelled if it is called again within that window of time. The debounced function should also receive the passed parameters.

For example, let's say t = 50ms, and the function was called at 30ms, 60ms, and 100ms.

The first 2 function calls would be cancelled, and the 3rd function call would be executed at 150ms.

If instead t = 35ms, The 1st call would be cancelled, the 2nd would be executed at 95ms, and the 3rd would be executed at 135ms.

Debounce Schematic

The above diagram shows how debounce will transform events. Each rectangle represents 100ms and the debounce time is 400ms. Each color represents a different set of inputs.

Please solve it without using lodash's _.debounce() function.

Example 1:

Input: 
t = 50
calls = [
  {"t": 50, inputs: [1]},
  {"t": 75, inputs: [2]}
]
Output: [{"t": 125, inputs: [2]}]
Explanation:
let start = Date.now();
function log(...inputs) { 
  console.log([Date.now() - start, inputs ])
}
const dlog = debounce(log, 50);
setTimeout(() => dlog(1), 50);
setTimeout(() => dlog(2), 75);

The 1st call is cancelled by the 2nd call because the 2nd call occurred before 100ms
The 2nd call is delayed by 50ms and executed at 125ms. The inputs were (2).

Example 2:

Input: 
t = 20
calls = [
  {"t": 50, inputs: [1]},
  {"t": 100, inputs: [2]}
]
Output: [{"t": 70, inputs: [1]}, {"t": 120, inputs: [2]}]
Explanation:
The 1st call is delayed until 70ms. The inputs were (1).
The 2nd call is delayed until 120ms. The inputs were (2).

Example 3:

Input: 
t = 150
calls = [
  {"t": 50, inputs: [1, 2]},
  {"t": 300, inputs: [3, 4]},
  {"t": 300, inputs: [5, 6]}
]
Output: [{"t": 200, inputs: [1,2]}, {"t": 450, inputs: [5, 6]}]
Explanation:
The 1st call is delayed by 150ms and ran at 200ms. The inputs were (1, 2).
The 2nd call is cancelled by the 3rd call
The 3rd call is delayed by 150ms and ran at 450ms. The inputs were (5, 6).

Constraints:

0 <= t <= 1000
1 <= calls.length <= 10
0 <= calls[i].t <= 1000
0 <= calls[i].inputs.length <= 10

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected behavior if the debounced function is called multiple times within the `wait` period?
What is the data type of the `wait` parameter, and what is its valid range?
Should the debounced function execute immediately upon the first call (leading edge), after the `wait` period (trailing edge), or both, or neither?
What should be returned by the `debounce` function itself? Should it return a function, and what is its expected signature?
If the debounced function is called with different arguments each time, should the last set of arguments be used when the function is eventually executed?

Brute Force Solution

Approach

Debouncing is about delaying a function call until after a certain amount of time has passed without any new calls. The brute force way is to simply keep track of every function call and, for each call, wait the specified time before executing it. This means handling each call individually and independently.

Here's how the algorithm would work step-by-step:

When a function is called, note the time and the function itself.
Set a timer for the specified delay time.
If the function is called again before the timer goes off, cancel the existing timer.
When the timer finally goes off, execute the function.
This process is repeated for every function call, ensuring that only the last call within the delay period is actually executed.

Code Implementation

import time
import threading

def debounce_brute_force(function, delay):
    timer = None

    def debounced(*arguments, **keywords):
        nonlocal timer

        # If there's a pending timer, cancel it
        if timer is not None:
            timer.cancel()

        # Define the function that will actually be executed
        def delayed_execution():
            function(*arguments, **keywords)

        # Create a new timer
        timer = threading.Timer(delay, delayed_execution)

        # Starts the timer
        timer.start()

        # We don't return anything because we call the function asynchronously
        
    return debounced

Big(O) Analysis

Time Complexity

O(1) – The debounce function, as described, essentially manages a single timer. Each call to the debounced function either cancels the existing timer (if it exists) or sets a new timer. The time it takes to set or clear a timer is considered constant, regardless of the number of times the debounced function is called. Therefore, the time complexity is O(1).

Space Complexity

O(1) – The debouncing algorithm described stores the function itself and the time of the function call. It also manages a timer. The amount of space used by these variables is constant regardless of the number of times the function is called. Therefore, the space complexity is O(1) because the memory usage does not scale with the input size N, which is the number of function calls.

Optimal Solution

Approach

The goal of Debounce is to only execute a function after a certain amount of time has passed since the last time it was called. We'll use a timer to keep track of this waiting period, ensuring the function isn't called too frequently. The clever trick is to use a single timer that gets reset each time the function is invoked before its delay time has elapsed, this way we can avoid multiple calls to the function.

Here's how the algorithm would work step-by-step:

When the function is called, first clear any existing timer that's already running.
Start a new timer that will wait for the specified delay time.
When the timer finishes its countdown, then, and only then, should you actually execute the function.
If the function is called again before the timer finishes, the existing timer is cleared, and a new timer starts from scratch. This ensures that the function is only executed after a period of inactivity.

Code Implementation

import threading

def debounce(function_to_debounce, delay):
    timer = None

    def debounced_function(*args, **kwargs):
        nonlocal timer
        # Clear existing timer to prevent premature execution
        if timer is not None:
            timer.cancel()

        # Define the function to be executed after the delay
        def run_function():
            function_to_debounce(*args, **kwargs)

        # Start a new timer
        timer = threading.Timer(delay, run_function)
        timer.start()

    return debounced_function

Big(O) Analysis

Time Complexity

O(1) – The debounce function's time complexity is O(1). Clearing a timer, setting a timer, and executing the function (when the timer completes) are all constant-time operations. The delay does not affect the Big O notation as it describes the relationship between the input size and the execution time. Regardless of how many times the debounced function is called, the core operations within the debounce wrapper take constant time.

Space Complexity

O(1) – The debounce function, as described, uses a timer. This timer occupies a fixed amount of memory, regardless of how many times the function is called or the specified delay. There are no additional data structures or variables created that scale with the input. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or undefined function input	Throw an error or return a no-op function to prevent unexpected behavior
Zero or negative wait time	Treat a zero or negative wait time as an immediate execution or throw an error
Function called rapidly, more frequently than the wait time	Ensure only the last function call within the wait period is executed by cancelling previous timers
The debounced function throws an error	Propagate the error to the caller or provide a try-catch within the debounced function itself
The 'this' context is different in each call	Preserve the correct 'this' context using Function.prototype.apply or Function.prototype.call
Arguments to the function are different in each call	Capture and pass the correct arguments from the latest invocation when the debounced function runs.
Debounced function is garbage collected before execution	No specific handling is needed; Javascript handles garbage collection automatically, but consider potential memory leaks from prolonged timers.
Multiple debounced functions with overlapping calls	Each debounced function needs its own independent timer and state management to prevent interference.

Null or undefined function input

How to Handle:

Throw an error or return a no-op function to prevent unexpected behavior

Zero or negative wait time

How to Handle:

Treat a zero or negative wait time as an immediate execution or throw an error

Function called rapidly, more frequently than the wait time

How to Handle:

Ensure only the last function call within the wait period is executed by cancelling previous timers

The debounced function throws an error

How to Handle:

Propagate the error to the caller or provide a try-catch within the debounced function itself

The 'this' context is different in each call

How to Handle:

Preserve the correct 'this' context using Function.prototype.apply or Function.prototype.call

Arguments to the function are different in each call

How to Handle:

Capture and pass the correct arguments from the latest invocation when the debounced function runs.

Debounced function is garbage collected before execution

How to Handle:

No specific handling is needed; Javascript handles garbage collection automatically, but consider potential memory leaks from prolonged timers.

Multiple debounced functions with overlapping calls

How to Handle:

Each debounced function needs its own independent timer and state management to prevent interference.