By Fedrianto Ramadhan in learning — Apr 8, 2022

Master the Coding Interview: Data Structures + Algorithms

Getting more Interviews

Resume

Use this online resume maker https://www.resumemaker.online/

Keypoint on having a nice resume - Should be One page, Relevant Skills (spesific job - spesific skills), Personalized ( dont use the same resume for every, customize the name ) , Online Link (github, website, portfolio)

Portfolio

Email

BIG O'S

Online IDE
https://replit.com/
https://glot.io/
Other Student work
https://github.com/punitpandey/DS-Algo GOlang
Mindmapping
https://coggle.it/
What is a good code = 1. Readable 2. Scalable

Cheatsheet Big O

O(1) Constant - no loops
O(log N) Logarithmic - usually searching algorithms have log n if they are sorted (Binary Search)
O(n) Linear - for loops, while loops through n items
O(n log(n)) Log Linear - usually sorting operations
O(n^2) Quadratic - every element in a collection needs to be compared to ever other element. Two nested loops
O(2^n) Exponential - recursive algorithms that solves a problem of size N
O(n!) Factorial - you are adding a loop for every element

Iterating through half a collection is still O(n)
Two separate collections: O(a * b)

WHAT CAN CAUSE TIME IN A FUNCTION?

Operations (+,-, \*, /)
Comparisons (<, >, ===)
Looping (for, while)
Outside Function call (function())

WHAT CAUSES SPACE COMPLEXITY?

Variables
Data Structures
Function Call
Allocations

O(n) - linear time

O(n) -> linear time
depends on number of input -> n

// Finding how long it takes to run in milliseconds

const {performance} = require('perf_hooks');
const nemo = ['nemo'];
const everyone = ['dory', 'bruce', 'marlin', 'nemo', 'gill', 'bloat', 'nigel', 'squirt', 'darla','hank'];
const large = new Array(1000).fill('nemo'); // will create 1000 nemo in array

function findNemo(array) {
  let t0 = performance.now();
  for (let i = 0; i < array.length; i++) {
   if (array[i] === 'nemo')  {
     console.log('Found NEMO!');
   }
  }
  let t1 = performance.now();
  console.log('Call to find Nemo took ' + (t1-t0) + ' milliseconds');
}

findNemo(large); // 0(n) --> Linear Time

O(1) - constant time

no matter how many time the boxes increase, we're always just grabbing the first item in array

const boxes = [0,1,2,3,4,5];
function logFirstTwoBoxes(boxes) {
  console.log(boxes[0]); // O(1)
  console.log(boxes[1]); // O(1)
}

logFirstTwoBoxes(boxes); // O(2)

Exercise 1

// What is the Big O of the below function? (Hint, you may want to go line by line)
function funChallenge(input) {
  let a = 10; // O(1)
  a = 50 + 3; // O(1)

  for (let i = 0; i < input.length; i++) { // O(n)
    anotherFunction(); // O(n)
    let stranger = true; // O(n)
    a++; O(n)
  }
  return a; // O(1)
}

BIG O(3 + 4n) simplify to O(n)

Exercise 2

// What is the Big O of the below function? (Hint, you may want to go line by line)
function anotherFunChallenge(input) {
  let a = 5; O(1)
  let b = 10; O(1)
  let c = 50; O(1)
  for (let i = 0; i < input; i++) { O(n)
    let x = i + 1; O(n)
    let y = i + 2; O(n)
    let z = i + 3; O(n)
  }
  for (let j = 0; j < input; j++) { O(n)
    let p = j * 2; O(n)
    let q = j * 2; O(n)
  }
  let whoAmI = "I don't know"; O(1)
}

O(4 + 7n)

RULE BOOK

Rule 1: Always worst Case

The worst case is that the input, instead of being the fourth item is at the very end. So even if we have this brake statement, we're still going to run this 10 times because we're still going to have to go through 10th item.

Rule 2: Remove Constants

function printFirstItemThenFirstHalfThenSayHi100Times(items) {
    console.log(items[0]); // O(1)

    var middleIndex = Math.floor(items.length / 2);
    var index = 0;

    while (index < middleIndex) {
        console.log(items[index]);
        index++;
    }

    for (var i = 0; i < 100; i++) {
        console.log('hi');
    }
}

// O(1 + n/2 + 100)
// removing 1 and /2
// O(n + 1)
// O(n)

Rule 3:

function compressBoxesTwice(boxes, boxes2) {
  boxes.forEach(function(boxes)) {
    console.log(boxes);
  }

  boxes2.forEach(function(boxes2)) {
    console.log(boxes2);
  }
}

//O(a + b)

Different inputs should have different variables: O(a + b).
A and B arrays nested would be: O(a * b)

+ for steps in order

* for nested steps

const boxes = ['a','b','c','d','e'];
function logAllPairsOfArray(array) {
  for(let i = 0; i< array.length; i++) {
    for(let j = 0; j < array.length; j++) {
      console.log(array[i], array[j])
    }
  }
}

logAllPairsOfArray(boxes);

//O(n^2)

Rule 4: Drop Non-dominant terms

function printAllNumbersThenAllPairSums(numbers) {

  console.log('these are the numbers:');
  numbers.forEach(function(number) {
    console.log(number);
  });

  console.log('and these are their sums:');
  numbers.forEach(function(firstNumber) {
    numbers.forEach(function(secondNumber) {
      console.log(firstNumber + secondNumber);
    });
  });
}

printAllNumbersThenAllPairSums([1,2,3,4,5])

// O( n + n^2) // remove n because n^2 is more important
// O( n^2)

How would you simplify this ?
O( x^2 + 3x + 100 + x/2 )
example if x = 5
x^2 = 25 3x = 15 100 x/2 = 2.5 -> 100 is relevant
but when x = 500 is not relevant anymore
to simplify it 
O(x^2)

