# Algorithms in JavaScript

## 40 Problems, Solutions, and Explanations

### Introduction

The **interview process** usually begins with an initial *phone screen* and then an all-day *on-site* that check for *coding skills* and *cultural fit*. Almost without exception, the deciding factor is **coding aptitude**. After all, engineers are paid to deliver working software at the end of the day. Traditionally, *whiteboarding* is used to test for this aptitude. More than getting the answer right is the thought process clearly articulated. In code as in life, the right answer is not always clear, but good reasoning is usually good enough. The ability to *reason* *effectively* signals the potential to learn, adapt, and evolve. The best engineers are always growing, and the best companies are always innovating.

**Algorithm challenges** are effective because there are more than one way to solve them. This opens the possibility for decisions to be made and the calculus of those decisions. When solving an algorithm problem, we should challenge ourselves to look at the *problem definition* from multiple perspectives, then weigh the *benefits* and *demerits* of various approaches. With enough practice, we might even glimpse a universal truth: *there’s no “perfect” solution.*

To truly master **Algorithms** is to understand them in relationship to **Data** **Structures**. Data structures and algorithms go hand-in-hand like Yin and Yang, the *glass* and the *water*. Without the glass, water cannot be contained. Without data structures, we have no objects by which to apply logic. Without water, the glass is empty and devoid of sustenance. Without algorithms, objects cannot be transformed or “consumed”.

*For a quick high-level analysis of **Data Structures in JavaScript**:*

### Primer

Applied to code, an algorithm is just a `function`

that transforms a certain **input*** data structure *into a certain **output*** data structure*. The **logic*** inside* decides the transformation. First and foremost, the inputs and outputs should *clearly* be defined, ideally, as **unit tests**. This requires fully understanding the problem at hand, which is not to be underestimated, because a thorough analysis of the problem can surface the solution naturally, without needing to write any code.

Once the problem domain is thoroughly grasped, **brainstorming** of the solution space can begin. *What variables will be needed? How many loops and what kinds? Are there any clever built-in methods that can help? Edge cases to consider? *Complex or repeated logic can be difficult to read and understand. *Can helper functions be extracted or abstracted? *An algorithm usually needs to be scalable. *As input sizes grow, how will the function perform?* *Should there be some kind of caching mechanisms? *Generally, memory optimizations (space) will need to be sacrificed for performance gains (time).

To make the problem more concrete, drawdiagrams!

When a high-level structure of the solution begins to appear, the **pseudocode **can begin. To really impress the interviewer, look *ahead* for opportunities to refactor and **reuse*** *code. Sometimes, similar-behaving functions can be combined into a more general function that accepts an extra parameter. Other times, de-parametrization through **currying** is better. Keeping functions **pure** to ease testing and maintenance also shows foresight. In other words, consider **architectural** and **design patterns** in the calculus of your decisions.

If anything is unclear,askfor clarification!

#### Big O

To assist in the calculus of runtime complexities, we approximate the scalability of an algorithm by extrapolating its *input sizes* toward infinity before counting the *number of operations *required. At this worst-case runtime upper bound, we can drop coefficients and additive terms, retaining only factors that dominate the function. Consequently, just a few categories can describe the scalability of almost any algorithm.

The most optimum algorithm scales in *constant* time and space. This means it does not care at all about the growth of its inputs. Next best is *logarithmic* time or space, then *linear*, *linearithmic*, *quadratic*, and *exponential*. The worst is *factorial* time or space. In **Big-O** notation:

**Constant**: O(1)**Logarithmic**: O(log n)**Linear**: O(n)**Linearithmic**: O(n log n)**Quadratic**: O(n²)**Expontential**: O(2^n)**Factorial**: O(n!)

Big-O *asymptotic analysis* is an indispensable tool as we consider the tradeoff between time and space complexities of an algorithm. However, Big O ignores constant factors when in actual practice may matter. Moreover, optimizing for time and space may increase implementation time or negatively impact code readability. When designing the structure and logic of an algorithm, the intuitive feel for what is truly negligible is as important.

#### Arrays

The cleanest algorithm usually takes advantage of *standard ***objects*** *inherent in the language. Arguably the most important in computer science is `Arrays`

. In JavaScript, no other object has more utility methods than arrays. Array methods worth remembering are: `sort`

, `reverse`

, `slice`

, and `splice`

. Array elements are inserted beginning at the *0th index*. This means the last element is at `array.length — 1`

. Arrays are the most optimal for *indexing *(pushing), but can be terrible at *inserting*, *deleting* (not popping), and *searching*. In JavaScript, arrays can grow *dynamically*.

In **Big O**:

**Indexing**: O(1)**Inserting**: O(n)**Deleting**: O(n)**Brute-Force Searching**: O(n)**Optimized Searching**: O(log n)

Examples of these `Array`

methods in code:

It’s also worthwhile to read the full documentation on MDN about `Arrays`

:

**Array**

*The JavaScript Array object is a global object that is used in the construction of arrays; which are high-level, list…*developer.mozilla.org

Similar to arrays are `Sets`

and `Maps`

. In a set, items are guaranteed to be *unique*. In a map, items consist of *keys* and *values* in a dictionary-like relationship. Of course, `Objects`

(and their literals) can also be used to store key-value pairs, but the keys must be `strings`

.

#### Iterations

Intimately associated with `Arrays`

is **iterating **through them using loops. In JavaScript, we can use *five* different *control structures* for iterations. The most customizable is the `for`

