These are the notes for JavaScript Coding Questions, episode 9, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Three questions: merge two sorted arrays into one sorted array, the intersection and union of two arrays, and the maximum subarray sum with Kadane's algorithm, including the case where every number is negative.
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
intersection: 1.640sare copied from a real run on one machine; your numbers will differ. What matters is the size of the gap.
Q1: Merge two sorted arrays
Problem. a and b are each sorted in ascending order (smallest first). Return one array with every item of both, also sorted.
[1, 4, 9] + [2, 3, 10] → [1, 2, 3, 4, 9, 10]
[1, 3] + [2, 4, 5, 6] → [1, 2, 3, 4, 5, 6]
[] + [7, 8] → [7, 8]
Real life: two sections of a class each have a sorted list of marks, and the school wants one merit list.
Think out loud
- The inputs are already sorted: that is the clue the question gives you.
- Edge cases: different lengths, an empty array, equal values on both sides.
The obvious attempt: glue and sort
function merge(a, b) {
return [...a, ...b].sort();
}
console.log(merge([1, 4, 9], [2, 3, 10]));
console.log(merge([5, 20], [8, 100]));
[ 1, 10, 2, 3, 4, 9 ]
[ 100, 20, 5, 8 ]
Episode 8's trap: with no compare function, sort compares items as strings, so "10" comes before "2". With a compare function it is correct:
function merge(a, b) {
return [...a, ...b].sort((x, y) => x - y);
}
console.log(merge([1, 4, 9], [2, 3, 10]));
console.log(merge([5, 20], [8, 100]));
[ 1, 2, 3, 4, 9, 10 ]
[ 5, 8, 20, 100 ]
Correct, but it ignores that both inputs were sorted and sorts everything again: O((n + m) log(n + m)). An interviewer wants one pass.
Two pointers: two queues, one counter
Picture a bank with two queues, each already in token order, and one counter that must serve everyone in token order. You only look at the front of each queue: call the smaller token, and that queue moves up.
The first version many people write:
function merge(a, b) {
const out = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) out.push(a[i++]);
else out.push(b[j++]);
}
return out;
}
console.log(merge([1, 4, 9], [2, 3, 10]));
console.log(merge([1, 3], [2, 4, 5, 6]));
console.log(merge([], [7, 8]));
[ 1, 2, 3, 4, 9 ]
[ 1, 2, 3 ]
[]
Items went missing, with no error: 10, then 4, 5, 6, then everything. The loop stops as soon as one array runs out; the rest of the other array is never copied. Fix: copy the leftovers.
function merge(a, b) {
const out = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) out.push(a[i++]);
else out.push(b[j++]);
}
while (i < a.length) out.push(a[i++]);
while (j < b.length) out.push(b[j++]);
return out;
}
console.log(merge([1, 4, 9], [2, 3, 10]));
console.log(merge([1, 3], [2, 4, 5, 6]));
console.log(merge([], [7, 8]));
console.log(merge([2, 2], [2]), merge([], []));
[ 1, 2, 3, 4, 9, 10 ]
[ 1, 2, 3, 4, 5, 6 ]
[ 7, 8 ]
[ 2, 2, 2 ] []
a[i++]uses the old value ofi, then adds 1 (postfix increment).- Only one of the two leftover loops actually runs.
<=takes the item fromafirst when values are equal, so the merge is stable (equal items keep their order). This exact step is the heart of merge sort (episode 25).
Complexity: every item is pushed once: O(n + m) time, O(n + m) space for the output.
Q2: Intersection and union
Problem. The intersection is the values that appear in both arrays; the union is every value that appears in either. Each value once.
[1, 2, 2, 1] ∩ [2, 2] → [2]
[1, 2, 2, 1] ∪ [2, 3] → [1, 2, 3]
Real life: students in both the chess club and the coding club (intersection), and students in at least one of them (union).
Think out loud
- "Each value once": duplicates must go.
- Edge cases: duplicates, an empty array, 50,000 items on each side.
The obvious attempt: filter + includes
function intersection(a, b) {
return a.filter(x => b.includes(x));
}
function union(a, b) {
return [...a, ...b];
}
console.log(intersection([1, 2, 2, 1], [2, 2]));
console.log(union([1, 2, 2, 1], [2, 3]));
[ 2, 2 ]
[ 1, 2, 2, 1, 2, 3 ]
Duplicates everywhere: filter keeps every matching item of a (and a has 2 twice), and spread just glues the arrays. Now the size test:
function intersection(a, b) {
return a.filter(x => b.includes(x));
}
const a = Array.from({ length: 50000 }, (_, i) => i * 2);
const b = Array.from({ length: 50000 }, (_, i) => i * 3);
console.time("intersection");
console.log(intersection(a, b).length);
console.timeEnd("intersection");
16667
intersection: 1.640s
includes scans b from the start for every item of a: up to 50,000 × 50,000 comparisons. O(n · m).
A Set: the guest list at the door
Reading the whole printed guest list for every guest is slow; a guard who knows every name answers in one glance. A Set answers has in O(1) on average, and holds each value once.
function intersection(a, b) {
const inB = new Set(b);
return [...new Set(a)].filter(x => inB.has(x));
}
function union(a, b) {
return [...new Set([...a, ...b])];
}
console.log(intersection([1, 2, 2, 1], [2, 2]));
console.log(union([1, 2, 2, 1], [2, 3]));
console.log(intersection([4, 9, 5], [9, 4, 9, 8, 4]), intersection([1], []));
const a = Array.from({ length: 50000 }, (_, i) => i * 2);
const b = Array.from({ length: 50000 }, (_, i) => i * 3);
console.time("intersection");
console.log(intersection(a, b).length);
console.timeEnd("intersection");
[ 2 ]
[ 1, 2, 3 ]
[ 4, 9 ] []
16667
intersection: 11.126ms
From 1.6 seconds to about 11 milliseconds. A Set remembers insertion order, so the results keep the order of a.
Complexity: O(n + m) time, O(n + m) space.
Built-in Set methods (Node 22+)
const a = new Set([1, 2, 2, 1]);
const b = new Set([2, 3]);
console.log(a.intersection(b));
console.log(a.union(b));
console.log([...a.union(b)]);
Set(1) { 2 }
Set(3) { 1, 2, 3 }
[ 1, 2, 3 ]
They return Sets; spread to get an array. There are also difference, symmetricDifference, isSubsetOf, isSupersetOf and isDisjointFrom. In an interview, write the filter version first to show the idea, then mention the built-ins.
Q3: Maximum subarray sum (Kadane's algorithm)
Problem. A subarray is a run of items next to each other, with at least one item. Return the largest sum any subarray has.
[-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (4, -1, 2, 1)
[5, 4, -1, 7, 8] → 23 (the whole array)
[-3, -1, -2] → -1 (just -1: at least one item!)
Real life: a tea stall writes down its profit or loss every day. What was its best run of consecutive days?
The obvious attempt: every subarray
function maxSubarray(arr) {
let best = -Infinity;
for (let i = 0; i < arr.length; i++) {
let sum = 0;
for (let j = i; j < arr.length; j++) {
sum += arr[j];
best = Math.max(best, sum);
}
}
return best;
}
console.log(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubarray([5, 4, -1, 7, 8]));
console.log(maxSubarray([-3, -1, -2]));
const days = Array.from({ length: 30000 }, (_, i) => (i * 37) % 101 - 50);
console.time("max");
console.log(maxSubarray(days));
console.timeEnd("max");
6
23
-1
124
max: 397.57ms
Correct, because best starts at -Infinity (any real sum beats it). But 30,000 starts, each extended to the end, is about 450 million additions: O(n²). Double the input, four times the time.
Kadane: should I keep the streak?
Walk once, carrying cur: the best total of a streak that ends today. Each day: if the streak you carry is negative, it can only drag today down, so drop it and start fresh today. Add today's value. If cur is the best ever, remember it.
The short version seen in many tutorials, with a bug:
function maxSubarray(arr) {
let best = 0, cur = 0;
for (const x of arr) {
cur = Math.max(x, cur + x);
best = Math.max(best, cur);
}
return best;
}
console.log(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubarray([5, 4, -1, 7, 8]));
console.log(maxSubarray([-3, -1, -2]));
const days = Array.from({ length: 30000 }, (_, i) => (i * 37) % 101 - 50);
console.time("max");
console.log(maxSubarray(days));
console.timeEnd("max");
6
23
0
124
max: 2.007ms
Fast, but [-3, -1, -2] gives 0. best started at 0 and no real sum beat it. 0 is the sum of the empty subarray, which the question does not allow. Fix: start best at arr[0]. This version also records where the best run starts and ends:
function maxSubarray(arr) {
let best = arr[0], cur = 0, start = 0, from = 0, to = 0;
for (let i = 0; i < arr.length; i++) {
if (cur < 0) { cur = 0; start = i; }
cur += arr[i];
if (cur > best) { best = cur; from = start; to = i; }
}
return { best, from, to };
}
console.log(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubarray([5, 4, -1, 7, 8]));
console.log(maxSubarray([-3, -1, -2]));
console.log(maxSubarray([7]));
const days = Array.from({ length: 30000 }, (_, i) => (i * 37) % 101 - 50);
console.time("max");
console.log(maxSubarray(days));
console.timeEnd("max");
{ best: 6, from: 3, to: 6 }
{ best: 23, from: 0, to: 4 }
{ best: -1, from: 1, to: 1 }
{ best: 7, from: 0, to: 0 }
{ best: 124, from: 15, to: 62 }
max: 0.718ms
Trace of [-2, 1, -3, 4, -1, 2, 1, -5, 4]:
| i | arr[i] | cur before | dropped? | cur after | best |
|---|---|---|---|---|---|
| 0 | -2 | 0 | no | -2 | -2 |
| 1 | 1 | -2 | yes, start = 1 | 1 | 1 |
| 2 | -3 | 1 | no | -2 | 1 |
| 3 | 4 | -2 | yes, start = 3 | 4 | 4 |
| 4 | -1 | 4 | no | 3 | 4 |
| 5 | 2 | 3 | no | 5 | 5 |
| 6 | 1 | 5 | no | 6 | 6 (from 3 to 6) |
| 7 | -5 | 6 | no | 1 | 6 |
| 8 | 4 | 1 | no | 5 | 6 |
Complexity: one pass, a few variables: O(n) time, O(1) space.
Complexity summary
| Question | Approach | Time | Extra space |
|---|---|---|---|
| Merge sorted | concat + sort | O((n + m) log(n + m)) | O(n + m) |
| Merge sorted | two pointers + leftovers | O(n + m) | O(n + m) output |
| Intersection | filter + includes | O(n · m) | O(n) |
| Intersection / union | Set | O(n + m) | O(n + m) |
| Intersection of sorted arrays | two pointers | O(n + m) | O(1) besides output |
| Max subarray | every subarray | O(n²) | O(1) |
| Max subarray | Kadane | O(n) | O(1) |
Common mistakes (and the exact outputs)
| Mistake | Code | What you see | Why | Fix |
|---|---|---|---|---|
| Default sort on merged numbers | [...a, ...b].sort() |
[ 1, 10, 2, 3, 4, 9 ] |
compared as strings | two pointers (or (x, y) => x - y) |
| Forgetting the leftovers | while (i < a.length && j < b.length) only |
[ 1, 2, 3 ] for [1, 3] + [2, 4, 5, 6] |
the loop stops at the shorter side | copy what's left |
filter + includes |
a.filter(x => b.includes(x)) |
[ 2, 2 ], intersection: 1.640s |
duplicates kept; O(n · m) | new Set(b) then has |
| Spread for union | [...a, ...b] |
[ 1, 2, 2, 1, 2, 3 ] |
nothing removes duplicates | [...new Set([...a, ...b])] |
| Comparing with the wrong type in a Set | new Set([5, 1, 4]).has("4") |
false |
"4" and 4 are different values |
convert first: Number(x) |
Kadane with best = 0 |
let best = 0 |
0 for [-3, -1, -2] |
0 is the empty subarray | best = arr[0] |
Mini project: the tea stall's best run
Two weeks of daily profit and loss; find the best run of days and print it.
// A tea stall's daily profit (+) and loss (-) in rupees for two weeks.
const days = [120, -300, 80, 150, -40, 210, -90, -250, 60, 90, 130, -20, 70, -400];
function bestStreak(arr) {
let best = arr[0], cur = 0, start = 0, from = 0, to = 0;
for (let i = 0; i < arr.length; i++) {
if (cur < 0) { cur = 0; start = i; }
cur += arr[i];
if (cur > best) { best = cur; from = start; to = i; }
}
return { best, from, to };
}
const { best, from, to } = bestStreak(days);
console.log(`Best run: day ${from + 1} to day ${to + 1}, profit ₹${best}`);
console.log(days.slice(from, to + 1).join(" + "), "=", best);
Best run: day 3 to day 6, profit ₹400
80 + 150 + -40 + 210 = 400
Extend it: also find the worst run (flip the signs, or track the minimum), or read the numbers from stdin (episode 14 of the JavaScript course).
Your turn: intersection of two SORTED arrays (solution)
Problem. Both arrays are sorted. Return the common values, each once, without a Set (O(1) extra space besides the output). [1, 2, 2, 4, 7] and [2, 2, 3, 7, 9] → [2, 7].
Solution
Walk both with two pointers, like the merge. If the fronts differ, the smaller one can't be in the other array any more (everything after it there is bigger), so move that pointer. If they are equal, it's common: push it once and move both.
function intersectSorted(a, b) {
const out = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] < b[j]) i++;
else if (a[i] > b[j]) j++;
else {
if (out.at(-1) !== a[i]) out.push(a[i]);
i++;
j++;
}
}
return out;
}
console.log(intersectSorted([1, 2, 2, 4, 7], [2, 2, 3, 7, 9]));
console.log(intersectSorted([1, 1, 1], [1, 1]), intersectSorted([1, 3], [2, 4]), intersectSorted([], [1]));
[ 2, 7 ]
[ 1 ] [] []
out.at(-1) is the last item pushed; because the input is sorted, a repeat can only be equal to the last one. O(n + m) time, O(1) extra space. Here the leftovers can be ignored: once one side runs out, nothing else can be common.
Practice questions (with solutions)
1. Difference: the values in a but not in b, each once.
Solution
function difference(a, b) {
const inB = new Set(b);
return [...new Set(a)].filter(x => !inB.has(x));
}
console.log(difference([1, 2, 3, 4, 2], [2, 4]), difference([1], [1]));
console.log(new Set([1, 2, 3, 4]).difference(new Set([2, 4])));
[ 1, 3 ] []
Set(2) { 1, 3 }
2. Merge three sorted arrays.
Solution
Merge two, then merge the result with the third.
function merge(a, b) {
const out = [];
let i = 0, j = 0;
while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);
while (i < a.length) out.push(a[i++]);
while (j < b.length) out.push(b[j++]);
return out;
}
const mergeThree = (a, b, c) => merge(merge(a, b), c);
console.log(mergeThree([1, 7], [2, 3, 9], [0, 8]));
console.log(mergeThree([], [5], []));
[
0, 1, 2, 3,
7, 8, 9
]
[ 5 ]
(Node prints arrays of more than 6 numbers over several lines.) For k arrays, merging them in pairs, like a tournament, keeps the total work at O(N log k), where N is the total number of items.
3. Maximum subarray, returning the subarray itself.
Solution
function maxSubarrayItems(arr) {
let best = arr[0], cur = 0, start = 0, from = 0, to = 0;
for (let i = 0; i < arr.length; i++) {
if (cur < 0) { cur = 0; start = i; }
cur += arr[i];
if (cur > best) { best = cur; from = start; to = i; }
}
return arr.slice(from, to + 1);
}
console.log(maxSubarrayItems([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubarrayItems([-3, -1, -2]), maxSubarrayItems([2, -1, 2]));
[ 4, -1, 2, 1 ]
[ -1 ] [ 2, -1, 2 ]
4. Merge in place (a common interview version): nums1 has length m + n, its first m items are sorted and the rest are 0 placeholders; merge nums2 (n sorted items) into it.
Solution
Fill from the back, so nothing that is still needed gets overwritten.
function mergeInPlace(nums1, m, nums2, n) {
let i = m - 1, j = n - 1, w = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) nums1[w--] = nums1[i--];
else nums1[w--] = nums2[j--];
}
return nums1;
}
console.log(mergeInPlace([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3));
console.log(mergeInPlace([0], 0, [1], 1), mergeInPlace([4, 5, 0, 0], 2, [1, 2], 2));
[ 1, 2, 2, 3, 5, 6 ]
[ 1 ] [ 1, 2, 4, 5 ]
The loop only needs to run while nums2 has items: leftovers of nums1 are already in place. O(m + n) time, O(1) space.
Quick quiz
1. (From the video.) What does this print?
const s = new Set([3, 1, 3, 2, 1]);
console.log([...s]);
(A) [ 1, 2, 3 ] (B) [ 3, 1, 2 ] (C) [ 3, 1, 3, 2, 1 ] (D) [ 3, 2, 1 ]
Answer
(B) [ 3, 1, 2 ]. A Set drops duplicates and keeps the order values were first added. It does not sort.
2. What do these print?
console.log([...new Set([1, 2]).union(new Set([2, 3]))].length);
const best = [-5, -2, -8].reduce((b, x) => Math.max(b, x), 0);
console.log(best);
Answer
3
0
The union is {1, 2, 3}. And the same trap as Kadane with best = 0: starting the maximum at 0 hides that every number is negative. Use Math.max(...arr) for small arrays, or start from arr[0].
3. What does this print?
console.log([5, 1, 4].includes(4), new Set([5, 1, 4]).has("4"));
Answer
true false
Sets compare values with the same rule as === (except that NaN equals NaN), so the string "4" is not the number 4.
Interview questions
- Merge two sorted arrays in O(n + m). Two pointers, push the smaller front item, then copy the leftovers.
- What bug do people make in the merge? Stopping when one array runs out and losing the rest of the other.
- Why is
<=better than<in the merge? Equal items come from the first array first: a stable merge, which merge sort relies on. - Intersection of two arrays in O(n + m)? Put one in a Set, filter the unique values of the other with
has. - Why is
filter+includesslow?includesis a linear scan, so the whole thing is O(n · m). - Intersection of two sorted arrays with O(1) extra space? Two pointers; move the smaller front.
- Does a Set keep order? Yes, insertion order. It does not sort.
- Explain Kadane's algorithm. Carry the best sum ending here; if it becomes negative, drop it and start fresh; track the best seen. O(n), O(1).
- What happens if every number is negative? The answer is the largest (least negative) single item; starting
bestat 0 wrongly returns 0. - How do you also return the subarray? Remember the start index when you restart, and save
fromandtowheneverbestimproves.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Sorted ascending | Smallest first | [1, 4, 9] |
| Merge | Combine two sorted arrays into one sorted array | [1, 4] + [2] → [1, 2, 4] |
| Two pointers | Two indexes that move through the data | i in a, j in b |
| Leftovers | Items still waiting in one array after the other runs out | 10 in [2, 3, 10] |
Postfix increment (i++) |
Uses the old value, then adds 1 | out.push(a[i++]) |
| Stable | Equal items keep their original order | <= in the merge |
| Merge sort | A sort that splits the array and merges sorted halves | episode 25 |
Spread (...) |
Expands an array (or Set) into items | [...a, ...b] |
| Intersection | Values in both collections | [1, 2] ∩ [2, 3] → [2] |
| Union | Values in either collection, each once | [1, 2] ∪ [2, 3] → [1, 2, 3] |
| Difference | Values in the first but not the second | [1, 2] − [2] → [1] |
includes |
Linear scan: is x in the array? O(n) | b.includes(x) |
| Set | A collection of unique values, in insertion order | new Set([1, 1, 2]) → {1, 2} |
set.has(x) |
Is x in the Set? O(1) on average | inB.has(2) |
| O(n · m) | Work grows with the product of two sizes | filter + includes |
| Subarray | Items next to each other, at least one | [4, -1, 2, 1] |
| Maximum subarray sum | The largest sum of any subarray | 6 |
| Kadane's algorithm | One-pass maximum subarray: drop a negative running sum | if (cur < 0) cur = 0 |
| Running sum | A total updated as you walk | cur += arr[i] |
| Empty subarray | A subarray with no items; its sum is 0 (not allowed here) | why best = 0 is wrong |
-Infinity |
A number smaller than every other number | let best = -Infinity |
Array.prototype.at |
Item by index, negative counts from the end | out.at(-1) |
slice(from, to) |
A copy of the items from from up to (not including) to |
arr.slice(3, 7) |
Summary
- Merge sorted arrays: use the clue that they are sorted. Two pointers, push the smaller front, then copy the leftovers. O(n + m). Concatenating and sorting is slower, and without a compare function it sorts numbers as strings.
- Intersection and union:
filter+includeskeeps duplicates and is O(n · m). A Set gives unique values and O(1)has: intersection = uniqueafiltered byinB.has, union =new Set([...a, ...b]). Node 22+ hasintersection,unionanddifferencebuilt in. - Maximum subarray (Kadane): carry the best sum ending here, drop it when it goes negative, track the best. O(n), O(1). Start
bestatarr[0], never 0, or an all-negative array returns 0.
Next episode: Array questions VI: flattening a nested array (recursion vs flat(Infinity)), splitting an array into chunks, and grouping items by a key with Object.groupBy.