Core Algorithms

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.

Installation and Setup

• npm Install
• npm test

Description

Write tests and implementations for algorithms commonly used in job interviews.

An "algorithm" is a technical term for "a particular set of steps to solve a defined problem". At the smallest scale, a sum() function is an example of an algorithm. At a large scale, the method by which Netflix recommends movies to its users is also called an algorithm.

Fork the the core-algorithms repository and use the fork as your project artifact.

Use the list in the algorithms.md file as a reference for each algorithm.

In addition, consider doing one or more of the Courses on algorithms listed in the Resources.

Context

Being able to design, implement, and test algorithms is a key skill for all programmers. Most of the algorithms you'll encounter on the job will not fall neatly into the set of "common algorithms" specified here, but will be new problems for which you will have to find new solutions and adapt existing ones.

For this reason, developing the ability to do algorithmic thinking is a high-value skill.

In addition, many job interview processes will include some algorithmic problem-solving component, and it is useful to be familiar with some of the most common problems and good approaches to find their solutions.

To be totally clear, the algorithms you design here are totally contrived. They are useful to know because interviewers may ask you to solve problems like this (a controversial fact of the software engineering industry), but beyond that it is unlikely that you will ever write a merge sort algorithm as part of a web development job.

However, that doesn't mean that they have no learning value. They are still useful as exercises in critical thinking, logic, and program design.

Specifications

• Artifact produced is a fork of the core-algorithms repo.
• Can run all tests with npm test.
• makeChange() algorithm is implemented according to the description in algorithms.md.
• Tests for makeChange() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• fizzBuzz() algorithm is implemented according to the description in algorithms.md.
• Tests for fizzBuzz() exist.
• isPalindrome() algorithm is implemented according to the description in algorithms.md.
• Tests for isPalindrome() exist with at least 2 unit tests using valid inputs.
• factorial() algorithm is implemented according to the description in algorithms.md.
• Tests for factorial() exist with at least 2 unit tests using valid inputs.
• fibonacci() algorithm is implemented according to the description in algorithms.md.
• Tests for fibonacci() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• collatzConjecture() algorithm is implemented according to the description in algorithms.md.
• Tests for collatzConjecture() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• setUnion() algorithm is implemented according to the description in algorithms.md.
• Tests for setUnion() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• setIntersection() algorithm is implemented according to the description in algorithms.md.
• Tests for setIntersection() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• setComplement() algorithm is implemented according to the description in algorithms.md.
• Tests for setComplement() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• setSymmetricDifference() algorithm is implemented according to the description in algorithms.md.
• Tests for setSymmetricDifference() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• binarySearch() algorithm is implemented according to the description in algorithms.md.
• Tests for binarySearch() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• bubbleSort() algorithm is implemented according to the description in algorithms.md.
• Tests for bubbleSort() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• mergeSort() algorithm is implemented according to the description in algorithms.md.
• Tests for mergeSort() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• closestPair() algorithm is implemented according to the description in algorithms.md.
• Tests for closestPair() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• isConnectedGraph() algorithm is implemented according to the description in algorithms.md.
• Tests for isConnectedGraph() exist with at least 2 unit tests using valid inputs, and at least 1 unit test using invalid inputs.
• Repository includes a README file with basic installation and setup instructions.
• All package dependencies are properly declared in package.json.
• All major features are added via pull requests with a clear description and concise commit messages.
• Code uses a linter and there are no linting errors.
• Variables, functions, files, etc. have appropriate and meaningful names.
• Functions are small and serve a single purpose.
• The artifact produced is properly licensed, preferably with the MIT license.

Stretch

Pick a different programming language from JavaScript (e.g. Ruby, Swift, Python, C, Java...) and write tests & implementations for each.

• Can run all non-JavaScript tests with a single command.
• For each algorithm identified above, there is a test file with multiple unit tests for each algorithm in a language other than JavaScript.
• For each algorithm identified above, there is an implementation file with a correct implementation of the algorithm in a language other than JavaScript.

Resources

Courses

• Frontend Masters: https://frontendmasters.com/courses/data-structures-algorithms/
• Khan Academy: Computer Science: Algorithms
• edX / IIT Bombay: Algorithms
• Coursera: Learn To Think Like A Computer Scientist
• Lynda: Introduction to algorithms

Books

• Data Structures and Algorithms with JavaScript

Other Resources

• Xkcd comic: collatzConjecture