Algorithms Flashcards
Describe Dijkstra’s Algorithm
Start with initial node, labeling above every node in the graph the distance from start vertex to that node. If it doesn’t directly connect to a vertex, the distance is currently infinity.
Check all vertices that have not been visited yet and select the one with the shortest current distance. (This means you do have to iterate through the list of vertices and check their distances each iteration.) Use it as an intermediary between the other vertices it is connected to. “Relax” the length of the vertices using the currently selected vertex as an intermediary. The formula is:
If (d[u] + c[u, v] < d[v])
d[v] = d[u] + c[u, v]
d[u] is the distance from the initial vertex to the currently selected vertex. c[u, v] is the distance from vertex u (selected) to vertex v (vertex we are calculating). Repeat “relaxation” for all vertexes directly touching the currently selected vertex.
Could be O(n^2) if every vertex was connected to every other vertex, in the worst case.
May fail and give a wrong answer if there are negative edges because a negative number can yield a better distance for a vertex, but since the vertex has already been selected, it won’t change it to the better value.
Describe the Binary Search Algorithm
Must be a sorted list. Check middle value if it is greater/less than the value we’re searching for. If it is greater, discard mid to high value and repeat for left side of array. Repeat until mid value is the searched for value/only value left. O(logn) time.
Describe BFS Algorithm
Add initial node to queue and add its value to the order list. Start the while loop. Pop it from the queue. Add all adjacent nodes that are connected to the current node to the queue and add them to the ordered list ONLY IF THEY HAVENT ALREADY BEEN EXPLORED (Don’t need to worry about most of the time). Repeat this process, popping the most recent node off the queue and adding adjacent nodes that haven’t been explored yet to the queue and the list.
Create a BFS spanning tree, adding solid lines to create the tree and dotted lines to adjacencies that have already been explored (cross-edges). Edges that go backward a back edges I believe.
Many possible outcomes because there is no specific order you have to go in when adding adjacent nodes to the queue.
O(n) time where n is the number of nodes in the tree and assuming there are no duplicate children. O(n) space for the queue to hold potentially all the nodes in the tree. O(n^2) time is possible if all nodes are connected to every other node.
Describe DFS Algorithm
Use a stack. See if initial node has an adjacent node. If it does, add initial node to the stack and the node it was connected to is now the current node. Repeat this until the current node does not have a node adjacent to it. Pop a node off the stack and check for another adjacent node that has not been visited. If there is, put it back on the stack and explore down that path. If not, pop the next one off the stack and make that the current node. Recursive solution also possible here.
Make DFS spanning tree, making back-edges to additional adjacencies that have already been visited.
Many possible outcomes here as well because you can choose different adjacencies.
Describe the Merge Sort Algorithm
Divide and conquer algorithm that separates a larger array into subarrays until each subarray has only 1 element (which is technically sorted). They then recursively merge the subarrays together.
The merge works by having two lists to sort and a third list to fill with the values of the two smaller lists. You keep track of the indexes of the two smaller lists and compare the list values at those indexes. Keep track of the third list’s index as well.
Merge(array A, array B):
Array C[A.size() + B.size()];
indexA = 0;
indexB = 0;
indexC = 0;
While (indexC < C.size()):
If (indexA < A.size() && A[indexA] < B[indexB]) { // && should short circuit so no OOB
C[indexC] = A[indexA];
indexC++; indexA++;
} else {
C[indexC] = B[indexB];
indexC++; indexA++;
}
Return C;
All of the recursions will be O(n), O(logn) times, so O(nlogn). If we are talking about merging itself without starting with an initial list, use O(n+m), where the two letters are the sizes of the two lists being compared.
Describe the Quick Sort Algorithm
Works on the idea that one of the numbers are already in the correct sorted place in the array, so add infinity to the end of the list (or after high index of place in array you want to be sorted) because the infinity will be in the correct spot.
Low value is lower index where you want the sorting to take place. High index is where you added infinity. The value at the starting low index is the number we’re going to place in the correct index relative to the other numbers we are sorting. All values below it will be lower and all values after will be higher. This is called the pivot. Variable I will start at low index. Variable j will start at high index. Increment I until you find a value greater than the pivot. Decrement j until you find a value lower than the pivot. If i is less than j, swap values. Continue to do this while index I is less than index j. When they cross over and index I becomes greater than index j, swap value at the low/starting index (which value is the pivot) with the value at index j. The pivot value is now in the correct spot and that quicksort was completed. Return j so the next iteration knows where the new high and low value will be. This function is called “partition”.
The returned j from the partition method is the new “high” index for the lower portion of the array, and j+1 is the “low” index for the right portion of the array. (Update: j doesn’t seem to work for all cases as the lower portion’s high. Use j-1 as the high and j+1 as the low for the right portion.) Run quicksort using the original low value for low and j as the new high, and also on the right portion using j+1 for the low and the original high as the right portion’s high
Quicksort(low, high):
If (low < high):
J = partition(low, high)
Quicksort(low, j)
Quicksort(j+1, high)
Describe Prim’s Algorithm
Greedy algorithm for finding a minimum cost spanning tree. Given a graph, start with the edge with the least cost. Then using the two vertices that are included in this initial tree, find the minimum cost edge stemming from those and connect the vertices at the end of that edge. The next edge will always be the lowest cost edge connected to the current tree we’re making that leads to a vertices that has not yet been visited.
SPANNING TREES ARE ONLY POSSIBLE WITH GRAPHS THAT ARE CONNECTED. NO ISLANDS.
Describe Kruskal’s Algorithm
This always adds the next lowest cost edge to the tree, but only if it does not form a cycle. In other words (I’m pretty sure), we just don’t add an edge that leads to a vertices that has already been visited. To find the next lowest cost edge each time is more expensive though. The algorithm ends up being O(v*e), or the number of edges times the number of vertices. There is an improvement though.
A min heap will keep those values sorted, so searching for those values will only be logn, for a total of O(nlogn) time. (A min heap is a binary tree that has the minimum value as the top node. A max heap has the maximum value as the top node. The data structure allows us to easily insert things into the heap while keeping everything sorted, and when we pop the top value, we can adjust the rest of the tree to maintain a sorted order as well.)
KRUSKAL’S CAN FIND MINIMUM SPANNING TREE FOR INDIVIDUAL COMPONENTS IF THE GRAPH IS NOT CONNECTED, BUT NOT A MINIMUM SPANNING TREE FOR THE WHOLE GRAPH.
A minimum cost spanning tree should have n-1 edges, where n is the number of vertices in the graph.
Describe the Floyd Warshall Algorithm
Make an adjacency matrix showing the path lengths to each vertex to every other vertex. Make new adjacency matrix, plugging in new values if using the first vertex as an intermediary yields a shorter path. (Note that vertices that do that have a path to another vertices has infinity as the length, so if the first vertex connects the two, the length will inevitably be smaller than the original matrix.) Continue to do this for all the other vertices, finding the smallest values for the adjacency matrix.
Notice that the initial matrix will have values of zero for the diagonal from top left to bottom right. This is because a length from vertex 1 to vertex 1 is zero. Same for 2-2, 3-3, etc. Also, when we are making a new matrix, using 1, for example, as the intermediary vertex, the row and column for 1 will maintain the same values as the initial matrix. When we move on and use vertex 2 as the intermediary, the row and column for 2 will be the same as the previous matrix we just made when we used 1 as the intermediary.
Always compare new matrices that we’re making to the matrix we just made before. This will maintain the smallest values.
This takes 3 for loops nested inside each other. O(n^3) time as each for loops is n time. O(n^3) space as well since each matrix is n^2 and there are n matrices that need to be made, so n^3.
What is the difference between Kruskal’s, Prim’s, Dijkstra’s, and Floyd Warshall Algorithms? Also Bellman Ford?
Kruskal’s and Prims are the same in that they are finding the minimum cost spanning tree, or in other words, they are recreating the given graph but attempting to include only the edges that will make the cost between nodes the smallest. There are n - 1 edges in a minimum spanning tree, where n is the number of nodes.
Prim’s and Kruskal’s are different because Kruskal’s picks whatever is the next shortest edge in the graph without making a cycle. Prim’s picks the shortest edge that is attached to the current tree. Prim’s starts with the lowest cost edge and sprouts from there. Since Kruskal’s has to search the whole graph for the next lowest cost edge each iteration, it will take more time, but Prim’s might be a worse solution.
Dijkstra’s is trying to find the least distance from a starting node to every other node. It uses intermediate nodes to reduce distances to other nodes by “relaxing” the distances. It is like Prim’s in that it “branches” out from a starting point, using the next lowest distance node as an intermediary between the other nodes.
Floyd Warshall uses Dynamic Programming (adjacency matrices) to essentially perform dijkstra’s on every node to every other node.
Bellman Ford iterates through all edges n-1 times, relaxing nodes with those edges. If done the nth time and there was a change, this means there was a negatively weighted cycle in the graph.
What is Dynamic Programming?
When you test all possible solutions at a given state and choose the best one.
Describe the Bellman Ford Algorithm
Make a list of every edge in the graph. Then start at the chosen starting node and set all other node distances to infinity. Iterate through every edge in the list and relax the edges. Iterate through every edge in the list again, continuing to relax edges with updated values. Do n-1 sets of iterations through the graph, or I suppose until no change is made through a round of relaxing all the edges. This allows you to work with graphs with negative edges. (When writing the algorithm, don’t stop until n - 1 times.)
Worst case O(n^2) normally, but if every node is connected to every other node, it will be O(n^3)
DOES NOT WORK IF THERE IS A NEGATIVE WEIGHT CYCLE. There will always be a shorter path being created within the cycle forever. A positive cycle is fine because it will produce a higher cost, so the algorithm won’t switch from the current value. You can use this algorithm to check if there is a negative weight cycle by going through the edges an nth time. If something changes, you know there was a negatively weighted cycle.
Describe the Insertion Sort Algorithm
Index zero is the “sorted” portion of the array, and everything to the right of it is unsorted. Store the value of index 1 in a variable and check to see if the previous value is greater than it. If it is, shift it up 1 index to fill the hole and put the value stored in the variable at index zero. Now those two are sorted. The next value will do the same thing, shifting previous values up if they are greater until we’ve reached index zero or found a value less than the current variable we are trying to place.
Best case is O(n) if array is already sorted. Worst case is O(n^2) if the values are reversely sorted I believe.
Describe the Selection Sort Algorithm
Make a second array of the same size. Iterate through all values in array we are trying to sort and store the minimum value. Also keep track of the index it was at. Push that value onto the second array and set the value in the first array at the stored index to infinity so it will never be chosen again. Do this n times until all the values from the first array have been added to the new array in ascending order. O(n^2) time.
What is a binary search tree? What are the functions you need to define for a BST implementation? How do you implement those functions?
A binary search tree is a tree data structure where each node in the tree satisfies this property: All children on the left of a node have a value less than the current node’s value and all children on the right have a value greater than or equal to the current node’s value.
To implement a BST, you need insert, remove, and contain functions.
// Insert
To insert, simply check if the value is less than the current node’s value or if it’s greater than/equal to the current node’s value. This will decide if it’s going right or left.
If the left/right node is currently null, make the node a new BST with the value we’re trying to insert. If the left/right node is not null, just call the same insert function on that child node and it will continue down the tree until there is a place to insert it.
public BST insert(int value) {
if (this.value > value) { // Going to the left
if (this.left == null) {
this.left = new BST(value);
} else {
this.left.insert(value);
}
} else { // Going to the right
if (this.right == null) {
this.right = new BST(value);
} else {
this.right.insert(value);
}
}
return this;
}
// Contains
Check if the value we’re searching for matches the current node’s value. If it does, return true. If the current node’s value is greater than the value we’re looking for, return the value that comes from calling contains(value) again on the left child of the current node. If that child doesn’t exist, return false. Vice versa with the right child if the value we’re looking for is greater than the current node’s value
public boolean contains(int value) {
if (this.value == value) {
return true;
}
else if (this.value > value) { // Search left
if (this.left != null) {
return this.left.contains(value);
} else {
return false;
}
} else { // Search right
if (this.right != null) {
return this.right.contains(value);
} else {
return false;
}
}
}
// Remove
This one is tricky. You traverse the graph the same way as contains until you find the value. There are 4 cases when this happens: left is null and right is not, right is null and left is not, both are null, and neither are null.
If one child is null and the other is not, just set the current node’s value and children equal to the non-null child. It will be as if the child just scooted up in the tree and the value we we’re searching for will be removed.
If the value has no children, return null, which indicates to the parent that we should just set that child to null, removing it.
If the node we’re removing has two children, we replace it with the lowest value on the right. This means jumping to the right child and then traversing children on the left until the left child is null. Once our helper function finds that value, we replace the current node’s value with that value and call remove again to remove it from the bottom of the tree. This process will ultimately move it from the bottom of the tree to the place our current node is, successfully removing the desired value and placing the appropriate value in its place.
Remember, whenever calling remove recursively, we need to set it equal to a BST. If that BST returns null, we need to set the child we called remove on to null.
public BST remove(int value) {
if (this.value == value) { // found it
if (this.left != null && this.right == null) {
BST left = this.left.left;
BST right = this.left.right;
this.value = this.left.value;
this.left = left;
this.right = right;
} else if (this.left == null && this.right != null) {
BST left = this.right.left;
BST right = this.right.right;
this.value = this.right.value;
this.left = left;
this.right = right;
} else if (this.left == null && this.right == null) { // Return null tells parents to set this child to null
return null;
} else {
int newValue = this.right.getSmallestFromRight();
this.value = newValue;
BST erase = this.right.remove(newValue);
if (erase == null) {
this.right = null;
}
}
}
if (this.value > value) { // Search left
if (this.left != null) {
BST erase = this.left.remove(value);
if (erase == null) {
this.left = null;
}
}
} else { // Search right
if (this.right != null) {
BST erase = this.right.remove(value);
if (erase == null) {
this.right = null;
}
}
}
// Do not edit the return statement of this method.
return this;
}
public int getSmallestFromRight() {
if (this.left == null) {
return this.value;
}
else { return this.left.getSmallestFromRight(); }
}
How do you validate a BST?
Take the BST given to you and pass it through a validate function with a minimum and maximum of -inf and inf.
return validate(tree, -inf, inf);
Each node traversed will have a minimum and maximum value that will make the tree valid, so the root node can be any number with infinite values as the parameters.
The validate function will return false if the node’s value is outside the boundaries of the min and max. If it falls within the boundaries, we can move on and check the child nodes if they are not null.
When checking the left child, pass through the validate function and maintain the current minimum value as the new min. The new maximum value will be the current node’s value - 1 since all nodes to the left of it should be strictly less than.
When checking the right child, pass through the validate function and maintain the current maximum value as the new max. The new minimum value will be the current node’s value since it must be greater than or equal to the current node’s value.
The validate function will return false if it finds an invalid value, so whenever validating a child, store the boolean return value. If it’s false, return false. If not, don’t do anything and just continue. At the end of the validate function, return true. This setup will jump up the layers of recursion and return false as soon as an invalid value is found. Otherwise, it will traverse the whole tree and eventually return true.
public static boolean validateBst(BST tree) {
return validate(tree, -Integer.MAX_VALUE, Integer.MAX_VALUE);
}
public static boolean validate(BST tree, int min, int max) {
if (tree.value > max || tree.value < min) {
return false;
}
if (tree.left != null) {
boolean left = validate(tree.left, min, tree.value - 1);
if (left == false) return false;
}
if (tree.right != null) {
boolean right = validate(tree.right, tree.value, max);
if (right == false) return false;
}
return true;
}
How do you perform traversals of a binary search tree? InOrder? PreOrder? PostOrder?
Do a depth first search in all cases, so the recursive function should call the traversal on the left child if not null and then the right child if its not null. At some point during those calls, the current node’s value should be added to the array that holds the order of traversal.
Inorder: the current node’s value should be added to the array after the left child’s traversal returns and before the right child’s traversal call.
PreOrder: the current node’s value should be added to the array at the start of the traversal function, before the left child is traversed.
PostOrder: the current node’s value should be added to the array after the right child has been traversed at the end of the traversal function.
What is a min height BST? How would you create a min height BST out of a list of integers given a properly implemented BST insert function?
First, create a helper function that gets the mid index given a left and right index. (Get the difference of the indexes, cut the difference in half (floor value), and add that half to the left index to get the index in the middle.)
public static int getMidIndex(int left, int right) {
int dif = right - left;
int half = (int)Math.floor(dif/2);
return left + half;
}
Now for the actual function, store the mid index of the entire array given.
int midIndex = getMidIndex(0, array.size()-1);
Then create the root node from that index.
BST tree = new BST(array.get(midIndex));
Now we need a recursive function that will assign left and right children to a given node after passing in the appropriate index boundaries. The idea here is to add the median value from each subarray in order to get a BST of the smallest height.
The assign child function will take the original BST, a left index, right index, and the integer array. With these values we have 3 special cases and a normal case.
If the right index is less than the left index, return.
If the left and right indexes are the same, insert the value at that index to the tree.
If the right index minus the left index is 1, there are just 2 values there we need to add, so add the left index value and the right index value and return.
Otherwise, get the mid index using the helper function, insert the value at that index into the tree, then call the assignChild function again using new left and right boundaries. The first will be the current left index as the left index and midIndex - 1 as the right index. The other call with have midIndex + 1 as the left index and the current right index as the right index. This process of adding the mid value to the tree and then splitting the left and right indexes up effectively splits the array in half over and over until all the array values are added to the tree in that fashion. This will produce a min height BST.
public static BST minHeightBst(List<Integer> array) {
int midIndex = getMidIndex(0, array.size() - 1);
BST tree = new BST(array.get(midIndex));
assignChild(tree, 0, midIndex-1, array);
assignChild(tree, midIndex+1, array.size()-1, array);
return tree;
}</Integer>
public static void assignChild(BST tree, int left, int right, List<Integer> array) {
if (right < left) return;
if (right - left == 1) {
tree.insert(array.get(left));
tree.insert(array.get(right));
return;
}
if (right == left) {
tree.insert(array.get(left));
return;
}
int midIndex = getMidIndex(left, right);
tree.insert(array.get(midIndex));
assignChild(tree, left, midIndex-1, array);
assignChild(tree, midIndex+1, right, array);
}</Integer>
How would you get the kth largest integer in a BST?
Do a depth first search going to the right and store the integers in an inOrder fashion. So your depth first search function will traverse the right child if it is not null, then add its value to the array, then traverse the left child if it is not null. After traversing all the nodes, the array will have the values sorted in descending order. You just need to return the value at the array at index k-1.
public int findKthLargestValueInBst(BST tree, int k) {
List<Integer> array = new ArrayList<>();
dfs(tree, array);
array.stream().forEach(n -> System.out.println(n));
return array.get(k-1);
}</Integer>
public void dfs(BST tree, List<Integer> array) {
if (tree.right != null) {
dfs(tree.right, array);
}
array.add(tree.value);
if (tree.left != null) {
dfs(tree.left, array);
}
}</Integer>
Given the preOrder traversal values of a BST, how would you recreate the BST?
Implement the BST insert function. Create a new BST out of the first value in the integer array, then loop through the rest of the array, inserting the values into the root of the BST.
class Program {
// This is an input class. Do not edit.
static class BST {
public int value;
public BST left = null;
public BST right = null;
public BST(int value) {
this.value = value;
}
public BST insert(int value) {
if (this.value > value) {
if (this.left == null) {
this.left = new BST(value);
} else {
this.left.insert(value);
}
}
if (this.value <= value) {
if (this.right == null) {
this.right = new BST(value);
} else {
this.right.insert(value);
}
}
return this;
} }
public BST reconstructBst(ArrayList<Integer> preOrderTraversalValues) {
// Write your code here.
BST tree = new BST(preOrderTraversalValues.get(0));
for (int i = 1; i < preOrderTraversalValues.size(); ++i) {
tree.insert(preOrderTraversalValues.get(i));
}
return tree;
}</Integer>
How do you invert a binary tree? (Note: this is not a binary search tree. Just a tree with two or less children per node.)
Just traverse the tree and for each node, switch the right and left children. Then continue the traversal on only non-null children. There are 3 cases each traversal:
If both children are non-null, swap them and traverse both.
If one child is null, set that to the non-null child and set the non-null child to null. Traverse the new non-null child. (This is 2 cases, either left is null or right is null and the other is not.)
How do you find the largest diameter in a binary search tree?
The diameter of a binary search tree is the longest path in the tree, which doesn’t necessarily have to include the root node.
To get it, do a depth first search that returns the height of the node returning. So when you reach a leaf node with no children, return 1 because leaf nodes have height 1.
On parent nodes, record the heights of the children if they exist by calling the same DFS function recursively, and if one of the children don’t exist, just set their height to 0.
To find the appropriate height and diameter of that node, set the diameter to the height of the left child plus the height of the right child. To set the height, get max(rightChildHeight, leftChildHeight) plus 1. In other words, the current node’s height is either the left or right child’s height – whichever is higher – plus one.
After you have your height and diameter, check if the diameter is greater than the largest diameter. If it is, change the largest diameter to the current node’s diameter. Then return its height.
Remember to make the largest diameter value a variable within the class. Passing it through the function recursively isn’t going to work.