loop, which we can use to iterate through array *indexes* in almost any order. If the *number of iterations* cannot be determined, we can use `while`

and `do while`

loops until a certain condition is met. For any object, we can use the `for in`

and `for of`

loops to iterate through its keys and values, respectively. To get both simultaneously, we can loop through its `entries()`

. We can also *break out* of a loop at any time using a `break`

statement, or *skip* *ahead* to the next iteration using a `continue`

statement. For the most control, iterating through `generator`

functions is the best.

Native array methods that iterate through all its items are: `indexOf`

, `lastIndexOf`

, `includes`

, `fill`

, and `join`

. Additionally, we can provide a `callback`

function to the following methods: `findIndex`

, `find`

, `filter`

, `forEach`

, `map`

, `some`

, `every`

, and `reduce`

.

Examples of these `Array`

methods in code:

#### Recursions

In a seminal paper, the Church-Turing Thesis proves that any iterative function can be reproduced with a recursive one, and vice versa. Sometimes, a recursive approach is cleaner, clearer, and more elegant. Take this iterative `factorial`

function for example:

constfactorial= number => {

let product = 1;

for (let i = 2; i <= number; i++) {

product *= i;

}

return product;

};

Expressed as a `recursive`

function, only *one* line of code is needed!

constfactorial= number => {

return number < 2 ? 1 : number * factorial(number - 1);

};

All recursive functions share a *common pattern*. They are made from creating a *recursive part* that calls itself, and a *base case* that does not. Whenever a `function`

calls itself, it pushes a new `execution context`

to the `execution stack`

. This continues until the *base case* is met, then the *stack* unwinds as *contexts* are popped off one by one. For this reason, careless dependence on recursion can lead to the dreaded `stack overflow`

runtime error.

The `factorial`

function in live code:

Finally, we are ready to take on any algorithm challenge! 😉

### Popular Algorithm Questions

In this section, we will walk through 22 *commonly-asked* algorithm questions in order of difficulty. Alternate approaches will be discussed as well their tradeoffs and runtime complexities. Usually, the most elegant solution utilizes a special “trick” or key insight. With this in mind, let’s begin!

#### 1. String Reversal

Given a `string of characters`

as *input*, write a `function`

that returns it with the characters *reversed*.

describe("String Reversal", () => {

it("Should reverse string", () => {

assert.equal(reverse("Hello World!"), "!dlroW olleH");

});

});

**Analysis**:

If we know the “trick”, the solution is trivial. That trick is to realize we can simply use the built-in `reverse`

method for an *array. *First, we use the `split`

method on a *string* to generate an `array of characters`

, then we can apply the `reverse`

method before using the `join`

method to combine the characters back into a *string *again. This solution can be written in just one line of code! Though not as elegant, the problem can also be solved using the latest syntax and helper method. With the new `for of`

loop that iterates through every character of any string, we can show off our familiarity with the latest syntax. Alternatively, we can also use the array’s `reduce`

method which eliminates the need to keep a temporary variable.

Given a string of characters, every character needs to be visited once. Though this happens multiple times, the *time complexity* normalizes out to *linear*. And since no separate internal data structure is kept, the *space complexity* is *constant*.

**Code**:

#### 2. Palindrome

A *palindrome* is a `word`

or `phrase`

that reads the same* backward as forward*. Write a `function`

that checks for this.

describe("Palindrome", () => {

it("Should return true", () => {

assert.equal(isPalindrome("Cigar? Toss it in a can. It is so tragic"), true);

});

it("Should return false", () => {

assert.equal(isPalindrome("sit ad est love"), false);

});

});

**Analysis**:

The key insight here is to realize that we can build on what we’d learned from the previous problem. Except, we need to return a `boolean`

value. This is as simple as returning a *triple equality *check against the *original string*. We could also use the new `every`

method on an *array* to check that the *first* and *last* characters match up in sequential order* towards the center*. However, this will check two times more than necessary. Similar to the previous problem, the runtime complexities for both time and space are identical.

What if we wanted to expand our function to test an entire *phrase*? We can create a *helper function* that uses **Regular Expressions** and the `replace`

method on a `string`

to keep only the letters. If regular expressions are not allowed, we can create an `array`

of *acceptable characters* to use as a filter.

**Code**:

#### 3. Integer Reversal

Given an `integer`

, *reverse* the order of the digits.

describe("Integer Reversal", () => {

it("Should reverse integer", () => {

assert.equal(reverse(1234), 4321);

assert.equal(reverse(-1200), -21);

});

});

**Analysis**:

The clever trick here is to first convert the integer to a `string`

using the built-in `toString`

method. Then, we can simply reuse the logic from the *String Reversal* algorithm. After the digits are reversed, we can use the global `parseInt`

function to convert the string back to an integer, and `Math.sign`

to carry over the polarity. This approach reduces to just one line of code!

Since we reuse the logic from *String Reversal*, this algorithm also shares the same runtime complexities for both space and time.

**Code**:

#### 4. Fizz Buzz

Given a `number`

as an input, print out every integer from 1 to that number. However, when the integer is divisible by 2, print out “Fizz”; when it’s divisible by 3, print out “Buzz”; when it’s divisible by both 2 and 3, print out “Fizz Buzz”.

