algos1

Question 1

What is the complexity of quicksort?

Answer 1

O(n log n) in the average case, O(n^2) in the worst case

Question 2

Why is quicksort O(n^2) in the worst case?

Answer 2

If the input is already sorted and you pick the first item as the pivot every time when you are partitioning, the depth of the call stack will be the same as the number of elements in the list (as you are not really dividing them).. Every time you partition you are going through each element (O(n)), but in the worst case you are partitioning more often before hitting the base case. N.b. in the average case the depth of the stack is log n as you are halving the list each time.

Question 3

What is a hash table?

Answer 3

A data structure which maps keys to values. When given an input key, this is hashed to give the index of the value, which can then be accessed in O(1) time.

Question 4

What can go wrong with a hash table?

Answer 4

Collisions. If the hashing algo is not good then many different inputs can get the same index from the hash (collisions). Can use a linked list at that index for the multiple values, but then are forced to search through the linked list in O(n) time to find something

Question 5

What are some use cases for hash tables?

Answer 5

Preventing duplicates; caching; any time you have to map a key to a value.

Question 6

What is a hash table’s load factor?

Answer 6

The number of elements / total number of slots in hash table. A load factor of 1 means there are the same number of elements as slots and there is likelihood of collision. To avoid this should expand hash table at load factor of 0.7.

Question 7

Describe binary search

Answer 7

Given a sorted list and an element e to search for. Get the midpoint of the list and check if e is there. If not, if element in mid is larger than e, reduce the search to the subarray below mid. If element in mid is smaller than e, reduce the search to subarray above mid. This means that every time you don’t find e you are halving the array. Which makes the complexity O(log n).

Question 8

Describe quicksort

Answer 8

Given a list to sort. Partition the list by picking an element and putting everything smaller to its left and everything larger to its right. Then take the subarray to the left and do the same again, and the subarray to the right and do the same again (recursively call quicksort on the subarrays). Eventually will reach base case where the start of the array is the same as the end of the array, so can return. Once all recursive calls return the array is sorted.

Question 9

What is breadth first search?

Answer 9

Searching a graph by searching connected nodes, then their connections, then the connections of their connections

Question 10

What is a graph?

Answer 10

An abstract data type made up of nodes and edges connecting those nodes. Represents a network.

Question 11

How can you implement a graph?

Answer 11

One way is to use a hash table / dictionary. e.g.
{
"bob": ["alice", "claire", "dave"],
"alice: ["dave", "edgar"]
"claire": ["alice"],
etc...
}
In the above, the names are nodes. The list mapped to bob contains bob's neighbours i.e. the nodes bob is connected to.

Question 12

What is the complexity of breadth first search?

Answer 12

You may be searching your entire network, following each edge. So it is at least O(number of edges). And you are also adding everybody to the queue, which is O(number of vertices). So total is O(V+E)

Question 13

What are some ways of representing graphs?

Answer 13

Edge lists:
Array of [vertex1, vertex2] objects.
e.g. [ [1, 5], [1, 2], [3, 5] ]

Adjacency matrices
[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]

