JS Technical interview cheatsheet

January 3, 2024 - 15 min read

Technical interviews are often a source of stress for developers. In this article, I will give you some tips to prepare for your next technical interview.

Technical Interview TODO List:

[] Understand Complexity
[] Understand Data Structures
[] Understand Common Algorithms (sorting, two pointers, sliding window, ...)
[] Do 'medium' Leetcode problems
[] Understand architectures

1. Complexity

Time Complexity

Definition: Time complexity is a measure of the amount of time an algorithm takes. It is usually expressed by using the big O notation.

Rules:

Constants are ignored O(2n) = O(n)
In cases of addition or subtraction, consider the term with the highest complexity O(n² + n) = O(n²)
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

O(n)


_10for (let fruit of fruits) {
_10    console.log(fruit);
_10}

In each for loop iteration, we are performing a print, which costs O(1). The for loop iterates n times, which gives a time complexity of O(1⋅n)=O(n).

O(n + m)


_10for (let fruit of fruits) {
_10    console.log(fruit);
_10}
_10
_10for (let vegetable of vegetables) {
_10    console.log(vegetable);
_10}

This algorithm has a time complexity of O(n + m) because we are performing two for loops, each of which has a time complexity of O(n) and O(m) respectively.

O(n²)


_10    for (let i = 0; i < arr.length; i++) {
_10        for (let j = i; j < arr.length; j++) {
_10            console.log(i + j);
_10        }
_10    }

O (log n)

means that somewhere in your algorithm, the input is being reduced by a percentage at every step. A good example of this is binary search, which is a searching algorithm that runs in O(log n) time.

O (2ⁿ)

means that the algorithm is doubling in time every time the input increases by one. This is common with recursive algorithms that solve a problem of size n by recursively solving two smaller problems of size n-1. (fibonacci)

Space Complexity

Definition: Space complexity is a measure of the amount of space in memory an algorithm takes.

Rules:

Do not count the space used by the inputs
Same rules as time complexity

O (1)


_10for (let fruit of fruits) {
_10    console.log(fruit);
_10}

The space used is limited to a single variable named fruit, which remains constant and does not vary with the size of the input n.

O (n)


_10let fruits = [];
_10for (let i = 0; i < n; i++) {
_10    fruits.push("apple");
_10}

Fruits array is growing with the size of the input n. So the space complexity is O(n).

O (n ⋅ m)


_10let fruits = [n][m];
_10for (let i = 0; i < arr.length; i++) {
_10    for (let j = i; j < arr.length; j++) {
_10        fruits[i][j] = "apple";
_10    }
_10}

Fruits is a matrix of size n x m. So the space complexity is O(n ⋅ m).

2. Understanding Data Structures

Arrays / Stacks / Queues


_22let array = ["apple", "banana", "orange"];
_22console.log(array[1]); // Display "apple"
_22array[1] = "mangue"; // Change "banana" into "mangue"
_22array.push("kiwi");
_22console.log(array.length); // Display 4
_22for (let i = 0; i < fruits.length; i++) {
_22    console.log(array[i]);
_22}
_22
_22
_22let stack = [];
_22stack.push(2); // stack is now [2]
_22stack.push(5); // stack is now [2, 5]
_22let i = stack.pop(); // stack is now [2]
_22alert(i); // displays 5
_22
_22
_22let queue = [];
_22queue.push(2); // queue is now [2]
_22queue.push(5); // queue is now [2, 5]
_22let i = queue.shift(); // queue is now [5]
_22alert(i); // displays 2

Array: A collection of elements that can be accessed by index, allowing for a wide range of operations like adding, removing, and modifying elements at any position.
Stack: A LIFO (Last In, First Out) structure where the last element added is the first one to be removed. Operations are typically limited to adding (push) and removing (pop) from the top of the stack.
Queue: A FIFO (First In, First Out) structure where the first element added is the first one to be removed. Elements are added to the back (enqueue) and removed from the front (dequeue) of the queue.

Useful methods for arrays

slice() : crée une copie de l'array si pas d'arguments ou une partie de l'array (comme une part de gateau) si arguments (start, end)
splice() : modifie l'array en insérant ou supprimant des éléments (start, deleteCount, item1, item2, ...)


