TechLead video here.
More about understanding the functional techniques.
1. DFS: The fundamental graph/tree traversal algorithm. Simple. Fundamental. Very popular to be asked.
2. BFS: The difference between DFS and BFS is the order. DFS uses a stack and BFS uses a queue.
3. Matching Parenthesis (Or Bracket) problem: Usually solve by using a stack.
4. Using Hash Tables: Make use of Hash Table to prevent revisiting values you have already visited and computed/calculated. Memoization or caching technique that is popular in dynamic programming. Example is the nth number in a Fibonacci sequence and you optimize this by keeping track of values you have already computed..
5. Variables/Pointers manipulation: Not an Algorithm itself but so common in working with algorithms. Example of manipulating multiple pointers is to find the longest palindromic substring in a string, (palindrome is the same letters front and backwards). Using things like “next” and “head” and “tail” for Linked Lists as well “prev” for Doubly Linked Lists as well as variables like “temp.”
6. Reverse Linked List (duplicates , removing duplicates): Very contrived algorithm. Contrived meaning deliberately created rather than arising naturally or spontaneously. Created or arranged in a way that seems artificial and unrealistic. Surprisingly important and can be sort of hidden in problems. Quite tricky to implement. When you use a link list you have to use three different pointers, (before, after, etc.).
7. Sorting Fundamentals (quick sort, merge sort, bubble sort techniques , runtime of a sort, time space complexity). Don’t necessarily need to know specifically how they work, (actually never advocates memorizing how these algorithms work). But need to understand the concepts behind them and why and when one is better than an another. Important to know how this O(n log n) affects your overall algorithms. For example, if your overall algorithm runs in n^2, and you implement a sort in O(n log n) then that’s fine. But if your overall algorithm is running on O(n) time, then your sorting algorithm just made that worse.
8. Recursion: Topic every engineer either hates or loves. Hate because you rarely see it in production code. But it is still used and tested a lot in interviews. Good indication of overall problem-solving skills although this is debatable. Practice makes perfect, (algoexpert.io).
9. Custom Data Structures (Object Oriented Programming): Not so much an algorithm again. Suffix-tree-like data structure. Example is wanting to capture a bunch of strings in a data structure all with S, then all with ST, then all with STR. There is also a gumball machine question randomly give you a pill and inside the pill is something with a certain color. USE OOP to construct an object with a class that helps you solve a problem well.
10. Binary Search: Really fundamental. Do not want to be the person that enters an interview that is asked a question related related to binary search and you don’t know how to implement. Often use in real life. Find the middle and eliminate half. In interviews you don’t get “implement binary search” but you get a question with “binary search” hidden inside, (Find the crash version of an app, or you have a bunch of commits and find the commit that has a bug in it). What is the time/space complexity of binary search? What is the time/space complexity of binary search? Space Complexity is skipped over but is O(n) and Time Complexity is O(log n).
The man. Video here that goes beyond 100 seconds. Also has a Big O in 100 Seconds here and Recursion in 100 seconds here.
He talks about using a Map versus an object (in the adjacency list section) when working with algorithms because you get a few extra API methods that be helpful in solving problems asked in interview questions.
// The graph
const adjacencyList = new Map()
// Add node
function addNode(airport) {
adjacencyList.set(airport, [])
}
// Add edge, indirected
function addEdge(origin, destination) {
adjacencyList.get(origin).push(destination)
adjacencyList.get(destination).push(origin)
}
// Create the Graph
airports.forEach(addNode)
routes.forEach(route => addEdge(...route))
console.log(adjacencyList)
// output expected
Each AP listed as a kye and the value is an array of strings that represent each AP they fly toNow we need to implement an algorithm to see if there is a route from Phoenix to Bangkok, (Graph Search or Traversal). DFS or BFS? BFS probably easier to understand.
// BFS
function BFS(start) {
const queue = [start] // a queue is just an array with FIFO
while(queue.length > 0) {
const airport = queue.shift() // mutates the queue
const destinations = adjancencyList.get(airport)
for(const destination of destinations) {
queue.push(destination)
if(destination === 'BKK') {
console.log("Found it")
}
}
}
} // end BFSNote: A major problem with the code above is that airports have many interconnected routes and that means our algorithm with be visiting the same nodes over and over again and that creates and infinite loop. So to avoid this we need to keep track of the airports that have been visited in the past and we can do that by implementing a Set, (a value in a Set may only occur once).
// BFS
function bfs(start) {
const visited = new Set()
const queue = [start] // a queue is just an array with FIFO
while(queue.length > 0) {
const airport = queue.shift() // mutates the queue
const destinations = adjancencyList.get(airport)
for(const destination of destinations) {
if(destination === 'BKK') {
console.log("Found it")
}
if(!visited.has(destination)) {
visited.add(destination)
queue.push(destination)
}
} // end for loop
} //end while loop
} // end BFS
// Call function with PHX as the starting node
bfs('PHX')At this point BFS would be really good for finding all possible routes to determine which one is the most efficient. But let’s say you are only interested if the route exists at all. How can you traverse the graph more efficiently? Enter DFS
function dfs(start, visited = new Set()) {
console.log(start)
visited.add(start)
const destinations = adjacencyList.get(start)
for (const destination of destinations) {
if (destination === "BKK") {
console.log('DFS found Bangkok in ${steps} steps')
return
}
if (!visited.has(destination)) {
dfs(destination, visited)
}
}
} // end DFS
dfs('PHX')What is the time complexity of this algorithm? O(V+E) representing nodes plus edges which equals O(n).
The code below is the non-recursive example of a Fibonacci
function fibonacci(targetIndex) {
const sequence = [0n, 1n]
for (let i = 2; i < targetIndex + 1; i++) {
const next = sequence[i-2] + sequence[i - 1]
sequence.push(next)
}
return sequence[targetIndex]
}And the Recursive solution is
function fibonacci(targetIndex) {
if(targetIndex < 1) return 1 // base case
return fibonacci(targetIndex - 1) + fibonacci(targetIndex - 2)
}But this will traverse down the entire sequence for every single index and this is O(n^2) time complexity which is not good at all. This should be improved with memoization and that video is here.
One video for Algorithms and one for Data Structures. He goes over some built-in data structures like Map and Sets as well.
Video here.
Heap’s Algorithm
Watched this video here.
Gives you all the permutations (possible ways you could order) any given collection of elements. Mathematical formula given number of n elements. Factorials, (4!). This algorithm is hard and unintuitive. This is an algorithm you study, not come up with on your own. Need to be comfortable with recursion. Pure functions discussed.
Found the code below from this site here.
Pseudo Code
generate (n, arr)
if n = 1
output arr
else
for i = 0; i < n; i += 1
generate (n - 1, arr)
if n is even
swap(arr[i], arr[n - 1])
else
swap(arr[0], arr[n - 1])Implementation
// Purpose is to create every permutation from the elements in the array
// We can do this by using Heap's algorithm
var start = [1, 2, 3];
// Get the permutations
generate(start.length, start);
// Generate the permutation for a given n (amount of elements) and a given array
function generate(n, arr) {
// If only 1 element, just output the array
if (n == 1) {
console.log(arr);
return;
}
for (var i = 0; i < n; i+= 1) {
generate(n - 1, arr);
// If n is even
if (n % 2 == 0) {
swap(arr, i, n - 1);
} else {
swap(arr, 0, n - 1);
}
}
}
function swap(arr, idxA, idxB) {
var tmp = arr[idxA];
arr[idxA] = arr[idxB];
arr[idxB] = tmp;
}Output
[2, 3, 1]
[3, 2, 1]
[1, 2, 3]
[2, 1, 3]
[3, 1, 2]
[1, 3, 2]
[2, 3, 1]
[3, 2, 1]