Untitled

// the problem essentially requires to implement a sliding window rate limiter

// simple approach that keeps track of the last click times for each event
function solutionNaive(clickData: string[][], maxClicks: number, timeAllowed: number): number[][] {
    const appeared = new Map<string, number[]>();

    return clickData.map((clicks, i) => clicks.map((click) => {
        if (!appeared.has(click)) appeared.set(click, []);
        let count = 0;
        const clickTimes = appeared.get(click)!;
        // reversing ensures that we only consider the click times that are within the timeAllowed window
        // since the click times are in increasing order
        for (let j = clickTimes.length - 1; j >= 0; j--) {
            if (clickTimes[j] < i - timeAllowed + 1) break;
            count += 1;
        }

        if (count < maxClicks) {
            clickTimes.push(i);
            return 1;
        }
        return 0;
    }));
}

// in a more structured and flexible approach, we can use a sliding window to keep track of the events
// with a circular buffer as the underlying data structure to allow O(1) pop/push on both ends
// this is a minimal implementation
class RingBuffer<T> {
    private buffer: (T | undefined)[];
    private head: number;
    private tail: number;
    private size: number;
    private capacity: number;

    constructor(initialCapacity: number = 16) {
        this.capacity = initialCapacity;
        this.buffer = new Array(initialCapacity);
        this.head = 0;
        this.tail = 0;
        this.size = 0;
    }

    public push(item: T): void {
        if (this.size === this.capacity) {
            this.resize();
        }
        this.buffer[this.tail] = item;
        this.tail = (this.tail + 1) % this.capacity;
        this.size++;
    }

    public shift(): T | undefined {
        if (this.size === 0) {
            return undefined;
        }
        const item = this.buffer[this.head];
        this.buffer[this.head] = undefined;
        this.head = (this.head + 1) % this.capacity;
        this.size--;
        return item;
    }

    public get length(): number {
        return this.size;
    }

    public peek(): T | undefined {
        if (this.size === 0) {
            return undefined;
        }
        return this.buffer[this.head];
    }

    public getArray(): T[] {
        const result: T[] = new Array(this.size);
        for (let i = 0; i < this.size; i++) {
            result[i] = this.buffer[(this.head + i) % this.capacity] as T;
        }
        return result;
    }

    private resize(): void {
        const newCapacity = this.capacity * 2;
        const newBuffer: (T | undefined)[] = new Array(newCapacity);
        for (let i = 0; i < this.size; i++) {
            newBuffer[i] = this.buffer[(this.head + i) % this.capacity];
        }
        this.buffer = newBuffer;
        this.capacity = newCapacity;
        this.head = 0;
        this.tail = this.size;
    }
}

class EventTimeSlidingWindow {
    public maxAge: number;
    private queue: RingBuffer<[number, number]>;

    constructor(maxAge: number) {
        this.maxAge = maxAge;
        this.queue = new RingBuffer(2);
    }

    public push(evt: [number, number]): void {
        this.queue.push(evt);
    }

    public getQueue(): [number, number][] {
        return this.queue.getArray();
    }

    public evictExpired(currentTime: number): void {
        while (this.queue.peek() !== undefined) {
            const [time, _] = this.queue.peek()!;
            if (time > currentTime - this.maxAge) {
                break;
            }
            this.queue.shift();
        }
    }
}

function solutionWindow(
    clickData: string[][],
    maxClicks: number,
    timeAllowed: number
): number[][] {
    const windows: { [key: string]: EventTimeSlidingWindow } = {};
    return clickData.map((clicks, i) => clicks.map((click) => {
        if (!(click in windows)) {
            windows[click] = new EventTimeSlidingWindow(timeAllowed);
        }
        const evtWindow = windows[click];
        evtWindow.evictExpired(i);

        // we could use a generator function to avoid the need to iterate over the queue twice
        // it's also probably possible to keep a running sum of the clicks in the window, with some additional bookkeeping
        const sumClicks = evtWindow.getQueue().reduce((acc, cur) => acc + cur[1], 0);
        const clickValue = sumClicks < maxClicks ? 1 : 0;

        evtWindow.push([i, clickValue]);
        return clickValue;
    }));
}