_10const months = ["Jan", "March", "April", "June"];
_10months.splice(1, 0, "Feb");
_10// Inserts at index 1
_10console.log(months);
_10// Expected output: Array ["Jan", "Feb", "March", "April", "June"]
_10
_10months.splice(4, 1, "May");
_10// Replaces 1 element at index 4
_10console.log(months);
_10// Expected output: Array ["Jan", "Feb", "March", "April", "May"]

unshift(): This method is used for adding new elements at the beginning of the array.
concat(): This method is used for joining various arrays into a single array.
lastIndexOf(): This method is used for returning the final index at which a given element appears in an array.
join(): This method is used for combining elements of an array into one single string and then returning it.

Complexity of Arrays

Access (by index): O(1) - Elements in an array can be accessed in constant time.
Search: O(n) - Searching for an element requires traversing the array.
Insertion/Deletion at the end: O(1) - These operations are typically fast due to dynamic memory management.
Insertion/Deletion at the beginning or in the middle: O(n) - Requires shifting elements.

Warning : Sort and reverse methods of the Array class modify the array in place, so they are not immutable.

Set


_18const set1 = new Set();
_18
_18set1.add("a");
_18set1.add("b");
_18set1.add("c");
_18
_18console.log(set1.has("a"));
_18// Expected output: true
_18
_18set1.add("a"); // Attempting to add a duplicate
_18
_18console.log(set1.size);
_18// Expected output: 3 (no change because "a" is already in the Set)
_18
_18set1.delete("b");
_18
_18console.log(set1.size);
_18// Expected output: 2

In this example:

add is used to add elements to the Set.
has checks if an element is present in the Set.
delete removes an element from the Set.
size returns the number of elements in the Set.

JavaScript Sets are collections of unique elements, so any attempt to add a duplicate is simply ignored, which distinguishes them from Maps.

Complexity of Set

Access: Not applicable - Sets do not provide direct access by index.
Search (has): O(1) on average - Based on a hash table.
Insertion/Deletion: O(1) on average - Also based on a hash table.

Map (Hash)


_21const map1 = new Map();
_21
_21map1.set("a", 1);
_21map1.set("b", 2);
_21map1.set("c", 3);
_21
_21console.log(map1.get("a"));
_21// Expected output: 1
_21
_21map1.set("a", 97);
_21
_21console.log(map1.get("a"));
_21// Expected output: 97
_21
_21console.log(map1.size);
_21// Expected output: 3
_21
_21map1.delete("b");
_21
_21console.log(map1.size);
_21// Expected output: 2

Complexity of Map

Access / Insertion / Deletion (by key): O(1) on average - Keys are organized using a hash table.
Search (by value): O(n) - Requires traversing all entries.

Tree (not native)


_27class Node {
_27    constructor(data) {
_27        this.data = data;
_27        this.children = [];
_27    }
_27
_27    add(data) {
_27        this.children.push(new Node(data));
_27    }
_27    remove(data) {
_27        this.children = this.children.filter((node) => {
_27            return node.data !== data;
_27        });
_27    }
_27}
_27
_27// or if Binary Tree
_27
_27class Node
_27{
_27    constructor(data)
_27    {
_27        this.data = data;
_27        this.left = null;
_27        this.right = null;
_27    }
_27}

Algo de recherche :

BFS (Breadth-First Search)
DFS (Depth-First Search)

For more details : Check this link

Graph (not native)


_12class GraphNode {
_12    constructor(value) {
_12        this.value = value;
_12        this.edges = []; // Les connexions avec d'autres nœuds
_12    }
_12}
_12
_12class Graph {
_12    constructor() {
_12        this.nodes = [];
_12    }
_12}

The key difference between a Tree and a Graph in JavaScript (and in general) can be summarized as follows:

Tree: A hierarchical structure with a single root node where each node has a single parent and potentially many children, but no cycles (i.e., no node can be revisited once left).
Graph: A more flexible structure where nodes (vertices) can have multiple or no parents, and connections (edges) can form complex networks, including cycles (i.e., paths that revisit nodes).

3. Common algorithms

Palindrome


