Grokking Algorithms Flashcards
what is an algorithm?
it’s a set of instructions that accomplish a specific task,
any piece of code is an algorithm.
what do we use for searching?
binary search
what does a binary search need?
it needs a sorted list as it’s input
what is the big o of linear time (exhaustive search)
O(n)
what is the big O of binary search?
O(Log(n))
what does big O notation do?
it gives an indication of how fast an algorithm is running
why do we calculate big O notation?
because algorithms grow at different rates
what does big O notation calculate?
number of operations
what scenario does big O notations give?
worst-case scenario
what is big O for reading an array vs linked list?
array : O(1)
list : O(n)
what is big O for insertion an array vs linked list?
array : O(n)
list : O(1)
what is big O for deletion an array vs linked list?
array : O(n)
list : O(1)
what are the types of accessing elements in memory?
1 - random access
2 - sequential access
what does random access mean and who do we use it with?
we use it with an array and it means i can go to an exact index in memory
what does sequential access mean and who do we use it with?
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
what is the big O notation for selection sort?
O(n^2)
what is the difference in performance for loops and recursion?
loops : performance for program
recursion : performance for programmer
what are the two parts for every recursive function?
1 - base case
2 - recursive case
what are the two operations of a stack?
push and pop
what is divide and conquer?
they are recursive algorithms
what is the worst case and average case for quicksort?
worst : O(n^2)
average : n log n
which is faster quick sort or merge sort?
quicksort because the constant is always smaller
how to choose the pivot for quicksort?
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
what is a hash function?
it takes in a string and gives back a number
what are the requirements for a hash function?
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
how to avoid collisions in a hash table?
1 - low load factor
2 - good hash function
what is a load factor in hash tables?
number of elements / number of slots
how to achieve a lower load factor?
by resizing the array of the hash table
what is breadth first search?
it’s an algorithm used to solve shortest path problems
what is a graph?
it models a set of connections
what are graphs made of?
nodes and edges
what are neighbors in a graph?
a node that is related to another node
what are the questions that a BFS answer?
1 - is there a connection between Node A and Node B?
2 - what is the shortest path between Node A and Node B?
what is the running time of BFS?
O(V + E)
v -> number of vertices (nodes)
e -> number of edges
what is the difference between directed graph and undirected graph?
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
what does djikstar algorithm find?
the fastest path no the shortest like BFS
what is the type of graph that dijkstra’s algorithm work with?
directed acyclic graph or DAGs
what type of weight the dijkstra algorithm cannot work on?
negative weighted edges
what is a greedy algorithm?
it finds the optimal local solution at each step and by that it finds the optimal global solution
