Arrays, iteration and collections

You use array methods every day. The interview does not ask whether you can call map — it asks which methods mutate, what reduce can actually do, why sort breaks on numbers, and whether you can rebuild these methods from scratch.

Every array method, and what it gives back

In simple words: the first thing to know about any array method is whether it changes the original array or returns a new one. Getting this wrong causes bugs that are very hard to trace.

Methods that change the original

Methods that return something new

Rebuild map, filter, reduce and forEach

In simple words: a standard interview task. It proves you understand callbacks, the thisArg parameter, and how sparse arrays behave.

Array.prototype.myMap = function (callback, thisArg) {
  if (typeof callback !== "function") throw new TypeError(callback + " is not a function");
 
  const source = Object(this);
  const length = source.length >>> 0;      // coerce to a 32-bit unsigned int
  const output = new Array(length);        // preserve length, including holes
 
  for (let i = 0; i < length; i++) {
    if (i in source) {                     // skip holes in sparse arrays
      output[i] = callback.call(thisArg, source[i], i, source);
    }
  }
 
  return output;
};
 
Array.prototype.myFilter = function (callback, thisArg) {
  const source = Object(this);
  const length = source.length >>> 0;
  const output = [];
 
  for (let i = 0; i < length; i++) {
    if (i in source && callback.call(thisArg, source[i], i, source)) {
      output.push(source[i]);
    }
  }
 
  return output;
};

reduce is the one they actually care about, because of the no-initial-value case:

Array.prototype.myReduce = function (callback, initialValue) {
  const source = Object(this);
  const length = source.length >>> 0;
 
  let index = 0;
  let accumulator;
 
  if (arguments.length >= 2) {
    accumulator = initialValue;
  } else {
    // no initial value: find the first real element and start there
    while (index < length && !(index in source)) index++;
    if (index >= length) {
      throw new TypeError("Reduce of empty array with no initial value");
    }
    accumulator = source[index++];
  }
 
  for (; index < length; index++) {
    if (index in source) {
      accumulator = callback(accumulator, source[index], index, source);
    }
  }
 
  return accumulator;
};

reduce, properly

In simple words: reduce is not just for adding numbers. It turns a list into anything — an object, a string, a nested structure, even another function.

const orders = [
  { id: 1, status: "paid", total: 250 },
  { id: 2, status: "pending", total: 100 },
  { id: 3, status: "paid", total: 400 },
];
 
// sum
orders.reduce((sum, o) => sum + o.total, 0);              // 750
 
// group by a key
const byStatus = orders.reduce((groups, order) => {
  (groups[order.status] ||= []).push(order);
  return groups;
}, {});
// { paid: [...], pending: [...] }
 
// index by id, for O(1) lookup later
const byId = orders.reduce((map, order) => {
  map[order.id] = order;
  return map;
}, {});
 
// frequency count
const words = ["a", "b", "a", "c", "a"];
words.reduce((counts, w) => {
  counts[w] = (counts[w] || 0) + 1;
  return counts;
}, {});
// { a: 3, b: 1, c: 1 }
 
// flatten one level
[[1, 2], [3], [4, 5]].reduce((flat, part) => flat.concat(part), []);
 
// pipe — reduce over functions instead of data
const pipe = (...fns) => (x) => fns.reduce((acc, fn) => fn(acc), x);

Modern JavaScript has Object.groupBy, which does the grouping case natively. Know both — interviewers usually want the reduce version.

sort

In simple words: with no comparator, sort converts everything to strings and sorts alphabetically. That is why numbers come out wrong.

[10, 9, 1, 100].sort();               // [1, 10, 100, 9]  -- string order
[10, 9, 1, 100].sort((a, b) => a - b); // [1, 9, 10, 100]  -- correct

The comparator returns a number, and the sign is all that matters:

• negative — a comes before b
• zero — leave their relative order alone
• positive — b comes before a

// numbers
list.sort((a, b) => a - b);                       // ascending
list.sort((a, b) => b - a);                       // descending
 
// strings, correctly for non-English text
names.sort((a, b) => a.localeCompare(b));
 
// by a field, then by another as a tie-breaker
users.sort((a, b) => a.age - b.age || a.name.localeCompare(b.name));
 
// dates
events.sort((a, b) => new Date(a.at) - new Date(b.at));

Stability means equal elements keep their original relative order. Since ES2019 sort is guaranteed stable in every engine, which is what makes the "sort by age, then by name" trick above work reliably.

Map and Set

In simple words: a Map is a dictionary that accepts any key type and remembers insertion order. A Set is a list that automatically rejects duplicates.

const cache = new Map();
const userKey = { id: 1 };
 
cache.set(userKey, "some value");   // an object as a key
cache.get(userKey);                 // "some value"
cache.get({ id: 1 });               // undefined -- different object, different key
 
cache.has(userKey);   // true
cache.delete(userKey);
cache.size;
 
for (const [key, value] of cache) { /* insertion order */ }
 
// Set: deduplicate in one line
const unique = [...new Set([1, 2, 2, 3, 3, 3])];   // [1, 2, 3]
 
// Set operations
const a = new Set([1, 2, 3]);
const b = new Set([2, 3, 4]);
const intersection = [...a].filter((x) => b.has(x));   // [2, 3]
const difference = [...a].filter((x) => !b.has(x));    // [1]

WeakMap and WeakSet

In simple words: the same idea, except they do not stop the garbage collector. If the only remaining reference to an object is the one inside a WeakMap, the object is collected and the entry disappears with it.

Keys must be objects, and you cannot iterate or read size — because the contents can vanish at any moment.

const metadata = new WeakMap();
 
function attach(element) {
  metadata.set(element, { clicks: 0 });   // does not keep the element alive
}
 
// When the DOM node is removed and no other reference exists, both the node
// and its metadata entry are collected. With a regular Map, the node would
// stay in memory forever -- a classic detached-DOM leak.

The two real uses: caches and metadata keyed by object, and private data for class instances before # fields existed.

flat, flatMap, and your own flatten

[1, [2, [3, [4]]]].flat();          // [1, 2, [3, [4]]]  -- depth 1 by default
[1, [2, [3, [4]]]].flat(2);         // [1, 2, 3, [4]]
[1, [2, [3, [4]]]].flat(Infinity);  // [1, 2, 3, 4]
 
// flatMap = map then flatten one level. Useful for one-to-many.
["a b", "c d"].flatMap((s) => s.split(" "));   // ["a", "b", "c", "d"]
 
// It also filters: return an empty array to drop an item
users.flatMap((u) => (u.active ? [u.name] : []));

function flatten(array, depth = 1) {
  if (depth < 1) return array.slice();
 
  return array.reduce(
    (out, item) =>
      out.concat(Array.isArray(item) ? flatten(item, depth - 1) : item),
    []
  );
}
 
// Iterative, so it cannot blow the call stack on deeply nested input
function flattenDeep(array) {
  const stack = [...array];
  const out = [];
 
  while (stack.length) {
    const item = stack.pop();
    if (Array.isArray(item)) stack.push(...item);
    else out.push(item);
  }
 
  return out.reverse();
}

Array-likes and iterables

In simple words: two different things people confuse. An array-like has a length and numeric keys but no array methods. An iterable has a Symbol.iterator and works with for...of and spread.

// array-like but NOT iterable
function old() {
  arguments.length;          // works
  arguments.map;             // undefined
  Array.from(arguments);     // now a real array
}
 
// iterable but NOT an array
const set = new Set([1, 2]);
[...set];                    // works
set.map;                     // undefined
 
// NodeList is both array-like and iterable
const nodes = document.querySelectorAll("li");
[...nodes].filter((n) => n.dataset.active);

Array.from handles both, and takes a mapping function as a second argument:

Array.from({ length: 5 }, (_, i) => i * 2);    // [0, 2, 4, 6, 8]
Array.from("hello");                           // ["h","e","l","l","o"]

The iterator protocol

In simple words: for...of and spread work by calling one method. Implement that method and your object joins in.

An object is iterable if it has a [Symbol.iterator] method that returns an iterator — an object with a next() method returning { value, done }.

class Playlist {
  constructor(tracks) { this.tracks = tracks; }
 
  [Symbol.iterator]() {
    let index = 0;
    const tracks = this.tracks;
    return {
      next: () =>
        index < tracks.length
          ? { value: tracks[index++], done: false }
          : { value: undefined, done: true },
    };
  }
}
 
const list = new Playlist(["one", "two"]);
[...list];                      // ["one", "two"]
for (const t of list) { }       // works
const [first] = list;           // destructuring works too

Generators

In simple words: a function that can pause and resume. Writing the iterator above by hand is tedious; a generator does it for you.

function* marks a generator. yield produces a value and pauses until the next next() call.

class Playlist {
  constructor(tracks) { this.tracks = tracks; }
 
  *[Symbol.iterator]() {          // the whole iterator, in three lines
    for (const track of this.tracks) yield track;
  }
}

Generators are lazy, which is what makes infinite sequences possible:

function* naturals() {
  let n = 1;
  while (true) yield n++;         // never ends, but only computes on demand
}
 
function* take(iterable, count) {
  let taken = 0;
  for (const value of iterable) {
    if (taken++ >= count) return;
    yield value;
  }
}
 
[...take(naturals(), 5)];         // [1, 2, 3, 4, 5]

They are also two-way — yield evaluates to whatever you pass into the next next():

function* conversation() {
  const name = yield "What is your name?";
  yield `Hello ${name}`;
}
 
const chat = conversation();
chat.next().value;            // "What is your name?"
chat.next("Subham").value;    // "Hello Subham"

That two-way channel is exactly how redux-saga works, and how async/await was originally polyfilled.

Typed arrays, briefly

Uint8Array, Float32Array and friends are fixed-length views over raw binary memory, backed by an ArrayBuffer. You meet them when handling file uploads, canvas pixel data, WebSockets with binary frames, or crypto APIs.

You do not need depth here. Recognise them, know they are fixed-size and typed, and know that Buffer in Node is a Uint8Array subclass.

Ten questions

1. 01

   Which common array methods change the original array?

   Show answer
2. 02

   Why does [10, 9, 1].sort() give [1, 10, 9]?

   Show answer
3. 03

   In your own reduce, how do you handle a missing initial value?

   Show answer
4. 04

   What is wrong with items.reduce((acc, x) => ({ ...acc, [x.id]: x }), {})?

   Show answer
5. 05

   When would you choose a Map over a plain object?

   Show answer
6. 06

   What does a WeakMap do that a Map cannot?

   Show answer
7. 07

   Why does new Array(5).map((_, i) => i) not produce [0,1,2,3,4]?

   Show answer
8. 08

   What is the difference between an array-like and an iterable?

   Show answer
9. 09

   What exactly makes an object work with for...of?

   Show answer
10. 10

    What can a generator do that a plain function cannot, and where is that useful?

    Show answer

Six exercises

1. 01

   Implement map, filter, reduce and forEach

   On Array.prototype, matching the spec: coerce length, skip holes, pass value, index and array, support thisArg. Prove myReduce throws on an empty array with no initial value, and works when the initial value is explicitly undefined.

2. 02

   Write groupBy with reduce, then compare

   Group an array of objects by a key selector that can be a string or a function. Then rewrite it using Object.groupBy and say which you would ship and why.

3. 03

   Sort by several fields

   Write sortBy(array, ...comparators) so that sortBy(users, byAge, byName) sorts by age and breaks ties by name. Prove the sort is stable by feeding it equal keys.

4. 04

   Flatten twice

   Write a recursive flatten(array, depth), then an iterative version using an explicit stack. Test both on an array nested 10,000 levels deep and explain what happens to each.

5. 05

   Build an LRU cache on Map

   Use the fact that a Map keeps insertion order. On a read, delete and re-set the key to move it to the end; on write, evict the first key when over capacity. Both operations must be O(1).

6. 06

   Lazy sequence tools

   Write generators range(start, end, step), take(iterable, n), mapIter(iterable, fn) and filterIter(iterable, fn). Chain them over an infinite sequence and confirm with a counter that only the values you consumed were ever computed.