Last active
August 17, 2020 19:42
-
-
Save Walkeryr/ea4077023f18c7176a86f741c2025377 to your computer and use it in GitHub Desktop.
Exercises from the "Grokking Algorithms" book
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function binarySearch(list: number[], item: number) { | |
| let low = 0 | |
| let high = list.length - 1 | |
| while (low <= high) { | |
| let mid = Math.floor((low + high) / 2) | |
| let guess = list[mid] | |
| if (guess === item) { | |
| return mid | |
| } | |
| if (guess > item) { | |
| high = mid - 1 | |
| } else { | |
| low = mid + 1 | |
| } | |
| } | |
| return null | |
| } | |
| const myList = [1, 3, 5, 7, 9] | |
| console.log(binarySearch(myList, 3)) | |
| console.log(binarySearch(myList, -1)) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function findSmallest(arr: number[]): number { | |
| let smallest = arr[0] | |
| let smallestIndex = 0 | |
| for (let i = 1; i < arr.length; i++) { | |
| if (arr[i] < smallest) { | |
| smallest = arr[i] | |
| smallestIndex = i | |
| } | |
| } | |
| return smallestIndex | |
| } | |
| function selectionSort(arr: number[]): number[] { | |
| let newArr: number[] = [] | |
| const elementCount = arr.length | |
| for (let i = 0; i < elementCount; i++) { | |
| let smallest = findSmallest(arr) | |
| newArr.push(arr[smallest]) | |
| arr.splice(smallest, 1) | |
| } | |
| return newArr | |
| } | |
| console.log(selectionSort([5, 3, 6, 2, 10])) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function binarySearch(list: number[], item: number): number|null { | |
| if (list.length === 0) { | |
| return null | |
| } | |
| let low = 0 | |
| let high = list.length - 1 | |
| let mid = Math.floor((low + high) / 2) | |
| let guess = list[mid] | |
| if (guess === item) { | |
| return mid | |
| } | |
| if (guess > item) { | |
| return binarySearch(list.slice(0, mid), item) | |
| } else { | |
| const result = binarySearch(list.slice(mid + 1), item) | |
| return result !== null ? (mid + 1) + result : null | |
| } | |
| } | |
| const myList = [1, 3, 5, 7, 9] | |
| console.log(binarySearch(myList, 3)) | |
| // console.log(binarySearch(myList, -1)) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function listCount(arr: any[]):number { | |
| if (arr.length === 0) { | |
| return 0 | |
| } | |
| return 1 + listCount(arr.slice(1)) | |
| } | |
| console.log(listCount([1, 2, 3, 4])) | |
| console.log(listCount([2, 4, 6])) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function findMax(arr: number[]):number { | |
| if (arr.length === 0) { | |
| return 0 | |
| } | |
| const leftItem = arr[0] | |
| const rightItem = findMax(arr.slice(1)) | |
| return leftItem > rightItem ? leftItem : rightItem | |
| } | |
| console.log(findMax([1, 2, 3, 4])) | |
| console.log(findMax([2, 4, 6])) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function quicksort(arr: number[]): number[] { | |
| if (arr.length < 2) { | |
| return arr | |
| } else { | |
| const pivot = arr[0] | |
| const less = arr.slice(1).filter(item => item <= pivot) | |
| const greater = arr.slice(1).filter(item => item > pivot) | |
| return [...quicksort(less), pivot, ...quicksort(greater)] | |
| } | |
| } | |
| console.log(quicksort([10, 5, 2, 3])) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function sum(arr: number[]):number { | |
| if (arr.length === 0) { | |
| return 0 | |
| } | |
| return arr[0] + sum(arr.slice(1)) | |
| } | |
| console.log(sum([1, 2, 3, 4])) | |
| console.log(sum([2, 4, 6])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment