Query batching

67.9% acceptance

Mar 31, 2026

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.

Solution

TypeScript

Time O(n)

Space O(1)

LeetCode

solution.ts

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

class QueryBatcher {
  private queryMultiple: QueryMultiple;
  private t: number;
  private queue: { key: string; resolve: (val: string) => void }[] = [];
  private lastCallTime: number = -Infinity;
  private timer: ReturnType<typeof setTimeout> | null = null;
  
  constructor(queryMultiple: QueryMultiple, t: number) {
    this.queryMultiple = queryMultiple;
    this.t = t;
  }
  
  async getValue(key: string): Promise<string> {
    return new Promise<string>((resolve) => {
      this.queue.push({ key, resolve });
      if (this.queue.length === 1 && this.timer === null) {
        const now = Date.now();
        const elapsed = now - this.lastCallTime;
        if (elapsed >= this.t) {
          this.flush();
        } else {
          this.timer = setTimeout(() => this.flush(), this.t - elapsed);
        }
      }
    });
  }
  
  private flush() {
    this.timer = null;
    this.lastCallTime = Date.now();
    const batch = [...this.queue];
    this.queue = [];
    const keys = batch.map(b => b.key);
    this.queryMultiple(keys).then(results => {
      for (let i = 0; i < batch.length; i++) {
        batch[i].resolve(results[i]);
      }
    });
    if (this.queue.length > 0) {
      this.timer = setTimeout(() => this.flush(), this.t);
    }
  }
};

/**
 * async function queryMultiple(keys) { 
 *   return keys.map(key => key + '!');
 * }
 *
 * const batcher = new QueryBatcher(queryMultiple, 100);
 * batcher.getValue('a').then(console.log); // resolves "a!" at t=0ms 
 * batcher.getValue('b').then(console.log); // resolves "b!" at t=100ms 
 * batcher.getValue('c').then(console.log); // resolves "c!" at t=100ms 
 */