What does it all means

Data structures are simply ways to store data, Algorithm are functions of ways to use data structures to make a program.

Data Structure + Algorithm = Program

https://www.bigocheatsheet.com/

O(n!)

Most expensive, some say Oh no...
We're adding a nested loop for every input that we have.

3 Pillars of programming

What is good code?

Readable
Scalable - Speed ( how much time does it take a function to run, etc) - Memory ( ram )

Which code is best?

readable
Memory - space complexity (what's the memory usage of code)
Speed - time complexity

In programming usually there's a trade off, if you want speed you might have to sacrifice memory and vice versa.

Space Complexity

what causes space complexity?

variables
data structure
function call
allocations

function booooo(n) {
  for (let i = 0; i < n.length; i++) {
    console.log('boooooo');
  }
}
booooo([1,2,3,4,5]);

// time O(n)
// space O(1)

Another way of loops

const findNemo2 = array => {
  array.forEach(fish => {
    if (fish === 'nemo') {
       console.log('Found Nemo');
    }
  });
}
findNemo2(everyone);

const findNemo3 = array => {
  for (let fish of array) {
    if (fish === 'nemo') {
      console.log('Found Nemo');
    }
  }
}

findNemo3(everyone);

The important thing that we learn here is that Big O is about how you can scale.

Premature optimization can be a root of evil.

How to solve coding problem

Knowing all data structures, algorithm etc, it doesn't guarantee that you succeed in a technical interview
It's not the smartest interviewer that gets hired most of the time, it's the interviewer that is able o answer this fundamental question. "Will you solve the company problem?"
It's not necessarily about the solution to a problem in a coding interview. It's about the thought process and knowing the tradeoffs between data structures and algorithm, space and time complexity.

What are companies looking for?

Analytic Skills
How can you think through a problem and analize things, and during interview they want to hear your thought process and how you go from not knowing the answer to solve problem
Coding Skills
Is your code clean, well organize, readable
Technical Skills
Fundamentals, do you understand pro's and cons of different solutions?
Communication Skills
Can you communicate with others?

Companies are looking for people who know how to look for answers, know your data structures and algorithms. When you should use a certain data structure / algorithm over the other.

What We Need For Coding Interviews

Example of coding interview at google

Step By Step through a problem:

1. When the interviewer says the question, write down the key points at the top (i.e. sorted array). Make sure you have all the details. Show how organized you are.

2. Make sure you double check: What are the inputs? What are the outputs?

3. What is the most important value of the problem? Do you have time, and space and memory, etc.. What is the main goal?

4. Don't be annoying and ask too many questions.

5. Start with the naive/brute force approach. First thing that comes into mind. It shows that you’re able to think well and critically (you don't need to write this code, just speak about it).

6. Tell them why this approach is not the best (i.e. O(n^2) or higher, not readable, etc...)

7. Walk through your approach, comment things and see where you may be able to break things. Any repetition, bottlenecks like O(N^2), or unnecessary work? Did you use all the information the interviewer gave you? Bottleneck is the part of the code with the biggest Big O. Focus on that. Sometimes this occurs with repeated work as well.

8. Before you start coding, walk through your code and write down the steps you are going to follow.

9. Modularize your code from the very beginning. Break up your code into beautiful small pieces and add just comments if you need to.

10. Start actually writing your code now. Keep in mind that the more you prepare and understand what you need to code, the better the whiteboard will go. So never start a whiteboard interview not being sure of how things are going to work out. That is a recipe for disaster. Keep in mind: A lot of interviews ask questions that you won’t be able to fully answer on time. So think: What can I show in order to show that I can do this and I am better than other coders. Break things up in Functions (if you can’t remember a method, just make up a function and you will at least have it there. Write something, and start with the easy part.

11. Think about error checks and how you can break this code. Never make assumptions about the input. Assume people are trying to break your code and that Darth Vader is using your function. How will you safeguard it? Always check for false inputs that you don’t want. Here is a trick: Comment in the code, the checks that you want to do… write the function, then tell the interviewer that you would write tests now to make your function fail (but you won't need to actually write the tests).

12. Don’t use bad/confusing names like i and j. Write code that reads well.

13. Test your code: Check for no params, 0, undefined, null, massive arrays, async code, etc… Ask the interviewer if we can make assumption about the code. Can you make the answer return an error? Poke holes into your solution. Are you repeating yourself?

14. Finally talk to the interviewer where you would improve the code. Does it work? Are there different approaches? Is it readable? What would you google to improve? How can performance be improved? Possibly: Ask the interviewer what was the most interesting solution you have seen to this problem

15. If your interviewer is happy with the solution, the interview usually ends here. It is also common that the interviewer asks you extension questions, such as how you would handle the problem if the whole input is too large to fit into memory, or if the input arrives as a stream. This is a common follow-up question at Google, where they care a lot about scale. The answer is usually a divide-and-conquer approach — perform distributed processing of the data and only read certain chunks of the input from disk into memory, write the output back to disk and combine them later.

Roleplay 1

Interviewer gives you these question

Given 2 arrays, create a functiont that let's a user know ( true/false) whether these two arrays contain any common items

For example:
const array1 = ['a','b', 'c','x'];
const array2 = ['z','y', 'i'];
should return false.
---------------------
const array1 = ['a','b', 'c','x'];
const array2 = ['z','y', 'x'];
should return true.

What you should do is : check step by step, So here :

1. When the interviewer says the question, write down the key points at the top (i.e. sorted array). Make sure you have all the details. Show how organized you are.

// write this down
2 parameters
return true / false

2. Make sure you double check: What are the inputs? What are the outputs? you can confirm the interviewer as well for the output can it be a number?

there are 2 arrays for input
there is 1 result for output

Update

// write this down
2 parameters - arrays
return true / false

3. What is the most important value of the problem? Do you have time, and space and memory, etc.. What is the main goal? How large is the array is going to get? if no more than 5 item we don't have to worry about BigO, time / space complexity as much.
you can ask interviewer, is our goal here to be as efficient possible with our function? whats more important? time / space complexity.
Interviewer just want the most efficient function, assuming that the array can be very large

Update

// write this down - arrays - no size limit
2 parameters - arrays
return true / false

4. Don't be annoying and ask too many questions. There usually time limit so ask only important questions.

5. Start with the naive/brute force approach. First thing that comes into mind. this look like a nested loop az ay ai etc, we know it's a big O(n^2), tell the interviewer that we know there's a easy/rough/naive solution.

6. Tell them why this approach is not the best. it maybe space or time, or maybe because it's big O (n^2)

7. Walk through your approach, comment things and see where you may be able to break things.

const array1 = ['a','b', 'c','x'];
const array2 = ['z','y', 'x'];

function containsCommonItem(arr1, arr2) {
  for (let i = 0 ; i < arr1.length; i++) {
    for (let j = 0; j < arr2.length; j++) {
      if (arr1[i] === arr2[j]) {
        return true;
      }
    }
  }
  return false;
}

containsCommonItem(array1, array2);
// O(n^2)

8. Never start a whiteboard interview not being sure of how things are going to work out. That is a recipe for disaster. Keep in mind: A lot of interviews ask questions that you won’t be able to fully answer on time. So think: What can I show in order to show that I can do this and I am better than other coders.

9. Modularize your code from the very beginning. Break up your code into beautiful small pieces and add just comments if you need to.

const array1 = ['a','b', 'c','x'];
const array2 = ['z','y', 'a'];

function containsCommonItem2(arr1, arr2) {
  //loop through first array and create object where properties === items in the array
  let map = {};
  for (let i=0; i < arr1.length ; i++) {
    if (!map[arr1[i]]) {
      const item = arr1[i];
      map[item] = true;
    }
  }
  //loop through second array and check if item in second array exists on created object.
  for (let j=0;j < arr2.length; j++) {
    if (map[array2[j]]) {
      //console.log(true);
      return true;
    }
  }
  //console.log(false);
  return false;
  
}

containsCommonItem2(array1, array2);

// O(a + b) Time Complexity

11. Think about error checks and how you can break this code. Never make assumptions about the input. we want to start thinking about how error may arise.

12. Don’t use bad/confusing names like i and j. Write code that reads well. maybe change the input to names we understand, more meaningful variable

const array1 = ['a','b', 'c','x'];
const array2 = ['z','y', 'a'];

function containsCommonItem2(users, items) {
  //loop through first array and create object where properties === items in the array
  let map = {};
  for (let i=0; i < users.length ; i++) {
    if (!map[arr1[i]]) {
      const item = arr1[i];
      map[item] = true;
    }
  }
  //loop through second array and check if item in second array exists on created object.
  for (let j=0;j < items.length; j++) {
    if (map[array2[j]]) {
      //console.log(true);
      return true;
    }
  }
  //console.log(false);
  return false;
  
}

containsCommonItem2(array1, array2);

13. Test your code: Check for no params, 0, undefined, null, massive arrays, async code, etc

14. Finally talk to the interviewer where you would improve the code. maybe use some methods

function containsCommonItem3(arr1, arr2) {
  console.log(arr1.some(item => arr2.includes(item)));
}

containsCommonItem3(array1, array2);

function containsCommonItem(arr1, arr2) {
  for (let i = 0 ; i < arr1.length; i++) {
    for (let j = 0; j < arr2.length; j++) {
      if (arr1[i] === arr2[j]) {
        return true;
      }
    }
  }
  return false;
}
// 0(1) - Space Complexity because we are not creating new variables just the inputs

const array1 = ['a','b', 'c','x'];
const array2 = ['z','y', 'a'];

function containsCommonItem2(users, items) {
  //loop through first array and create object where properties === items in the array
  let map = {};
  for (let i=0; i < users.length ; i++) {
    if (!map[arr1[i]]) {
      const item = arr1[i];
      map[item] = true;
    }
  }
  //loop through second array and check if item in second array exists on created object.
  for (let j=0;j < items.length; j++) {
    if (map[array2[j]]) {
      //console.log(true);
      return true;
    }
  }
  //console.log(false);
  return false;
  
}

containsCommonItem2(array1, array2);

// O (a+b)
//O(a) Space Complexity, we are creating variables

Data Structures : Introduction

What is a Data Structure?

is a collection of values, values can have relationships and they can have function apply to them. Each data structure is good and is specialized for its own thing.

Block chain at the end of the day is simply a data structure, a way to hold information.

How to build one
How to use it

Data Structures in different language

Each language has their own data types or built in data types, example - javascript (boolean, strings, true, undefined), has data structures to organize these data types ( [] {} )

Operations on Data Structures

Traversal means access each data item exactly once so that it can be processed.

Arrays

The concept of array in coding

class MyArray {
  constructor() {
    this.length = 0;
    this.data = {};
  }

  get(index) {
    return this.data[index];
  }
  push(item) {
    this.data[this.length] = item;
    this.length++;
    return this.length;
  }
  pop() {
    const lastItem = this.data[this.length - 1];
    delete this.data[this.length - 1]
    this.length--;
    return lastItem;
  }

  delete(index) {
    const item = this.data[index];
    this.shiftItems(index);
    return item;
  }

  shiftItems(index) {
    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }
    delete this.data[this.length - 1];
    this.length--;
    //this.data[this.length-1]
  }
}

const newArray = new MyArray();
newArray.push('hi');
newArray.push('you');
newArray.push('!');
// newArray.pop();
// newArray.pop();
newArray.delete(0);

newArray.push('are');
newArray.push('nice');
newArray.delete(1);
console.log(newArray)

Reverse string

//Create a function that reverses a string:
// 'Hi My name is Andrei' should be:
// 'ierdnA si eman yM iH'

//first way
function reverse(str) {
  if (!str || typeof str !== 'string') {
    return 'hmm that is not good';
  }

  const backwards = [];
  const totalItems = str.length - 1;
  for (let i = totalItems; i >= 0; i--) {
    backwards.push(str[i]);
  }
  console.log(backwards);
  return backwards.join('');
}

//second way
function reverse2(str) {
  return str.split('').reverse().join('');
}
var string = "Hi My name is Andrei";

//third way
const reverse3 = str => [...str].reverse().join('');

console.log(reverse(string));
console.log(reverse2(string));
console.log(reverse3(string));

Hashmaps

Each language has each built-in hashmaps. python - dictionary, javascript - objects, java - maps, ruby - hashes.

Hash function

example of hash function - md5, sha1, sha-256 etc. Idempotent = a function given an input always the same output.

Collision

When you have a collision it slows down reading & writing in hash table with O(n/k) which O(n).

Map() = difference between a map and an object is the fact that a map allows you to save any data type as the key, member with an object you can only save the key as string with the map it allows us to have functions as key,

Sets() = similar to map the only difference is that it only stores the keys, no values.

//Google Question
// Given an array = [2,5,1,2,3,5,1,2,4]
// It should return 2
function firstRecurringCharacter(input) {
	for (let i = 0; i < input.length; i++) {
		for (let j = i + 1; j < input.length; j++) {
			if (input[i] === input[j]) {
				return input[i];
			}
		}
	}
	return undefined;
} //O(n^2)

const array = [2, 5, 1, 2, 3, 5, 1, 2, 4];
console.log(firstRecurringCharacter(array));

function firstRecurringCharacter2(input) {
	let map = {};
	for (let i = 0; i < input.length; i++) {
		if (map[input[i]] !== undefined) {
			return input[i];
		} else {
			map[input[i]] = i;
		}
	}
	return undefined;
} // O(n)
console.log(firstRecurringCharacter2(array));

Linked lists

This can traverse from head to tail but not the other way around.

Takes less memory

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null
    }
    this.tail = this.head;
    this.length = 1;
  }
  append(value) {
    const newNode = new Node(value);
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }

  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
    this.length++;
    return this;
  }
  printList() {
    const array = [];
    let currentNode = this.head;
    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.next;
    }
    console.log(array);
  }

  insert(index, value) {
    const newNode = new Node(value);
    if (index >= this.length) {
      return this.append(value);
    }
    const leader = this.traverseToIndex(index - 1);
    const holdingPointer = leader.next;
    leader.next = newNode;
    newNode.next = holdingPointer;
    this.length++;
    return this.printList();
  }
  traverseToIndex(index) {
    //check params
    let counter = 0;
    let currentNode = this.head;
    while (counter !== index) {
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }
  remove(index) {
    const leader = this.traverseToIndex(index - 1);
    const unwantedNode = leader.next;
    leader.next = unwantedNode.next;
    this.length--;
    return this.printList();
  }
}