_15const isPalindrome = (str) => {
_15    // split() creates a new array, making it safe to use reverse() on it
_15    return str === str.split("").reverse().join("");
_15};
_15
_15// OR
_15
_15const isPalindrome = (str) => {
_15    for (let i = 0; i < str.length / 2; i++) {
_15        if (str[i] !== str[str.length - 1 - i]) {
_15            return false;
_15        }
_15    }
_15    return true;
_15}

Fibonacci


_36// Is not the best solution because of the complexity O(2ⁿ)
_36function fibonacciRecursive(n) {
_36    if (n <= 1) {
_36        return n;
_36    }
_36    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
_36}
_36
_36// Intermediate solution with O(n) complexity thanks to cache
_36const cache = new Map();
_36function fibonacciRecursive(n) {
_36    if (n <= 1) {
_36        return n;
_36    }
_36    if (cache.has(n)) {
_36        return cache.get(n);
_36    }
_36    const result = fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
_36    cache.set(n, result);
_36    return result;
_36}
_36
_36// Better solution O(n)
_36function fibonacciIterative(n) {
_36    let a = 0,
_36        b = 1,
_36        c;
_36    if (n === 0) return a;
_36
_36    for (let i = 2; i <= n; i++) {
_36        c = a + b;
_36        a = b;
_36        b = c;
_36    }
_36    return b;
_36}

Two pointers

When to use: Finding pairs, Checking symmetry, Comparing or Merging.

Main idea: Two pointers is a widely used method for tackling problems related to arrays and strings. This technique employs two integer variables, which simultaneously traverse through an iterable


_10function fn(arr):
_10    left = 0
_10    right = arr.length - 1
_10
_10    while left < right:
_10        Do some logic here depending on the problem
_10        Do some more logic here to decide on one of the following:
_10            1. left++
_10            2. right--
_10            3. Both left++ and right--

Example 'Check Palindrome'


_13const checkIfPalindrome = function(s) {
_13    let left = 0;
_13    let right = s.length - 1;
_13
_13    while (left < right) {
_13        if (s[left] != s[right]) {
_13            return false;
_13        }
_13        left++;
_13        right--;
_13    }
_13    return true;
_13}

Example 'Container With Most Water'


_44    /**   
_44        You are provided with an array of n elements, each representing the height of vertical lines. These lines are positioned so that their two endpoints can form the sides of a container.
_44
_44        Return the maximum amount of water a container can store.
_44
_44        Example 1:
_44
_44        Input: height = [1,1]
_44        Output: 1
_44        Explanation: The distance between the two pointers is 1 and the minimum height is 1 so the area is 1 * 1 = 1.
_44
_44        Example 2:
_44
_44        Input: height = [1,0,2]
_44        Output: 2
_44        Explanation: The distance between the two best pointers is 2 and the minimum height is 1 so the area is 2 * 1 = 2.
_44
_44        Example 3:
_44
_44        Input: height = [1,8,6,2,5,4,8,3,7]
_44        Output: 49
_44    */
_44    const maxArea = function (height) {
_44        let start = 0;
_44        let end = height.length - 1;
_44
_44        let maxArea = 0;
_44        while (end > start) {
_44            const maxH = Math.min(height[start], height[end]);
_44            const area = getArea(end - start, maxH);
_44            maxArea = Math.max(maxArea, area);
_44            if (height[start] > height[end]) {
_44                end--;
_44            } else {
_44                start++;
_44            }
_44        }
_44
_44        return maxArea;
_44    };
_44
_44    const getArea = (long, larg) => {
_44        return long * larg;
_44    }

Advanced example 'Longest Palindromic Substring'


