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.
Implement bubble sort.
void bubbleSort(int arr[])
{
int n = arr.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
{
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}What is selection sort?
Find the smallest element using a linear scan and move it to the front (swapping it with the front element). Then, find the second smallest and move it, again doing a linear scan. Continue doing this until all the elements are in place
Implement selection sort.
void sort(int arr[])
{
int n = arr.length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
What is quick sort?
QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.
There are many different versions of quickSort that pick pivot in different ways.
- Always pick first element as pivot.
- Always pick last element as pivot
- Pick a random element as pivot.
- Pick median as pivot.
The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x.
Implement quickSort’s partition method. Pivot should be the last element.
static int partition(int[] arr, int low, int high)
{
int pivot = arr[high];
int i = (low - 1);
for(int j = low; j <= high - 1; j++)
{
if (arr[j] < pivot)
{
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
What is Heap sort?
Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements.
How counting sort works? Explain with example input input: 1,4,1,2,7,5,2.
- ) count in a separate array how many times each object is present in the input.
- ) change the count, by adding the count of the previous object to the current object
- ) go through input and check the corresponding index in the counting array.
- ) remove one from that count on the index and write input value to the position of the remaining count
- ) do this for the whole input
Example:
input: 1,4,1,2,7,5,2
counting array initialized: 0,0,0,0,0,0,0,0
counting array with counts: 0,2,2,0,1,1,0,1
changing counting (adding previous): 0,2,4,4,5,6,6,7
forming output:
input: 1 –> 1st element of counting array: 2 –> remove one (2-1=1) –> put 1 at index 1
changed counting array: 0,1,4,4,5,6,6,7
output: 0,1,0,0,0,0,0
input: 4 –> 4th element of counting array: 5 –> remove one (5-1=4) –> put 4 at index 4
changed counting array: 0,1,4,4,4,6,6,7
output: 0,1,0,0,4,0,0
input: 1 –> 1st element of counting array: 1 –> remove one (1-1=0) –> put 1 at index 0
changed counting array: 0,0,4,4,4,6,6,7
output: 1,1,0,0,4,0,0
input: 2 –> 2nd element of counting array: 4 –> remove one (4-1=3) –> put 2 at index 3
changed counting array: 0,0,3,4,4,6,6,7
output: 1,1,0,2,4,0,0
input: 7 –> 7th element of counting array: 7 –> remove one (7-1=6) –> put 7 at index 6
changed counting array: 0,0,3,4,4,6,6,6
output: 1,1,0,2,4,0,7
input: 5 –> 5th element of counting array: 6 –> remove one (6-1=5) –> put 5 at index 5
changed counting array: 0,0,3,4,4,6,5,6
output: 1,1,0,2,4,5,7
input: 2 –> 2th element of counting array: 3 –> remove one (3-1=2) –> put 2 at index 2
changed counting array: 0,0,2,4,4,6,5,6
output: 1,1,2,2,4,5,7
When is counting sort efficient?
Counting sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted. Consider the situation where the input sequence is between range 1 to 10K and the data is 10, 5, 10K, 5K.
Explain how radix sort works.
we iterate through each digit of the number, grouping numbers by each digit. t. For example, if we have an array of integers, we might first sort by the first digit, so that the 0s are grouped together. Then, we sort each of these groupings by the next digit. We
repeat this process sorting by each subsequent digit, until finally the whole array is sorted.
