leah

Bitwise Operation

num[index] * 2^(index-1)

AND

both
& : return 1 if both has 1 (same)

1. change num into bitwise
2. &

   5 & 9
   5 –> 0101(2)
   9 –> 1001(2)
   0101

   &1001

   0001(2) –> 1

OR

at least
| : return 1 if at least one has 1

1. change num into bitwise
2. |

   5 | 9
   5 –> 0101(2)
   9 –> 1001(2)
   0101

   1001
   1101(2) –> 13

XOR

just one
^ : return 1 if the value is different, return 0 if same

1. change num into bitwise
2. ^

   5 ^ 9
   5 –> 0101(2)
   9 –> 1001(2)
   0101

   ^1001

   1100(2) –> 12

NOT

~ : return the oppostie value

actually, there are 0 as many as the size of the integer range(<=256, thus 8개) in front of the bits

• -(x) -1 (// in JS)
• negative
  • starts from -1
  • meaning of 0, 1 is swtiched: 0 -> decrement

    ~5
    5 –> 0101(2)

    ~0101(2)

    1010(2) –> -6 (in JS, normally -5) // 1011(2) –> -5 in JS

Left Shift

<< n : shift bits to the left to the n extent and fill the right bit with 0

5 << 1
0101(2)
—– << 1
1010(2)

Sign-propagating Right Shift

>> n : shift bits to the right to the n extent and fill the left bit with the same one as the original last right value which is sign property

8 >>> 1
0…1000(2)
———– >> 1
00…0100(2) // 4
-8 >>> 1
1…1000(2)
———– >> 1
11…1100(2) // -4

Zero-fill Right Shift

>>> n : shift bits to the right to the n extent and fill the left bit with 0

[1]1…0111 // -8
——— >>> 1
[0]1…1011 // 2147483644

blog.logrocket.com/interesting-use-cases-for-javascript-bitwise-operators/
Interesting use cases for JavaScript bitwise operators - LogRocket Blog
Although we don’t often see bitwise operators used in JavaScript, they have some cool use cases. Learn their theory and implementation.
blog.logrocket.com

compare multiple values together

first comparison -> compare with the next one -> (((repeat)))

Algorithm

qiao.github.io/PathFinding.js/visual/
PathFinding.js
qiao.github.io

Dijkstra

• only need the weight
• evaluate all the nodes -> slower

1. set the weight of starting point to 0, and others to INF (as not started yet)

A*

• only evaluate shorter distance ->faster
• need weight and distance both

1. set additional array with distance

BFS

Breadth First Search

• Queue
  : go same level node first and go deeper

• push root node
• pop root node
  • push children nodes From Left to Right
• pop child node one by one and…
  • push children nodes from child (((repeat)))

1
2
3
4
5
6
7
8

queue.enqueue(this);
while (queue.length > 0) {
    current = queue.dequeue();
    children = current.children;
    for (let i=0; i<children.length; i++) {
    	queue.enqueue(children[i]);
    }
}

DFS

Depth First Search

• Stack
  : go down to the leaf node first and move on to the other children

• push root node
• pop root node
  • push children nodes From Left To Right
• pop child node and…
  • push children nodes of child (((repeat)))
• pop the leaf node
  • pop other leaf nodes on the same level / push children nodes of the node on the same level
• pop parent node and move on (((repeat)))

1
2
3
4
5
6
7
8

stack.push(this);
while (stack.length > 0) {
  current = stack.pop();
  children = current.children;
  for (let i=0; i<children.length; i++) {
    stack.push(children[i]);
  }
}

Algorithms

• like a recipe
• concrete steps to solve the problem
• language independent (logic itself)

Complexity Analysis

• Objective Criteria

• time, space
• best, average, worst (always think in worst case!)
• Big O

Be aware of the Complexity

Recognise patterns

Think if you can bring it down

Big O

DROP the constant in front of the N

1. Constant - O(k) (k: constant number)
   : stays the same independently of the size of the problem
2. Linear - O(n) (n: number of items)
   : grows proportional to the size of the problem
   e.g. for loop, linked list- find the item
3. Logarithmic - O(logn)

• random array => cut half => repeat until find the element (Binary Search)
• sorted => increase by one

  1 2 3 4 5 6 7

  let count = 0; let limit = 100; for (let i=0; i<limit; i++) { limit /= 2; count++; }

4. Quadratic - O(n^2)
   : nested for loop
5. N log n - O (nlogn)

   1 2 3 4 5 6 7 8 9

   let count = 0; let limit = 100; for (let i=0; i<limit; i++) { limit /= 2; for (let j=0; j<limit; j++) { count++; } }

   e.g. mergeSort

BAD Time Complexity

6. Exponential - O(2^n)
7. Factorial - O(n!)
   e.g. Queen Problem

Hash Table: O(1) average and amortized case complexity, however it suffers from O(n) worst case time complexity.

• Worst Case

1. If too many elements were hashed into the same key: looking inside this key may take O(n) time.
2. Once a hash table has passed its load balance - it has to rehash [create a new bigger table, and re-insert each element to the table].

• average and amortized case

1. It is very rare that many items will be hashed to the same key [if you chose a good hash function and you don’t have too big load balance.
2. The rehash operation, which is O(n), can at most happen after n/2 ops, which are all assumed O(1): Thus when you sum the average time per op, you get : (n*O(1) + O(n)) / n) = O(1)

REF

www.bigocheatsheet.com/

Data Structure

• The way to organize the data

Stack

push : put at the top
pop : remove from the top

• LIFO (Last In First Out)
• Call Stack (e.g. factorial function)
  • always interact with the top element

Queue

enqueue : put at the back
dequeue : remove from the first

• FIFO (First In First Out)

Linked-List

head
tail
next

• Node and Pointer
  • just store two nodes as a pointer (head/ tail)
• No need to initialise
• No need to relocate (linking)
• No need of indices (head / tail linking)
  • change the point of next when add the element

    Block Chain
    Delegation Chain

What If we want to go back?

Double-Linked-List

• first : H -> null, T -> null
• add the node : H, T -> node
• add one more : H -> new node, T -> old node, new -> old node

LL: {head: Node7, tail: Node29}
Node7: {val: 7, next: Node34}
Node34: {val: 34, next: Node29}
Node29: {val: 29, next: null}

Set

Tree

• Can’t Have a LOOP
• subTree
  • Root
  • Children / Parent
  • Siblings
  • Cousins
  • Descendent
• Leaf Node: bottom node without any children (null)

Implementations

Array

Object

Hash Table/ Hash Map

• Object in JS: Hash Table/ Map
• same input -> same output
• elements are evenly distributed along the range using hash function
  • hash function: MAX === size of the array
  • multiple values in the same key: contains() -> return true;
    Array : used to keep objecs as elements
    => arr = [obj1, obj2, …]
    Linked-List : used to link the elements that object has
    => obj1 = {[key, value] -> [key, value], …}
    e.g. Person = [name: ‘Lisa’] -> [age: 28] -> …

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
예를 들어 우리가 (Key, Value)가 (“John Smith”, “521-1234”)인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자. 그러면 먼저 index = hash_function(“John Smith”) % 16 연산을 통해 index 값을 계산한다. 그리고 array[index] = “521-1234” 로 전화번호를 저장하게 된다.

REF
mangkyu.tistory.com/102

Tree Family

Heap

• type of Tree
• parent has higher priority than children (root: most important)
• highest property is retrieved first

Binary Heap

Add : the leaf node, check the priority through the entire tree by going up
Delete : the root node, put the last leaf node in the root and check the priority by going down the entire tree layer by layer

• Max Heap
• Min Heap
• fully filled layer by layer, with at most 2 leaf nodes

REF
www.cs.usfca.edu/~galles/visualization/Heap.html

Binary Search Tree (BST)

• divide the tree into two parts
  • Left: smaller than the root node
  • Right: bigger than the root node
• UNBALANCED TREE: if adds onlly bigger/ smaller elements, the height of the tree will be longer, thus unbalanced

REF
www.cs.usfca.edu/~galles/visualization/BST.html

B-Tree

• evolution of the binary search tree
• can have more than 2 children
• can have more than 1 key in 1 node

  one key -> 2 children
  two keys -> 3 children
  three keys -> divide into 2 keys with promotting the mid-value to the parent node

• maintain a balance (complement the cons of a BST)
• can have duplicated keys

REF
www.cs.usfca.edu/~galles/visualization/BTree.html

Graph

path
adjacency

• connection between edges with weights (e.g. facebook familiarity)
• pair of sets (Vertices: V, Edges: E)

Testing

not in the production, just for element checking before a deployment

Automated Tests
반복되는 test 작업을 줄임

1. Unit
   receives a single case input, return certain type of output
   wouldn’t pass unless the entire process works out
   e.g. validation email & password -> similar word -> set the function as a unit with diff. input

2. Integration
   multiple single inputs -> integrates into a single output
   e.g. email / pw -> basic email : password

3. E2E
   end-to-end
   user-perspective, operation on the browser, entire process without manually fixing it
   hard to point where the error comes out

TDD

Test Driven Development
fail-fix-refactor

• one test at a time

BDD

Bahaviour Driven Development
E2E

• testing single unit, element to test entirely
• implemented in non-technical env. -> no coding

diff: technical or not

Testing Frameworks: the function to run the tests (in JS - Mocha, Jasmine(React), Jest)

# : e.g. #func() : recall all the elements including func()

• describe()
• it()
• Hooks; rather than list singly, wrap it for organizing
  • start a server, create DB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

describe('hooks', function() {
  before(function() {
    // runs once before the first test in this block
  });

  after(function() {
    // runs once after the last test in this block
  });

  beforeEach(function() {
    // runs before each test in this block
  });

  afterEach(function() {
    // runs after each test in this block
  });

  // test cases
});

inside each hooks: it()

Assertion

1. assert -> technical, not readable

   • built-in in Node.js
   • typeOf(var, typeof, [msg])
   • equal(var, val, [msg])
   • lengthOf(var, length, [msg])

2. expect
   e.g. expect(foo).to.not.equal('bar')

3. should
   e.g. foo.should.not.equal('bar')

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

function add (a, b) {
	if (typeof a === 'number' && b === undefined) return a;
    if (typeof a !== 'number' || typeof b !== 'number') return undefined;
	// return 8;
    return a + b;
}

// write the test first
var should = require('chai').should();

describe('Add', function () {
	it('should sum two numbers', function () {
    	add(3, 5).should.equal(8);
        // add another ex to fail add(a,b) {return 8;} function
        add(2, 7).should.equal(9);
    });
    
    it('should return undefined when is not passed numbers', function () {
    	should.equal(add('hello', 'world'), undefined);
        // add('').should.equal이 아닌 이유:
        // undefined을 반환하면 undefined.should.equal()이 되고,
        // 이는 error(cannot read the property)를 반환 (undefined의 function 정의 불가)
        // 따라서 should.equal(add(''))의 결과와 undefined를 matching
        
        should.equal(add(1, 'world'), undefined);
        should.equal(add('hello', 1), undefined);
    });
    
    it('should return the number if only one is passed', function () {
    	should.equal(add(8), 8);
        // add(8).should.equal(8);
    });
});

REF

kent c.dodds web
mochajs.com

a function that adds from two invocations.
e.g. twoAdds(3)(4) -> 7

1
2
3
4
5
6
7

function twoAdds (num) {
	return function (num2) {
		return num+num2;
	};
}
// twoAdds(num1)(num2)
// twoAdds(num1) // return value as a function -> value(num2)

currying is the technique of converting a function that takes multiple arguments into a sequence of functions that each take a single argument.

Closure vs Currying

• Closure: allows a function to access variables in a parent scope without passing them in.
• Currying: the pattern of functions that immediately evaluate and return other functions.

REF

www.youtube.com/watch?v=hRJrp17WnOE&feature=youtu.be

Git workflow

-fork
-clone
-commit (status, diff, add)
-push
(-sync with upstream)
-pull requests

cd //project root folder//
git clone //project url//
cd //project folder//
npm install: get the all dependencies, environment needed for the repository
-> needed for npm test: debugging
git checkout – ./: A checkout is an operation that moves the HEAD ref pointer to a specified commit.
git status: check changes
ls -a: local machine 외에 변경 사항이 확인되는지
// lists all files including hidden files starting with ‘. ‘
💥 git add . => git status 시 여전히 modified file이 존재할 수 있음: 다른 폴더에 변경된 파일이 있을 때
-> git status로 항상 check하기!!
git commit -m “first commit”
gs: == git status, branch HEAD 확인할 것!
git log: commit log 확인
git remote -v: branch 확인
git push: push everything to the repo, up-to-date
💥 synchronization
git remote -v
git remote add upstream //original repo url – forked one//
git pull upstream master: upstream -> master branch로 if any change exists, pull

Q. override => version conflict =>
pull request로 merge 전 conflict 방지
Q. pull request, sync with upstream의 목적 =>

1. sync with upstream: orinigal repo의 changes 확인
2. pull request: 💥 MERGE와 구분! feedback, review의 목적
   => when git history gets merged, adds commit on the top and merge
   => pull request before merge minimizes unuseful conflicts -> check others’ codes
   ★ Merge: add changes of ver2. to ver1.

git commit //file1// //file2// : individually commit 가능

REF

velog.io/@zansol/Pull-Request-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0