bradtraversy/traversy-js-challenges

Challenges & docs from JS Algorithms & Data Structures course

Traversy JS Challenges: Data Structures & Algorithms

This is the sandbox for my 70+ JS Challenges: Data Structures & Algorithms Course. Just about all of the concepts that are included, also exist in other languages. So, if you are not a JavaScript developer, you can still follow along and learn from this course/repo.

This course/repo goes over everything from basic loop challenges, high order array methods, recursion, time & space complexity, data structures such as stacks, queues, linked lists, trees, graphs, and we touch on sorting algorithms like bubble sort, insertion and merge sort. You should already know the basics of JavaScript before doing any of the challenges or taking the course.

Please do not make any PRs to this repo as it goes along with a specific course. I may open another one for student solutions and new challenges.

File Structure

Each folder includes:

• readme.md - The challenge/code instructions. This also includes hints, tests and a dropdown with the solution code as well as the explanation of the solution code.
• [name].js - This is your working file. It has the name of the function and the function is exported. No parameters are passed to the function. That is up to you to add.
• [name]-run.js - File to run the code manually. The function is already imported and called with expected parameters.
• [name]-solution.js The solution code with heavy commenting. Some challenges have multiple solutions. If you want the solution without comments, look in the readme.md file.
• [name]-test.js - Jest tests for the solution code. You will need to rename this file to [name].test.js to run the tests.

Learning Modules/Lessons

Some lessons/modules are not challenges, they are more like mini-lessons. I don't just throw you a challenge using a new concept (Trees, Stacks, Bubble Sorts, etc) without explaining it first. I try to explain the concept and then give you a challenge to practice or implement it. So some folders will not have a challenge, just a readme file.

Running Tests

In order for the Jest tests to run, you need to rename the test file to [name].test.js. For example, if you are working on the hello-world challenge, you need to rename the hello-world-test.js file to hello-world.test.js. This is because Jest looks for files with the .test.js extension.

Run the command npm run test from the root directory and it will run all the tests.

These Don't Have to be "Challenges"

Some people, such as myself are not great at doing this stuff off the top of their head. Even though most of the code is setup as a challenge, you can certainly just follow along with the course and/or just study the solutions and learn from them.

You can use the tests to see if your code passes, but use the run files to run the code manually. This is so that you can experiment, console.log, etc.

Getting Started

1. Clone the repo
2. Run npm install
3. Run npm run test to run the tests. Again, you will need to rename the test files and replace the -test with .test to run the tests.

Index of Challenges/Lessons

01. Basic Challenges 1

These are mostly challenges that have to do with loops, conditionals, and string manipulation. I do not go over fundamentals like "what is a for loop". You should already know the basics of JavaScript.

1. Hello World Test Challenge
2. Get Sum Test Challenge
3. Calculator
4. Count Occurrences
5. Find Max Number
6. Title Case
7. Reverse String
8. Palindrome
9. Count Vowels
10. Remove Duplicates

02. Basic Challenges 2

These are more challenges that have to do with iteration. They are slightly harder than the first set of challenges.

1. FizzBuzz Array
2. Array Intersection
3. Display Likes
4. Find Missing Number
5. Find Missing Letter
6. Are All Characters Unique
7. First Non-Repeating Character
8. Dice Game Simulation
9. Format Phone Number
10. Validate Email

03. High Order Array Methods

The next set of challenges/lessons will have to do with high order array methods such as map, filter, reduce, sort, etc. Even though most of these can be done with a for loop, I want you to practice using these methods.

1. Simple Examples
2. Sum Of Even Squares
3. Calculate Total Sales
4. Highest Scoring Word
5. Valid Anagrams
6. HashTag Generator
7. Valid IPv4 Address
8. Analyze Car Milage
9. Password Validator
10. Find Missing Letter Refactor

04. Recursion

The next batch of challenges/lessons will have to do with recursion. We will first talk about what recursion is and then we can look at some challenges.

1. Recursion Intro (Count Down)
2. Unwinding (Sum Up To)
3. Reverse String Recursion
4. Fibonacci Sequence
5. Factorial
6. Power
7. Array Sum
8. Number Range
9. Flatten Array
10. Permutations

05. Complexity

This is more of a learning section than a challenge section. We will talk about Big O notation and how to calculate the time complexity of an algorithm. We will also talk about space complexity and how to calculate that as well. We will talk about the different types of complexity such as constant, linear, quadratic, etc.

