learn-co-students / js-algorithms-dumbo-web-062518

JavaScript Algorithms Practice

Take an hour to work on the below algorithms and then share you work with a partner and/or group. These algorithms are listing in increasing difficulty, so don't be surprised if the last one taxes your brain!!!

Practice working on these as you would work on them in an interview. Restate the problem and break it into smaller subproblems. Write some messy code, then refactor and think about how your refactoring improves your code. Get to the simplest working code first (often the brute force solution), then think about if there is another way to solve the problem that might be more efficient.

Lastly, these are all very common algorithms. Feel free to search the web and read more about their implementation, but avoid from looking at any code before you write your own. After you've spent an hour with them, feel free to compare your work to solutions on the internet.

Fibonacci

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Extra credit: Try creating a recursive answer.

Two Sum

Given an array of integers, return the indices of the two numbers that add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Given nums = [2, 7, 11, 15] and a target = 9 the return value should be [0, 1] because nums[0] + nums[1] = 2 + 7 = 9

Collatz Sequence

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even) n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Merge Sort

The merge sort algorithm sorts a list in two main steps.

First, take an unordered list and continue splitting the list into smaller and smaller subarrays until the subarrays each one element.

[7, 1, 2, 8, 6, 10, 4, 3]
  
[7, 1, 2, 8]   [6, 10, 4, 3]

[7, 1] [2, 8]   [6, 10] [4, 3]

[7] [1] [2] [8]  [6] [10] [4] [3]

So the first step is to take the unsorted list and break it up.

Second, couple up the neighboring lists and merge them together. While the merge operation only applies to sorted lists, when the list has only one element in it, it is automatically sorted.

merge([7],[1]) merge([2], [8])  merge([6], [10]) merge([4], [3])

Now think about what this gives us. Well the merge operation takes two sorted arrays and combines them into one sorted array. So merging pairs of eight sorted arrays, produces four sorted arrays, which we can then merge again.

merge([7],[1]) merge([2], [8])  merge([6], [10]) merge([4], [3])

// [1, 7] [2, 8] [6, 10] [3, 4] 

merge([1, 7], [2, 8]) merge([6, 10] [3, 4])

// [1, 2, 7, 8]  [3, 4, 6, 10] 
// which we can merge again
merge([1, 2, 7, 8], [3, 4, 6, 10])

//[1, 2, 3, 4, 6, 7, 8, 10]
// providing us with a sorted array

That's it! Two steps. First, continuously divide an unsorted array until we have subarrays each of one element. Second, call the merge operation on the subarrays until we are left with one sorted array.

This algorithm is challenging because it uses recursion, but it also involves the use of two separate functions!!!