Query Batching - Practice Coding Problems

Query Batching - Problem

JavaScript Hard

Design and implement a QueryBatcher class that efficiently batches multiple small queries into larger ones using a throttling mechanism.

The class constructor accepts:

queryMultiple: An asynchronous function that takes an array of string keys and returns a Promise resolving to an array of corresponding values
t: Throttle time in milliseconds

Implement the method:

async getValue(key): Returns a Promise that resolves to the value for the given key

Throttling Rules:

First call to getValue immediately triggers queryMultiple
Subsequent calls within t milliseconds are batched together
After t milliseconds, all pending keys are sent to queryMultiple
Each key is guaranteed to be unique

Input & Output

Example 1 — Basic Throttling

$ Input: queryMultiple = async (keys) => keys.map(k => `value_${k}`), t = 100

› Output: First getValue('key1') returns 'value_key1' immediately, subsequent calls batched

💡 Note: First call executes immediately. Calls within 100ms window get batched together and executed after timeout.

Example 2 — Multiple Batches

$ Input: Multiple getValue calls over time with 200ms throttle

› Output: Separate batches for calls outside throttle window

💡 Note: Calls separated by more than throttle time create new batches, maintaining efficient grouping.

Example 3 — Single Key Immediate

$ Input: Single getValue call when no pending queries

› Output: Immediate execution without waiting

💡 Note: When no queries are pending and enough time has passed, execute immediately for best performance.

Constraints

1 ≤ t ≤ 10⁴ (throttle time in milliseconds)
queryMultiple never rejects
All keys passed to getValue are unique
queryMultiple returns array same length as input

Visualization

Tap to expand

Understanding the Visualization

Input Queries

Multiple getValue calls with different keys

Throttle Logic

First call immediate, others batched within time window

Batched Output

Fewer queryMultiple calls with better efficiency

Key Takeaway

🎯 Key Insight: Throttling creates optimal batches while maintaining fast response for the first query

Asked in

N Netflix 15 U Uber 12 M Meta 10 G Google 8

The key insight is implementing a throttling mechanism that balances responsiveness with efficiency. The optimal approach uses immediate execution for the first call and setTimeout-based batching for subsequent calls within the throttle window. Time: O(1) per call, Space: O(k) where k is batch size.

Common Approaches

Approach	Time	Space	Notes
✓ Immediate Query Approach	O(1)	O(1)	Call queryMultiple immediately for every getValue request
Throttled Batching	O(1)	O(k)	Use setTimeout to batch queries within throttle window

Immediate Query Approach — Algorithm Steps

Step 1: Receive key in getValue
Step 2: Immediately call queryMultiple with [key]
Step 3: Return the result

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

getValue('key1') → queryMultiple(['key1'])

Second Call

getValue('key2') → queryMultiple(['key2'])

Result

Two separate query calls, no batching

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Simplified synchronous version for C
typedef struct {
    char** (*queryMultiple)(char** keys, int count, int* resultCount);
    int t;
} QueryBatcher;

QueryBatcher* createQueryBatcher(char** (*qm)(char**, int, int*), int t) {
    QueryBatcher* batcher = malloc(sizeof(QueryBatcher));
    batcher->queryMultiple = qm;
    batcher->t = t;
    return batcher;
}

char* getValue(QueryBatcher* batcher, char* key) {
    char** keys = malloc(sizeof(char*));
    keys[0] = key;
    int resultCount;
    char** results = batcher->queryMultiple(keys, 1, &resultCount);
    char* result = malloc(strlen(results[0]) + 1);
    strcpy(result, results[0]);
    free(keys);
    return result;
}

char** mockQueryMultiple(char** keys, int count, int* resultCount) {
    *resultCount = count;
    char** results = malloc(count * sizeof(char*));
    for (int i = 0; i < count; i++) {
        results[i] = malloc(100);
        snprintf(results[i], 100, "value_%s", keys[i]);
    }
    return results;
}

int main() {
    int t;
    scanf("%d", &t);
    
    QueryBatcher* batcher = createQueryBatcher(mockQueryMultiple, t);
    char* result1 = getValue(batcher, "key1");
    char* result2 = getValue(batcher, "key2");
    
    printf("[\"%s\",\"%s\"]\n", result1, result2);
    
    free(result1);
    free(result2);
    free(batcher);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Single function call per request

✓ Linear Growth

Space Complexity

O(1)

No additional storage needed

✓ Linear Space

25.4K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Immediate Query Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler