JavaScript for Coding Interview

5/19/2019Time to read: 4 min

Recently I have been practicing coding interviews questions using JavaScript. Unlike Java and C++, JavaScript doesn't come with a standard library. It lacks some useful data structure. The good part is that JavaScript is very dynamic and much more succinct than Java and C++. I have found that coding for interview questions requires a different mindset than coding a web app. This post will discuss some tips and tricks that I realized while practicing using JavaScript.

Basic data structures

JavaScript doesn't have lots of data structures. However, the most common data structures in an interview can usually be represented using simple structs like array or objects.

Array

These are some array operations I found useful.

// create an array
const arr1 = [];

// create an array of length 10, fill with true
const arr2 = new Array(10).fill(true);

// create an array of length 10, fill with Foo instances
const arr3 = Array.from({length: 10}).map(() => new Foo());

// create an array of 0 .. 9
const arr4 = Array.from({length: 10}).map((element, index) => index);

// create a 10 by 10 2-D array and fill with true
const arr5 = Array.from({length: 10}).map(() => new Array(10).fill(true));

JavaScript's array is very powerful. It's possible to write both functional and elegant code for most array operations. Here are some examples:

// sort an number array from small to large
[4, 2, 3, 1].sort((value1, value2) => value1 - value2);
// sort an string array based on lexical order
['b', 'c', 'a', 'd'].sort();
// get truthy value from an array
[2, 3, 'string', null, undefined, {hello: 'world'}].filter(Boolean); // this is useful to filter out null or undefined values in an array
// sum array
[1, 2, 3, 4].reduce((sum, current) => sum + current, 0);

Stack and queue

Stack and queue in JavaScript are usually implemented using array.

// creating a stack
const stack1 = [];
// pushing onto stack
stack1.push(1);
// poping from stack
const popped = stack1.pop();
// peeking the top item of stack
stack1.slice(-1)[0];

// creating a queue
const queue = [];
// adding item into a queue
queue.push(1);
// removing item from a queue
const removed = queue.shift(); 
// Note that this has O(n) complexity, if that is a concern,
// we can create a linked list or use a pointer variable for head.

// peeking the head
queue[0];
// peeking the tail
queue.slice(-1)[0];

HashMap

JavaScript object is a great string based hashmap. Although I have found that it might be less performant than ES6 Map when we are adding a lot of keys, for interview purpose, this shouldn't be a concern.

// create a map
const map1 = {};
// increment a value inside map, if the value is not defined, initialize into 0 before increment
map1.counter = (map1.counter || 0) + 1;
// get all the keys of the map
Object.keys(map1);
// get all the values of the map
Object.values(map1);
// create a shallow copy of the map
const map2 = {...map1};

Tree

There are multiple representations of a tree. I found the most commonly used tree representation is using tree nodes that reference each other. For example, a very basic tree node implementation for a binary tree would be:

const createNode = () => ({
  left: null,
  right: null,
});

We can use this function to build up a tree

const root = createNode();
const leftChild = createNode();
const rightChild = createNode();
root.left = leftChild;
root.right = rightChild;

Math operation

Most interview questions won't require heavy mathmetical calculations so the built-in support is usually enough. Just make sure to avoid floating point calculation as much as possible, because

// check if even
const num = 12;
const isEven = num % 2 === 0;
// round up number
Math.ceil(12.2); // 13
// round down number
Math.floor(12.2); // 12
// truncate number
Math.trunc(12.2) // 12
// divide by 2 and truncate (only work for number smaller or equal to 2^31 - 1)
13 >> 1; // 6

String operation

// reverse a string
'hello'.split('').reverse().join(''); // Assuming we are not dealing with unicode, because https://stackoverflow.com/q/24531751

Bonus

Once in a while, we will be able to solve an interview question using some unique feature of JavaScript. For example, for the following question on leetcode

341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer or a list -- whose elements may also be integers or other lists.

Example:

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,1,2,1,1].

If we are asked to print out the flatten array, the solution would simply be a recursion. However, iterators don't return all the value at once. Using other languages, we might need to maintain a stack to keep track of the subarrays we are flattening. JavaScript comes with generators. We can solve this question using an approach not much different from the recursion solution.

function * iterate(list) {
  for (let item of list) {
    if (Array.isArray(item)) {
      yield * iterate(item);
    } else {
      yield item;
    }
  }
}

const iterator = iterate([[1,1],2,[1,1]]);
iterator.next().value; // 1
iterator.next().value; // 1
iterator.next().value; // 2