const myLinkedList = new LinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);
myLinkedList.prepend(1);
myLinkedList.printList();
myLinkedList.insert(2, 99);
myLinkedList.insert(20, 88);
myLinkedList.printList();
myLinkedList.remove(2)

Double Linked List

This can traverse both way from tail to head or vice versa.

Takes more memory.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null
    }
    this.tail = this.head;
    this.length = 1;
  }
  append(value) {
    const newNode = new Node(value);
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }

  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head.prev = newNode;
    this.head = newNode;
    this.length++;
    return this;
  }
  printList() {
    const array = [];
    let currentNode = this.head;
    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.next;
    }
    console.log(array);
  }

  insert(index, value) {
    const newNode = new Node(value);
    if (index >= this.length) {
      return this.append(value);
    }
    const leader = this.traverseToIndex(index - 1);
    const follower = leader.next;
    leader.next = newNode;
    newNode.prev = leader;
    newNode.next = follower;
    follower.prev = newNode;
    this.length++;
    return this.printList();
  }
  traverseToIndex(index) {
    //check params
    let counter = 0;
    let currentNode = this.head;
    while (counter !== index) {
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }
  remove(index) {
    const leader = this.traverseToIndex(index - 1);
    const follower = leader.next;
    console.log(follower);
    const unwantedNode = leader.next;
    leader.next = unwantedNode.next;
    follower.prev = unwantedNode.prev;
    this.length--;
    return this.printList();
  }
}

