These are the notes for JavaScript Coding Questions, episode 7, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Three array questions: find the missing number in 1 to n, count how often each value appears, and find the majority element. We meet an off-by-one bug, a word counter that breaks on the word constructor, and the Boyer-Moore voting trick that finds a majority with O(1) extra memory.
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. Plain modern JavaScript, no packages.
About the timings. Lines like
includes: 705.119msare copied from a real run on one machine; what matters is the size of the gap.
Q1: Find the missing number
Problem. The array holds the numbers 1 to n in any order with exactly one missing. Return it. [3, 1, 4, 5] → 2.
Real life. A teacher's roll call: the class has n students, one is absent.
Think out loud
- The array length is n - 1, so n =
arr.length + 1. - Edge cases: 1 is missing, n itself is missing, the empty array (n = 1, so 1 is missing), 100,000 numbers.
The obvious attempt: includes for every i
function missing(arr) {
const n = arr.length;
for (let i = 1; i <= n; i++) {
if (!arr.includes(i)) return i;
}
}
console.log(missing([3, 1, 4, 5]), missing([2, 3, 4, 5]), missing([1, 2, 3, 4]));
const big = Array.from({ length: 99999 }, (_, i) => (i < 41000 ? i + 1 : i + 2));
console.time("includes");
console.log(missing(big));
console.timeEnd("includes");
Output:
2 1 undefined
41001
includes: 705.119ms
The big test array is 1 to 100,000 without 41001: Array.from builds i + 1 for the first 41,000 indexes and i + 2 after that.
Two bugs.
- Off-by-one. n is the length plus one. With
n = arr.length, the loop never checks n, so[1, 2, 3, 4](missing 5) falls off the end and returnsundefined. An off-by-one error is a loop or index that is one too big or too small. - O(n²).
includesscans the array from the start each time: n checks × up to n steps.
The sum trick
Real-life picture. Roll numbers 1 to 5 should add up to 1 + 2 + 3 + 4 + 5 = 15. The students present (3, 1, 4, 5) add up to 13. 15 - 13 = 2: roll number 2 is absent.
The sum 1 + 2 + ... + n is n(n + 1) / 2 (pair the first and last: 1 + n, 2 + (n - 1), ...: n/2 pairs of n + 1).
The XOR trick
From episode 4: x ^ x = 0 and x ^ 0 = x, and the order doesn't matter. XOR every number from 1 to n and every number in the array: each present number appears twice and cancels; only the missing one is left.
function missing(arr) {
const n = arr.length + 1;
let sum = 0;
for (const x of arr) sum += x;
return (n * (n + 1)) / 2 - sum;
}
function missingXor(arr) {
const n = arr.length + 1;
let x = 0;
for (let i = 1; i <= n; i++) x ^= i;
for (const v of arr) x ^= v;
return x;
}
console.log(missing([3, 1, 4, 5]), missing([2, 3, 4, 5]), missing([1, 2, 3, 4]), missing([]));
console.log(missingXor([3, 1, 4, 5]), missingXor([2, 3, 4, 5]), missingXor([1, 2, 3, 4]));
const big = Array.from({ length: 99999 }, (_, i) => (i < 41000 ? i + 1 : i + 2));
console.time("sum");
console.log(missing(big), missingXor(big));
console.timeEnd("sum");
Output:
2 1 5 1
2 1 5
41001 41001
sum: 10.328ms
Both are O(n) time, O(1) space. Why mention XOR? n * (n + 1) grows like n², and past 2⁵³ a Number is no longer exact (episode 3). XOR results never exceed the size of the numbers themselves (for values that fit in 32 bits, since ^ works on 32 bits).
A Set also works in O(n) time, but needs O(n) space:
const big = Array.from({ length: 99999 }, (_, i) => (i < 41000 ? i + 1 : i + 2));
const s = new Set(big);
console.time("Set lookup");
let missingNo = null;
for (let i = 1; i <= big.length + 1; i++) if (!s.has(i)) { missingNo = i; break; }
console.timeEnd("Set lookup");
console.log(missingNo);
Set lookup: 2.126ms
41001
Q2: Count how often each value appears
Problem. Return the frequency of every value, in the order values first appear. [3, 1, 3, 2, 3] → 3: 3, 1: 1, 2: 1.
Real life. Counting votes, or the words in customer reviews.
The obvious attempt: a plain object
function frequency(items) {
const counts = {};
for (const x of items) counts[x] = (counts[x] || 0) + 1;
return counts;
}
console.log(frequency([3, 1, 3, 2, 3]));
console.log(frequency([1, "1", 1]));
console.log(frequency("to be or not to be".split(" ")));
console.log(frequency("the constructor of the class".split(" ")));
Output:
{ '1': 1, '2': 1, '3': 3 }
{ '1': 3 }
{ to: 2, be: 2, or: 1, not: 1 }
{
the: 2,
constructor: 'function Object() { [native code] }1',
of: 1,
class: 1
}
Three problems.
- Keys become strings.
1and"1"are the same key'1', so they are merged into a count of 3. - Integer-like keys are listed in ascending order, before other keys, so the order of first appearance is lost.
- Inherited properties. Every object inherits from
Object.prototype, which has aconstructorproperty (theObjectfunction).counts["constructor"]already exists,|| 0keeps it, andfunction + 1turns into the text'function Object() { [native code] }1'.
const o = {};
console.log("constructor" in o, o.constructor === Object, Object.hasOwn(o, "constructor"));
const safe = Object.create(null);
safe["constructor"] = (safe["constructor"] || 0) + 1;
console.log(safe.constructor, Object.keys({ b: 1, 10: 1, 2: 1, a: 1 }));
true true false
1 [ '2', '10', 'b', 'a' ]
in sees inherited properties; Object.hasOwn sees only the object's own. Object.create(null) makes an object with no prototype, so nothing is inherited; it still turns keys into strings and reorders integer keys, which the last line shows.
The fix: a Map
Real-life picture. A printed form that comes with some rows already filled in (a plain object) vs a blank tally sheet where rows are added in arrival order (a Map). A Map is a collection of key → value pairs that starts truly empty, keeps any type of key exactly, and remembers insertion order.
function frequency(items) {
const counts = new Map();
for (const x of items) counts.set(x, (counts.get(x) ?? 0) + 1);
return counts;
}
console.log(frequency([3, 1, 3, 2, 3]));
console.log(frequency([1, "1", 1]));
console.log(frequency("the constructor of the class".split(" ")));
const f = frequency("to be or not to be".split(" "));
for (const [word, count] of f) console.log(word, count);
console.log(f.get("to"), f.get("xyz"), f.size);
Output:
Map(3) { 3 => 3, 1 => 1, 2 => 1 }
Map(2) { 1 => 2, '1' => 1 }
Map(4) { 'the' => 2, 'constructor' => 1, 'of' => 1, 'class' => 1 }
to 2
be 2
or 1
not 1
2 undefined 4
get(key)returns the value orundefined;?? 0turnsundefinedinto 0 (and, unlike||, would keep a real 0).for (const [key, value] of map)loops over entries in insertion order.sizeis the number of keys.
Complexity: O(n) time (each get/set is O(1) on average), O(k) space for k distinct values.
Plain object {} |
Map |
|
|---|---|---|
| Key types | strings (and symbols) only | any value, kept exactly |
| Inherited keys | yes (constructor, toString...) |
none |
| Order | integer keys first, ascending | insertion order |
| Size | Object.keys(o).length |
m.size |
| Best for | fixed records, JSON | counting, lookups, caches |
Q3: The majority element
Problem. Return the value that appears more than n / 2 times, or null if there is none. [2, 2, 1, 2, 3] → 2; [1, 2, 3] and [1, 1, 2, 2] → null. Follow-up: O(n) time and O(1) extra space (a counting Map is O(n) space).
The obvious attempt: the middle of the sorted array
A majority fills more than half the array, so after sorting it must cover the middle position.
function majority(arr) {
const sorted = [...arr].sort((a, b) => a - b);
return sorted[Math.floor(sorted.length / 2)];
}
console.log(majority([2, 2, 1, 2, 3]), majority([7, 7, 5, 7]));
console.log(majority([1, 2, 3]), majority([1, 1, 2, 2]));
2 7
2 2
Right when a majority exists, but wrong when it doesn't: the middle is then just some value. And sorting is O(n log n).
Boyer-Moore majority vote
Real-life picture: an election where votes cancel. The first vote makes its candidate the leader with 1 vote. A vote for the leader adds 1; a vote for anyone else cancels one of the leader's votes (one supporter and one opponent leave together). At 0 votes, the next voter's choice becomes the leader. A real majority has more votes than all the others together, so it can never be cancelled out completely.
const arr = [2, 2, 1, 2, 3];
let candidate = null, votes = 0;
for (const x of arr) {
if (votes === 0) candidate = x;
votes += x === candidate ? 1 : -1;
console.log(x, "->", candidate, votes);
}
2 -> 2 1
2 -> 2 2
1 -> 2 1
2 -> 2 2
3 -> 2 1
If there is no majority, someone is still left standing, so a second pass confirms the candidate:
function majority(arr) {
let candidate = null, votes = 0;
for (const x of arr) {
if (votes === 0) candidate = x;
votes += x === candidate ? 1 : -1;
}
let count = 0;
for (const x of arr) if (x === candidate) count++;
return count > arr.length / 2 ? candidate : null;
}
for (const a of [[2, 2, 1, 2, 3], [7, 7, 5, 7], [1, 2, 3], [1, 1, 2, 2], [4], []]) {
console.log(JSON.stringify(a), majority(a));
}
[2,2,1,2,3] 2
[7,7,5,7] 7
[1,2,3] null
[1,1,2,2] null
[4] 4
[] null
Complexity: O(n) time (two passes), O(1) space. If the problem guarantees a majority exists, the second pass can be skipped; ask the interviewer.
Complexity summary
| Question | Approach | Time | Extra space |
|---|---|---|---|
| Missing number | includes for each i |
O(n²) | O(1) |
| Missing number | Set | O(n) | O(n) |
| Missing number | sum formula / XOR | O(n) | O(1) |
| Frequency | plain object | O(n) | O(k), but wrong keys |
| Frequency | Map | O(n) | O(k) |
| Majority | sort + middle | O(n log n) | O(n) copy; wrong without a majority |
| Majority | Map of counts | O(n) | O(k) |
| Majority | Boyer-Moore + confirm | O(n) | O(1) |
Common mistakes (and the exact outputs)
| Mistake | Code | What you see | Why | Fix |
|---|---|---|---|---|
| n = length | const n = arr.length |
missing([1, 2, 3, 4]) → undefined |
one number is missing | arr.length + 1 |
| Search inside a loop | arr.includes(i) for each i |
includes: 705.119ms |
O(n²) | sum, XOR or a Set |
Counting in {} |
counts[x] = (counts[x] \|\| 0) + 1 |
constructor: 'function Object() { [native code] }1' |
inherited keys | new Map() |
Mixed key types in {} |
frequency([1, "1", 1]) |
{ '1': 3 } |
keys become strings | Map keeps types |
Expecting insertion order from {} |
[3, 1, 3, 2, 3] |
{ '1': 1, '2': 1, '3': 3 } |
integer keys sorted | Map |
| Middle of sorted = majority | sorted[n >> 1] |
[1, 2, 3] → 2 |
only valid if one exists | Boyer-Moore + confirm |
| Skipping the confirm pass | candidate only | a "majority" that isn't | someone always survives | count again |
Mini project: top words in a review
const review = `The food was good, the service was slow.
Good food, good price! The constructor of this building did a good job.`;
const words = review.toLowerCase().match(/[a-z]+/g);
const counts = new Map();
for (const w of words) counts.set(w, (counts.get(w) ?? 0) + 1);
const top = [...counts].sort((a, b) => b[1] - a[1]).slice(0, 3);
console.log(words.length, "words,", counts.size, "different");
for (const [word, count] of top) console.log(word.padEnd(8), "#".repeat(count), count);
21 words, 14 different
good #### 4
the ### 3
food ## 2
match(/[a-z]+/g) returns every run of letters (punctuation dropped). [...counts] turns the Map into [word, count] pairs to sort by count. Because sort is stable, words with equal counts keep their first-seen order. Extend it: ignore common words like "the" and "a" with a Set of stop words.
Your turn: find the duplicate (solution)
Problem. The array has n + 1 numbers, each from 1 to n, and exactly one value appears twice. Find it. [3, 1, 3, 4, 2] → 3.
Solution
Three ways:
function duplicateSum(arr) {
const n = arr.length - 1;
let sum = 0;
for (const x of arr) sum += x;
return sum - (n * (n + 1)) / 2;
}
function duplicateSet(arr) {
const seen = new Set();
for (const x of arr) {
if (seen.has(x)) return x;
seen.add(x);
}
return null;
}
function duplicateFloyd(arr) {
let slow = arr[0], fast = arr[0];
do {
slow = arr[slow];
fast = arr[arr[fast]];
} while (slow !== fast);
slow = arr[0];
while (slow !== fast) {
slow = arr[slow];
fast = arr[fast];
}
return slow;
}
for (const a of [[3, 1, 3, 4, 2], [1, 1], [2, 5, 4, 1, 3, 5]]) {
console.log(JSON.stringify(a), duplicateSum(a), duplicateSet(a), duplicateFloyd(a));
}
console.log(duplicateSum([2, 2, 2, 1]), duplicateSet([2, 2, 2, 1]), duplicateFloyd([2, 2, 2, 1]));
[3,1,3,4,2] 3 3 3
[1,1] 1 1 1
[2,5,4,1,3,5] 5 5 5
1 2 2
- Sum (turned around): the array sums to 1 + ... + n plus the duplicate, so subtract n(n + 1) / 2. O(n), O(1), but it only works if every number 1..n is present and exactly one is doubled; the last line shows it breaks when a value appears three times (
[2, 2, 2, 1]gives 1). - Set: the first value already seen. O(n), O(n) space; works for any input.
- Floyd's cycle detection (the LeetCode follow-up, O(1) space without changing the array): treat each value as a pointer to an index. The duplicate value is pointed to twice, which creates a cycle; a slow and a fast pointer meet inside it, and restarting one from the beginning finds the cycle's entrance. We'll meet this "tortoise and hare" idea again with linked lists in episode 26.
Practice questions (with solutions)
1. Two missing numbers in 1..n.
Solution
Use the sum and the sum of squares: a + b = S and a² + b² = Q give (a - b)² = 2Q - S².
function twoMissing(arr) {
const n = arr.length + 2;
let sum = (n * (n + 1)) / 2, squares = (n * (n + 1) * (2 * n + 1)) / 6;
for (const x of arr) { sum -= x; squares -= x * x; }
// a + b = sum, a² + b² = squares → a - b = √(2·squares − sum²)
const diff = Math.sqrt(2 * squares - sum * sum);
return [(sum - diff) / 2, (sum + diff) / 2];
}
console.log(twoMissing([1, 3, 5]), twoMissing([3, 4]), twoMissing([1, 2, 3, 4]));
[ 2, 4 ] [ 1, 2 ] [ 5, 6 ]
O(n), O(1). (For large n the squares overflow 2⁵³; a Set is the safe fallback.)
2. The most frequent element (first one to reach the top count wins ties).
Solution
function mostFrequent(arr) {
const counts = new Map();
let best = null, bestCount = 0;
for (const x of arr) {
const c = (counts.get(x) ?? 0) + 1;
counts.set(x, c);
if (c > bestCount) { best = x; bestCount = c; }
}
return arr.length ? [best, bestCount] : null;
}
console.log(mostFrequent([3, 1, 3, 2, 1, 1]), mostFrequent(["a", "b", "a"]), mostFrequent([]));
[ 1, 3 ] [ 'a', 2 ] null
One pass, O(n) time, O(k) space.
3. Every element that appears more than n / 3 times (at most two can).
Solution
Boyer-Moore with two candidates, then confirm both:
function majorityThird(arr) {
let c1 = null, v1 = 0, c2 = null, v2 = 0;
for (const x of arr) {
if (x === c1) v1++;
else if (x === c2) v2++;
else if (v1 === 0) { c1 = x; v1 = 1; }
else if (v2 === 0) { c2 = x; v2 = 1; }
else { v1--; v2--; }
}
const result = [];
for (const c of [c1, c2]) {
if (c !== null && arr.filter(x => x === c).length > arr.length / 3) result.push(c);
}
return result;
}
for (const a of [[3, 2, 3], [1, 1, 1, 3, 3, 2, 2, 2], [1, 2, 3], [5]]) console.log(JSON.stringify(a), majorityThird(a));
[3,2,3] [ 3 ]
[1,1,1,3,3,2,2,2] [ 1, 2 ]
[1,2,3] []
[5] [ 5 ]
O(n) time, O(1) space.
Quick quiz
1. (From the video.) What does this print?
const m = new Map([[1, "a"]]);
const o = { 1: "a" };
console.log(m.get("1"), o["1"]);
(A) a a (B) undefined a (C) a undefined (D) undefined undefined
Answer
(B) undefined a. The Map's key is the number 1, so the string "1" is a different key. The object turned its key into the string "1", so o["1"] (and o[1]) find it.
2. What does console.log(5 ^ 3 ^ 5) print?
Answer
3: the two 5s cancel (x ^ x = 0), leaving 3. That's why the XOR missing-number trick works.
3. Boyer-Moore on [1, 2, 3] ends with which candidate before the confirm pass?
Answer
3 (1 is cancelled by 2, then 3 becomes the leader). The confirm pass counts one 3, not more than 1.5, so the answer is null.
Interview questions
- Find the missing number in 1..n. n = length + 1; n(n + 1)/2 - sum, or XOR of 1..n and the array. O(n), O(1).
- Why might you prefer XOR to the sum? The sum formula grows like n² and can pass 2⁵³; XOR stays small.
- What's wrong with
includesinside a loop? It is a hidden O(n) scan, making the whole thing O(n²). - Why use a Map rather than an object for counting? Keys keep their type, insertion order is kept, and there are no inherited keys like
constructor. - What does
Object.create(null)give you? An object with no prototype: no inherited keys (but keys are still strings). - Explain the Boyer-Moore majority vote. Keep a candidate and a counter; same value +1, different -1, new candidate at 0. A true majority survives. Confirm with a second pass. O(n), O(1).
- When can you skip the confirm pass? When the problem guarantees a majority exists.
- Why is
sorted[n / 2]not enough? It's only the majority if one exists; for[1, 2, 3]it returns 2. - How many elements can appear more than n/3 times? At most two; extend Boyer-Moore to two candidates.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Off-by-one error | A loop or index that is one too big or too small | n = arr.length instead of + 1 |
includes |
True if the array contains a value (scans: O(n)) | [1, 2].includes(2) |
| Arithmetic series sum | 1 + 2 + ... + n = n(n + 1) / 2 | n = 5 → 15 |
XOR (^) |
Bitwise "differ"; x ^ x = 0, x ^ 0 = x | 5 ^ 3 ^ 5 is 3 |
| Frequency | How many times a value appears | 3 appears 3 times |
| Plain object | {}: string keys, inherits from Object.prototype |
counts["to"] |
| Prototype | The object another object inherits properties from | Object.prototype |
| Inherited property | A property found on the prototype, not the object itself | constructor |
in operator |
True for own and inherited properties | "constructor" in {} |
Object.hasOwn |
True only for the object's own properties | Object.hasOwn({}, "constructor") is false |
Object.create(null) |
An object with no prototype | a "safe" dictionary |
Map |
Key → value pairs; any key type, insertion order | new Map() |
map.get / map.set |
Read / write the value for a key | m.set("to", 2) |
map.size |
Number of keys | f.size is 4 |
Nullish coalescing (??) |
Right side only for null/undefined |
undefined ?? 0 |
| Majority element | Appears more than n / 2 times | 2 in [2, 2, 1, 2, 3] |
| Boyer-Moore majority vote | One-pass candidate + counter algorithm | O(n), O(1) |
| Candidate | The current leader in the vote | candidate = x |
| Confirm pass | A second pass to check the candidate really is a majority | count > n / 2 |
| Floyd's cycle detection | Slow and fast pointers meet inside a cycle | find the duplicate |
match(/[a-z]+/g) |
All runs of lowercase letters in a string | words of a review |
| O(k) space | Grows with the number of distinct values k | the counting Map |
Summary
- Missing number: n = length + 1;
n(n + 1) / 2 - sumor XOR of 1..n and the array. O(n) time, O(1) space.includesin a loop is a hidden O(n²). - Frequencies: count with a Map (
get,set,?? 0): keys keep their type, insertion order is kept, nothing is inherited. A plain object merges1and"1", sorts integer keys, and breaks onconstructor. - Majority: Boyer-Moore voting finds a candidate in one pass with O(1) space; a second pass confirms it. The middle of a sorted array is only right when a majority exists.
Next episode: Array questions IV: two sum (brute force vs a Map), moving zeros to the end while keeping the order, and the default sort() trap: [10, 9, 1].sort() gives [1, 10, 9].