We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Throttle

Number: 2771

Difficulty: Medium

Paid? Yes

Companies: Yandex

Problem Description

Given a function fn and a time interval t in milliseconds, create and return a throttled version of fn. The throttled function should execute immediately on the first call and then, within the next t milliseconds, block additional immediate executions. Instead, it must store the latest received arguments during the delay period and execute fn with those arguments right after the delay ends. This process repeats for subsequent calls.

Key Insights

  • The first call always invokes fn immediately.
  • Subsequent calls within the throttle period (t milliseconds) should not immediately execute fn; only the latest set of arguments is retained.
  • Once the delay period expires, if there are saved arguments, fn should be called with them and a new delay period begins.
  • The solution requires accurate tracking of timing and pending arguments.

Space and Time Complexity

Time Complexity: O(n), where n is the number of calls, since each call is processed individually.
Space Complexity: O(1), as only limited state (next allowed time and latest arguments) is maintained.

Solution

We implement the throttling behavior by tracking the next allowed time for invoking fn and using a variable to store the most recent pending arguments if a call occurs during the delay period. On each call, if the current time is beyond the next allowed time, we execute fn immediately (or, if pending arguments were saved from prior calls, execute with those) and update the next allowed time. Otherwise, we simply update the pending arguments to ensure that only the latest ones are used when the delay ends. The key challenge is simulating this delay mechanism in a synchronous environment or using timers in an asynchronous environment.

Code Solutions

def throttle(fn, t):
    # Initialize next_allowed_time to 0 and pending_args to None.
    next_allowed_time = 0
    pending_args = None

    def throttled(*args, **kwargs):
        nonlocal next_allowed_time, pending_args
        # This function assume there is a mechanism to get current time in ms.
        current_time = get_current_time()  # Placeholder for a function returning millis
        if current_time >= next_allowed_time:
            # If there was a pending call from before, execute it first.
            if pending_args is not None:
                last_args, last_kwargs = pending_args
                fn(*last_args, **last_kwargs)
                pending_args = None
            else:
                fn(*args, **kwargs)
            # Update next allowed time.
            next_allowed_time = current_time + t
        else:
            # Within throttle period, update the pending arguments with the latest.
            pending_args = (args, kwargs)
    return throttled

# Note: get_current_time() is assumed to provide the current time in milliseconds.
← Back to All Questions