describe("Fizz Buzz", () => {

beforeEach(() => (output = fizzBuzz(30)));

it("Should output number", () => {

assert.equal(output[0], 1);

});

it("Should output Fizz", () => {

assert.equal(output[1], "Fizz");

});

it("Should output Buzz", () => {

assert.equal(output[2], "Buzz");

});

it("Should output Fizz Buzz", () => {

assert.equal(output[5], "Fizz Buzz");

});

});

**Analysis**:

When we realize that the *modulus operator *can be used to check for divisibility, this classic algorithm challenge becomes trivial. The modulus divides two numbers and returns the remainder. Therefore, we can simply loop through every integer and check for remainders of `0`

. To show off our mathematical prowess, we can take into account that when a number is divisible by both `a`

and `b`

, it’s also divisible by their *lowest common multiple*.

As usual, the runtime complexities are the same because every integer is visited and checked without needing to keep an internal state.

**Code**:

#### 5. Max Character

Given a `string`

of characters, return the `character`

that *appears the most often*.

describe("Max Character", () => {

it("Should return max character", () => {

assert.equal(max("Hello World!"), "l");

});

});

**Analysis**:

The trick is to create a table that tallies the appearance of each character as we loop through the string. This table can be created using an `object literal`

where the `characters`

are *keys* and the `counters`

are *values*. Then, we can iterate through the table to find the character that has the largest counter by keeping *temporary *`variables`

* *for its key and value.

Though we use two separate loops that iterate through two different inputs (*character string* and *character map*), the time complexity is still *linear*. It may be derived from the character string, but eventually, the size of the character map will reach a limit because there’s only a *finite* number of characters in any language. For the same reason, the space complexity is *constant* despite how the input string grows even though an internal state is kept. Temporary primitives are also negligible at large scales.

**Code**:

#### 6. Anagrams

Anagrams are `words`

or `phrases`

that contain the *same number of characters*. Create a `function`

that checks for this.

describe("Anagrams", () => {

it("Should implement anagrams", () => {

assert.equal(anagrams("hello world", "world hello"), true);

assert.equal(anagrams("hellow world", "hello there"), false);

assert.equal(anagrams("hellow world", "hello there!"), false);

});

});

**Analysis**:

An obvious approach is to create a *character map* that tallies the number of characters for each input string. Then, we can compare the maps to see if they are identical. The logic that creates the character maps can be extracted as a *helper function* for easier reuse. To be thorough, we should first remove all non-alphabetic characters from the input strings and then make the remainder all lowercase.

As we’ve seen, character maps have a *linear* time complexity and a *constant* space complexity. To be more precise, this approach has `O(n + m)`

for time because two different strings are checked.

A more elegant approach is to realize that we can simply `sort`

the input strings and then check for equality! However, the downside is that sorting usually requires *linearithmic* time.

**Code**:

#### 7. Vowels

Given a `string`

of words or phrases, *count* the number of `vowels`

.

describe("Vowels", () => {

it("Should count vowels", () => {

assert.equal(vowels("hello world"), 3);

});

});

**Analysis**:

The easiest solution is to take advantage of *regular expressions* to extract all the vowels and then count them. If regular expressions are not allowed, we can simply loop through every character and check it against a collection of vowels. The string should be *lowercased* first.

Both approaches have *linear* time complexity and *constant* space complexity because every character needs to be checked and temporary primitives are negligible.

**Code**:

#### 8. Array Chunking

Given an `array`

and a `size`

, split the array *items* into a `list`

of *arrays* of the given size.

describe("Array Chunking", () => {

it("Should implement array chunking", () => {

assert.deepEqual(chunk([1, 2, 3, 4], 2), [[1, 2], [3, 4]]);

assert.deepEqual(chunk([1, 2, 3, 4], 3), [[1, 2, 3], [4]]);

assert.deepEqual(chunk([1, 2, 3, 4], 5), [[1, 2, 3, 4]]);

});

});

**Analysis**:

An obvious solution is to keep a reference to the last “chunk” and check its size as we loop through the array items. A more elegant solution is to use the built-in `slice`

method. This way, no reference is needed, producing a cleaner code. This can be achieved with a `while`

loop or a `for`

loop that increments by steps of the given size.

These algorithms all have *linear* time complexity because every array item needs to be visited once. They also have a *linear* space complexity because an internal array of “chunks” is kept which grows proportionally to the input array.

**Code**:

#### 9. Reverse Array

Given an `array`

of items, *reverse* the order.

describe("Reverse Arrays", () => {

it("Should reverse arrays", () => {

assert.deepEqual(reverseArray([1, 2, 3, 4]), [4, 3, 2, 1]);

assert.deepEqual(reverseArray([1, 2, 3, 4, 5]), [5, 4, 3, 2, 1]);

});

});

**Analysis**:

Of course, an obvious solution is to use the built-in `reverse`

method. But this would be too easy! If not allowed, we can simply loop through one half of the array and *swap* the beginning with the end. This means we will need to temporarily store *one* of the items in memory. To circumvent this need, we can use *destructuring assignment* with array matching.

Though only one half of the input array is visited, the time complexity is still *linear* because Big O asymptotically ignores coefficients.

**Code**:

#### 10. Reverse Words

Given a `phrase`

, *reverse* the order of the characters of each word.

describe("Reverse Words", () => {

it("Should reverse words", () => {

assert.equal(reverseWords("I love JavaScript!"), "I evol !tpircSavaJ");

});

});

**Analysis**:

We can use the split method to create an array of individual words. Then for each word, we can reuse the logic from *Reverse String* to reverse its characters. An alternative approach is to loop through each word in *reverse order *and store the result in a temporary variable. Either way, we will need to temporarily save all the reversed words before joining them at the end.

Because every character is visited and the required temporary variable grows proportionately to the input string, the time and space complexities are *linear*.

**Code**:

#### 11. Capitalization

Given a `phrase`

, *capitalize* every word.

describe("Capitalization", () => {

it("Should capitalize phrase", () => {

assert.equal(capitalize("hello world"), "Hello World");

});

});

**Analysis**:

One approach is to loop through every character, and when the previous character is a *space*, apply `toUpperCase`

to capitalize the current character. Because **string literals** are *immutable* in JavaScript, we will need to rebuild the input string with the appropriate capitalizations. This approach requires us to always capitalize the first character. Perhaps a cleaner approach is to `split`

the input string into an *array of words.* Then, we can loop through this array and capitalize the first characters, before joining the words back together again. For the same reason of immutability, we will need to hold in memory a *temporary array* that contains the appropriate capitalizations.

Both approaches have a *linear* time complexity because every character is visited at least once. They also have a *linear* space complexity because a temporary variable is kept which grows proportionally to the input string.

**Code**:

#### 12. Caesar Cipher

Given a `phrase`

, *substitute* each character by shifting it up or down the alphabet by a given `integer`

. If necessary, the shifting should wrap around back to the beginning or end of the alphabet.

describe("Caesar Cipher", () => {

it("Should shift to the right", () => {

assert.equal(caesarCipher("I love JavaScript!", 100), "E hkra FwrwOynelp!");

});

it("Should shift to the left", () => {

assert.equal(caesarCipher("I love JavaScript!", -100), "M pszi NezeWgvmtx!");

});

});

**Analysis**:

Firstly, we will need to create an `array`

of *alphabet characters* in order to calculate the result of shifting a character. This means we need to lowercase the `input string`

before iterating through its characters. We should use a regular `for`

loop to easily keep track of the current index. We will need to build up a `new string`

that contains the shifted characters per iteration. When we meet a non-alphabetic character, we should immediately append it to the end of our solution string and use the `continue`

statement to skip ahead to the next iteration. The key insight is to realize that we can use the `modulus operator`

to mimic the behavior of wrapping around to the beginning or end of the alphabet array when the shifting is more than 26. Lastly, we need to check for capitalization in the original string before appending the result to our solution.

Since every character in the input string needs to be visited and a new string needs to be created from it, this algorithm has a *linear* time and space complexity.

**Code**:

#### 13. Ransom Note

Given a `magazine of words`

and a `ransom note`

, determine if it’s possible to “cut out” and create the *ransom note* from the *magazine words*.

constmagazine=

"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum";

describe("Ransom Note", () => {

it("Should return true", () => {

assert.equal(ransomNote("sit ad est sint", magazine), true);

});

it("Should return false", () => {

assert.equal(ransomNote("sit ad est love", magazine), false);

});

it("Should return true", () => {

assert.equal(ransomNote("sit ad est sint in in", magazine), true);

});

it("Should return false", () => {

assert.equal(ransomNote("sit ad est sint in in in in", magazine), false);

});

});

**Analysis**:

An obvious solution is to split the magazine words and ransom words into *arrays* of individual words, and then check every ransom word against every magazine word. However, this approach scales in *quadratic* time, or `O(n * m)`

which is not performant. If we create a table of magazine words first, and then check each ransom word against this table, we can achieve *linear* time. This is because table lookup in *map objects* occurs in *constant* time. However, we will need to sacrifice space complexity in order to hold the map object in memory.

In code, this means we create a count of every magazine word, and then check if this “hash table” contains the right number of ransom words.

**Code**:

#### 14. Mean, Median, and Mode

Given an `array`

of numbers, calculate the *mean*, *median*, and *mode*.

conststat1= new Stats([1, 2, 3, 4, 4, 5, 5]);

conststat2= new Stats([1, 1, 2, 2, 3, 3, 4, 4]);

describe("Mean", () => {

it("Should implement mean", () => {

assert.equal(Stats.round(stat1.mean()), 3.43);

assert.equal(Stats.round(stat2.mean()), 2.5);

});

});

describe("Median", () => {

it("Should implement median", () => {

assert.equal(stat1.median(), 4);

assert.equal(stat2.median(), 2.5);

});

});

describe("Mode", () => {

it("Should implement mode", () => {

assert.deepEqual(stat1.mode(), [4, 5]);

assert.deepEqual(stat2.mode(), []);

});

});

**Analysis**:

In terms of difficulty, the algorithm to find the *mean* of a collection of numbers is the easiest. Statistically, the `mean`

is defined as the *sum* of the collection divided by its *size*. Therefore, we can simply use the array’s `reduce`

method to calculate its sum and then divide that by its `length`

. This algorithm has runtime complexities of *linear* time and *constant* space because every number needs to be added while no internal memory is necessary.

The algorithm to find the *median* of a collection is of medium difficulty. First, we need to sort the array, but if its size is even, we will need extra logic to deal with two middle numbers. In these cases, we will need to return the *average* of those two numbers. This algorithm has a *linearithmic* time complexity due to sorting and a *linear* space complexity because internal memory is needed to hold the sorted array.

The algorithm to find the *mode* is the most challenging. Since the `mode`

is defined as the number or numbers that appear the most often, we will need to maintain a *frequency table*. To complicate things further, if every value appears the same number of times, there is no mode. In code, this means we will need to create a *hash map* that tallies the frequency of each unique number, and then loop through it to collect the maximum number or numbers, or none. Because every number needs to be counted to create the hash table which is held in memory, this algorithm has a *linear* time and space complexity.

**Code**:

#### 15. Two Sum

Given an `array`

of numbers, return *all pairs* that add up to a given `sum`

. The numbers can be used more than once.

describe("Two Sum", () => {

it("Should implement two sum", () => {

assert.deepEqual(twoSum([1, 2, 2, 3, 4], 4), [[2, 2], [3, 1]]);

});

});

**Analysis**:

An obvious solution is to create *nested loops* that check each number against every other number in the same array. Those that add up to the given sum can be pushed to a *solution array* as pairs. However, this nesting causes a *quadratic* time complexity which is not performant for large inputs.

A clever trick is to maintain an array that contains the “counterpart” of each number as we iterate through the input array, while simultaneously checking for the existence of each number’s counterpart. By maintaining such an array, we sacrifice space efficiency to gain a *linear* time complexity.

**Code**:

#### 16. Max Profit

Given an `array`

of stock prices, find the *minimum *`buy price`

and the *maximum *`sell price`

that produce the *greatest profit*.

describe("Max Profit", () => {

it("Should return minimum buy price and maximum sell price", () => {

assert.deepEqual(maxProfit([1, 2, 3, 4, 5]), [1, 5]);

assert.deepEqual(maxProfit([1, 3, 2, 5, 4]), [1, 5]);

`assert.deepEqual(maxProfit([2, 10, 1, 3]), [2, 10]);`

});

**Analysis**:

Again, we can create *nested loops* that check every possible combination of buy price and sell price to see which pair produces the greatest profit. Because technically we cannot sell before we buy, not every combination needs to be checked. Specifically, for a given buy price, we can ignore all preceding prices for the sell price. As such, the time complexity for this algorithm is better than *quadratic*.

With a little more thought, we can solve the problem using only one loop through the prices array. The key insight is to realize that the sell price should never be less than the buy price; if so, we should have bought the stock at that lower price. In code, this means we can simply hold a *temporary boolean* to indicate that we should change the buy price on the next iteration. Requiring only one loop, this elegant approach has a *linear* time and *constant* space complexity.

**Code**:

#### 17. Sieve of Eratosthenes

For a given `number`

, find all the *prime numbers* from zero to that number.

describe("Sieve of Eratosthenes", () => {

it("Should return all prime numbers", () => {

assert.deepEqual(primes(10), [2, 3, 5, 7]);

});

});

**Analysis**:

At first blush, we may be tempted to loop through every possible number and simply use the modulus operator to check for all the possible divisibilities. However, it’s easy to surmise that this approach is terribly inefficient, with a time complexity worse than quadratic. Thankfully, *Eratosthenes of Cyrene*, the inventor of geography, also invented an efficient method for identifying prime numbers.

In code, the first step is to create an array as large as the given number, with all its values initialized as `true`

. In other words, the array *indexes* represent all the possible prime numbers, with all being *true* at the beginning. Then, we create a `for`

loop that iterates from 2 to the *square root* of the given number, using array *key interpolation* to designate the `product`

with every number as *false*. By definition, products of any integer cannot be prime, while 0 and 1 are ignored because divisibility by them does not affect primality. Lastly, we can simply filter out all the *falsey* values to arrive at all the prime numbers.

By sacrificing space efficiency to maintain an internal “hash table”, this *sieve* of Eratosthenes has a time complexity better than quadratic, or `O(n * log (log n))`

.

**Code**:

#### 18. Fibonacci

Implement a `function`

that returns the *fibonacci number* at a given `index`

.

describe("Fibonacci", () => {

it("Should implement fibonacci", () => {

assert.equal(fibonacci(1), 1);

assert.equal(fibonacci(2), 1);

assert.equal(fibonacci(3), 2);

assert.equal(fibonacci(6), 8);

assert.equal(fibonacci(10), 55);

});

});

**Analysis**:

Since a fibonacci number is the sum of the previous two, the simplest approach is to use *recursion*. The fibonacci series is premised on the first two being 0 and 1; therefore, we can use this fact to create our *base case*. For index that is greater than 2, we can recall our fibonacci function to add the previous two. Though quite elegant, this recursive approach is terribly inefficient, with an *exponential* time and *linear* space complexity. Because every function call requires exponential memory on the call stack, it will quickly break.

Though not as elegant, an iterative approach is more time efficient. By using a loop to build the entire fibonacci series up to the given index, it achieves *linear *time and space.

**Code**:

#### 19. Memoized Fibonacci

Implement a *performant* recursive function for the fibonacci series.

describe("Memoized Fibonacci", () => {

it("Should implement memoized fibonacci", () => {

assert.equal(fibonacci(6), 8);

assert.equal(fibonacci(10), 55);

});

});

**Analysis**:

Since the fibonacci series makes redundant exponential calls to itself, it can benefit dramatically from a strategy called *memoization*. In other words, if we keep a *cache* of all the inputs and outputs as we call our function, the number of calls will reduce to *linear* time. Of course, this means we have sacrificed additional memory.

In code, we can implement the memoization technique inside the function itself, or we can abstract it as a higher-order utility function that decorates any function with memoization.

**Code**:

#### 20. Staircase

For a given number of `steps`

, print out a “staircase” using *hashes* and *spaces*.

describe("Steps", () => {

it("Should print steps", () => {

assert.equal(steps(3), "# \n## \n###\n");

assert.equal(_steps(3), "# \n## \n###\n");

});

});

**Analysis**:

The key insight is to realize that as we move down the steps, the number of `hashes`

*increments* while the number of `spaces`

*decrements*. If we have `n`

steps, the overall dimension is `n`

by `n`

. This means the runtime complexity is *quadratic* for both time and space.

A recursive approach is also possible using this insight. Except, we need to pass along *additional parameters* in place of the necessary temporary variables.

**Code**:

#### 21. Pyramid

For a given number of `levels`

, print out a “pyramid” using *hashes* and *spaces*.

describe("Pyramid", () => {

it("Should print pyramid", () => {

assert.equal(pyramid(3), " # \n ### \n#####\n");

assert.equal(_pyramid(3), " # \n ### \n#####\n");

});

});

**Analysis**:

The key insight is to realize that a pyramid with `n`

steps (height) has a width of `2 * n — 1`

. Then, it’s just a matter of *incrementing* the number of *hashes* and *decrementing* the number of *spaces* starting from the center outwards as we go down the levels. Since this algorithm iteratively builds up a pyramid of size `n`

by `2 * n — 1`

, it has a `quadratic`

runtime complexity for both time and space.

Again, a recursive approach is also possible using this insight. Except, we need to pass along *additional parameters* in place of the necessary temporary variables.

**Code**:

#### 22. Matrix Spiral

Create a *square matrix* of a given `size`

in which elements are in *spiral order*.

describe("Matrix Spiral", () => {

it("Should implement matrix spiral", () => {

assert.deepEqual(spiral(3), [[1, 2, 3], [8, 9, 4], [7, 6, 5]]);

});

});

**Analysis**:

Though a very challenging problem, the trick is to create `temporary variables`

that point at the *current row* and *current column*, both at the *start* and the *end*. That way, we can iteratively *increment* the `starting row`

and `starting column`

and *decrement* the `ending row`

and `ending column`

in a manner that spirals toward the center of the matrix.

Because this algorithm iteratively builds up a *square* matrix of a given size, its runtime complexity is *quadratic* for both time and space.

**Code**:

### Data Structure Algorithms

Since data structures are the “building blocks” of algorithms, it’s worthwhile to explore the most popular ones.

*Again, for a quick high-level analysis, check out:*

#### Queues

Given two `queues`

as inputs, create a *new* queue by “weaving” them together.

describe("Weaving with Queues", () => {

it("Should weave two queues together", () => {

const one = new Queue();

one.enqueue(1);

one.enqueue(2);

one.enqueue(3);

const two = new Queue();

two.enqueue("one");

two.enqueue("two");

two.enqueue("three");

const result = weave(one, two);

assert.equal(result.dequeue(), 1);

assert.equal(result.dequeue(), "one");

assert.equal(result.dequeue(), 2);

assert.equal(result.dequeue(), "two");

assert.equal(result.dequeue(), 3);

assert.equal(result.dequeue(), "three");

assert.equal(result.dequeue(), undefined);

});

**Analysis**:

At the minimum, the `Queue`

* *class needs to have an `enqueue`

, `dequeue`

, and `peek`

methods. Then, we can use the `while`

loop to *peek* for existence, and if truthy, we can *dequeue* it out and then *enqueue* it to our new* *`queue`

.

This algorithm has `O(n + m)`

for both time and space because we need to iterate through two different collections and store them.

**Code**:

#### Stacks

Implement a `Queue`

class using two *stacks*.

describe("Queue from Stacks", () => {

it("Should implement queue using two stacks", () => {

const queue = new Queue();

queue.enqueue(1);

queue.enqueue(2);

queue.enqueue(3);

assert.equal(queue.peek(), 1);

assert.equal(queue.dequeue(), 1);

assert.equal(queue.dequeue(), 2);

assert.equal(queue.dequeue(), 3);

assert.equal(queue.dequeue(), undefined);

});

});

**Analysis**:

We can begin with a *class constructor* that initializes two stacks. Because the *last* record inserted is the *first* record removed in a *stack*, we will need to loop to the last record to “dequeue” or “peek” to mimic the behavior of a *queue,* whereby the the *first* record inserted is the *first* record removed. We can do this by using the second stack to *temporarily* hold all the items from the first stack until we reach the end. After the “peeking” or “dequeuing”, we simply move everything back to the first stack. To “enqueue” a record, we can simply push it to the first stack.

Though we use two stacks and need to loop twice, this algorithm is still asymptotically *linear* in time and space.

**Code**:

#### Linked Lists

Single linked lists usually have the following functionalities:

describe("Linked List", () => {

it("Should implement insertHead", () => {

const chain = new LinkedList();

chain.insertHead(1);

assert.equal(chain.head.data, 1);

});

it("Should implement size", () => {

const chain = new LinkedList();

chain.insertHead(1);

assert.equal(chain.size(), 1);

});

it("Should implement getHead", () => {

const chain = new LinkedList();

chain.insertHead(1);

assert.equal(chain.getHead().data, 1);

});

it("Should implement getTail", () => {

const chain = new LinkedList();

chain.insertHead(1);

assert.equal(chain.getTail().data, 1);

});

it("Should implement clear", () => {

const chain = new LinkedList();

chain.insertHead(1);

chain.clear();

assert.equal(chain.size(), 0);

});

it("Should implement removeHead", () => {

const chain = new LinkedList();

chain.insertHead(1);

chain.removeHead();

assert.equal(chain.size(), 0);

});

it("Should implement removeTail", () => {

const chain = new LinkedList();

chain.insertHead(1);

chain.removeTail();

assert.equal(chain.size(), 0);

});

it("Should implement insertTail", () => {

const chain = new LinkedList();

chain.insertTail(1);

assert.equal(chain.getTail().data, 1);

});

it("Should implement getAt", () => {

const chain = new LinkedList();

chain.insertHead(1);

assert.equal(chain.getAt(0).data, 1);

});

it("Should implement removeAt", () => {

const chain = new LinkedList();

chain.insertHead(1);

chain.removeAt(0);

assert.equal(chain.size(), 0);

});

it("Should implement insertAt", () => {

const chain = new LinkedList();

chain.insertAt(0, 1);

assert.equal(chain.getAt(0).data, 1);

});

it("Should implement forEach", () => {

const chain = new LinkedList();

chain.insertHead(1);

chain.insertHead(2);

chain.forEach((node, index) => (node.data = node.data + index));

assert.equal(chain.getTail().data, 2);

});

it("Should implement iterator", () => {

const chain = new LinkedList();

chain.insertHead(1);

chain.insertHead(2);

for (let node of chain) node.data = node.data + 1;

assert.equal(chain.getTail().data, 2);

});

});

**Code**:

**Challenge #1: Midpoint**

Without keeping a counter, return the *middle value* of a linked list.

describe("Midpoint of Linked List", () => {

it("Should return midpoint of linked list", () => {

const chain = new LinkedList();

chain.insertHead(1);

chain.insertHead(2);

chain.insertHead(3);

chain.insertHead(4);

chain.insertHead(5);

assert.equal(midpoint(chain).data, 3);

});

});

**Analysis**:

The trick is to traverse down the list *two times*, one of which is *two times faster*. When the faster one reaches the end, the slower one stops at the middle!

This algorithm has *linear* time and *constant* space.

**Code**:

**Challenge #2: Circular**

Without keeping node references, check if a linked list is *circular*.

describe("Circular Linked List", () => {

it("Should check for circular linked list", () => {

const chain = new LinkedList();

chain.insertHead(1);

chain.insertHead(2);

chain.insertHead(3);

chain.head.next.next.next = chain.head;

assert.equal(circular(chain), true);

});

});

**Analysis**:

Many linked list functionalities are predicated on having a *definite* ending node. Therefore, ensuring that it’s not circular is critical. Again, the trick is to traverse the list two times, one of which is two times faster. If the list is circular, eventually, the faster one will loop around and coincide with the slower one. We can exit the loop here and return `true`

. Otherwise, the end will be reached, and we can return `false`

.

This algorithm also has *linear* time and *constant* space.

**Code**:

**Challenge #3: From Tail**

Without keeping a counter, return the *value* in a linked list that is at a given `step`

away from the end.

describe("From Tail of Linked List", () => {

it("Should step from tail of linked list", () => {

const chain = new LinkedList();

chain.insertHead(1);

chain.insertHead(2);

chain.insertHead(3);

chain.insertHead(4);

chain.insertHead(5);

assert.equal(fromTail(chain, 2).data, 3);

});

});

**Analysis**:

The trick is similar to the previous in that we traverse the list two times. In this case, however, the “faster” one begins *ahead* of the “slower” one, at the given `step`

away. Then, we walk them both down the list at the same pace until the faster one reaches the end. At that point, the slower one is precisely at the right step away from the end.

This algorithm also has *linear* time and *constant* space.

**Code**:

#### Trees

Trees usually have the following functionalities:

describe("Trees", () => {

it("Should add and remove nodes", () => {

const root = new Node(1);

root.add(2);

assert.equal(root.data, 1);

assert.equal(root.children[0].data, 2);

root.remove(2);

assert.equal(root.children.length, 0);

});

it("Should traverse by breadth", () => {

const tree = new Tree();

tree.root = new Node(1);

tree.root.add(2);

tree.root.add(3);

tree.root.children[0].add(4);

const numbers = [];

tree.traverseBF(node => numbers.push(node.data));

assert.deepEqual(numbers, [1, 2, 3, 4]);

});

it("Should traverse by depth", () => {

const tree = new Tree();

tree.root = new Node(1);

tree.root.add(2);

tree.root.add(3);

tree.root.children[0].add(4);

const numbers = [];

tree.traverseDF(node => numbers.push(node.data));

assert.deepEqual(numbers, [1, 2, 4, 3]);

});

});

**Code**:

**Challenge #1: Tree Widths**

For a given `tree`

, return the *width* of each level.

describe("Width of Tree Levels", () => {

it("Should return width of each tree level", () => {

const root = new Node(1);

root.add(2);

root.add(3);

root.children[1].add(4);

assert.deepEqual(treeWidths(root), [1, 2, 1]);

});

});

**Analysis**:

A tree can be traversed by *depth first* or *breadth first* using a `stack`

or `queue`

to help iterate through all its *slices* and *levels*, respectively. Since we want to count all the nodes on each level, we need to traverse the tree by *breadth first* with the help of a `queue`

. The trick here is to enqueue a special `marker`

to let us know that the end of the current level has been reached so that we can *reset* the `counter`

for the next level.

This approach has a *linear* time and space complexity. Though our `counter`

is an array, its size can never be greater than linear.

**Code**:

**Challenge #2: Tree Height**

For a given `tree`

, return the *height* (maximum number of levels).

describe("Height of Tree", () => {

it("Should return max number of levels", () => {

const root = new Node(1);

root.add(2);

root.add(3);

root.children[1].add(4);

assert.deepEqual(treeHeight(root), 2);

});

});

**Analysis**:

We can simply reuse our logic from the first challenge. In this case, however, we increment our `counter`

whenever we encounter `“reset”`

instead. The logic is nearly identical, so this algorithm also has a *linear* time and space complexity. Here, our `counter`

is just an integer, which makes its size even more negligible.

**Code**:

#### Graphs

Please check back! (TK)

### Sorting Algorithms

There are many algorithms that we can use to sort a collection of data. Thankfully, interviewers only expect us to understand the basics and first principles. For instance, the best algorithms can achieve *linearithmic* time in *constant* space. In this spirit, we will review the most popular ones in order of increasing difficulty and efficiency.

#### Bubble Sort

This algorithm is the easiest to understand but is also the most inefficient. It *compares* every item against every other item, *swapping* the order until the bigger ones “bubble” to the top. This algorithm requires *quadratic* time and *constant* space.

#### Insertion Sort

Like bubble sort, every item is compared with every other item. Instead of swapping, it “splices” in the correct order. In effect, it maintains the original order of repeated items. This “greedy” algorithm also requires *quadratic* time and *constant* space.

#### Selection Sort

As the loop iterates through a collection, this algorithm finds and “selects” the index with the *lowest value* and swaps it with the beginning index wherever appropriate. This algorithm also requires *quadratic* time and *constant* space.

#### Quick Sort

This algorithm recursively selects an element as the *pivot* and iteratively pushes all the smaller elements to the left and all the larger elements to the right until all is sorted. This algorithm requires *quadratic* time and *logarithmic* space such that in practice is often the *fastest*. As such, most programming languages natively implement this algorithm for sorting.

#### Merge Sort

Though one of the most efficient, this algorithm can be challenging to understand. It requires a *recursive* part that splits up a collection into single units, and then an *iterative* part that combines them back together in the right order. This algorithm takes *linearithmic* time and *linear* space.

#### Counting Sort

If we somehow know the *maximum value*, we can use this algorithm to sort a collection in *linear* time and space! The maximum value lets us create an array of that size to *count* the occurrence of each *index value*. Then, it’s just a matter of extracting all the indexes that have *non-zero* counts into our result array. By exploiting the *constant-time* lookup of arrays, this hash-like algorithm is the most performant possible.

#### Other Sorting Algorithms

### Search Algorithms

The worst algorithm needs to search every item in a collection, taking `O(n)`

time. If somehow the collection is already sorted, only half needs to be checked at each iteration, taking just `O(log n)`

time, a huge performance boost especially for very large datasets.

#### Binary Search

When a collection is sorted, we can *iteratively* or *recursively* check our desired value against the middle item, discarding the half where we know our value cannot exist. In effect, our target can be found in *logarithmic* time and *constant* space.

#### Binary Search Tree

An alternative to sorting a collection is to generate a *Binary Search Tree *(BST)* *from it. As a BST, searching through it is as efficient as binary search. In a similar way, we can discard the half that we know cannot contain our desired value at every iteration. In fact, another way to sort a collection is to do a depth-first traversal across this tree *in-order*!

BST creation happens in *linear* time and space, but searching through it happens in *logarithmic* time and *constant* space.

To validate that a binary tree is a BST, we can recursively check that every left child must be less than the root (maximum possible) and every right child must be greater than the root (minimum possible) *at every root*. This solution requires *linear* time and *constant* space.

### Conclusion

In modern web development, **functions** lie at the heart of the web experience. **Data structures** enter and exit functions while **algorithms** dictate the internal mechanics. The way a data structure scales is described by its *space complexity*, while the way an algorithm scales is described by its *time complexity*. In practice, runtime complexities are expressed as **Big-O** notations which help engineers to compare and contrast all the solution possibilities. The most efficient runtime is *constant* and does not depend on input sizes; the most inefficient requires *exponential* operations and memories. To truly master algorithms and data structures is to be able to reason *linearly* and *systemically* in* *parallel*.*

Theoretically, every problem has both an **iterative** solution and a **recursive** one. An iterative approach starts from the bottom and *dynamically* arrives at a solution. A recursive approach starts from the top by recognizing *overlapping subproblems*. Usually, a recursive solution is more expressive and simpler to implement, but an iterative solution is easier to grok and requires less memory. With *first-class* functions and *control-flow* constructs, JavaScript natively supports both approaches. Generally, space efficiency needs to be sacrificed for performance gains, or time efficiency needs to be sacrificed for less memory usage. The right balance depends on the context and the environment. Thankfully, most interviewers are more concerned with the *calculus* than the outcome.

To really impress your interviewer, expand her purview by looking ahead and above for opportunities to utilize **architectures** and **design patterns** that increase *reusability* and *maintainability*. If you’re seeking a senior position, knowledge of fundamentals and first principles, and experience with system-level design are equally important. Nevertheless, the best companies also assess for *cultural fit*. Because no one is perfect, the right team is essential. More importantly, some things in this world are impossible to achieve alone. More often than not, the things we create together and for each other are the most satisfying and meaningful.

*Interested in **blockchain**? **Learn Ethereum** and come work for us!*