20 System-Thinking DSA Problems

1// PROBLEM 1: HIT COUNTER — Count hits in last 5 minutes
2class HitCounter {
3  constructor() {
4    this.hits = new Array(300).fill(0); // 5 min = 300 sec
5    this.times = new Array(300).fill(0);
6  }
7
8  hit(timestamp) {
9    const idx = timestamp % 300;
10    if (this.times[idx] !== timestamp) {
11      this.times[idx] = timestamp;
12      this.hits[idx] = 1;
13    } else {
14      this.hits[idx]++;
15    }
16  }
17
18  getHits(timestamp) {
19    let total = 0;
20    for (let i = 0; i < 300; i++) {
21      if (timestamp - this.times[i] < 300) total += this.hits[i];
22    }
23    return total;
24  }
25}
26
27// PROBLEM 7: URL SHORTENER
28class URLShortener {
29  constructor() {
30    this.urlToCode = new Map();
31    this.codeToUrl = new Map();
32    this.counter = 0;
33  }
34
35  encode(longUrl) {
36    if (this.urlToCode.has(longUrl)) return this.urlToCode.get(longUrl);
37    const code = this.toBase62(this.counter++);
38    this.urlToCode.set(longUrl, code);
39    this.codeToUrl.set(code, longUrl);
40    return 'http://tiny.url/' + code;
41  }
42
43  decode(shortUrl) {
44    const code = shortUrl.split('/').pop();
45    return this.codeToUrl.get(code);
46  }
47
48  toBase62(num) {
49    const chars = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
50    if (num === 0) return '0';
51    let result = '';
52    while (num > 0) { result = chars[num % 62] + result; num = Math.floor(num / 62); }
53    return result;
54  }
55}
56
57// PROBLEM 16: CONSISTENT HASHING
58class ConsistentHash {
59  constructor(numReplicas = 3) {
60    this.replicas = numReplicas;
61    this.ring = new Map(); // hash → server
62    this.sortedKeys = [];
63  }
64
65  hash(key) {
66    let h = 0;
67    for (let i = 0; i < key.length; i++) h = (h * 31 + key.charCodeAt(i)) & 0x7fffffff;
68    return h;
69  }
70
71  addServer(server) {
72    for (let i = 0; i < this.replicas; i++) {
73      const h = this.hash(server + ':' + i);
74      this.ring.set(h, server);
75      this.sortedKeys.push(h);
76    }
77    this.sortedKeys.sort((a, b) => a - b);
78  }
79
80  getServer(key) {
81    const h = this.hash(key);
82    for (const k of this.sortedKeys) {
83      if (k >= h) return this.ring.get(k);
84    }
85    return this.ring.get(this.sortedKeys[0]); // Wrap around
86  }
87}
88
89// PROBLEM 19: UNDO/REDO
90class UndoRedo {
91  constructor() { this.undoStack = []; this.redoStack = []; this.state = ''; }
92
93  execute(operation) {
94    this.undoStack.push(this.state);
95    this.state = operation(this.state);
96    this.redoStack = []; // Clear redo after new action
97  }
98
99  undo() {
100    if (this.undoStack.length === 0) return;
101    this.redoStack.push(this.state);
102    this.state = this.undoStack.pop();
103  }
104
105  redo() {
106    if (this.redoStack.length === 0) return;
107    this.undoStack.push(this.state);
108    this.state = this.redoStack.pop();
109  }
110}