Problem

Batching multiple small queries into a single large query can be a useful optimization. Write a class QueryBatcher that implements this functionality.

The constructor should accept two parameters:

  • An asynchronous function queryMultiple which accepts an array of string keys input. It will resolve with an array of values that is the same length as the input array. Each index corresponds to the value associated with input[i]. You can assume the promise will never reject.
  • A throttle time in milliseconds t.

The class has a single method.

  • async getValue(key). Accepts a single string key and resolves with a single string value. The keys passed to this function should eventually get passed to the queryMultiple function. queryMultiple should never be called consecutively within t milliseconds. The first time getValue is called, queryMultiple should immediately be called with that single key. If after t milliseconds, getValue had been called again, all the passed keys should be passed to queryMultiple and ultimately returned. You can assume every key passed to this method is unique.

The following diagram illustrates how the throttling algorithm works. Each rectangle represents 100ms. The throttle time is 400ms.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Input: 
queryMultiple = async function(keys) { 
return keys.map(key => key + '!');
}
t = 100 
calls = [
{"key": "a", "time": 10}, 
{"key": "b", "time": 20}, 
{"key": "c", "time": 30}
]
Output: [
{"resolved": "a!", "time": 10},
{"resolved": "b!", "time": 110},
{"resolved": "c!", "time": 110}
]
Explanation:
const batcher = new QueryBatcher(queryMultiple, 100);
setTimeout(() => batcher.getValue('a'), 10); // "a!" at t=10ms
setTimeout(() => batcher.getValue('b'), 20); // "b!" at t=110ms
setTimeout(() => batcher.getValue('c'), 30); // "c!" at t=110ms
queryMultiple simply adds an "!" to the key
At t=10ms, getValue('a') is called, queryMultiple(['a']) is immediately called and the result is immediately returned.
At t=20ms, getValue('b') is called but the query is queued
At t=30ms, getValue('c') is called but the query is queued.
At t=110ms, queryMultiple(['a', 'b']) is called and the results are immediately returned.

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

Input: 
queryMultiple = async function(keys) {
await new Promise(res => setTimeout(res, 100));
return keys.map(key => key + '!');
}
t = 100
calls = [
{"key": "a", "time": 10},
{"key": "b", "time": 20},
{"key": "c", "time": 30}
]
Output: [
{"resolved": "a!", "time": 110},
{"resolved": "b!", "time": 210},
{"resolved": "c!", "time": 210}
]
Explanation:
This example is the same as example 1 except there is a 100ms delay in queryMultiple. The results are the same except the promises resolve 100ms later.

Example 3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Input: 
queryMultiple = async function(keys) { 
await new Promise(res => setTimeout(res, keys.length * 100)); 
return keys.map(key => key + '!');
}
t = 100
calls = [
{"key": "a", "time": 10}, 
{"key": "b", "time": 20}, 
{"key": "c", "time": 30}, 
{"key": "d", "time": 40}, 
{"key": "e", "time": 250}
{"key": "f", "time": 300}
]
Output: [
{"resolved":"a!","time":110},
{"resolved":"e!","time":350},
{"resolved":"b!","time":410},
{"resolved":"c!","time":410},
{"resolved":"d!","time":410},
{"resolved":"f!","time":450}
]
Explanation: queryMultiple(['a']) is called at t=10ms, it is resolved at t=110ms
queryMultiple(['b', 'c', 'd']) is called at t=110ms, it is resolved at 410ms
queryMultiple(['e']) is called at t=250ms, it is resolved at 350ms
queryMultiple(['f']) is called at t=350ms, it is resolved at 450ms

Constraints:

  • 0 <= t <= 1000
  • 0 <= calls.length <= 10
  • 1 <= key.length <= 100
  • All keys are unique

Solution

Method 1 – Throttled Batching with Timer

Intuition

To efficiently batch queries, we use a timer to collect keys within the throttle window. The first call is immediate, and subsequent calls within the window are batched and sent together after the throttle time.

Approach

  1. Store pending keys and their resolvers in a queue.
  2. On the first call, immediately call queryMultiple and resolve the promise.
  3. For subsequent calls within t ms, queue the keys and set a timer if not already set.
  4. When the timer fires, call queryMultiple with all queued keys and resolve their promises.
  5. Ensure no two queryMultiple calls are within t ms.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

type QueryMultiple = (keys: string[]) => Promise<string[]>;

class QueryBatcher {
    private queryMultiple: QueryMultiple;
    private t: number;
    private queue: { key: string, resolve: (v: string) => void }[] = [];
    private timer: any = null;
    private lastCall: number = -Infinity;

    constructor(queryMultiple: QueryMultiple, t: number) {
        this.queryMultiple = queryMultiple;
        this.t = t;
    }

    async getValue(key: string): Promise<string> {
        return new Promise<string>((resolve) => {
            const now = Date.now();
            if (now - this.lastCall >= this.t) {
                this.lastCall = now;
                this.queryMultiple([key]).then(([val]) => resolve(val));
            } else {
                this.queue.push({ key, resolve });
                if (!this.timer) {
                    const wait = this.t - (now - this.lastCall);
                    this.timer = setTimeout(() => {
                        const batch = this.queue;
                        this.queue = [];
                        this.timer = null;
                        this.lastCall = Date.now();
                        this.queryMultiple(batch.map(x => x.key)).then(res => {
                            for (let i = 0; i < batch.length; ++i) batch[i].resolve(res[i]);
                        });
                    }, wait);
                }
            }
        });
    }
}

Complexity

  • ⏰ Time complexity: O(1) per getValue call, batching is handled by timer and queue.
  • 🧺 Space complexity: O(n), where n is the number of queued keys in the throttle window.