Problem Description

This problem asks you to implement two custom functions that manage intervals with a variable timing pattern.

Function 1: customInterval

You need to create a function that takes three parameters:

• fn: A function to be executed repeatedly
• delay: The initial delay before the first execution (in milliseconds)
• period: The increment value for calculating subsequent delays (in milliseconds)

The function should execute fn at intervals following a linear pattern. The timing for each execution is calculated using the formula: delay + period * count, where count starts at 0 and increases by 1 after each execution.

For example, if delay = 100 and period = 50:

• First execution happens after: 100 + 50 * 0 = 100ms
• Second execution happens after: 100 + 50 * 1 = 150ms
• Third execution happens after: 100 + 50 * 2 = 200ms
• And so on...

The function should return a unique id (number) that can be used to stop the interval later.

Function 2: customClearInterval

You need to create a function that takes one parameter:

• id: The identifier returned by customInterval

This function should stop the execution of the interval associated with the given id, preventing any future executions of the function fn.

The implementation uses recursive setTimeout calls rather than setInterval to achieve the variable timing pattern. A Map is used to track active intervals by their IDs, allowing them to be cleared when needed.

Intuition

The key insight is that JavaScript's built-in setInterval function executes at fixed intervals, but we need variable intervals that increase linearly. Since each execution happens at a different delay (delay + period * count), we can't use setInterval directly.

Instead of trying to modify setInterval, we can use setTimeout recursively. Each time the function executes, we schedule the next execution with a new calculated delay. This gives us full control over when each execution happens.

Why recursive setTimeout works:

1. After each execution, we calculate the next delay based on the current count
2. We schedule the next execution using setTimeout with this new delay
3. This creates a chain of scheduled executions, each with its own timing

The challenge is managing these recursive timeouts so they can be cancelled. We need to:

• Track the current active timeout for each custom interval
• Update this reference each time we create a new timeout in the chain
• Be able to stop the entire chain by clearing the current timeout

A Map is perfect for this because:

• We can use unique IDs as keys to track multiple custom intervals simultaneously
• We can easily update the timeout reference for a given ID
• We can check if an interval exists and clear it when needed

The Date.now() approach for generating IDs ensures uniqueness since it returns the current timestamp in milliseconds. While there's a theoretical chance of collision if two intervals are created at the exact same millisecond, it's practical enough for most use cases.

The recursive pattern naturally handles the incrementing count - each recursive call represents the next iteration, so we increment count after each execution and use it to calculate the delay for the next timeout.

Solution Approach

The solution uses a Map data structure to track active intervals and recursive setTimeout calls to achieve the variable timing pattern.

Data Structure:

• intervalMap: A Map that stores the relationship between interval IDs and their current timeout objects
  • Key: The unique ID (number) for each custom interval
  • Value: The NodeJS.Timeout object that can be cleared

Implementation of customInterval:

1. Initialize the counter: Start with count = 0 to track how many times the function has executed

2. Create a recursive function: Define recursiveTimeout that:

   • Schedules the next execution using setTimeout
   • Calculates the delay as delay + period * count
   • Inside the timeout callback:
     • Executes the provided function fn()
     • Increments count++ for the next iteration
     • Calls itself recursively to schedule the next execution
   • Stores the timeout reference in the Map with the interval's ID

3. Generate unique ID: Use Date.now() to create a timestamp-based unique identifier

4. Start the chain: Call recursiveTimeout() to begin the interval sequence

5. Return the ID: Return the generated ID for later reference

Implementation of customClearInterval:

1. Check existence: Verify if the provided ID exists in the intervalMap

2. Clear the timeout: If it exists:

   • Retrieve the timeout object using intervalMap.get(id)
   • Call clearTimeout() to cancel the scheduled execution
   • This breaks the recursive chain since the next recursiveTimeout won't be called

3. Clean up: Remove the entry from the Map using intervalMap.delete(id)

Key Pattern - Recursive setTimeout:

The core pattern replaces traditional setInterval with a self-scheduling timeout:

function recursiveTimeout() {
    setTimeout(() => {
        // Execute task
        // Update state
        recursiveTimeout(); // Schedule next execution
    }, calculatedDelay);
}

This pattern allows dynamic delay calculation for each iteration, enabling the linear progression of intervals required by the problem.

Example Walkthrough

Let's walk through a concrete example where we want to log "Hello" with increasing delays.

Setup:

• fn = () => console.log("Hello")
• delay = 100ms
• period = 50ms

Step 1: Call customInterval

const id = customInterval(() => console.log("Hello"), 100, 50);
// Returns id = 1699564800000 (example timestamp)

Step 2: First execution (count = 0)

• Calculate delay: 100 + 50 * 0 = 100ms
• Schedule setTimeout for 100ms
• After 100ms:
  • Execute: console.log("Hello") → Output: "Hello"
  • Increment count to 1
  • Schedule next timeout

Step 3: Second execution (count = 1)

• Calculate delay: 100 + 50 * 1 = 150ms
• Schedule setTimeout for 150ms
• After 150ms:
  • Execute: console.log("Hello") → Output: "Hello"
  • Increment count to 2
  • Update intervalMap[1699564800000] with new timeout reference
  • Schedule next timeout

Step 4: Third execution (count = 2)

• Calculate delay: 100 + 50 * 2 = 200ms
• Schedule setTimeout for 200ms
• After 200ms:
  • Execute: console.log("Hello") → Output: "Hello"
  • Increment count to 3
  • Update intervalMap[1699564800000] with new timeout reference
  • Schedule next timeout

