These are the notes for JavaScript Coding Questions, episode 28, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Last episode we built stacks and queues on plain arrays. Today we pick up two sharper tools: Map and Set. Three questions interviewers love: an LRU cache, group anagrams, and the longest consecutive sequence in O(n).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was run with Node.js 24 (node main.js), the SyntaxPilot compiler's JavaScript command, and every output below is real. Some programs measure time with console.time("label") and console.timeEnd("label"), which print how long the code between them took. Timings differ on every machine and every run: only the size of the difference (seconds against milliseconds) matters.
First: Map and Set in one minute
A shop keeps a stock register: next to each item's name, how many are left. That's a Map: a collection of key → value pairs. A teacher's attendance sheet ticks each roll number once; ticking it twice changes nothing. That's a Set: a collection of unique values.
| Map | Set | |
|---|---|---|
| Holds | key → value pairs | unique values |
| Add | map.set(key, value) |
set.add(value) |
| Read | map.get(key) (or undefined) |
— |
| Is it there? | map.has(key) |
set.has(value) |
| Remove | map.delete(key) |
set.delete(value) |
| How many | map.size |
set.size |
| Order when you loop | the order keys were first inserted | the order values were first added |
Speed of has / get |
O(1) on average | O(1) on average |
const stock = new Map();
stock.set("samosa", 12);
stock.set("vada pav", 8);
stock.set(1, "a number key");
console.log(stock.get("samosa"), stock.has("idli"), stock.size);
console.log([...stock.keys()]);
const present = new Set([7, 3, 7, 9, 3]);
present.add(12);
console.log(present, present.has(9), present.size);
12 false 3
[ 'samosa', 'vada pav', 1 ]
Set(4) { 7, 3, 9, 12 } true 4
- O(1) ("order one", constant time): the work doesn't grow with the size of the collection.
map.has(key)on a Map with a million keys is about as fast as on a Map with ten. O(n): the work grows in step with n.array.includes(x)andarray.find(...)may read every element: O(n). [...stock.keys()]uses the spread operator...to copy the keys into an array so we can print them.- Unlike a plain object, a Map's key can be any value: a number stays a number, an object can be a key. A plain object turns every key into a string (see the quiz).
Map vs plain object
const m = new Map();
m.set(1, "number"); m.set("1", "string");
const o = {};
o[1] = "number"; o["1"] = "string";
console.log(m.size, Object.keys(o).length);
console.log(m.get(1), m.get("1"), o[1]);
const visits = new Map();
const asha = { name: "Asha" };
visits.set(asha, 3); // an object as a key
console.log(visits.get(asha), visits.get({ name: "Asha" }));
2 1
number string string
3 undefined
An object key is matched by identity (the same object in memory), not by its contents: { name: "Asha" } written again is a different object, so get gives undefined.
Q1: LRU cache
Problem. Design a class LRUCache(capacity) with:
get(key): the value forkey, or-1if it isn't there. Agetcounts as using the key.put(key, value): store the pair (update it if the key exists). If that makes the cache bigger thancapacity, throw out the least recently used key: the one nobody has used for the longest time.- Both in O(1).
A cache is a small, fast store that keeps recently used data so you don't fetch or compute it again. LRU stands for Least Recently Used, the rule for what to throw out (evict) when it's full.
Real life. A phone's recent apps screen with room for 2 apps. Open maps, open chat, go back to maps, then open music: chat gets closed, because maps was used more recently.
put maps → [maps]
put chat → [maps, chat]
get maps → [chat, maps] maps used again: it becomes the newest
put music → [maps, music] full: chat (the oldest) is evicted
get chat → -1
Edge cases. A get refreshes a key; put on a key that already exists (update + refresh, no eviction); capacity 1; a big cache.
Attempt: an array of pairs, oldest first
class LRUCache {
constructor(capacity) { this.capacity = capacity; this.items = []; }
get(key) {
const i = this.items.findIndex(p => p[0] === key);
if (i === -1) return -1;
const [pair] = this.items.splice(i, 1);
this.items.push(pair);
return pair[1];
}
put(key, value) {
const i = this.items.findIndex(p => p[0] === key);
if (i !== -1) this.items.splice(i, 1);
this.items.push([key, value]);
if (this.items.length > this.capacity) this.items.shift();
}
}
const apps = new LRUCache(2);
apps.put("maps", 1); apps.put("chat", 2);
apps.get("maps");
apps.put("music", 3);
console.log(apps.get("chat"), apps.get("maps"), apps.get("music"));
const big = new LRUCache(20000);
console.time("40,000 operations");
for (let i = 0; i < 40000; i++) { big.put(i % 25000, i); big.get(i % 21000); }
console.timeEnd("40,000 operations");
-1 1 3
40,000 operations: 3.373s
Correct, but seconds (on our machine) for 40,000 puts and 40,000 gets.
Why? findIndex reads pairs one by one until it finds the key: O(n). splice(i, 1) and shift() then move every pair after the gap one place: O(n). So every get and put is O(capacity), not O(1).
The trap: set on an existing key keeps its place
A Map remembers the order keys were first inserted. That order is exactly "oldest used → newest used" if we re-insert a key every time it's used. But:
const recent = new Map();
recent.set("maps", 1); recent.set("chat", 2); recent.set("music", 3);
console.log([...recent.keys()]);
recent.set("maps", 10);
console.log([...recent.keys()]);
console.log(recent.keys().next().value);
recent.delete("maps"); recent.set("maps", 10);
console.log([...recent.keys()]);
[ 'maps', 'chat', 'music' ]
[ 'maps', 'chat', 'music' ]
maps
[ 'chat', 'music', 'maps' ]
seton a key that already exists updates the value but keeps the old position.- To move a key to the newest end:
deleteit, thensetit. map.keys()returns an iterator (an object that hands out the keys one at a time)..next()gives{ value, done }for the first key, somap.keys().next().valueis the oldest key, in O(1).
Fix: a Map, refreshed with delete + set
class LRUCache {
constructor(capacity) { this.capacity = capacity; this.map = new Map(); }
get(key) {
if (!this.map.has(key)) return -1;
const value = this.map.get(key);
this.map.delete(key); this.map.set(key, value);
return value;
}
put(key, value) {
this.map.delete(key); this.map.set(key, value);
if (this.map.size > this.capacity)
this.map.delete(this.map.keys().next().value);
}
}
const apps = new LRUCache(2);
apps.put("maps", 1); apps.put("chat", 2);
apps.get("maps");
apps.put("music", 3);
console.log(apps.get("chat"), apps.get("maps"), apps.get("music"));
apps.put("maps", 10); apps.put("news", 4);
console.log([...apps.map.keys()], apps.get("maps"));
const big = new LRUCache(20000);
console.time("40,000 operations");
for (let i = 0; i < 40000; i++) { big.put(i % 25000, i); big.get(i % 21000); }
console.timeEnd("40,000 operations");
-1 1 3
[ 'maps', 'news' ] 10
40,000 operations: 142.344ms
getcheckshasfirst, so a stored value like0orundefinedis not mistaken for "missing".putdeletes first (harmless if the key is new), so an update also refreshes the key.- After
get("music")andget("maps"), the order is[music, maps];put("maps", 10)refreshes maps, soput("news", 4)evicts music:[ 'maps', 'news' ].
Complexity. get and put: O(1) on average (a fixed number of Map operations). Space: O(capacity).
In languages without an ordered map (C++, Java's HashMap), the classic answer is a hash map + doubly linked list. JavaScript's Map is already ordered, which is why this answer is so short. If the interviewer asks for the linked-list version, see "Going further".
Q2: Group anagrams
Problem. Given an array of words, group the words that are anagrams of each other: same letters, same counts, different order.
["eat", "tea", "tan", "ate", "nat", "bat"] → [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
Real life. Give each word's letters as tiles and line them up A to Z: eat, tea and ate all become a e t. Same line-up, same group. The line-up is the group's key.
Edge cases. Empty strings ("" and "" are anagrams), a single word, an empty list, thousands of words.
Attempt 1: w.sort()
const key = w => w.sort().join("");
function groupAnagrams(words) {
const groups = [];
for (const w of words) {
const g = groups.find(g => key(g[0]) === key(w));
if (g) g.push(w); else groups.push([w]);
}
return groups;
}
console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
main.js:1
const key = w => w.sort().join("");
^
TypeError: w.sort is not a function
Why? sort is an array method. A string is not an array, and strings are immutable (they can't be changed in place), so there's no sort on them. Split it into an array of letters, sort, join back: w.split("").sort().join("").
Attempt 2: the right key, but find over every group
const key = w => w.split("").sort().join("");
function groupAnagrams(words) {
const groups = [];
for (const w of words) {
const g = groups.find(g => key(g[0]) === key(w));
if (g) g.push(w); else groups.push([w]);
}
return groups;
}
console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
const many = Array.from({ length: 6000 }, (_, i) => "w" + i.toString(36));
console.time("6,000 words");
groupAnagrams(many);
console.timeEnd("6,000 words");
[ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]
6,000 words: 6.148s
Right groups, but seconds for 6,000 different words.
Why? For every word, find walks through every group so far and recomputes both keys each time: up to n × n key calculations, O(n²). (i.toString(36) writes i in base 36, digits and letters, an easy way to make thousands of different words.)
Fix: a Map from key to its group
const key = w => w.split("").sort().join("");
function groupAnagrams(words) {
const groups = new Map();
for (const w of words) {
const k = key(w);
if (!groups.has(k)) groups.set(k, []);
groups.get(k).push(w);
}
return [...groups.values()];
}
console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
console.log(groupAnagrams(["", ""]), groupAnagrams(["a"]), groupAnagrams([]));
const many = Array.from({ length: 6000 }, (_, i) => "w" + i.toString(36));
console.time("6,000 words");
groupAnagrams(many);
console.timeEnd("6,000 words");
[ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]
[ [ '', '' ] ] [ [ 'a' ] ] []
6,000 words: 6.786ms
Complexity. n words, each up to k letters. Each key costs O(k log k) (sorting k letters), each Map lookup O(1): O(n · k log k) time, O(n · k) space.
A faster key: count the letters
For lowercase a–z, count each letter instead of sorting: O(k) per word. Join the 26 counts with a separator, or "aab" and "ab" + extra digits could collide.
function countKey(w) {
const counts = new Array(26).fill(0);
for (const ch of w) counts[ch.charCodeAt(0) - 97]++;
return counts.join("#");
}
console.log(countKey("eat") === countKey("tea"), countKey("eat") === countKey("eta"));
console.log(countKey("ab") === countKey("aab"));
true true
false
"a".charCodeAt(0) is 97, so charCodeAt(0) - 97 turns a…z into 0…25. Time O(n · k).
Q3: Longest consecutive sequence
Problem. Given unsorted integers, return the length of the longest run of consecutive values (x, x+1, x+2, …). The values can be in any order in the array. Aim for O(n).
[100, 4, 200, 1, 3, 2] → 4 (1, 2, 3, 4)
Real life. The roll numbers of students present today, written down as they walked in. What's the longest unbroken run of roll numbers?
Edge cases. Duplicates ([1, 2, 2, 3] → 3), negatives, a single number, an empty list (→ 0), 30,000 numbers.
Attempt 1: sort, then walk
function longest(rolls) {
const s = [...rolls].sort();
let best = 0, run = 0;
for (let i = 0; i < s.length; i++) {
run = (i > 0 && s[i] === s[i - 1] + 1) ? run + 1 : 1;
best = Math.max(best, run);
}
return best;
}
console.log([100, 4, 200, 1, 3, 2].sort());
console.log(longest([100, 4, 200, 1, 3, 2]));
[ 1, 100, 2, 200, 3, 4 ]
2
Why? With no comparator (the function that tells sort which of two items comes first), sort converts every element to a string and compares the text. "100" starts with "1", so it comes before "2". For numbers, always pass (a, b) => a - b (negative: a first, positive: b first).
Attempt 2: numeric sort, but duplicates
function longest(rolls) {
const s = [...rolls].sort((a, b) => a - b);
let best = 0, run = 0;
for (let i = 0; i < s.length; i++) {
run = (i > 0 && s[i] === s[i - 1] + 1) ? run + 1 : 1;
best = Math.max(best, run);
}
return best;
}
console.log(longest([100, 4, 200, 1, 3, 2]));
console.log(longest([1, 2, 2, 3]));
4
2
The duplicate 2 isn't "one more than 2", so the run restarted. You could skip equal neighbours (if (s[i] === s[i - 1]) continue;), and that version is correct, but sorting is still O(n log n), and the question asks for O(n).
Attempt 3: a Set, counting up from every number
function longest(rolls) {
const present = new Set(rolls);
let best = 0;
for (const x of present) {
let len = 1;
while (present.has(x + len)) len++;
best = Math.max(best, len);
}
return best;
}
console.log(longest([100, 4, 200, 1, 3, 2]));
const allPresent = Array.from({ length: 30000 }, (_, i) => i);
console.time("30,000 rolls");
console.log(longest(allPresent));
console.timeEnd("30,000 rolls");
4
30000
30,000 rolls: 8.618s
The Set removes duplicates and answers "is x present?" in O(1). Correct, but seconds for one long run of 30,000.
Why? 0 counts 30,000 steps, 1 counts 29,999, 2 counts 29,998… about n²/2 = 450 million steps: O(n²).
Fix: only count from the start of a run
A run can only start at x if x − 1 is missing. If x − 1 is present, x is in the middle of someone else's run: skip it.
function longest(rolls) {
const present = new Set(rolls);
let best = 0;
for (const x of present) {
if (present.has(x - 1)) continue; // not the start of a run
let len = 1;
while (present.has(x + len)) len++;
best = Math.max(best, len);
}
return best;
}
console.log(longest([100, 4, 200, 1, 3, 2]));
console.log(longest([1, 2, 2, 3]), longest([7]), longest([]));
console.log(longest([-1, 0, 1, 5]));
const allPresent = Array.from({ length: 30000 }, (_, i) => i);
console.time("30,000 rolls");
console.log(longest(allPresent));
console.timeEnd("30,000 rolls");
4
3 1 0
3
30000
30,000 rolls: 7.026ms
Complexity. Building the Set: O(n). The while loop only runs from the start of each run, so across the whole program it visits each number once. Total O(n) time, O(n) space. continue jumps straight to the next turn of the loop.
Going further
LRU cache with a hash map + doubly linked list
This is the version for languages without an ordered map, and a common follow-up ("now do it without relying on Map's order"). A doubly linked list is a chain of nodes where each node points to the next and the previous one, so a node can be unlinked in O(1). The Map gives O(1) access from a key to its node.
class Node { constructor(key, value) { this.key = key; this.value = value; this.prev = this.next = null; } }
class LRUList {
constructor(capacity) {
this.capacity = capacity; this.map = new Map();
this.head = new Node(); this.tail = new Node(); // sentinels: oldest after head, newest before tail
this.head.next = this.tail; this.tail.prev = this.head;
}
unlink(n) { n.prev.next = n.next; n.next.prev = n.prev; }
addNewest(n) { n.prev = this.tail.prev; n.next = this.tail; this.tail.prev.next = n; this.tail.prev = n; }
get(key) {
const n = this.map.get(key);
if (!n) return -1;
this.unlink(n); this.addNewest(n);
return n.value;
}
put(key, value) {
let n = this.map.get(key);
if (n) { n.value = value; this.unlink(n); }
else { n = new Node(key, value); this.map.set(key, n); }
this.addNewest(n);
if (this.map.size > this.capacity) {
const old = this.head.next;
this.unlink(old); this.map.delete(old.key);
}
}
}
const apps = new LRUList(2);
apps.put("maps", 1); apps.put("chat", 2);
apps.get("maps");
apps.put("music", 3);
console.log(apps.get("chat"), apps.get("maps"), apps.get("music"));
-1 1 3
Sentinels are dummy nodes at both ends, so unlink and addNewest never have to check for null.
Map, Set and the newer Set methods
Node 22 and later have set operations built in:
const java = new Set(["Asha", "Ravi", "Neha"]);
const js = new Set(["Ravi", "Kabir", "Neha"]);
console.log(java.intersection(js));
console.log(java.union(js));
console.log(java.difference(js));
console.log(java.isSubsetOf(new Set(["Asha", "Ravi", "Neha", "Meera"])));
Set(2) { 'Ravi', 'Neha' }
Set(4) { 'Asha', 'Ravi', 'Neha', 'Kabir' }
Set(1) { 'Asha' }
true
Map.groupBy
Map.groupBy(items, fn) puts every item into a Map under the key fn returns: exactly our anagram tray desk.
const words = ["eat", "tea", "tan", "ate", "nat", "bat"];
const groups = Map.groupBy(words, w => w.split("").sort().join(""));
console.log(groups);
console.log([...groups.values()]);
Map(3) {
'aet' => [ 'eat', 'tea', 'ate' ],
'ant' => [ 'tan', 'nat' ],
'abt' => [ 'bat' ]
}
[ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]
Complexity summary
| Question | Attempt | Time | Fix | Time | Extra space |
|---|---|---|---|---|---|
| LRU cache | array + findIndex / splice / shift |
O(capacity) per call | Map + delete/set, evict keys().next() |
O(1) per call | O(capacity) |
| Group anagrams | find over all groups |
O(n² · k log k) | Map from sorted key | O(n · k log k) (O(n · k) with a count key) | O(n · k) |
| Longest run | sort + walk | O(n log n) | Set + start only where x − 1 is missing | O(n) | O(n) |
| Longest run | Set, count from every number | O(n²) | (same fix) | O(n) | O(n) |
Common mistakes (and the exact outputs)
| Mistake | Code | What you see | Why | Fix |
|---|---|---|---|---|
Refreshing with set alone |
recent.set("maps", 10) |
[ 'maps', 'chat', 'music' ] (maps still first) |
set on an existing key keeps its place |
delete(key) then set(key, value) |
Array + findIndex cache |
this.items.findIndex(...) |
40,000 operations: 3.373s (on our machine) |
O(n) search, splice and shift |
a Map |
Testing get(key) for missing |
if (!this.map.get(key)) |
a stored 0 counts as missing |
0, "", false are falsy |
this.map.has(key) |
| Sorting a string | "tea".sort() |
TypeError: w.sort is not a function |
sort is an array method |
w.split("").sort().join("") |
| Sorting numbers with no comparator | [100, 4, 200, 1, 3, 2].sort() |
[ 1, 100, 2, 200, 3, 4 ] |
the default compares text | sort((a, b) => a - b) |
| Ignoring duplicates after a sort | longest([1, 2, 2, 3]) |
2 |
the duplicate restarts the run | skip equal neighbours, or use a Set |
| Counting from every number | while (present.has(x + len)) for every x |
30,000 rolls: 8.618s (on our machine) |
O(n²) on one long run | if (present.has(x - 1)) continue; |
| Object keys | o[1] and o["1"] |
1 key, not 2 |
objects turn keys into strings | a Map keeps the type |
The get trap, for real:
const prices = new Map([["free sample", 0], ["chai", 15]]);
for (const item of ["free sample", "chai", "idli"]) {
console.log(item, "| truthy check:", prices.get(item) ? "found" : "missing", "| has:", prices.has(item));
}
free sample | truthy check: missing | has: true
chai | truthy check: found | has: true
idli | truthy check: missing | has: false
Mini project: a "recently viewed" list for a shopping app
Show the last 3 products a user viewed, newest first, with no duplicates. Viewing a product again moves it to the front. It's the LRU idea without values.
class RecentlyViewed {
constructor(limit) { this.limit = limit; this.items = new Set(); }
view(product) {
this.items.delete(product); // move to the newest end
this.items.add(product);
if (this.items.size > this.limit) this.items.delete(this.items.values().next().value);
}
list() { return [...this.items].reverse(); } // newest first
}
const r = new RecentlyViewed(3);
for (const p of ["kurta", "shoes", "watch", "shoes", "bag"]) {
r.view(p);
console.log(`viewed ${p.padEnd(5)} →`, r.list());
}
viewed kurta → [ 'kurta' ]
viewed shoes → [ 'shoes', 'kurta' ]
viewed watch → [ 'watch', 'shoes', 'kurta' ]
viewed shoes → [ 'shoes', 'watch', 'kurta' ]
viewed bag → [ 'bag', 'shoes', 'watch' ]
A Set keeps insertion order too, and delete + add moves a value to the end, just like the Map in Q1.
Your turn: two sum with a Map (solution)
Given item prices and a budget, return the indexes of two items that add up exactly to the budget (or null).
function twoSum(prices, budget) {
const seen = new Map(); // price → index
for (let i = 0; i < prices.length; i++) {
const need = budget - prices[i];
if (seen.has(need)) return [seen.get(need), i];
seen.set(prices[i], i);
}
return null;
}
console.log(twoSum([40, 15, 25, 60], 65));
console.log(twoSum([30, 30], 60));
console.log(twoSum([10, 20], 100), twoSum([], 5));
[ 0, 2 ]
[ 0, 1 ]
null null
- Walk once. For each price, ask the Map for the partner
budget - pricebefore storing the current price, so an item is never paired with itself, and[30, 30]still works. - Time O(n), space O(n). The nested-loop version is O(n²).
Practice questions (with solutions)
1. First unique character. Return the index of the first character that appears exactly once, or −1.
Solution
function firstUnique(s) {
const count = new Map();
for (const ch of s) count.set(ch, (count.get(ch) ?? 0) + 1);
for (let i = 0; i < s.length; i++) if (count.get(s[i]) === 1) return i;
return -1;
}
console.log(firstUnique("samosa"), firstUnique("chai"), firstUnique("aabb"));
2 0 -1
Two passes: count, then find. count.get(ch) ?? 0 gives 0 for a letter not seen yet (?? uses the right side only for null or undefined). O(n).
2. Intersection of two arrays (each common value once).
Solution
function intersect(a, b) {
const inB = new Set(b);
return [...new Set(a.filter(x => inB.has(x)))];
}
console.log(intersect([1, 2, 2, 3, 4], [2, 4, 4, 6]));
console.log(intersect([1, 2], [3]));
[ 2, 4 ]
[]
a.filter(x => inB.has(x)) keeps the common values (O(1) each); new Set(...) drops repeats. O(n + m).
3. Contains a duplicate within k positions. Is there i ≠ j with nums[i] === nums[j] and |i − j| ≤ k?
Solution
function nearbyDuplicate(nums, k) {
const last = new Map(); // value → its latest index
for (let i = 0; i < nums.length; i++) {
if (last.has(nums[i]) && i - last.get(nums[i]) <= k) return true;
last.set(nums[i], i);
}
return false;
}
console.log(nearbyDuplicate([1, 2, 3, 1], 3), nearbyDuplicate([1, 2, 3, 1], 2));
true false
4. Count word frequencies, most common first.
Solution
function topWords(text) {
const freq = new Map();
for (const w of text.toLowerCase().split(/\s+/).filter(Boolean)) freq.set(w, (freq.get(w) ?? 0) + 1);
return [...freq].sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0]));
}
console.log(topWords("Chai and samosa and chai and jalebi"));
[ [ 'and', 3 ], [ 'chai', 2 ], [ 'jalebi', 1 ], [ 'samosa', 1 ] ]
split(/\s+/) cuts at any run of spaces; filter(Boolean) drops empty pieces. [...freq] turns the Map into [word, count] pairs. The comparator sorts by count (high first), and ties A to Z with localeCompare.
5. An LFU cache (least frequently used): evict the key used the fewest times; on a tie, the least recently used of those. A simple version that's O(capacity) on eviction:
Solution
class LFUCache {
constructor(capacity) { this.capacity = capacity; this.map = new Map(); } // key → { value, uses }
get(key) {
const e = this.map.get(key);
if (!e) return -1;
e.uses++;
this.map.delete(key); this.map.set(key, e); // also keep recency order for ties
return e.value;
}
put(key, value) {
if (this.capacity === 0) return;
const e = this.map.get(key);
if (e) { e.value = value; this.get(key); return; }
if (this.map.size === this.capacity) {
let victim = null, fewest = Infinity;
for (const [k, v] of this.map) if (v.uses < fewest) { fewest = v.uses; victim = k; } // first = oldest on a tie
this.map.delete(victim);
}
this.map.set(key, { value, uses: 1 });
}
}
const c = new LFUCache(2);
c.put("a", 1); c.put("b", 2);
c.get("a"); // a used twice
c.put("c", 3); // b has fewest uses: evicted
console.log(c.get("b"), c.get("a"), c.get("c"));
-1 1 3
The O(1) LFU uses a Map from use-count to an ordered set of keys, plus the current minimum count: a good stretch exercise.
Quick quiz
const m = new Map();
m.set(1, "number"); m.set("1", "string");
const o = {};
o[1] = "number"; o["1"] = "string";
console.log(m.size, Object.keys(o).length);
Answer
2 1
A: 2 1. A Map keeps the key's type, so 1 and "1" are two different keys. A plain object turns every key into a string, so o[1] and o["1"] are the same key.
Interview questions
- Map vs object: when do you choose a Map? Keys that aren't strings, lots of adding and deleting, needing
size, or needing insertion order you can rely on. Objects are fine for fixed records like{ name, age }. - Why is an LRU cache O(1) with a Map?
has,get,deleteandsetare O(1) on average, insertion order gives "oldest first", andkeys().next().valuereads the oldest key in O(1). - What does
map.setdo to the order of an existing key? Nothing: it keeps its original position. Delete it first to move it to the end. - Why does
[10, 1, 2].sort()give[1, 10, 2]? The default compares elements as strings. - How does the longest consecutive sequence stay O(n) with a nested
while? Thewhileonly starts where x − 1 is missing, so each number is walked once in total. - Group anagrams: what other keys work? A sorted string, or a 26-count signature joined with a separator (O(k) per word). A plain sum of letter codes does not: different words can have the same sum.
- Are Map lookups always O(1)? On average. Hash tables can degrade in rare worst cases, but engines handle this well in practice.
- How would you build an LRU cache in Java or C++? A hash map from key to a node of a doubly linked list (or Java's
LinkedHashMapwith access order).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Map | A collection of key → value pairs; any value can be a key; remembers insertion order | new Map([["chai", 15]]) |
| Set | A collection of unique values; remembers insertion order | new Set([7, 3, 7]) → {7, 3} |
| Key | The name you look a value up by | "samosa" in stock.get("samosa") |
| Insertion order | The order keys were first added; Maps and Sets loop in this order | [...map.keys()] |
| Iterator | An object that hands out items one at a time with next() |
map.keys().next().value |
| Cache | A small, fast store of recently used data | the recent apps screen |
| LRU | Least Recently Used: the eviction rule that removes the key unused for longest | chat is closed, not maps |
| Evict | Remove an entry to make room | map.delete(oldestKey) |
| Capacity | The most entries a cache may hold | new LRUCache(2) |
| Anagram | A word with the same letters in a different order | eat, tea, ate |
| Immutable | Can't be changed in place | strings: no sort, no reverse |
| Comparator | A function telling sort the order of two items |
(a, b) => a - b |
| Consecutive sequence | Numbers that follow each other by 1 | 1, 2, 3, 4 |
| O(1), O(n), O(n²), O(n log n) | Big-O: how the work grows as the input size n grows | set.has is O(1) |
| Average case | The typical cost, not the rare worst one | Map get is O(1) on average |
| Doubly linked list | Nodes with next and prev pointers; unlink in O(1) |
the LRU follow-up |
| Sentinel | A dummy node at the end of a list that avoids null checks |
head, tail |
| Spread operator | ... copies the items of an iterable into an array or call |
[...set] |
?? (nullish coalescing) |
Uses the right side only if the left is null or undefined |
count.get(ch) ?? 0 |
continue |
Skip to the next turn of the loop | if (has(x - 1)) continue; |
console.time / console.timeEnd |
Print how long the code between them took | 40,000 operations: 3.5s |
Summary
- Map = key → value, any key type, insertion order, O(1)
get/has/set/delete. Set = unique values with O(1)has. - LRU cache: a Map; refresh with
delete+set(plainsetkeeps the old place), evictkeys().next().value. O(1) per call. - Group anagrams: strings have no
sort; key =split("").sort().join(""); a Map from key to words turns O(n²) into O(n · k log k). - Longest consecutive sequence: default
sort()compares text; a Set drops duplicates; count only from numbers whose x − 1 is missing: O(n). - Next episode: the machine coding round: an event emitter, a key-value store with expiry, tested with
node:test.