Problem Statement: Given a list of integers arrange them in ascending order
Solution: We first create a binary search for the input values and then we do the in-Order traversal of that tree which results in a sorted list of integers.
Author Archives: Nitin Nizhawan
kth Order Statistic (Iterative)
December 24, 2010 – 3:14 pm
Problem Statement: Given a list of numbers and a number ‘k’, find kth smallest element in the list
Solution: kth order statistic problem is also known as selection algorithm. we can use quickselect algorithm for it. This algorithm is also known as Hoare’s selection algorithm. The critical step in this algorithm is to partition the list using a pivot element such that all elements to the left of pivot are smaller than or equal to pivot and all elements to the right are larger or equal to it. Once the list has been partitioned using such a pivot. The position of pivot ‘i’ is the i-th order in the list. The logic for partitioning is same as that used in quick sort. This algorithm is also divide and conquer algorithm. We pick a random element and partition the array using it. If the final position of pivot is equal to the k then pivot is the k-th smallest element, if k is less than the position of pivot then we discard the right sub array and again partition the left sub-array. On the other hand if k is larger that position of pivot then we discard left sub-array and partition the right subarray. we repeat this procedure until we find a pivot such that position of pivot is equal to k. This algorithm as expected (average) running time of O(n) and worst case running time of O(n²).
Radix Sort
December 24, 2010 – 2:43 pm
Problem Statement: Sort in ascending order given a list of numbers
Solution: We use radix sort for it. Radix sort is done by sorting numbers by digits. First numbers are sorted using lowest significant digit then fo r higher significant digits. Usually counting sort used as the sorting algorithm.
Below is a small example
| Input List | Step1 ( one’s place) | Step2( Ten’s place) | Step3(Hundred’s place) |
| 456 | 762 | 9 | 9 |
| 67 | 23 | 23 | 23 |
| 98 | 456 | 456 | 67 |
| 678 | 67 | 762 | 98 |
| 9 | 98 | 67 | 456 |
| 23 | 678 | 678 | 678 |
| 762 | 9 | 98 | 762 |
Counting Sort
December 23, 2010 – 9:41 am
Problem statement: Given a list of integers sort them in ascending order.
Solution:
We will use counting sort for this problem. There are three main steps in counting sort.
Step1. Calculate the number of occurrences of given number in the input list. The numbers in input list range from x to y, where x and y are minimum and maximum numbers in the list these are mapped to range 0 to some value z.
Step2. Find a cumulative sum of all the counts. This cumulative sum reserves space for all the integers in the list.
Step3. For each element in the input list, starting from the last one to the first one, find its new position using cumulative sum we calculated in previous step.
Below is an example to explain above steps in detail
Let input list be 6,5,3,5,6.
min = 3, max = 6
range = max – min +1 = 6 – 3 + 1 = 4
count = 0,0,0,0 // we need count array of length four
// step 1 count the occurrences from minimum to maximum numbers
count = 1,0,2,2 ( 3 is 1 times, 4 is 0 times, 5 is 2 times, 6 is 2 time)
// find cumulative sum.
count = 1,1,3,5
// this cumulative sum say that, 1 space is reserved for minimum item that is 3 so next element should come in at 1 position, then second item in cumulative sum means that 0 space is reserved so next element can come at 1 position. Third element says that 2 spaces are reserved for ‘5’ therefore, next element should come in at 3rd position and lastly 5 says that 2 more spaces are reserved for ‘6’ so next element should come at 5th position.
Now we iterate the input list starting from last element. And we will find its correct position using cumulative sum array.
Let output list be [-,-,-,-,-]
Iter1. Last element is 6 mapping it to 0,z range we get 6 –min = 3, count[3] is 5 so 6 comes in at [-,-,-,-,6], also decrement the count so count is [1,1,3,4]
Iter2. Second last element is 5, mapping it to 0,z range we get 5-min = 2, count[2] is 3 so 5 comes in at [-,-,5,-,6], also decrement the count so count is [1,1,2,4]
Iter 3. Third last element is 3, mapping it to 0,z range we get 3-min =0, count[0] is 1 so 3 comes in at [3,-,5,-,6], also decrement the count so count is [0,1,2,4]
Iter4. Fourth last element is 5, mapping it to 0,z range we get 5 –min = 2, count[2] is 2 so 5 comes in at [3,5,5,-,6] also decrement the count so count is [0,1,1,4]
Iter5. Fifth last element is 6, mapping it to 0,z range we get 6-min = 3, count[3] is 4 so 6 comes in at [3,5,5,6,6] also decrement the count so count is[0,1,1,3]
This gives us the sorted array [3,5,5,6,6]
Running time of this algorithm is O(k*n) where k is the range and n is the number of elements in the list.
Simple Counting Sort
December 23, 2010 – 9:03 am
Problem Statement: Give a list of integers sort them in ascending order.
Solution: To sort a given list of integers we can use counting sort. This particular version of counting sort is a simple one, here we gather statistics about the input list and then regenerate numbers in the list in ascending order. We first calculate the range of numbers in the given list, which can be calculated by finding out maximum and minimum integers. We create an auxiliary storage equals to this range with all elements initialized to zero, this storage will be use to count the occurrence of numbers in input list. Then we iterate over the input list and increment a corresponding element in the auxiliary array.
Once we have the count of each element, starting from each element in the whole range we find out how many times they existed in input list and for that many times we stack elements in the output array.
Example
Input Array : [6,4,3,7,3,7,8]
min = 3, max = 8;
range = 8 – 3 +1 = 6;
count = [0,0,0,0,0,0] ; // 6 items
// after counting the number of items we have
count = [2,1,0,1,2,1];
// explanation , 3 which is the minimum item is 2 times in input array, 4 is 1 times, 5 is 0 times, 6 is 1 times, 7 is 2 times, 8 is 1 times.
// now we have count lets reconstruct the sortedList
now for each element in count
1. i=0;
j will range from 0 to 1 // count[0] is 2
two elements pushed to sortedArray are i+min, 0+3, i.e. 3 and 3, thus after first loop of i, sortedArray = [3,3]
2. i=1
j will range from 0 to 0 // count[1] = 1
one element pushed to sortedArray is i+min, 1+3 = 4, thus after this loop of i, sortedArray = [3,3,4]
3. i=2
j loop will not run // count[2] = 0
no element is pushed to sortedArray , thus after this loop of i, sortedArray = [3,3,4]
4. i=3
j will range from 0 to 0 // count[3] = 1
one element pushed to sortedArray is i+min, 3+3 = 6, thus after this loop of i, sortedArray = [3,3,4,6]
5. i=4;
j will range from 0 to 1 // count[4] is 2
two elements pushed to sortedArray are i+min, 4+3, i.e. 7 and 7, thus after first loop of i, sortedArray = [3,3,4,6,7,7]
6. i=5
j will range from 0 to 0 // count[1] = 1
one element pushed to sortedArray is i+min, 5+3 = 8, thus after this loop of i, sortedArray = [3,3,46,7,7,8]
This particular version of counting sort though simple but is not very useful. There are two disadvantages
1. Sorting time is O(range*(Average number of duplicate number of items) + number of items in input list) = O(k*dup_factor + n) which is more than O(k+n) which is the time complexity of original counting sort algorithm
2. Since we regenerate the numbers, this algorithm is not useful for sorting records based on keys as there is no way to keep track of those references, this can be used only for sorting numbers themselves.
Quick Sort
December 22, 2010 – 2:12 am
Problem Statement: Arrange a given list of integers in ascending order.
Solution: Quicksort is a divide and conquer algorithm. First we pick a random element in the list and find out its correct position in the array. This process is called partitioning the array. Position of this element divides array two parts such that all elements on the left of it are less than or equal to it, and all the elements on the right of it are greater than or equal to it. Partitioning can be done in linear time. We then repeat partitioning procedure on these two parts of the arrays. This algorithm has worst case running time of O(n2) and has average case running time of O(n*log(n)).
Matrix Multiplication
December 21, 2010 – 7:14 am
Problem Statement: Given two matrices, find their product
Solution: Solution is an implementation of two matrices. Wherein we find a dot(inner)product of each row of first matrix with each column of second matrix. For two matrices to be multipliable the first matrix should have same columns as the number of rows in second column.
Suppose first matrix is a m x n matrix and second matrix is n x p matrix. Since we multiply each row of first matrix with each column second matrix and that there are n element is each row of first matrix. The Running time of this simple algorithm is m*n*p. For a simple case when m = p = n we can say that this matrix multiplication algorithm is O(n3)
In Place Merge Sort
December 20, 2010 – 11:13 am
Problem Statement: Given a list of integers sort them in ascending order
Solution: To solve this problem we use in place merge sort algorithm. Inplace merge algorithm works exactly the same way as normal merge sort works, except its merge routine. Which is capable of merging in place without using any additional memory. I works as like this, suppose we are merging following two sub arrays.
Index …… | 4 5 6 7 | 8 9 10 11 …..
Values ….. 2 5 7 9 1 3 4 8 …..
So we have two sub arrays from 4 to 7 and 8 to 11 and values are listed below it
After Pass one since smallest element is on the higher sub array, we will shift elements from lower sub array. So after 1st pass we have. Also partition will move one level up, since there is one less number in upper sub array
Index ….. 4 | 5 6 7 8 | 9 10 11 …..
Values ….. 1 2 5 7 9 3 4 8 …..
After second pass. Now since head of lower sub array has the smallest element we just move ahead the head of lower sub array. so after second pass we have.
Index ….. 4 5 | 6 7 8 | 9 10 11 …..
Values ….. 1 2 5 7 9 3 4 8 …..
After third pass. Now head of the upper subarray has the smallest element. So we move remove it and move all the items up by one position and insert this item in front of the lower sub array. So after third pass we have.
Index ….. 4 5 6 | 7 8 9 | 10 11 …..
Values ….. 1 2 3 5 7 9 4 8 …..
After fourth pass Now head of the upper subarray has the smallest element. So we move remove it and move all the items up by one position and insert this item in front of the lower sub array. So after fourth pass we have.
Index ….. 4 5 6 7 | 8 9 10 | 11 …..
Values ….. 1 2 3 4 5 7 9 8 …..
After fifth pass. just move the head of lower sub array.
Index ….. 4 5 6 7 8 | 9 10 | 11 …..
Values ….. 1 2 3 4 5 7 9 8 …..
After sixth pass. Again just move the head of lower sub array
Index ….. 4 5 6 7 8 9 | 10 | 11 …..
Values ….. 1 2 3 4 5 7 9 8 …..
After seventh pass. Now head of the upper subarray has the smallest element. So we move remove it and move all the items up by one position and insert this item in front of the lower sub array. So after seventh pass we have.
Index ….. 4 5 6 7 8 9 10 | 11 |…..
Values ….. 1 2 3 4 5 7 8 9 …..
After eigth pass. Again just move the head of lower sub array
Index ….. 4 5 6 7 8 9 10 11 ||…..
Values ….. 1 2 3 4 5 7 8 9 …..
Now as we can see all the elements are sorted.
Merge Sort (Recursive)
December 19, 2010 – 12:13 pm
Problem Statement: Given a list of integers, sort them in ascending order.
Solution: To solve this we use merge sort algorithm. Merge sort is divide and conquer recursive algorithm. It has mainly three steps as follows
Step 1. If there is only one element in the list, then it means that its already sorted. This step acts as the base case for the recursion
Step 2. If there are more than one elements in the list, we divide the list in two parts, This step represents the divide part of divide and conquer strategy
Step 3. The we recursively call merge sort to sort these two list, this part is the conquer part of divide and conquer strategy.
Step 4 Once the two parts are sorted we merge them using a merge routine. The merge routines copies the smallest element from the two sub array into the auxiliary array. Since the two sub arrays are sorted, the smallest element is always at the top/front of either of the two sub lists. Once one of the lists has been completely copied over to the auxiliary array we copy remaining elements from the other list sequentially. And as the last step we copy elements from auxiliary array back to original list and return it.
Some Salient points about this algorithm
This algorithm requires a auxiliary array of the same size as the input array. This auxiliary array is required during the merge step to copy the elements. So this algorithm require additional memory of the order of O(n)
The merge routine requires O(n) steps to merge two arrays.
At each step we divide the array by two and then sort and merge them until we have array with size of one. All this takes O(lg(n)) recursive calls. So the running time of merge sort algorithm is of the order of O(n*log(n)).
Alien Language (Google Code Jam)
December 18, 2010 – 6:00 pm
Problem Statement: (copied from Google Code Jam)
After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.
Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.
A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.
Input Description
The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique. These Lines are passed to algorithm as an array of strings. See Sample Input
Sample Input
["3 5 4","abc","bca","dac","dbc","cba","(ab)(bc)(ca)","abc","(abc)(abc)(abc)","(zyx)bc"]
Solution:
This problem appeared in as problem A in Qualification round of 2009 Google Code Jam. Solution of this problem is covered in two steps, first step is to parse the testcases, lets take a testcase from sample testcases “(abc)(abc)(abc)”. This testcase can be parsed as ["abc","abc","abc"].
testcase “(zyx)bc” will be parsed as ["zyx","b","c"]. Each element of parsed array is called a group. Thus parsing a testcase results in a array of groups. Each group denotes possible chracters that can match in that position. Solution involves taking each dictionary word one by one and checking if each alphabet of the dictionary word is in the group in the corresponding position for the given test case.
So for testcase “(abc)(abc)(abc)” which is parsed into ["abc","abc","abc"], initially number of matches is 0
- For Dictionary word “abc”, a exists in first group”abc”, b is in second group “abc”, and c is also in third group”abc”, therefore number of matches is now 1
- For dictionary word “bca”, b is in first group “abc”, c is in second group “abc”, and a is in third group “abc”, therefore number of matches is now 2
- for dictionary word “dac”, d is not in first group “abc”, therefore number of matches stays at 2
- for dictionary word “dbc”, d is not in first group “abc” , therefore number of matches stays at 2
- for dictionary word “cba”, c is in first group “abc”, b is in second group “abc”, a is in third group “abc”, therefore number of matches is now 3, which is the right answer for this testcase.