Step 5: Clear the interval

customClearInterval(1699564800000);

• Find timeout in intervalMap using id 1699564800000
• Call clearTimeout on the current timeout object
• Remove entry from intervalMap
• The recursive chain breaks - no more executions

Timeline visualization:

Time:   0ms ---100ms---250ms---450ms---[CLEARED]
Event:  Start   Hello   Hello   Hello    Stop
Delay:          100ms   150ms   200ms

Notice how each delay increases by 50ms (the period), creating the pattern: 100ms, 150ms, 200ms, 250ms, etc. The total time from start to each execution follows the cumulative pattern.

Solution Implementation

Time and Space Complexity

Time Complexity:

• customInterval: O(1) for each call. The function performs constant-time operations including creating a closure, calling Date.now(), and initiating the first recursive call. Each subsequent timeout execution also takes O(1) time to set up the next timeout and execute the callback function fn().

• customClearInterval: O(1). The function performs a hash map lookup with has(), retrieval with get(), clearing the timeout, and deletion with delete(), all of which are constant-time operations on average for a Map.

Space Complexity:

• customInterval: O(1) per interval created. Each interval stores:

  • One entry in the intervalMap (key-value pair)
  • One closure maintaining the count, id, and reference to fn
  • One active timeout in the event loop at any given time

• customClearInterval: O(1). No additional space is allocated; it only removes existing entries.

Overall Space Complexity: O(n) where n is the number of active intervals. The intervalMap grows linearly with the number of intervals created and not yet cleared.

Note: There's a bug in the code - the recursive timeout calculation delay + period * count causes increasingly longer delays between executions rather than maintaining a constant period. The timeout should likely be just period after the initial delay to achieve typical interval behavior.

Common Pitfalls

1. Thread Safety Issues with Shared State

The current implementation uses a global interval_map dictionary that can be accessed by multiple threads simultaneously (main thread and timer threads). Python's GIL provides some protection, but operations like checking existence and deletion aren't atomic, potentially causing race conditions.

Problem Example:

# Thread 1: Clearing an interval
if id in interval_map:  # Check passes
    # Thread 2: Same interval naturally completes and removes itself
    timer = interval_map[id]  # KeyError - entry was just deleted!

Solution: Use a thread lock to ensure atomic operations:

import threading

interval_lock = threading.Lock()
interval_map: Dict[int, threading.Timer] = {}

def custom_clear_interval(id: int) -> None:
    with interval_lock:
        if id in interval_map:
            timer = interval_map[id]
            timer.cancel()
            del interval_map[id]

2. Memory Leak from Uncanceled Timers

If intervals aren't explicitly cleared, the recursive nature keeps creating new timer objects indefinitely. The interval_map continues to hold references, preventing garbage collection even after timers complete.

Problem Example:

# Creating many short-lived intervals without clearing them
for i in range(1000):
    custom_interval(lambda: print("test"), 0.1, 0.1)
# Memory keeps growing as old timer references remain in interval_map

Solution: Clean up the map entry after each execution:

def schedule_next_execution():
    current_delay = delay + period * execution_count[0]
  
    def execute_and_reschedule():
        # Remove old timer reference before creating new one
        if interval_id in interval_map:
            del interval_map[interval_id]
      
        fn()
        execution_count[0] += 1
        schedule_next_execution()
  
    timer = threading.Timer(current_delay, execute_and_reschedule)
    timer.daemon = True
    timer.start()
    interval_map[interval_id] = timer

3. ID Collision Risk

Using int(time.time() * 1000000) for ID generation can produce collisions when multiple intervals are created within the same microsecond, especially on systems with lower time resolution.

Problem Example:

# Creating intervals in rapid succession
id1 = custom_interval(func1, 1, 1)
id2 = custom_interval(func2, 1, 1)  # Might get same ID!
# id2 overwrites id1 in the map, making id1 unclearable

Solution: Use a counter with thread-safe increment:

import itertools

id_counter = itertools.count(1)  # Thread-safe counter

def custom_interval(fn: Callable, delay: float, period: float) -> int:
    interval_id = next(id_counter)  # Guaranteed unique
    # ... rest of implementation

4. Delay Drift Accumulation

The recursive approach calculates delay from the start time but doesn't account for execution time of fn(). If fn() takes significant time, the actual interval between executions differs from the expected pattern.

Problem Example:

def slow_function():
    time.sleep(0.5)  # Takes 500ms to execute
    print("done")

# Expected: Execute at 1s, 2s, 3s...
# Actual: Execute at 1s, 2.5s, 4s... (includes execution time)
custom_interval(slow_function, 1, 1)

Solution: Track absolute start time and calculate delays from it:

def custom_interval(fn: Callable, delay: float, period: float) -> int:
    interval_id = next(id_counter)
    start_time = time.time()
    execution_count = [0]
  
    def schedule_next_execution():
        # Calculate delay from absolute start time
        target_time = start_time + delay + period * execution_count[0]
        current_time = time.time()
        actual_delay = max(0, target_time - current_time)
      
        def execute_and_reschedule():
            fn()
            execution_count[0] += 1
            schedule_next_execution()
      
        timer = threading.Timer(actual_delay, execute_and_reschedule)
        timer.daemon = True
        timer.start()
        interval_map[interval_id] = timer
  
    schedule_next_execution()
    return interval_id