const myLinkedList = new DoublyLinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);
myLinkedList.prepend(1);
//console.log(myLinkedList);
myLinkedList.insert(1, 99);
//myLinkedList.printList();
// myLinkedList.insert(20, 88);
// myLinkedList.printList();
myLinkedList.remove(1)

singleLinkedList.js

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null
    }
    this.tail = this.head;
    this.length = 1;
  }
  append(value) {
    const newNode = new Node(value);
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }

  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head.prev = newNode;
    this.head = newNode;
    this.length++;
    return this;
  }
  printList() {
    const array = [];
    let currentNode = this.head;
    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.next;
    }
    console.log(array);
  }

  insert(index, value) {
    const newNode = new Node(value);
    if (index >= this.length) {
      return this.append(value);
    }
    const leader = this.traverseToIndex(index - 1);
    const follower = leader.next;
    leader.next = newNode;
    newNode.prev = leader;
    newNode.next = follower;
    follower.prev = newNode;
    this.length++;
    return this.printList();
  }
  traverseToIndex(index) {
    //check params
    let counter = 0;
    let currentNode = this.head;
    while (counter !== index) {
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }
  remove(index) {
    const leader = this.traverseToIndex(index - 1);
    const follower = leader.next;
    console.log(follower);
    const unwantedNode = leader.next;
    leader.next = unwantedNode.next;
    follower.prev = unwantedNode.prev;
    this.length--;
    return this.printList();
  }
}