_38    /**   
_38        Given a string s, return the longest  palindromic substring in s.
_38
_38        Example 1:
_38
_38        Input: s = "babad"
_38        Output: "bab"
_38        Explanation: "aba" is also a valid answer.
_38        Example 2:
_38
_38        Input: s = "cbbd"
_38        Output: "bb"
_38
_38        Solution : Use Sliding window technic but taking the center as the point of extension to find the palindrome.
_38    */
_38const longestPalindrome = function (s) {
_38    if (s.length < 1 || s === null) return "";
_38
_38    let longestPalindrome = "";
_38
_38    for (let i = 0; i < s.length; i++) {
_38        let oddPalindrome = expandFromCenter(s, i, i);
_38        let evenPalindrome = expandFromCenter(s, i, i + 1);
_38
_38        let longerPalindrome = oddPalindrome.length > evenPalindrome.length ? oddPalindrome : evenPalindrome;
_38        longestPalindrome = longestPalindrome.length > longerPalindrome.length ? longestPalindrome : longerPalindrome;
_38    }
_38
_38    return longestPalindrome;
_38};
_38
_38function expandFromCenter(s, left, right) {
_38    while (left >= 0 && right < s.length && s[left] === s[right]) {
_38        left--;
_38        right++;
_38    }
_38    return s.substring(left + 1, right);
_38}

More info : Two pointers

Sliding window

When to use: When the problem will either explicitly or implicitly define criteria that make a subarray "valid" or ask you to find some valid subarrays.

Main idea: The main idea behind the sliding window technique is to convert two nested loops into a single loop. Usually, the technique helps us to reduce the time complexity from O(n²) or O(n³) to O(n)"

Example 'Longest Substring without repeating character'


_67    /**   
_67        Example 1:
_67
_67        Input: s = "abcabcbb"
_67        Output: 3
_67        Explanation: The answer is "abc", with the length of 3.
_67        Example 2:
_67
_67        Input: s = "bbbbb"
_67        Output: 1
_67        Explanation: The answer is "b", with the length of 1.
_67        Example 3:
_67
_67        Input: s = "pwwkew"
_67        Output: 3
_67        Explanation: The answer is "wke", with the length of 3.
_67        Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
_67    */
_67
_67    // Naive :
_67    const lengthOfLongestSubstring = function (s) {
_67        let maxCount = 0;
_67        let count = 0;
_67        let charactersSeen = [];
_67        const size = s.length;
_67        for (let i = 0; i < size; i++) {
_67            for (let j = i; j < size; j++) {
_67                if (charactersSeen.includes(s[j])) {
_67                    count = 1;
_67                    charactersSeen = [s[j]];
_67                } else {
_67                    count++;
_67                    charactersSeen.push(s[j]);
_67                }
_67                maxCount = count > maxCount ? count : maxCount;
_67            }
_67            count = 0;
_67            charactersSeen = [];
_67        }
_67
_67        return maxCount;
_67    };
_67
_67    // Sliding window :
_67    const lengthOfLongestSubstring = function (s) {
_67        // window frame
_67        let start = 0;
_67        let end = 0;
_67        const slidingWindow = new Set();
_67
_67        let maxCount = 0;
_67        let currentSize = 0;
_67
_67        while (end < s.length) {
_67            if (slidingWindow.has(s[end])) {
_67                slidingWindow.delete(s[start]);
_67                start++;
_67            } else {
_67                slidingWindow.add(s[end]);
_67                end++;
_67            }
_67            currentSize = end - start
_67            maxCount = currentSize > maxCount ? currentSize : maxCount;
_67        }
_67
_67        return maxCount;
_67    };

More info : Sliding window

4. Interview Questions

Questions on 'prototype'


_20// Overriding Inherited Properties
_20function Person() {}
_20Person.prototype.age = 30;
_20
_20const bob = new Person();
_20bob.age = 25; // Overrides inherited property
_20
_20console.log(bob.age); // 25, not 30
_20console.log(Person.prototype.age); // Still 30
_20
_20// Shared Prototype properties
_20function Dog() {}
_20Dog.prototype.traits = [];
_20
_20const dog1 = new Dog();
_20const dog2 = new Dog();
_20
_20dog1.traits.push("friendly");
_20
_20console.log(dog2.traits); // ['friendly']

Name some design patterns

Creational Patterns : Singleton, Factory, Builder, State Machine, Prototype
Structural Patterns : Decorator, Facade, Adapter, Proxy, Composite
Behavioral Patterns : Observer, Mediator, Iterator, Visitor, Strategy

Good luck with your interviews, and may your coding journey be rewarding and successful!

Al1x-ai

Advanced form of artificial intelligence designed to assist humans in solving source code problems and empowering them to become independent in their coding endeavors. Feel free to reach out to me on X (twitter).