Grokking Algorithms

Question 1

what is an algorithm?

Answer 1

it’s a set of instructions that accomplish a specific task,

any piece of code is an algorithm.

Question 2

what do we use for searching?

Answer 2

binary search

Question 3

what does a binary search need?

Answer 3

it needs a sorted list as it’s input

Question 4

what is the big o of linear time (exhaustive search)

Answer 4

O(n)

Question 5

what is the big O of binary search?

Answer 5

O(Log(n))

Question 6

what does big O notation do?

Answer 6

it gives an indication of how fast an algorithm is running

Question 7

why do we calculate big O notation?

Answer 7

because algorithms grow at different rates

Question 8

what does big O notation calculate?

Answer 8

number of operations

Question 9

what scenario does big O notations give?

Answer 9

worst-case scenario

Question 10

what is big O for reading an array vs linked list?

Answer 10

array : O(1)

list : O(n)

Question 11

what is big O for insertion an array vs linked list?

Answer 11

array : O(n)

list : O(1)

Question 12

what is big O for deletion an array vs linked list?

Answer 12

array : O(n)

list : O(1)

Question 13

what are the types of accessing elements in memory?

Answer 13

1 - random access

2 - sequential access

Question 14

what does random access mean and who do we use it with?

Answer 14

we use it with an array and it means i can go to an exact index in memory

Question 15

what does sequential access mean and who do we use it with?

Answer 15

we use it with linked lists and arrays, and it means that we have to go through the list reach time to reach a specific element or index

Question 16

what is the big O notation for selection sort?

Answer 16

O(n^2)

Question 17

what is the difference in performance for loops and recursion?

Answer 17

loops : performance for program

recursion : performance for programmer

Question 18

what are the two parts for every recursive function?

Answer 18

1 - base case

2 - recursive case

Question 19

what are the two operations of a stack?

Answer 19

push and pop

Question 20

what is divide and conquer?

Answer 20

they are recursive algorithms

Question 21

what is the worst case and average case for quicksort?

Answer 21

worst : O(n^2)

average : n log n

Question 22

which is faster quick sort or merge sort?

Answer 22

quicksort because the constant is always smaller

Question 23

how to choose the pivot for quicksort?

Answer 23

always choose the middle because if you get the first or last you might end up in the worst case scenario because it divides the sorted array into uneven sides and you will often hit the worst case

Question 24

what is a hash function?

Answer 24

it takes in a string and gives back a number

Question 25

what are the requirements for a hash function?

Answer 25

1 - consistent: meaning apple always returns 1

2 - it should map different words to different numbers as there is no point in returning the name number each time

Question 26

how to avoid collisions in a hash table?

Answer 26

1 - low load factor

2 - good hash function

Question 27

what is a load factor in hash tables?

Answer 27

number of elements / number of slots

Question 28

how to achieve a lower load factor?

Answer 28

by resizing the array of the hash table

Question 29

what is breadth first search?

Answer 29

it’s an algorithm used to solve shortest path problems

Question 30

what is a graph?

Answer 30

it models a set of connections

Question 31

what are graphs made of?

Answer 31

nodes and edges

Question 32

what are neighbors in a graph?

Answer 32

a node that is related to another node

Question 33

what are the questions that a BFS answer?

Answer 33

1 - is there a connection between Node A and Node B?

2 - what is the shortest path between Node A and Node B?

Question 34

what is the running time of BFS?

Answer 34

O(V + E)
v -> number of vertices (nodes)
e -> number of edges

Question 35

what is the difference between directed graph and undirected graph?

Answer 35

1 - directed : it follows a relationship from A to B but not from B to A so it follows the direction of an Arrow
2 - undirected : doesn’t have arrows so it goes both ways

Question 36

what does djikstar algorithm find?

Answer 36

the fastest path no the shortest like BFS

Question 37

what is the type of graph that dijkstra’s algorithm work with?

Answer 37

directed acyclic graph or DAGs

Question 38

what type of weight the dijkstra algorithm cannot work on?

Answer 38

negative weighted edges

Question 39

what is a greedy algorithm?

Answer 39

it finds the optimal local solution at each step and by that it finds the optimal global solution