Untitled
unknown
typescript
25 days ago
8.1 kB
3
Indexable
// 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.");
Editor is loading...
Leave a Comment