SyntaxPilot
Courses/JavaScript Coding Questions/Lesson 28
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript Coding Questions · Lesson 28 of 30

Map and Set questions

LRU cache with a Mapgroup anagramslongest consecutive sequence

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) and array.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 for key, or -1 if it isn't there. A get counts as using the key.
  • put(key, value): store the pair (update it if the key exists). If that makes the cache bigger than capacity, 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' ]
  • set on a key that already exists updates the value but keeps the old position.
  • To move a key to the newest end: delete it, then set it.
  • map.keys() returns an iterator (an object that hands out the keys one at a time). .next() gives { value, done } for the first key, so map.keys().next().value is 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
  • get checks has first, so a stored value like 0 or undefined is not mistaken for "missing".
  • put deletes first (harmless if the key is new), so an update also refreshes the key.
  • After get("music") and get("maps"), the order is [music, maps]; put("maps", 10) refreshes maps, so put("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 - price before 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

  1. 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 }.
  2. Why is an LRU cache O(1) with a Map? has, get, delete and set are O(1) on average, insertion order gives "oldest first", and keys().next().value reads the oldest key in O(1).
  3. What does map.set do to the order of an existing key? Nothing: it keeps its original position. Delete it first to move it to the end.
  4. Why does [10, 1, 2].sort() give [1, 10, 2]? The default compares elements as strings.
  5. How does the longest consecutive sequence stay O(n) with a nested while? The while only starts where x − 1 is missing, so each number is walked once in total.
  6. 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.
  7. Are Map lookups always O(1)? On average. Hash tables can degrade in rare worst cases, but engines handle this well in practice.
  8. 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 LinkedHashMap with 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 (plain set keeps the old place), evict keys().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.