const myLinkedList = new DoublyLinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);
myLinkedList.prepend(1);
//console.log(myLinkedList);
myLinkedList.insert(1, 99);
//myLinkedList.printList();
// myLinkedList.insert(20, 88);
// myLinkedList.printList();
myLinkedList.remove(1)

doubleLinkedList.js

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor(value) {
    this.head = {
      value: value,
      next: null
    }
    this.tail = this.head;
    this.length = 1;
  }
  append(value) {
    const newNode = new Node(value);
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }

  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
    this.length++;
    return this;
  }
  printList() {
    const array = [];
    let currentNode = this.head;
    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.next;
    }
    console.log(array);
  }

  insert(index, value) {
    const newNode = new Node(value);
    if (index >= this.length) {
      return this.append(value);
    }
    const leader = this.traverseToIndex(index - 1);
    const holdingPointer = leader.next;
    leader.next = newNode;
    newNode.next = holdingPointer;
    this.length++;
    return this.printList();
  }
  traverseToIndex(index) {
    //check params
    let counter = 0;
    let currentNode = this.head;
    while (counter !== index) {
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }
  remove(index) {
    const leader = this.traverseToIndex(index - 1);
    const unwantedNode = leader.next;
    leader.next = unwantedNode.next;
    this.length--;
    return this.printList();
  }

  reverse() {
    if (!this.head.next) {
      return this.head;
    }
    let first = this.head;
    this.tail = this.head;
    let second = first.next;
    while (second) {
      const temp = second.next;
      second.next = first;
      first = second;
      second = temp;
    }
    this.head.next = null;
    this.head = first;
    return this.printList();
  }
}

const myLinkedList = new LinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);
myLinkedList.prepend(1);
myLinkedList.printList();
myLinkedList.insert(2, 99);
myLinkedList.insert(20, 88);
myLinkedList.printList();
myLinkedList.remove(2);
myLinkedList.reverse();

reverseLinkedList.js

Stacks and queues

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
    this.bottom = null;
    this.length = 0;
  }
  peek() {
    return this.top;
  }
  push(value) {
    const newNode = new Node(value);
    if (this.length === 0) {
      this.top = newNode;
      this.bottom = newNode;
    } else {
      const holdingPointer = this.top;
      this.top = newNode;
      this.top.next = holdingPointer;
    }
    this.length++;
    return this;
  }
  pop() {
    if (!this.pop) {
      return null;
    }
    if (this.top === this.bottom) {
      this.bottom = null;
    }
    const holdingPointer = this.top;
    this.top = this.top.next;
    this.length--;
    return this;
  }
  isEmpty() {

  }
}

const myStack = new Stack();
myStack.push('google');
myStack.push('udemy');
myStack.push('discord');
//console.log(myStack);
myStack.pop();
myStack.pop();
console.log(myStack.pop());

stack linked list

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.array = [];
  }
  peek() {
    return this.array[this.array.length - 1];
  }
  push(value) {
    this.array.push(value);
    return this
  }
  pop() {
    this.array.pop();
    return this;
  }
  isEmpty() {

  }
}

const myStack = new Stack();
myStack.push('google');
myStack.push('udemy');
myStack.push('discord');
console.log(myStack);
myStack.pop();
//myStack.pop();
console.log(myStack.pop());

stack array

Data Structures: Trees

Search Binary Trees

// level 0 : 2^0 = 1;
// level 1 : 2^1 = 2;
// level 2 : 2^2 = 3;
// level 3 : 2^3 = 4;
// # of nodes = 2^h - 1;
// log nodes = steps

class Node {
  constructor(value) {
    this.left = null;
    this.right = null;
    this.value = value;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
    } else {
      let currentNode = this.root;
      while (true) {
        if (value < currentNode.value) {
          // left
          if (!currentNode.left) {
            currentNode.left = newNode;
            return this;
          }
          currentNode = currentNode.left;
        } else {
          // right
          if (!currentNode.right) {
            currentNode.right = newNode;
            return this;
          }
          currentNode = currentNode.right;
        }
      }
    }

  }
  lookup(value) {
    if (!this.root) {
      return false;
    }
    let currentNode = this.root;
    while (currentNode) {
      if (value < currentNode.value) {
        currentNode = currentNode.left;
      } else if (value > currentNode.value) {
        currentNode = currentNode.right;
      } else if (currentNode.value === value) {
        return currentNode;
      }
    }
    return false;
  }
  remove(value) {
    if (!this.root) {
      return false;
    }
    let currentNode = this.root;
    let parentNode = null;
    while (currentNode) {
      if (value < currentNode.value) {
        parentNode = currentNode;
        currentNode = currentNode.left;
      } else if (value > currentNode.value) {
        parentNode = currentNode;
        currentNode = currentNode.right;
      } else if (currentNode.value === value) {
        // we have a match
        //option 1 : no right child;
        if (currentNode.right === null) {
          if (parentNode === null) {
            this.root = currentNode.left;
          } else {
            // if parent > current value, make current left child a child of a parent
            if (currentNode.value < parentNode.value) {
              parentNode.left = currentNode.left;
              //if parent < current value, make left child a right child of parent
            } else if (currentNode.value > parentNode.value) {
              parentNode.right = currentNode.left;
            }
          }
        } else if (currentNode.right.left === null) {
          if (parentNode === null) {
            this.root = currentNode.left;
          } else {
            currentNode.right.left = currentNode.left;
            // if parent > current, make right child of the left the parent
            if (currentNode.value < parentNode.value) {
              parentNode.left = currentNode.right;
              //if parent < current, make right child a right child of the parent
            } else if (currentNode.value > parentNode.value) {
              parentNode.right = currentNode.right;
            }

          }
        } else {
          // find the right child left most child
          let leftmost = currentNode.right.left;
          let leftmostParent = currentNode.right;
          while (leftmost.left !== null) {
            leftmostParent = leftmost;
            leftmost = leftmost.left;
          }
          //parent's left subtree is now leftmost right subtree
          leftmostParent.left = leftmost.right;
          leftmost.left = currentNode.left;
          leftmost.right = currentNode.right;
          if (parentNode === null) {
            this.root = leftmost;
          } else {
            if (currentNode.value < parentNode.value) {
              parentNode.left = leftmost;
            } else if (currentNode.value > parentNode.value) {
              parentNode.right = leftmost;
            }
          }
        }
      }
    }
  }
}
const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(6);
tree.insert(20);
tree.insert(170);
tree.insert(15);
tree.insert(1);
console.log(tree.lookup(170));
tree.remove(170);
console.log(JSON.stringify(traverse(tree.root)));

