Chapter 1
Binary search
divide array into sub parts until target is found
function binarySearch(nums, target) {
let low = 0
let high = nums.length-1
while(low <= high) {
let mid = Math.floor( (low+high) / 2)
if(nums[mid] === target) return mid
else if(nums[mid] > target){
high = mid - 1;
} else {
low = mid + 1
}
}
return -1
}
Big O notation
how quickly it grows relative to the input, as the input gets arbitrarily large
Binary search O(logn)
linear search O(logn)
quick sort O(nlogn)
selection sort O(n2)
Chapter 2
Arrays and linked lists
Arrays:
-
list of elements,
-
contiguous memory,
-
can access via random index
-
postion of element called index,
-
index start with 0.
Linked lists:
-
list of elements,
-
non-contiguous memory,
-
can't access via random index
-
it store node data & address of next node
Selection sort
function selectionSort(array) {
for(let i =0 ;i <array.length-1;i++) {
let midIndex = i
for(let j = i+1; j < array.length; j++) {
if(array[j] < array[midIndex] ) {
midIndex = j
}
}
let temp = array[i]
array[i] = array[midIndex]
array[j] = temp
}
return array
}
Chapter 3
Recursion
function call its self until base condtion met
function counter(i) {
console.log(i)
if(i >= 10) return // Recursion condtion base condition
counter(i+1)
}
Stack & callstack
Stack
stack is data structure First in Last out
the computer uses that structure internally called callstack
example
function greet1(name) {
print("Hello " + name)
greet2(name)
bye()
}
greet1("raj")
greet2 into a stack and poped greet1 into a stack
bye() into stack and poped greet1 push into stack
last greet1 is poped
Chapter 4
Divide & conquer
divide problem into subproblem, conquer small problem
merging them to find solution to original problem
Quicksort implementation
function quicksort(array) {
if(array.length < 2) return array
let mid = array[0]
let eq = array.filter((a) => a == mid)
let less = array.filter((a) => a < mid)
let gt = array.filter((a) => a > mid)
return quicksort(less).concat(eq).concat(quicksort(gt))
}
Chapter 5
Hash table
its key-value DS, helps fast look up
Hash fuction
based on input string, create unique value (number) for that specific input
Collisions
Hash fuction create same kesy for different input e.g apple its create 7 and for avocado also 7
when I want to retriev apple its fetched avocado.
Good hash function: A good hash function distributes values in the array evenly
Chapter 6
Graph
a Graph models a set of connection
grpah made of node & edge
there are many types of graph directed, undirected, weighted graph so on
BFS
Graph traversal algorithm,
its begin with node, once all adjacent are visisted,
then their adjacent are traversed.
BFS implementation
function bfs(graph) {
let queue = []
queue.push(...graph["you"])
while(queue.length) {
let node = queue.shift()
if(isVisited(node)) { //
console.log(`${node} `)
return true
} else {
queue.push(...graph[node]) //
}
}
retturn false
}
Chapter 7
Dijkstra’s Algorithm
is algorithms for finding shortest paths between weighted grpah.
Implementation
let node = findLowestNode(costs)
while(node !=null) {
let cost = costs[node]
let neighbours = graph[node]
for(let n of neighbours ) {
let newCost = cost + neighbors[n]
if(consts[n] >newCost) {
costs[n] = newCost;
parents[n] = node;
}
}
processed.push(node);
node = findLowestCostNode(costs);
}
Chapter 8
Greedy Algorithms
always makes the choice that best at that moment.
The knapsack problem
e.g
function minimumWaitingTime(queries) {
queries.sort((a,b) => a-b)
let sum = 0
for (let i = 0; i < queries.length; i++) {
sum += queries[i] * (queries.length - (i+1))
}
return sum;
}
console.log(minimumWaitingTime([3, 2, 1, 2, 6]))