Tests and implementations for algorithms commonly used in job interviews. See the full list in the algorithms.md file.
Base repository for the Core Algorithms goal.
- To clone this repository on your local machine:
git clone https://github.com/morelme/core-algorithms.git - To install any dependencies:
npm i
- To run the tests:
npm tLink to Big O time complexities: http://bigocheatsheet.com/
Classic | Numeric | Set Operations | Sorting and Searching | Graphing and Geometry
- makeChange
Given a price and an amount paid, return the number of coins in each denomination that should be given as change.
Note: because JavaScript is bad at decimal math, the inputs are given as integers that represent dollar + cent amounts, so 139 = $1.39.
makeChange({ price: 100, amountGiven: 100 })
// => { quarters: 0, dimes: 0, nickels: 0, pennies: 0 }
makeChange({ price: 159, amountGiven: 200 })
// => { quarters: 1, dimes: 1, nickels: 1, pennies: 1 }
makeChange({ price: 432, amountGiven: 500 })
// => { quarters: 2, dimes: 1, nickels: 1, pennies: 3 }- fizzBuzz
Return an array of numbers from 1 to 100.
For multiples of three, use the string Fizz instead of the number and for multiples of five replace with Buzz.
For numbers which are multiples of both three and five replace with FizzBuzz.
fizzBuzz()
// => [1, 2, 'Fizz', 4, 'Buzz', 'Fizz', 7, 8, 'Fizz', 'Buzz', 11, 'Fizz', 13, 14, 'FizzBuzz', ...]- isPalindrome
Determine if a string is a palindrome. Return true or false.
Ignore punctuation, spacing, and case sensitivity.
isPalindrome('radar')
// => true
isPalindrome('bananas')
// => false
isPalindrome('A man, a plan, a canal: Panama')
// => true- factorial
Return the factorial of a number.
factorial(5)
// => 120- fibonacci
Return an array of Fibonacci numbers to the nth position.
fibonacci(10)
// => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]- collatzConjecture
Return the Collatz sequence for a given number.
The Collatz sequence for any positive integer n is defined as follows:
If
nis even, divide it by 2 to getn / 2. Ifnis odd, multiply it by 3 and add 1 to obtain3n + 1. Repeat the process until you reach 1.
collatzConjecture(1)
// => [1]
collatzConjecture(7)
// => [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]- setUnion
Return the union of two sets.
const a = [1, 2, 3, 4]
const b = [2, 4, 6, 8]
setUnion(a, b)
// => [1, 2, 3, 4, 6, 8]- setIntersection
Return the intersection of two sets.
const a = [1, 2, 3, 4]
const b = [2, 4, 6, 8]
setIntersection(a, b)
// => [2, 4]- setCompliment
Return the compliment of two sets.
const a = [1, 2, 3, 4]
const b = [2, 4, 6, 8]
setCompliment(a, b)
// => [6, 8]- setSymmetricDifference
Return the symmetric difference of two sets.
const a = [1, 2, 3, 4]
const b = [2, 4, 6, 8]
setSymmetricDifference(a, b)
// => [1, 3, 6, 8]- mergeSort
Sort an array of numbers using the merge sort algorithm.
mergeSort([10, 2, 7, 5, 8, 3, 6, 1, 4, 9])
// => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]- bubbleSort
Sort an array of numbers using the bubble sort algorithm.
bubbleSort([10, 2, 7, 5, 8, 3, 6, 1, 4, 9])
// => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]- binarySearch
Search for a number within an array using the binary search algorithm.
const numbers = [5, 10, 15, 20, 25, 30, 35, 40, 45, 50]
binarySearch(numbers, 45)
// => 8- [ ]closestPair
Given a set of points on a 2-dimensional plane, return the pair of points with the least distance between them.
Reference: Wikipedia
const points = [
[2,1],
[4,0],
[-1,0],
[5,3],
[-2,5],
[3,-3],
[-2,0],
[3,4],
[5,-4],
[0,-2]
]
closestPair(points)
// => { pair: [[-1, 0], [-2, 0]], distance: 1 }- [ ]isConnectedGraph
Check if a graph is connected or disconnected. Return true or false.
A graph is connected when there is a path between every pair of vertices.
Reference: Wikipedia
const graphA = {
'a': ['b', 'c'],
'b': ['a', 'd'],
'c': ['a', 'd'],
'd': ['b', 'c'],
}
isConnectedGraph(graphA)
// => true
const graphB = {
'a': ['b'],
'b': ['a'],
'c': ['d'],
'd': ['c'],
}
isConnectedGraph(graphB)
// => false