algorithms Flashcards
Implement Insertion sort
for(int i = 1; i < arr.length; i++){
int key = arr[i];
int j = i - 1;
while(j >=0 && arr[j]>key){
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
When is best to use Insertion sort?
When array is almost sorted and/or when there are not many elements
Implement merge in merge sort.
public void merge(int[] numbers, int start, int cut, int end){
int leftSize = (cut-start)+1;
int rightSize = end-cut;
int[] left = new int[leftSize];
int[] right = new int[rightSize];
for(int i = 0; i < leftSize; i++){
left[i] = numbers[start+i];
}
for(int i = 0; i < rightSize; i++){
right[i] = numbers[(cut+1)+i];
}
int leftIndex = 0;
int rightIndex = 0;
int k = start;
while(leftIndex < leftSize && rightIndex < rightSize){
if(left[leftIndex] <= right[rightIndex]){
numbers[k] = left[leftIndex];
leftIndex++;
}else{
numbers[k] = right[rightIndex];
rightIndex++;
}
k++;
}
while(leftIndex < leftSize){
numbers[k] = left[leftIndex];
leftIndex++;
k++;
}
while(rightIndex < rightSize){
numbers[k] = right[rightIndex];
rightIndex++;
k++;
}
}
Implement the sort function of merge sort.
void sort(int arr[], int l, int r)
{
if (l < r) {
// Find the middle point
int m =l+ (r-l)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
How does the Rabin-Karp Algorithm work? (describe it)
The Rabin-Karp Algorithm is one of the string pattern searching algorithms.
It works similarly to a brute force algorithm (checking the text for the pattern in each position) but uses a rolling hash instead, so the runtime is much better. The rehashing calculation of course has to be really efficient, it should take constant time.
You could implement it by using these steps:
- calculate hash for pattern
- calculate hash from position 0 until the length of the pattern
- check if hash value is the same, if so, check if characters are the same, if so return
- if there wasn’t a match so far calculate the next hash, be subtracting the hash value of the first character and add the value of the now new last character
- check if the two hash values are the same, if so check if characters are the same, if so return
- and so on, until the end of the text
When calculating hash:
- we need to keep the collisions low
- we need a solution to not use too big numbers
- make sure that each pattern’s hash value depends on not just the characters but the characters position too. So ‘asd’ won’t be the same as ‘das’.
Give an example how to calculating hash for the next position in a Rabin-Karp algorithm.
int prime = any prime number
int d = 10^pattern.length-1
int remove = oldHash - ((OldFirstCharValued) mod prime)
if remove is negative –> remove += prime;
newHash = ((remove10) mod prime+newCharValue) mod prime
Describe the runner technique and some useful applications of it.
You iterate over the linked list with two pointers, one is moving faster than the other.
For example if you want to find the middle point of a linked list, you can have a slower pointer which incremented by one each time, and a faster which incremented by two. When the faster reaches the end you have to be in the middle point with the slower one. (if the list has odd elements it is the middle, but if it’s even you are at the two middle points.)
Implement in-order binary tree traversal
void inOrderTraversal(TreeNode node){
if (node != null){
inOrderTraversal(node.left);
visit(node);
inOrderTraversal(node.right);
}
}Implement a pre-order binary tree traversal.
void preOrderTraversal(TreeNode node){
if (node != null){
visit(node);
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}Implement a post-order binary tree traversal
void postOrderTraversal(TreeNode node){
if (node != null){
postOrderTraversal(node.left);
postOrderTraversal(node.right);
visit(node);
}
}Describe how a new node is inserted in a binary search tree?
- check if tree is empty, if it is add new node as root
- otherwise start from root and compare it with the new node
- if new node is smaller, go left, otherwise go right
- when reached end insert node left if smaller or right if greater
Implement adding a new node to a binary search tree
void insert(Node n){
insert(root,n);
}
void insert(Node root, Node newNode){
if(root == null){
root = newNode;
}
if(newNode < root){
insert(root.left,newNode);
}else{
insert(root.right,newNode);
}
}
How the deletion of a node works in a binary search tree?
if it’s a leaf node just delete it
if it has one child just swap it with child and delete it
if it has two children swap it with it’s in-order successor and delete it
Name the two most common ways to search a graph and explain them.
Depth-first search (DFS): We explore each branch completely before moving on to the next branch. Going deep before going wide.
Breadth-first search (BFS): Explore each neighbor before going on to any children. We go wide before we go deep.
What is bubble sort?
In bubble sort, we start at the beginning of the array and swap the first two elements if the first is greater than the second. Then, we go to the next pair, and so on, continuously making sweeps of the array until it is sorted. In doing so, the smaller items slowly “bubble” up to the beginning of the list.