// validation

const solutions: { name: string; fn: (clickData: string[][], max_clicks: number, time_allowed: number) => number[][] }[] = [
    { name: "solutionNaive", fn: solutionNaive },
    { name: "solutionWindow", fn: solutionWindow },
];

// not using a testing framework to keep the code simple and make it runnable in a playground

type TestCase = {
    inp: string[][];
    max_clicks: number;
    time_allowed: number;
    expected: number[][];
};

const testCases: TestCase[] = [
    {
        inp: [["101"], ["101"], ["101"], ["101"], ["101"], ["101"]],
        max_clicks: 2,
        time_allowed: 4,
        expected: [[1], [1], [0], [0], [1], [1]],
    },
    {
        inp: [
            ["101", "201"],
            ["101"],
            ["101", "201"],
            ["101"],
            ["101", "201"],
            ["101"],
        ],
        max_clicks: 2,
        time_allowed: 4,
        expected: [[1, 1], [1], [0, 1], [0], [1, 1], [1]],
    },
    {
        inp: [["101"], ["102"], ["103"]],
        max_clicks: 1,
        time_allowed: 1,
        expected: [[1], [1], [1]],
    },
    {
        inp: [["101"], ["101"], ["101"], ["101"], ["101"]],
        max_clicks: 3,
        time_allowed: 3,
        expected: [[1], [1], [1], [1], [1]],
    },
    {
        inp: [["101", "102"], ["102", "103"], ["101", "103"]],
        max_clicks: 1,
        time_allowed: 2,
        expected: [[1, 1], [0, 1], [1, 0]],
    },
    {
        inp: [],
        max_clicks: 1,
        time_allowed: 1,
        expected: [],
    },
    {
        inp: [[], [], []],
        max_clicks: 1,
        time_allowed: 1,
        expected: [[], [], []],
    },
    {
        inp: [["101"], ["101"]],
        max_clicks: 0,
        time_allowed: 2,
        expected: [[0], [0]],
    },
    {
        inp: [["101"], ["101"], ["101"]],
        max_clicks: 2,
        time_allowed: 0,
        expected: [[1], [1], [1]],
    },
    {
        inp: [["101"], ["101"], ["101"], ["101"], ["101"]],
        max_clicks: 3,
        time_allowed: 4,
        expected: [[1], [1], [1], [0], [1]],
    },
    {
        inp: [["101", "102"], ["101", "102"], ["101"], ["102"], ["101", "102"]],
        max_clicks: 2,
        time_allowed: 3,
        expected: [[1, 1], [1, 1], [0], [1], [1, 1]],
    },
    {
        inp: [["101"], ["101"], ["101"], ["101"]],
        max_clicks: 4,
        time_allowed: 10,
        expected: [[1], [1], [1], [1]],
    },
    {
        inp: [["101"], [], [], [], ["101"], ["101"]],
        max_clicks: 1,
        time_allowed: 3,
        expected: [[1], [], [], [], [1], [0]],
    },
    {
        inp: [
            ["101", "102"],
            ["101", "103"],
            ["101", "104"],
            ["102", "103"],
            ["101", "104"],
            ["102"],
        ],
        max_clicks: 2,
        time_allowed: 4,
        expected: [[1, 1], [1, 1], [0, 1], [1, 1], [1, 1], [1]],
    },
];

function deepEqual(a: unknown, b: unknown): boolean {
    return JSON.stringify(a) === JSON.stringify(b);
}

for (const sol of solutions) {
    for (let idx = 0; idx < testCases.length; idx++) {
        const { inp, max_clicks, time_allowed, expected } = testCases[idx];
        const result = sol.fn(inp, max_clicks, time_allowed);
        if (!deepEqual(result, expected)) {
            throw new Error(
                `${sol.name} failed case #${idx + 1}: (got) ${JSON.stringify(result)} != (expected) ${JSON.stringify(expected)}`
            );
        }
    }
}

console.log("All tests passed successfully.");