Adjacency lists
[ [1, 6, 8],
  [0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]

Question 14

What is time for searching for a given edge in different representations of graphs?

Answer 14

edge list: O(E)
adjacency matrix: O(1)
adjacency list: O(degree)

Question 15

Pseudo code breadth first search

Answer 15

Create a graph (either adjacency matrix, adjacency list or edge list, or as a hashtable)
Create a queue.

Add source node to queue.
while queue is not empty:
  dequeue next node
  get node's neighbours from graph.
  for each neighbour that has not been visited:
    mark as visited
    check if goal / set predecessor and distance
    add to queue

So will visit source, then nodes adjacent to source, then nodes adjacent to those nodes etc.

Question 16

Pseudo code Dijkstra’s algorithm

Answer 16

The goal of DA is to find the shortest path between two nodes in a WEIGHTED, directed (?) graph.

Create a graph (e.g. hashtable mapping nodes to neighbours and the weight between them)
Create a hashtable mappping nodes to cost - i.e the cost to get to that node from the start node.
Create a hashtable mapping nodes to predecessor - their pred on the path from start to finish.

Initialise Costs and Preds for the neighbours of the start node, to contain cost = weight from start to that node and pred = the start node. The rest have cost = infinity and pred = null

Main algo:
Get lowest cost node (LCN)
While lowest cost node != null
For neighbours of lowest cost node:
cost = current cost of neighbour (Costs[n])
new_cost = weight between LCN and neighbour + cost
of LCN
if new_cost < cost, we have found a shorter path to that
node, so make cost of neighbour be new_cost
set Preds[neighbour] to LCN
Add LCN to processed
Get lowest cost node

return Costs, Preds

For finding lowest cost node:
loop through Costs to get node with current lowest cost

Question 17

Pseudo code depth first search

Answer 17

DFS works by picking a source node's child, visiting its child, then the child of its child etc. Can be implemented recursively like this:
dfs(source, graph):
 for each neighbour of source in graph:
   if neighbour is not visited:
     mark neighbour as visited
     dfs(neighbour, graph)

With the recursion we are using the call stack to go deep, then backtrack back and go deep on another neighbour.

Can also be implemented iteratively like this:
dfs_iterative(source, graph):
  mark source as visited
  add source to stack
  while stack is not empty:
    pop node off stack
    for each neighbour of node in graph:
      mark node as visited
      push neighbour on to stack

Question 18

When do you use breadth first search and when do you do depth first search?

Answer 18

BFS is useful for finding shortest path. It looks at nodes 1 level deep, then 2 levels deep, etc. So it will find the shortest path to a target node.
DFS is useful for finding if a path exists.
It will sometimes depend on the structure of the graph whether one is more useful than another.
https://stackoverflow.com/questions/3332947/when-is-it-practical-to-use-depth-first-search-dfs-vs-breadth-first-search-bf

Question 19

Example of a greedy algorithm

Answer 19

Scheduling classroom classes when class times overlap.
Pick the class that finishes earliest. Then pick the class that starts after that class finishes and finishes earliest. And repeat.

Question 20

Pseudo code partitioning for quicksort

Answer 20

Input is array, start index, end index.
Pick pivot - e.g. last element in array.
Set 2 array pointers (follower, leader) to same as start.
While leader <= end:
Check element at array[follower]
If elem is larger than pivot, do nothing.
If it is smaller, swap element at array[follower] with array[leader]. Increment follower.
Increment leader.
End up with follower at index of the last thing that was larger than pivot, so swap elem at pivot with elem in follower.
e.g.
[2, 6, 3, 5, 4]

Question 21

What is an NP complete problem?

Answer 21

Problems with no known fast solutions. In this context, NP stands for “nondeterministic polynomial time”.
Can use approximation algorithm (e.g. greedy) to find approximate solution.

Question 22

What is a greedy algorithm?

Answer 22

An algorithm which takes the locally optimal solution each time, with the aim to get the ultimate optimal solution. E.g. for knapsack problem, take the most expensive item that fits in bag, then take second most expensive item which fits in bag, etc.
Or for scheduling - take the class which finishes earliest, then take the class that starts after that which finishes earliest etc.

Question 23

What is big O complexity?

Answer 23

todo
include this https://medium.com/@.RT/total-n00bs-guide-to-big-o-big-%CF%89-big-%CE%B8-aa259ae8a1c2

Asymptoptic/complexity analysis in general: a way of describing the performance of an algorithm, more specifically a measure of how quickly the algorithm will scale with its input. The quicker it scales/grows, the slower it gets with bigger input.

Big O: Big O, in strict academic terms, is the upper bound of a given algorithm. You can say e.g. that a function 4n is Big O of n^2. But also that 4n is Big O of n^3.
The general definition is that a function f(n) is Big O of g(n) if there is a constant M such that after a given value of n the following is always true:
f(n) <= M * g(n)
Essentially that g(n), from some n onwards, will always be greater than f(n).

Big Omega: Is the opposite of Big O. It is the lower bound of a function.
f(n) >= M * g(n)

Big Theta: A function f(n) is Big Theta of g(n) if there is a given constant M for which f(n) is both Big O AND Big Omega of g(n). This means that our algo is tightly bound by g(n).

N.B. when people talk about Big O, they generally mean Big Theta.

Question 24

What is dynamic programming? What is top-down and what is bottom-down approach?

Answer 24

A means of solving problems in such a way that breaks them down into subproblems and memoizes the results of the subproblems so they can be combined to solve the actual problem.

Top-down - Formulate recursive solution, store solutions to subproblems. Whenever attempting to solve a subproblem, check the table to see if already solved.
Bottom-up - Solve the sub-problems first and build on them as you go.

Question 25

Pseudo code DP fibonacci function

Answer 25

Similar to non DP recursive fibonacci but store solutions to sub-problems.
fib(n):
Have a map M tracking results for each n.
if n is smaller or equal to 1, return n.
Otherwise check if n is in M. If it is not, add it to M as the result of fib(n-1) + fib(n-2).
Return M[n].

Because we are storing results for each n in map, we are only calculating them once, and thereafter using the value from M.

Question 26

What are the 2 key attributes a problem must have to be solvable by DP?

Answer 26

1. Optimal substructure - you must be able to obtain the optimal solution to problem by combining optimal solutions to sub-problems.
2. Overlapping sub-problems (same sub-problems get solved multiple times - think non-DP recursive fibonacci). This property is missing from e.g. merge sort or quick sort which is why they are not DP.

Question 27

What is an array?

Answer 27

Data structure which stores items in memory contiguously.

Question 28

What is time complexity of inserting and deleting from array and why?

Answer 28

O(n) (linear time), because if you want to insert at a certain index you have to shift the other elements. However just inserting at the end is O(1).

Question 29

What is time complexity of reading from array?

Answer 29

O(1) (constant time). Elements are stored contiguously. Accessing an array e.g. arr[3] you can go straight to that location. So it is constant time.

Question 30

What is a linked list?

Answer 30

A linked list is a linear collection of data elements whose order is not given by their physical placement in memory (as opposed to an array). Instead, each element has a reference to the location of the next element in the list.

Question 31

What is time complexity of reading specific item in linked list? (e.g. 10th element)

Answer 31

O(n) - have to traverse the list, jumping from element to element until you get to your desired element

Question 32

What is time complexity of inserting into linked list (somewhere not at the start)

Answer 32

Actual insertion is O(1) - just repointing references. But to get to the place where you want to insert you have to traverse the list, which is O(n).

Question 33

Arrays vs Linked Lists

Answer 33

Arrays are fast access and can be accessed randomly. Insertion into LLs can be faster and LLs are dynamic and can add as many elements as you want without having to resize.

Question 34

Pseudo code selection sort

Answer 34

Selection sort by repeatedly finding the smallest element in the subarray left to sort and putting it in the leftmost position

Given a list input
Starting at index 0, find the smallest element in list, put in index 0.
Increase index by 1 and repeat.

Question 35

Pseudo code insertion sort

Answer 35

Insertion sort works by taking the element to the right of the sorted subarray and placing it in the correct place within the subarray.

Given an array input
At the start, sorted subarray will be arr[0]
Take elem at arr[1] and move to the left of everything it is smaller than
Increment index and repeat

Question 36

Pseudo code bubble sort

Answer 36

Bubble sort works by comparing each pair in array and putting them in order. Bigger elements will bubble up to the right of the array.

Given array input
For i from 0 to len(arr)
For j from 0 to len(arr)-i
Compare elements at j and j+1, swap if j is bigger

Question 37

Pseudo code merge sort

Answer 37

Given a list of items, a left and right index:
if left >= right return
If not, find the middle index by subtracting left from right and dividing by 2
Call mergesort(items, left, mid)
Call mergesort(items, mid+1, right)
Call merge(items, left, mid, right)

Merge takes list and a left, midpoint and right indices.
Create 2 new lists, left and right.
Put everything up to middle in L, everything after middle in R.
Keep 3 pointers - i for the main list, j for left list, k for right list.
While j <= L.length and k <= R.length:
compare L[j] and R[k], put smallest in main[i].
increment i and increment whichever of j and k was smallest.
Once out of the while loop, loop through remainder of items in L and R and add to main[i], i++ etc. Merge complete.

Question 38

Pseudo code insert into binary search tree

Answer 38

To insert element e
Current = root;
If e < current:
if root.left is null, insert at root.left, otherwise current=root.left
if e > current, do the same but to the right

RECURSIVE:
to insert element e
insert(root, e)
if root is null, root = e
else if e < root, if root.left is null, insert at root.left. Otherwise call insert(root.left, e).
If e > root, do same for right.

Question 39

Pseudo code delete from binary search tree

Answer 39

What you need to do depends on whether node has children or not.
No kids: simply remove node
1 kid: Set value of node to kid’s value, delete kid
2 kids: Set value of node to value of leftmost child in right subtree, remove that child

Question 40

What is a binary search tree?

Answer 40

An ADT made up of nodes, each having up to 2 children, and ordered such that a child that is smaller is to the left of its parent and a child that is greater is to the right of its. Therefore for a given root node we know that all nodes smaller than it are in the left subtree and all the nodes greater than it are in the right subtree.