function traverse(node) {
  if (!node) {
    return false;
  }
  const tree = { value: node.value };
  tree.left = node.left === null ? null : traverse(node.left);
  tree.right = node.left === null ? null : traverse(node.right);
  return tree;
}

Binary search tree, insert

AVL Trees + Red Black Trees

AVL Tree Visualzation

Red/Black Tree Visualization

Binary Heaps

Memory heap != Heap data structure, Good for Priority queue

Trie

Graph

// Edge List
const graph = [[0, 2], [2, 3], [2, 1], [1, 3]];

//Adjacent List
const graph = [[2], [2, 3], [0, 1, 3], [1, 2]];

//Adjecent Matrix
const graph = [
  [0, 0, 1, 0],
  [0, 0, 1, 1],
  [1, 1, 0, 1],
  [0, 1, 1, 0]
];

example of graph in a variable

class Graph {
  constructor() {
    this.numberOfNodes = 0;
    this.adjacentList = {};
  }
  addVertex(node) {
    this.adjacentList[node] = [];
    this.numberOfNodes++;
  }
  addEdge(node1, node2) {
    //undirected Graph
    this.adjacentList[node1].push(node2);
    this.adjacentList[node2].push(node1);
  }
  showConnections() {
    const allNodes = Object.keys(this.adjacentList);
    for (let node of allNodes) {
      let nodeConnections = this.adjacentList[node];
      let connections = "";
      let vertex;
      for (vertex of nodeConnections) {
        connections += vertex + " ";
      }
      console.log(node + "-->" + connections);
    }
  }
}

const myGraph = new Graph();
myGraph.addVertex('0');
myGraph.addVertex('1');
myGraph.addVertex('2');
myGraph.addVertex('3');
myGraph.addVertex('4');
myGraph.addVertex('5');
myGraph.addVertex('6');
myGraph.addEdge('3', '1');
myGraph.addEdge('3', '4');
myGraph.addEdge('4', '2');
myGraph.addEdge('4', '5');
myGraph.addEdge('1', '2');
myGraph.addEdge('1', '0');
myGraph.addEdge('0', '2');

myGraph.showConnections();

undirected graph

Tools - neo4j

Algorithms

What is an algorithm? Underneath the hood, algorithms are just functions that programmers write. Certain algorithms allow us to simplify our big complexity into smaller or better time complexity.
Data Structures + Algorithms = Programs.
Class {} + function() = Programs

Recursion (concept)

Recursion is when you define something in terms of itself, simply it's a function that refers to itself inside the function. it's really good for tasks that have repeated subtasks to do.

let counter = 0;
function inception() {
  console.log(counter);
  if (counter > 3) {
    console.log('done!');
    return;
  }
  counter++;
  inception();
}

inception();

Factorial

// 0(n)
function findFactorialRecursive(number) {
  if (number === 2) {
    return 2;
  }
  return number * findFactorialRecursive(number - 1);
}

// O(n)
function findFactorialIterative(number) {
  let answer = 1;
  if (number === 2) {
    answer = 2
  }
  for (let i = 2; i <= number; i++) {
    answer = answer * i;
  }
  return answer;
}

console.log(findFactorialRecursive(5));
console.log(findFactorialIterative(5));

When to use recursion

Every time you are using a tree or converting something into a tree, consider recursion.

Divided into a number of subproblems that are smaller instances of the same problem.
Each instance of the subproblem is identical in nature.
The solutions of each subproblem can be combined to solve the problem at hand.

Divide and conquer using recursion.

Anything you do with a recursion CAN be done iteratively (loop) use this when talking about these topics - Merge sort, Quick Sort, Tree Traversal, Graph Traversal

Sort

const letters = ['a', 'd', 'z', 'e', 'r', 'b'];
const basket = [2, 65, 34, 2, 1, 7, 8];

console.log(basket.sort());

basket.sort(function(a, b) {
  return a - b;
});

console.log('2'.charCodeAt(0))
console.log('65'.charCodeAt(0))
console.log('34'.charCodeAt(0))

Bubble Sort

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function bubbleSort(array) {
  const length = array.length;
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length; j++) {
      //ex [99, 44] if 99 > 44
      if (array[j] > array[j + 1]) {
        //swap numbers
        // put 99 in a temp
        let temp = array[j];
        // swap the current to the right
        array[j] = array[j + 1];
        // swap the right to current
        array[j + 1] = temp;
      }
    }
  }
}
bubbleSort(numbers)
console.log(numbers);