1. What Is Time Complexity?
2. Big O Notation
3. Constant Time Complexity
4. Linear Time Complexity
5. Quadratic Time Complexity
6. Logarithmic Time Complexity
7. Space Complexity
8. Max Subarray Quadratic
9. Sliding Window Technique
10. Space Complexity

06. Hash Tables, Maps & Sets

In this section, we will start to look at data structures. We will start with a data structure called a hash table. This will include maps and sets, which are built-in JavaScript data structures that are similar to hash tables. We will also create a custom hash table class and use it in a couple challenges.

1. What Are Data Structures?
2. Hash Table Intro
3. Maps
4. Word Frequency Counter
5. Phone Number Directory
6. Anagram Grouping
7. Sets
8. Symmetric Difference
9. Two Sum
10. Longest Consecutive
11. Custom Hash Table
12. Word Instance Counter
13. Add getValues() Method
14. Add getValues() Method

07. Stacks, Queues & Linked Lists

In this section, we will look at working with data structures such as stacks, queues, and linked lists. We will also look at fast and slow pointers.

1. What Is A Stack?
2. Stack Implementation
3. Reverse String With Stack
4. Balanced Parentheses
5. What Is A Queue?
6. Queue Implementation
7. Reverse String With Queue
8. Palindrome With Queue & Stack
9. What Is A Linked List?
10. Linked List Implementation
11. Reverse String With Linked List
12. Fast & Slow Pointers
13. Find Middle
14. What Is A Doubly Linked List?
15. Doubly Linked List Implementation
16. Find Pair Sum

08. Binary Trees & Binary Search Trees & Graphs

In this section, we will look at trees and graphs. We will start with binary trees and binary search trees. We will also look at graphs and graph traversal.

1. What Is A Tree?
2. Tree Node Class
3. Depth First Traversal
4. Depth First Traversal Recursive
5. Breadth First Traversal
6. Maximum Depth
7. What Is A Binary Search Tree?
8. Binary Search Tree Implementation
9. Validate BST
10. What is a Graph?
11. Adjacency Matrix & Adjacency List
12. Graph Implementation
13. Graph Traversal
14. Graph Depth First Traversal
15. Graph Breadth First Traversal

09. Sorting Algorithms

In this section, we will get into sorting algorithms. We will start with bubble sort, which is very popular in interviews. We will also look at selection sort, insertion sort, merge sort, and quick sort.

1. What Are Sorting Algorithms?
2. Bubble Sort Algorithm
3. Bubble Sort Implementation
4. Insertion Sort Algorithm
5. Insertion Sort Implementation
6. Selection Sort Algorithm
7. Selection Sort Implementation
8. Merge Sort Algorithm
9. Merge Sort Implementation
10. Quick Sort Algorithm
11. Quick Sort Implementation

traversy-js-challenges's Issues

sumUpTo() function has not been imported in test file

In 04-recursion/02-unwinding/sum-up-to-test.js , there is no import statement for the sumUpTo() function.
Hence there is a error while testing, as sumUpTo is not defined in test file

Incomplete solution for Valid Anagrams problem

In Valid Anagrams problem. the solution is not complete.
it is checking that frequencyCount1 is matching with frequencyCount2 but we also need to test frequencyCount2 is matching with frequencyCount1. for example: if I run the test with const result = validAnagrams('app', 'ppax'); it returns true but it should be false.

Anagram function does not consider string length

The current implementation of the validAnagrams function in the repository does not consider the length of the input strings when determining if they are anagrams. For example, it expects to return false but returns true in cases like validAnagrams("abcd", "abcde")

function validAnagrams(str1, str2) {
  const freqCount1 = str1.split('').reduce((acc, char) => {
    acc[char] = (acc[char] || 0) + 1;
    return acc;
  }, {});

  const freqCount2 = str2.split('').reduce((acc, char) => {
    acc[char] = (acc[char] || 0) + 1;
    return acc;
  }, {});

  return Object.keys(freqCount1).every(
    (char) => freqCount1[char] === freqCount2[char]
  );
}

This function also needs to check the length of strings to be equal at the beginning:

 if (str1.length !== str2.length) {
        return false;
    }

Other possible solution for challenge 02/09 format phone number using regex

There is a solution possible with format phone number using regexes and replacing groups. So whatever you put inside brackets, you can then reference in the replace clause using $1 $2 and so on.

Here is the code:

const formatPhoneNumber = (numbers) => numbers
    .reduce((output, number) => output + number, '')
    .replace(/([0-9]{3})([0-9]{3})([0-9]{4})/, '($1) $2-$3')

So I am first converting the numbers array into string using reduce.
Then I am creating regex groups in the left side of replace statement:

• ([0-9]{3}) means first 3 digits will be accessible via $1
• ([0-9]{3}) means next 3 digits will be accessible via $2
• ([0-9]{3}) means last 4 digits will be accessible via $3

Then you can reference it in the right side of replace statement using ($1) $2-$3.

Test file with a wrong name.

The file 06-hash-tables-maps-sets/13-add-get-values-method/get-values.test.js should be renamed to 06-hash-tables-maps-sets/13-add-get-values-method/get-values-test.js.

So basically replace the dot with a dash. Otherwise, Jest fails the test. This might confuse people when they try to test the first problems (i.e. "Hello World) and see an error despite their solution being correct.

Incorrect test value

05-time-complexity/08-max-subarray-quadratic and 05-time-complexity/10-max-subarray-linear

For k2 = 4 the expected result should be -11 instead of -9.

Wrong test case/question in 06-title-case

https://github.com/bradtraversy/traversy-js-challenges/tree/main/01-basic-challenges-1/06-title-case

In the examples

titleCase("I'm a little tea pot"); // I'm A Little Tea Pot
titleCase('sHoRt AnD sToUt'); // Short And Stout
titleCase('HERE IS MY HANDLE HERE IS MY SPOUT'); // Here Is My Handle Here Is My Spout

It shows that we need to convert the first letter of each word to UpperCase and the rest to LowerCase.

https://github.com/bradtraversy/traversy-js-challenges/blob/main/01-basic-challenges-1/06-title-case/readme.md#solutions
In the first solution as well it is clearly converted toLowerCase

But in the second solution, only the first character is converted to upper case and rest remains the same.

So either the question and test-cases are wrong, or the examples and Solution 1 is wrong.

Test for "Find Missing Letter" has 2 missing letters instead of 1

I got an error while trying to run a test in find-missing-letter-run.js for the "Find the Missing Letter" challenge.

result = findMissingLetter(['a', 'b', 'c', 'f', 'g']);

As you can see, it's missing both the letters 'd' and 'e'. I believe you meant to only have one missing, right?

Max Subarray - O(n²): Test error

In the video, Brad runs into a bug with the code and fixes it by replacing let maxSum = 0; with let maxSum = -Infinity;

The problem is that the wrong code is still in the repo. Just need to replace it like in the video.

A small typo in 03-high-order-array-methods/04-highest-scoring-word/highest-scoring-word-run.js

I found one more small bug.

in 03-high-order-array-methods > 04-highest-scoring-word, the Constraints in the readme state that the input string will only contain lowercase letters.

However, the run file uses the string highestScoringWord('Hello my name is xavier'); with an uppercase H.

Typo in 05-complexity/07-space-complexity/readme.md

In the readme file at the bottom most section of space complexity examples , there is a typo in heading where it states "Constant Time O(1) and Linear Space O(n)" , rather it should be "Constant Space O(1) and Linear Time O(n)". As it is correctly stated in description of that same section.

Test completion suggestion for calculator (Challenge 01/03)

The test as-is didn't cover faulty operator handling, so I came up with

// calculator.test.js
// Division
...
// Error case: Invalid operator
  expect(() => calculator(num1, num2, "//")).toThrow("Invalid operator");

Adding the error throwing handling naturally requires the main file to throw an error in this case. I used the default for that:

function calculator(num1, num2, operator) {
    switch (operator) {
        case "+": return num1 + num2;
        case "-": return num1 - num2;
        case "*": return num1 * num2;
        case "/": return num1 / num2;
        default: throw new Error('Invalid operator');
    }
}

This way, anything other than the operators throws an error. You're welcome to use it, if you choose.

Error in 02-basic-challenges-2/05-find-missing-letter/find-missing-letter-run.js

In section 02-basic-chalanges-2 > 05-find-missing-letter, the run file is missing 2 letters (d and e), rather than one

const findMissingLetter = require('./find-missing-letter');

result = findMissingLetter(['a', 'b', 'c', 'f', 'g']);

console.log(result);

A simple oversight, I'm sure. Loving the challenges, BTW!

One Jest Test is named with a dot instead of a hyphen

The file 06-hash-tables-maps-sets/13-add-get-values-method/get-values.test.js should be renamed to 06-hash-tables-maps-sets/13-add-get-values-method/get-values-test.js. Otherwise, it fails when running earlier tests.

This might be confusing to some newer developers.

Getting error when trying to run --> npm test

I am getting error here (Screenshot Attached) while running the command npm test

https://prnt.sc/oWYSeZINdF4R