Skip to content

Commit e88994f

Browse files
ddaniel27ddaniel27
authored
Merge branch 'TheAlgorithms:master' into master
2 parents aa5f9db + 8c27d86 commit e88994f

31 files changed

+764
-21
lines changed

‎.github/workflows/Ci.yml

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@ jobs:
1212
runs-on: ubuntu-latest
1313
steps:
1414
- uses: actions/checkout@v3
15+
1516
- uses: actions/setup-node@v3
1617
with:
1718
node-version: 16
@@ -20,8 +21,13 @@ jobs:
2021
- name: 📦 Install dependencies
2122
run: npm ci
2223

23-
- name: 🧪 Run tests
24-
run: npm test
24+
- name: 🧪 Run all tests
25+
if: ${{ github.event_name == 'push' }}
26+
run: npm run test
27+
28+
- name: 🧪 Run tests for changed files only
29+
if: ${{ github.event_name == 'pull_request' }}
30+
run: npm run test-changed
2531

2632
- name: 💄 Code style
2733
run: npm run style

‎.gitpod.yml

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,11 @@
1+
github:
2+
prebuilds:
3+
addBadge: true
4+
addComment: false
5+
addCheck: false
6+
master: true
7+
branches: true
8+
pullRequestsFromForks: true
9+
110
tasks:
211
- init: npm install
3-

‎.husky/pre-commit

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,4 +2,4 @@
22
. "$(dirname "$0")/_/husky.sh"
33

44
npm run style
5-
npm run test
5+
npm run test-changed

‎CONTRIBUTING.md

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -63,15 +63,16 @@ should add unique value.
6363

6464
#### Module System
6565

66-
We use the [ES Module](https://hacks.mozilla.org/2018/03/es-modules-a-cartoon-deep-dive/) system, which bring an official, standardized module system to JavaScript.
66+
We use the [ES Module](https://hacks.mozilla.org/2018/03/es-modules-a-cartoon-deep-dive/) system, which bring an
67+
official, standardized module system to JavaScript.
6768

6869
It roughly means you will need to use `export` and `import` statements instead of `module.exports` and `require()`.
6970

7071
#### Testing
7172

7273
Be confident that your code works. When was the last time you committed a code change, your build failed, and half of
7374
your app stopped working? Mine was last week. Writing tests for our Algorithms will help us ensure the implementations
74-
are air tight even after multiple fixes and code changes.
75+
are airtight even after multiple fixes and code changes.
7576

7677
We use [Jest](https://jestjs.io/) to run unit tests on our algorithms. It provides a very readable and expressive way to
7778
structure your test code.
@@ -107,6 +108,12 @@ You can also start Jest in "watch" mode:
107108
npm test -- --watchAll
108109
```
109110

111+
We also prepared a helper script that runs tests only for changed files:
112+
113+
```shell
114+
npm run test-changed
115+
```
116+
110117
This will run all tests and watch source and test files for changes. When a change is made, the tests will run again.
111118

112119
#### Coding Style

‎DIRECTORY.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -89,6 +89,7 @@
8989
* [ClimbingStairs](Dynamic-Programming/ClimbingStairs.js)
9090
* [CoinChange](Dynamic-Programming/CoinChange.js)
9191
* [EditDistance](Dynamic-Programming/EditDistance.js)
92+
* [FastFibonacciNumber](Dynamic-Programming/FastFibonacciNumber.js)
9293
* [FibonacciNumber](Dynamic-Programming/FibonacciNumber.js)
9394
* [FindMonthCalendar](Dynamic-Programming/FindMonthCalendar.js)
9495
* [KadaneAlgo](Dynamic-Programming/KadaneAlgo.js)
@@ -104,6 +105,7 @@
104105
* [RodCutting](Dynamic-Programming/RodCutting.js)
105106
* [Shuf](Dynamic-Programming/Shuf.js)
106107
* [SieveOfEratosthenes](Dynamic-Programming/SieveOfEratosthenes.js)
108+
* [UniquePaths](Dynamic-Programming/UniquePaths.js)
107109
* **Sliding-Window**
108110
* [LongestSubstringWithoutRepeatingCharacters](Dynamic-Programming/Sliding-Window/LongestSubstringWithoutRepeatingCharacters.js)
109111
* [PermutationinString](Dynamic-Programming/Sliding-Window/PermutationinString.js)
@@ -240,6 +242,7 @@
240242
* [Problem020](Project-Euler/Problem020.js)
241243
* [Problem023](Project-Euler/Problem023.js)
242244
* [Problem025](Project-Euler/Problem025.js)
245+
* [Problem028](Project-Euler/Problem028.js)
243246
* [Problem044](Project-Euler/Problem044.js)
244247
* **Recursive**
245248
* [BinaryEquivalent](Recursive/BinaryEquivalent.js)
@@ -249,6 +252,7 @@
249252
* [FibonacciNumberRecursive](Recursive/FibonacciNumberRecursive.js)
250253
* [FloodFill](Recursive/FloodFill.js)
251254
* [KochSnowflake](Recursive/KochSnowflake.js)
255+
* [LetterCombination](Recursive/LetterCombination.js)
252256
* [Palindrome](Recursive/Palindrome.js)
253257
* [SubsequenceRecursive](Recursive/SubsequenceRecursive.js)
254258
* [TowerOfHanoi](Recursive/TowerOfHanoi.js)

‎Data-Structures/Array/Reverse.js

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
/** https://www.geeksforgeeks.org/write-a-program-to-Reverse-an-array-or-string/
2+
* This function will accept an array and
3+
* Reverse its elements and returns the inverted array
4+
* @param {Array} arr array with elements of any data type
5+
* @returns {Array} array with inverted elements
6+
*/
7+
8+
const Reverse = (arr) => {
9+
// limit specifies the amount of Reverse actions
10+
for (let i = 0, j = arr.length - 1; i < arr.length / 2; i++, j--) {
11+
const temp = arr[i]
12+
arr[i] = arr[j]
13+
arr[j] = temp
14+
}
15+
return arr
16+
}
17+
export { Reverse }

‎Data-Structures/Array/test/Reverse.test.js

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
import { Reverse } from '../Reverse.js'
2+
import each from 'jest-each'
3+
4+
describe('reverse elements in an array', () => {
5+
each`
6+
array | expected
7+
${[]} | ${[]}
8+
${[1]} | ${[1]}
9+
${[1, 2, 3, 4]} | ${[4, 3, 2, 1]}
10+
`.test('returns $expected when given $array', ({ array, expected }) => {
11+
expect(Reverse(array)).toEqual(expected)
12+
})
13+
})

‎Data-Structures/Tree/SegmentTree.js

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
/**
2+
* Segment Tree
3+
* concept : [Wikipedia](https://en.wikipedia.org/wiki/Segment_tree)
4+
* inspired by : https://www.geeksforgeeks.org/segment-tree-efficient-implementation/
5+
*
6+
* time complexity
7+
* - init : O(N)
8+
* - update : O(log(N))
9+
* - query : O(log(N))
10+
*
11+
* space complexity : O(N)
12+
*/
13+
class SegmentTree {
14+
size
15+
tree
16+
constructor (arr) {
17+
// we define tree like this
18+
// tree[1] : root node of tree
19+
// tree[i] : i'th node
20+
// tree[i * 2] : i'th left child
21+
// tree[i * 2 + 1] : i'th right child
22+
// and we use bit, shift operation for index
23+
this.size = arr.length
24+
this.tree = new Array(2 * arr.length)
25+
this.tree.fill(0)
26+
27+
this.build(arr)
28+
}
29+
30+
// function to build the tree
31+
build (arr) {
32+
const { size, tree } = this
33+
// insert leaf nodes in tree
34+
// leaf nodes will start from index N
35+
// in this array and will go up to index (2 * N – 1)
36+
for (let i = 0; i < size; i++) {
37+
tree[size + i] = arr[i]
38+
}
39+
40+
// build the tree by calculating parents
41+
// tree's root node will contain all leaf node's sum
42+
for (let i = size - 1; i > 0; --i) {
43+
// current node's value is the sum of left child, right child
44+
tree[i] = tree[i * 2] + tree[i * 2 + 1]
45+
}
46+
}
47+
48+
update (index, value) {
49+
const { size, tree } = this
50+
51+
// only update values in the parents of the given node being changed.
52+
// to get the parent move to parent node (index / 2)
53+
54+
// set value at position index
55+
index += size
56+
// tree[index] is leaf node and index's value of array
57+
tree[index] = value
58+
59+
// move upward and update parents
60+
for (let i = index; i > 1; i >>= 1) {
61+
// i ^ 1 turns (2 * i) to (2 * i + 1)
62+
// i ^ 1 is second child
63+
tree[i >> 1] = tree[i] + tree[i ^ 1]
64+
}
65+
}
66+
67+
// interval [L,R) with left index(L) included and right (R) excluded.
68+
query (left, right) {
69+
const { size, tree } = this
70+
// cause R is excluded, increase right for convenient
71+
right++
72+
let res = 0
73+
74+
// loop to find the sum in the range
75+
for (left += size, right += size; left < right; left >>= 1, right >>= 1) {
76+
// L is the left border of an query interval
77+
78+
// if L is odd it means that it is the right child of its parent and our interval includes only L and not the parent.
79+
// So we will simply include this node to sum and move to the parent of its next node by doing L = (L + 1) / 2.
80+
81+
// if L is even it is the left child of its parent
82+
// and the interval includes its parent also unless the right borders interfere.
83+
if ((left & 1) > 0) {
84+
res += tree[left++]
85+
}
86+
87+
// same in R (the right border of an query interval)
88+
if ((right & 1) > 0) {
89+
res += tree[--right]
90+
}
91+
}
92+
93+
return res
94+
}
95+
}
96+
97+
export { SegmentTree }

‎Data-Structures/Tree/test/SegmentTree.test.js

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
import { SegmentTree } from '../SegmentTree'
2+
3+
describe('SegmentTree sum test', () => {
4+
const a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
5+
6+
const segment = new SegmentTree(a)
7+
8+
it('init sum check', () => {
9+
expect(segment.query(0, 2)).toBe(6)
10+
})
11+
12+
it('init sum check', () => {
13+
segment.update(2, 1)
14+
expect(segment.query(0, 2)).toBe(4)
15+
})
16+
})

‎Dynamic-Programming/UniquePaths.js

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
2+
/*
3+
*
4+
* Unique Paths
5+
*
6+
* There is a robot on an `m x n` grid.
7+
* The robot is initially located at the top-left corner.
8+
* The robot tries to move to the bottom-right corner.
9+
* The robot can only move either down or right at any point in time.
10+
*
11+
* Given the two integers `m` and `n`,
12+
* return the number of possible unique paths that the robot can take to reach the bottom-right corner.
13+
* More info: https://leetcode.com/problems/unique-paths/
14+
*/
15+
16+
/*
17+
* @param {number} m
18+
* @param {number} n
19+
* @return {number}
20+
*/
21+
22+
const uniquePaths = (m, n) => {
23+
// only one way to reach end
24+
if (m === 1 || n === 1) return 1
25+
26+
// build a linear grid of size m
27+
// base case, position 1 has only 1 move
28+
const paths = new Array(m).fill(1)
29+
30+
for (let i = 1; i < n; i++) {
31+
for (let j = 1; j < m; j++) {
32+
// paths[j] in RHS represents the cell value stored above the current cell
33+
// paths[j-1] in RHS represents the cell value stored to the left of the current cell
34+
// paths [j] on the LHS represents the number of distinct pathways to the cell (i,j)
35+
paths[j] = paths[j - 1] + paths[j]
36+
}
37+
}
38+
return paths[m - 1]
39+
}
40+
41+
export { uniquePaths }

0 commit comments

Comments
 (0)