Insertion Sort

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function insertionSort(array) {
  const length = array.length;
  for (let i = 0; i < length; i++) {
    if (array[i] < array[0]) {
      //move number to the first position
      array.unshift(array.splice(i, 1)[0]);
    } else {
      //find where number should go
      for (let j = 1; j < i; j++) {
        if (array[i] > array[j - 1] && array[i] < array[j]) {
          //move number to the right spot
          array.splice(j, 9, array.splice(i, 1)[0]);
        }
      }
    }
  }
}

insertionSort(numbers);
console.log(numbers);

Selection Sort

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function selectionSort(array) {
  for (let i = 0; i < array.length; i++) {
    let min = i;
    let temp = array[i];
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[min]) {
        min = j;
      }
    }
    array[i] = array[min];
    array[min] = temp;
  }
}

selectionSort(numbers);
console.log(numbers);

Merge Sort (divide & conquer)

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function mergeSort(array) {
  if (array.length === 1) {
    return array
  }

  // split array in into right and left
  const length = array.length;
  const middle = Math.floor(length / 2)
  const left = array.slice(0, middle)
  const right = array.slice(middle)

  return merge(
    mergeSort(left),
    mergeSort(right)
  )
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < left.length && rightIndex < right.lengtth) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
console.log(mergeSort(numbers))

Quick Sort (divide & conquer)

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function quickSort(array, left, right){
  const len = array.length; 
  let pivot;
  let partitionIndex;

  if(left < right) {
    pivot = right;
    partitionIndex = partition(array, pivot, left, right);
    
    //sort left and right
    quickSort(array, left, partitionIndex - 1);
    quickSort(array, partitionIndex + 1, right);
  }
  return array;
}
   
function partition(array, pivot, left, right){
  let pivotValue = array[pivot];
  let partitionIndex = left;

  for(let i = left; i < right; i++) {
    if(array[i] < pivotValue){
      swap(array, i, partitionIndex);
      partitionIndex++;
    }
  }
  swap(array, right, partitionIndex);
  return partitionIndex;
}

function swap(array, firstIndex, secondIndex){
    var temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
}

//Select first and last index as 2nd and 3rd parameters
quickSort(numbers, 0, numbers.length - 1);
console.log(numbers);

Which sort is the best

Insertion sort should be used with only a few items if your input is small or items are mostly sorted.
Bubble sort, Insertion sort is only really used for educational purposes as a way to teach sorting.

Merge sort is really good because of divide and conquer, if you're worried about worst-case scenarios, you should use merge sort. if you want to sort in memory on your machine and you're worried about space complexity, merge sort going to be really expensive.

Quick sort is better than merge sort, the most popular algorithm, are you pick a bad pivot it will be really slow.

Non-comparison sorts

Counting sort

Counting Sort Visualization

Radix sort

Radix Sort Visualzation

Exercise - which type of sort would you use?

#1 - sort 10 schools around your house by distance: insertion sort - really fast on small sorts, easy to code, space complexity O(1)

#2 - eBay sorts listings by the current bid amount: radix or counting sort - the bid is usually a number because it's a fixed length of integers, integers are most likely not going to be 100 million because

#3 - sport scores on ESPN : quick sort most efficient

#4 - massive database (can't fit all into memory) needs to sort through past year's user data : merge sort

#5 almost sorted udemy review data needs to update and add 2 new reviews: insertion sort

#6 - temperature records for the past 50 years in Canada: radix counting sort / quick sort

#7 - large user name database needs to be sorted. Data is very random: Quick sort

#8 - you want to teach sorting for the first time: bubble sort, selection sort

Algorithms: Searching + BFS + DFS

Linear search

var beasts = ['Centaur', 'Godzilla', 'Mosura', 'Minotaur', 'Hydra', 'Nessie'];

var indexOf = beasts.indexOf('Centaur');

console.log(indexOf);

var findIndex = beasts.findIndex(function(item) {
  return item === 'Godzilla';
})

console.log(findIndex);

var find = beasts.find(function(item) {
  return item === 'Godzilla';
});
console.log(find);

var includes = beasts.includes('Godzilla');
console.log(includes);

Binary Search - 0(log n)

You split a list of sorted items and decide from there whether the item you're looking for is on the left or right of the list.

Graph + tree traversals

Breadth first search (BFS) - from top to bottom from each layer from left to right - high memory - O(n)

// if you know a solution is not far from the root of the tree:
BFS
// if the tree is very deep and solutions are rare:
BFS (DFS will take long)
// if the tree is very wide:
DFS (BFS will take )
// if solutions are frequent but located deep in the tree
DFS
// determining whether a path exists between two nodes:
DFS
// finding the shortest path
DFS

9 6 12 1 4 34 last

breathFirstSearch() {
    let currentNode = this.root;
    let list = [];
    let queue = [];
    while (queue.length > 0) {
      currentNode = queue.shift();
      list.push(currentNode.value);
      if (currentNode.left) {
        queue.push(currentNode.left);
      }
      if (currentNode.right) {
        queue.push(currentNode.right);
      }
    }
    return list;
  }
  
  breadthFirstSearchR(queue, list) {
    if (!queue.length) {
      return list;
    }
    let currentNode = this.queue.shift();
    list.push(currentNode.value);
    if (currentNode.left) {
      queue.push(currentNode.left);
    }
    if (currentNode.right) {
      queue.push(currentNode.right);
    }
    return this.breadthFirstSearchR(queue, list);
  }

Depth First Search (DFS) - low memory - O(n)

9 6 1 4 9 12 34 12 35

in order - [1,4,6,9,12,34,45]

Pre order - [9,6,1,4,12,34,46]

Post Order - [1,4,6,34,45,12,9]

What is the time and space complexity of a breadth first and depth first tree traversal?

Can someone explain with an example how we can calculate the time and space complexity of both these traversal methods? Also, how does recursive solution to depth first traversal affect the time and

Stack OverflowFrank Q.

inorder - from the smallest value to higher
preorder - from parent left to right

DFSInorder() {
return traverseInOrder(this.root, [])
}
DFSPostorder() {
return traversePostOrder(this.root, [])

}
DFSPreorder() {
return traversePreOrder(this.root, [])
}

function traverseInOrder(node, list) {
  if (node.left) {
    traverseInOrder(node.left, list);
  }
  list.push(node.value);
  if (node.right) {
    traverseInOrder(node.right, list);
  }
  return list
}

function traversePreOrder(node, list) {
  list.push(node.value);
  if (node.left) {
    traversePreOrder(node.left, list);
  }
  if (node.right) {
    traversePreOrder(node.right, list);
  }
  return list
}

function traversePostOrder(node, list) {
  if (node.left) {
    traversePostOrder(node.left, list);
  }
  if (node.right) {
    traversePostOrder(node.right, list);
  }
  list.push(node.value);
  return list
}

Dijsktra + Bellman

Dynamic Programming

Memoization

memoization is a specific form of caching that involves caching the return value.

function addTo80(n) {
  console.log('long time')
  return n + 80;
}

function memoizedAddTo80(n) {
  let cache = {}
  return function(n) {
    if (n in cache) {
      return cache[n];
    } else {
      console.log('long time')
      cache[n] = n + 80;
      return cache[n]
    }
  }
}
const memoized = memoizedAddTo80()

console.log(memoized(5))
console.log(memoized(5))
console.log(memoized(6))

Fibonacci + memoized

//0,1,1,2,3,5,8,13,21,34,55,89,144,233..
// 0+1 = 1 1+1=2 1+2=3 2+3=5 3+5=8 5+8=13
// O(2^n)
let slow = 0;
let medium = 0;
let fast = 0;
function fibonacci(n) {
  slow++;
  if (n < 2) {
    return n
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// O(n)
function fibonacciMaster(n) {
  let cache = {};
  return function fib(n) {
    fast++;
    if (n in cache) {
      return cache[n];
    } else {
      if (n < 2) {
        return n;
      } else {
        cache[n] = fib(n - 1) + fib(n - 2);
        return cache[n];
      }
    }
  }
}

function fibonacciMaster2(n) {
  let answer = [0,1];
  for (let i = 2; i <= n; i++) {
    medium++;
    answer.push(answer[i-2]+answer[i-1]);
  }
  return answer.pop();
}


const fasterFib = fibonacciMaster();
console.log('slow', fibonacci(20));
console.log('DP', fasterFib(20));
console.log('we did slow :' + slow)
console.log('we did medium :' + medium)
console.log('we did fast :' + fast)

Non Technical interview

Mindset - treat everything as a learning experience, Don't hope for everything at all, learn about the company, and see how good you are in an interview. Your goal is to enter the room with a lot of energy, being happy, and excited to be there.

4 Heroes

Technical - Story you worked on a really difficult project or personal project that is going to impress the interviewer.

Success - Maybe start a little app that turned out to be quite successful and it got a lot of users. You want to have some sort of story that shows you that you're a successful person, not a person that never succeeds in any job.

Leadership - Do you have leadership qualities, are you the type of person that takes charge, and doesn't get told what to do all the time?

Challenge - may be a challenging technical problem that you had on a project and how you overcame it because you're the type of person who when presented with something that is really difficult has no clear solution

Tell me about yourself

your triggers of success
mention things you want to get asked
skills should be relevant to the job

Why us?

show you want to grow
demonstrate why you are the best

Why did you leave your job?

No negativity

Tell me about the problem + how you solved it

Have this prepared
Have metrics and numbers
scaling, performance, security

SAR - situation, action, result

Tell me about an interesting project.

show how you are different
relate it to this job

What is your biggest weakness?

Real answer
show how you improved it

Talk about weakness but turn it around into strength

Any questions for me?

Focus on them, not the company (YOU)
Mention something they mentioned
Example - what they wish somebody told them when they just started the job at this company

Secret Weapon

Simplicity over complexity
premature optimization is the root of all evil
Overall goal, not myopic (focus on one thing)
No complaining about client/code/etc
No ego

After the interview

Don't overuse "I"
Talk about the interviewer
Express how you are the ideal candidate
Don't brag

Example: Thank you for your time, I'm sure you have lots of candidates to see, but I want to say one last thing, There are no shortages of developers for you to interview, however, there's a shortage of good, talented, egoless developers with ambition to learn. It's not the ones that are unable to admit they are wrong, the best developers aren't the ones that know the language in and out at the expense of having blinders, it is not the ones who are unable to admit they are wrong, I am not the most experienced developer that you may interview today, but the one thing that you can guarantee is that nobody that you will interview that will work as hard to develop his or her skill every day, play nicely with all the other developers at the company and isn't so narrow-minded and problem-solving that he or she isn't willing to try new and novel ideas. When you hire me, you will rest assured that you won't have to micromanage me, you don't have to extinguish fires, and in one year, I'll be one of your most valuable employees, I can guarantee that I am at a point in my career where I want to be surrounded by a team that I can grow with and be surrounded by smart people like yourself and I've chosen this company specifically for that reason. and you've probably had similar experiences in your career where one company allows you to really have an impact and propel your career. I am at the stage now and I hope to be part of the team with you. so thank you for your time and I hope to hear back soon from you.

Offer + Negotiation

Handling Rejection

When you get rejected, see if we can extract as much information or feedback as possible from the company. Tell them that you're constantly looking to improve and that you love some feedback.