int atoi( char* pStr ) {
int iRetVal = 0;
if (pStr)
{
while ( *pStr && *pStr <= '9' && *pStr >= '0' )
{
iRetVal = (iRetVal * 10) + (*pStr - '0');
pStr++;
}
}
return iRetVal;
}
If we allow -ve and + signs we need to take care of them as well in the out put and check for invalid characters.
Saturday, September 3, 2011
Atoi
Check if array elements are consecutive
The idea is to check for following two conditions. If following two conditions are true, then return true.
1) max – min + 1 = n where max is the maximum element in array, min is minimum element in array
and n is the number of elements in array.
2) All elements are distinct.
To check if all elements are distinct, we can create a visited[] array of size n.
We can map the ith element of input array arr[] to visited array by using arr[i] – min as index in visited[].
Majority Element
A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).
Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:
I/P : 3 3 4 2 4 4 2 4 4
O/P : 4
I/P : 3 3 4 2 4 4 2 4
O/P : NONE
Using Moore’s Voting Algorithm:
This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.
1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.
findCandidate(a[], size)
1. Initialize index and count of majority element
maj_index = 0, count = 1
2. Loop for i = 1 to size – 1
(a)If a[maj_index] == a[i]
count++
(b)Else
count--;
(c)If count == 0
maj_index = i;
count = 1
3. Return a[maj_index]
Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count,
if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1.
First Phase algorithm gives us a candidate element. In second phase we need to check if the candidate is really a majority element.
Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2.
Example : A[] = 2, 2, 3, 5, 2, 2, 6 , answer : 2.
2. Check if the element obtained in step 1 is majority
printMajority (a[], size)
1. Find the candidate for majority
2. If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3. Else
Print "NONE"
Searching a pivot in the sorted rotated array
Implement the following function, FindSortedArrayRotation, which takes as its input an array of unique integers that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength – 1). An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the array.
Solution:
This time you have to search for the rotation pivot. There is a subtle observation. This problem is in fact the same as finding the minimum element’s index. If the middle element is greater than the right most element, then the pivot must be to the right; if it is not, the pivot must be to the left.
1 2 3 4 5 6 7 8 9 10 11 12 13 | int FindSortedArrayRotation(int A[], int N) { int L = 0; int R = N - 1; while (A[L] > A[R]) { int M = L + (R - L) / 2; if (A[M] > A[R]) L = M + 1; else R = M; } return L;} |
Some Test Cases:
{ 1 }
return 0
return 0
{ 1, 2 }
return 0
{ 2, 1 }
return 1
{ 1, 2, 3 }
return 0
{ 3, 1, 2 }
return 1
{ 2, 3, 1 }
return 2
{ 1, 2, 3, 4, 5 }
return 0
{ 2, 3, 4, 5, 1 }
return 4
{ 3, 4, 5, 1, 2 }
return 3
{ 4, 5, 1, 2, 3 }
return 2
{ 5, 1, 2, 3, 4 }
return 1
{ 1, 2, 3, 4, 5, 6 }
return 0
{ 2, 3, 4, 5, 6, 1 }
return 5
{ 3, 4, 5, 6, 1, 2 }
return 4
{ 4, 5, 6, 1, 2, 3 }
return 3
{ 5, 6, 1, 2, 3, 4 }
return 2
{ 6, 1, 2, 3, 4, 5 }
return 1
{ 6, 8, 1, 2, 4, 5 }
return 2
Searching an Element in a Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently?
At first look, we know that we can do a linear search in O(n) time. But linear search does not need the elements to be sorted in any way.
First, we know that it is a sorted array that’s been rotated. Although we do not know where the rotation pivot is, there is a property we can take advantage of. Here, we make an observation that a rotated array can be classified as two sub-array that is sorted (i.e., 4 5 6 7 0 1 2 consists of two sub-arrays 4 5 6 7 and 0 1 2.
Do not jump to conclusion that we need to first find the location of the pivot and then do binary search on both sub-arrays. Although this can be done in O(lg n) time, this is not necessary and is more complicated.
In fact, we don’t need to know where the pivot is. Look at the middle element (7). Compare it with the left most (4) and right most element (2). The left most element (4) is less than (7). This gives us valuable information — All elements in the bottom half must be in strictly increasing order. Therefore, if the key we are looking for is between 4 and 7, we eliminate the upper half; if not, we eliminate the bottom half.
When left index is greater than right index, we have to stop searching as the key we are finding is not in the array.
Since we reduce the search space by half each time, the complexity must be in the order of O(lg n). It is similar to binary search but is somehow modified for this problem. In fact, this is more general than binary search, as it works for both rotated and non-rotated arrays.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | int rotated_binary_search(int A[], int N, int key) { int L = 0; int R = N - 1; while (L <= R) { // Avoid overflow, same as M=(L+R)/2 int M = L + ((R - L) / 2); if (A[M] == key) return M; // the bottom half is sorted if (A[L] <= A[M]) { if (A[L] <= key && key < A[M]) R = M - 1; else L = M + 1; } // the upper half is sorted else { if (A[M] < key && key <= A[R]) L = M + 1; else R = M - 1; } } return -1;} |
Segregate even and odd nodes in a Linked List
Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear
before all the odd numbers in the modified linked list. Also, keep the order of even and odd numbers same.
Method 1
The idea is to get pointer to the last node of list. And then traverse the list starting from the head node and
move the odd valued nodes from their current position to end of the list.
Algorithm:
1) Get pointer to the last node.
2) Move all the odd nodes to the end.
a) Consider all odd nodes before the first even node and move them to end.
b) Change the head pointer to point to the first even node.
c) Consider all odd nodes after the first even node and move them to the end.
Implement Queue using Stacks
A queue can be implemented using two stacks.
Let queue to be implemented be q and stacks used to implement q be stack1 and stack2.
q can be implemented in two ways:
Method 1 (By making enQueue operation costly)
This method makes sure that newly entered element is always at the top of stack 1,
so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.
enQueue(q, x)
1) While stack1 is not empty, push everything from satck1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it
Method 2 (By making deQueue operation costly)
In this method, in en-queue operation, the new element is entered at the top of stack1.
In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from satck1 to stack2.
3) Pop the element from stack2 and return it.
Method 2 is definitely better than method 1. Method 1 moves all the elements twice in enQueue operation,
while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.
Queue can also be implemented using one user stack and one Function Call Stack.
Below is modified Method 2 where recursion is used to implement queue using only one user defined stack.
enQueue(x)
1) Push x to stack1.
deQueue:
1) If stack1 is empty then error.
2) If stack1 has only one element then return it.
3) Recursively pop everything from the stack1, store the popped item
in a variable res, push the res back to stack1 and return res
The step 3 makes sure that the last popped item is always returned and since the recursion stops when there is only one item in stack1 (step 2), we get the last element of stack1 in dequeue() and all other items are pushed back in step 3.
Levenshtein Distance
int LevenshteinDistance(char s[1..m], char t[1..n])
{
// for all i and j, d[i,j] will hold the Levenshtein distance between
// the first i characters of s and the first j characters of t;
// note that d has (m+1)x(n+1) values
declare int d[0..m, 0..n]
for i from 0 to m
d[i, 0] := i // the distance of any first string to an empty second string
for j from 0 to n
d[0, j] := j // the distance of any second string to an empty first string
for j from 1 to n
{
for i from 1 to m
{
if s[i] = t[j] then
d[i, j] := d[i-1, j-1] // no operation required
else
d[i, j] := minimum
(
d[i-1, j] + 1, // a deletion
d[i, j-1] + 1, // an insertion
d[i-1, j-1] + 1 // a substitution
)
}
}
return d[m,n]
}
|
|
Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
Example : 10,12, 20,30, 25,40,32,31,35,50,60
1) Find the candidate unsorted subarray
a) Scan from left to right and find the first element which is greater than the next element.Let s be the index of such an element. In the above example 1, s is 3 (index of 30).
b) Scan from right to left and find the first element (first in right to left order) which is smaller than the next element (next in right to left order).Let e be the index of such an element.In the above example 1, e is 7 (index of 31).
2) Check whether sorting the candidate unsorted subarray makes the complete array sorted or not. If not, then include more elements in the subarray.
a) Find the minimum and maximum values in arr[s..e]. Let minimum and maximum values be min and max. min and max for [30, 25, 40, 32, 31] are 25 and 40 respectively.
b) Find the first element (if there is any) in arr[0..s-1] which is greater than min, change s to index of this element.There is no such element in above example 1.
c) Find first element (if there is any) in arr[e+1..n-1] which is smaller than max, change e to index of this element.In the above example 1,e is changed to 8 (index of 35)
3) Print s and e.
Find the pair from an sorted array whose difference is x
Here is an inplace solution with O(n) complexity.
i=0,j=1;
while((i!=n-1) or j!=n)
{
/*compare difference of a[j] and a[i]*/
if( (a[j]-[a[i]])>x ) {
i++;j++;
}
else if( (a[j]-a[i]) {
j++;
}
else
{
/*SOLUTION*/
return;
}
}
Find 10 maximum integer out of 1 million integers
You Have File of Containing 1 Million Integers You need To Find 10 Maximum Integer Out of Them.How You Will Do That. What is Time & space Complexity of Algorithm that you will use then optimize the solution.. Constraints- U can't Store Whole File in memory @ one time e.g. if u will do that gigabyte of memory may be required so that should be avoided. Answer: Using the first 10 numbers, build a max heap. Then add each number into the 11th array position (always the 11th position) and perform the up-heap operation. At the end of the input, discard the 11th number in the heap. The remaining numbers will be the 10 maximum. O(n log k) where n = the number of items in the list and k = the number of maximum items you want.
Find whether given tree is a subtree or not
Given two binary trees T1 and T2 which store character data, duplicates allowed. You have to devise an algorithm to decide whether the T2 is a subtree of T1. T1 has millions of nodes and T2 has hundreds of nodes.
Pseudo code :
check( node t1 , node t2 )
{
if ( t1->data == t2->data)
{
return check( t1->left , t2->left ) && check(t1->right, t2->right) ;
}
else
{
return check(t1->left , t2) || check(t1->right , t2);
}
}
Time complexity :O(n) because each node in T1 needs to be visited once.
Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array
Given an array of integers, each element represents the max number of jumps can make forward.
What is the minimum number of element selections to reach the end of the array (starting from the first element) ?
Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3
with the sequence : 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
If an element is 0, then cannot make any jumps
Implementation : Using Dynamic programming -
int find_min_steps(int arr[], int n)
{
// min_steps_dp[i] is an array which
// indicate minimum jumps required to reach i.
int min_steps_dp[20];
int i, temp, next_vacant;
// next_vacant : Is the index in the array whose min_steps needs to be updated
// in the next iteration.
next_vacant = 1;
for(i=0;i= n)
{
min_steps_dp[n-1] = min(min_steps_dp[n-1],min_steps_dp[i] +1);
}
else
{
min_steps_dp[temp] = min(min_steps_dp[temp],min_steps_dp[i]+1);
}
if(temp>next_vacant)
{
for(;next_vacant<temp;next_vacant++)
{
// this loop executes only ONCE for each element in the array, so over the
// course of execution, is an O(n) loop only.
min_steps_dp[next_vacant] =min(min_steps_dp[next_vacant],min_steps_dp[temp]);
}
}
}
for(i=0;i<n;i++)
{
printf("%d ",min_steps_dp[i]);
}
return min_steps_dp[n-1];
}
main()
{
int arr[] = {1,3,5,8,9,2,6,7,6,8,9};
int len;
len = sizeof(arr)/sizeof(arr[0]);
printf("\n MIN steps : %d\n",find_min_steps(arr,len));
}
Friday, September 2, 2011
Maximum size square sub-matrix with all 1s
Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
For example, consider the below binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
The maximum square sub-matrix with all set bits is
1 1 1
1 1 1
1 1 1
Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
For the given M[R][C] in above example, constructed S[R][C] would be:
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 2 2 0
1 2 2 3 1
0 0 0 0 0
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3).
Using the maximum value and its coordinates, we can find out the required sub-matrix.
#include
#define bool int
#define R 6
#define C 5
void printMaxSubSquare(bool M[R][C])
{
int i,j;
int S[R][C];
int max_of_s, max_i, max_j;
/* Set first column of S[][]*/
for(i = 0; i < R; i++)
S[i][0] = M[i][0];
/* Set first row of S[][]*/
for(j = 0; j < C; j++)
S[0][j] = M[0][j];
/* Construct other entries of S[][]*/
for(i = 1; i < R; i++)
{
for(j = 1; j < C; j++)
{
if(M[i][j] == 1)
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
else
S[i][j] = 0;
}
}
/* Find the maximum entry, and indexes of maximum entry
in S[][] */
max_of_s = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
if(max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}
printf("\n Maximum size sub-matrix is: \n");
for(i = max_i; i > max_i - max_of_s; i--)
{
for(j = max_j; j > max_j - max_of_s; j--)
{
printf("%d ", M[i][j]);
}
printf("\n");
}
}
Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Auxiliary Space: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Algorithmic Paradigm: Dynamic Programming
How to find whether two Strings are Anagrams or not
Method 1 : Scan first one and compute sum and product of the ASCII character codes. Do the same for the other and compare the sums and products. You are computing two different hashcodes that are position invariant and by doing a sum and a product, you are reducing a chance of a collision. Overflow (esp in case of product) increases the chances of collision. Method 2 : Just take an array of 256 length and initialize with 0. Now,traverse string1 and just increment the value at index=ascii code of character. Then traverse string2, and this time decrement. At any point if time, if you get -1 then you can break. If you dont find so, then traverse the whole array again to check if all locations are zero then they are anagram. Method 3 : Sort both the strings and compare with each other , if both are same then they are Anagrams else not.
Permutations for a given number
Below are the permutations of string ABC. ABC, ACB, BAC, BCA, CAB, CBA Here is a solution using backtracking./* Function to swap values at two pointers */ void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } /* Function to print permutations of string This function takes three parameters: 1. String 2. Starting index of the string 3. Ending index of the string. */ void permute(char *a, int i, int n) { int j; if (i == n) printf("%s\n", a); else { for (j = i; j <= n; j++) { swap((a+i), (a+j)); permute(a, i+1, n); swap((a+i), (a+j)); //backtrack } } } /* Driver program to test above functions */ int main() { char a[] = "ABC"; permute(a, 0, 2); getchar(); return 0; } Algorithm Paradigm: Backtracking Time Complexity: O(n!)
Pair of indices such that A[i] 十A[j] =K in given Array
Design an efficient algorithm for determining if there exist
a pair of indices such that A[i] 十A[j] =K.
Normal way would cost us O(n^2) complexity. But using Hashing complexity reduces to O(n).
Second approach is to while parsing the array find the complement (K - arr[i]) . Store the array index in to a hash table. In the hash table we search for the complement. if the complement exist, it returns it.
sub pairsum(arr, K)
{
H={}; // Hash array initialize to zero.
for i in range(arr, len)
complement = K - arr[i];
H[arr[i]] = i; // Store the index of array element.
if(H[complement])
return H[complement], arr[i];
}
Inorder Tree Traversal without recursion and without stack!
A threaded binary tree may be defined as follows:
"A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the node."
A threaded binary tree makes it possible to traverse the values in the binary tree via a linear traversal that is more rapid than a recursive in-order traversal.
It is also possible to discover the parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack, albeit slowly.
This can be useful where stack space is limited, or where a stack of parent pointers is unavailable (for finding the parent pointer via DFS).
Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.
1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
Although the tree is modified through the traversal, it is reverted back to its original shape after the completion.Unlike Stack based traversal, no extra space is required for this traversal.
Implementation :
/* A binary tree tNode has data, pointer to left child and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};
/* Function to traverse binary tree without recursion and without stack */
void MorrisTraversal(struct tNode *root)
{
struct tNode *current,*pre;
if(root == NULL)
return;
current = root;
while(current != NULL)
{
if(current->left == NULL)
{
printf(" %d ", current->data);
current = current->right;
}
else
{
/* Find the inorder predecessor of current */
pre = current->left;
while(pre->right != NULL && pre->right != current)
pre = pre->right;
/* Make current as right child of its inorder predecessor */
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}
/* Revert the changes made in if part to restore the original
tree i.e., fix the right child of predecssor */
else
{
pre->right = NULL;
printf(" %d ",current->data);
current = current->right;
} /* End of if condition pre->right == NULL */
} /* End of if condition current->left == NULL*/
} /* End of while */
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
MorrisTraversal(root);
getchar();
return 0;
}
Find two non repeating elements in the given array which contains all repeated elements except two
Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way.
Method 1(Use Sorting)
First sort all the elements. In the sorted array, by comparing adjacent elements we can easily get the non-repeating elements. Time complexity of this method is O(nLogn)
Method 2(Use XOR)
Let x and y be the non-repeating elements we are looking for and arr[] be the input array. First calculate the XOR of all the array elements.
xor = arr[0]^arr[1]^arr[2].....arr[n-1]
All the bits that are set in xor will be set in one non-repeating element (x or y) and not in other. So if we take any set bit of xor and divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. Now if we do XOR of all the elements in first set, we will get first non-repeating element, and by doing same in other set we will get the second non-repeating element.
Let us see an example.
arr[] = {2, 4, 7, 9, 2, 4}
1) Get the XOR of all the elements.
xor = 2^4^7^9^2^4 = 14 (1110)
2) Get a number which has only one set bit of the xor.
Since we can easily get the rightmost set bit, let us use it.
set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010
Now set_bit_no will have only set as rightmost set bit of xor.
3) Now divide the elements in two sets and do xor of
elements in each set, and we get the non-repeating
elements 7 and 9.
Implementation:
#include
#include
/* This finction sets the values of *x and *y to nonr-epeating
elements in an array arr[] of size n*/
void get2NonRepeatingNos(int arr[], int n, int *x, int *y)
{
int xor = arr[0]; /* Will hold xor of all elements */
int set_bit_no; /* Will have only single set bit of xor */
int i;
*x = 0;
*y = 0;
/* Get the xor of all elements */
for(i = 1; i < n; i++)
xor ^= arr[i];
/* Get the rightmost set bit in set_bit_no */
set_bit_no = xor & ~(xor-1);
/* Now divide elements in two sets by comparing rightmost set
bit of xor with bit at same position in each element. */
for(i = 0; i < n; i++)
{
if(arr[i] & set_bit_no)
*x = *x ^ arr[i]; /*XOR of first set */
else
*y = *y ^ arr[i]; /*XOR of second set*/
}
}
/* Driver program to test above function */
int main()
{
int arr[] = {2, 3, 7, 9, 11, 2, 3, 11};
int *x = (int *)malloc(sizeof(int));
int *y = (int *)malloc(sizeof(int));
get2NonRepeatingNos(arr, 8, x, y);
printf(" The non-repeating elements are %d and %d", *x, *y);
getchar();
}
Time Complexity: O(n)
Auxiliary Space: O(1)
Explanation :
XOR of two same numbers results in 0(000..00)
XOR of two different numbers x and y results in a number which contains set bits at the places where x and y differ. So if x and y are 10...0100 and 11...1001, then result would be 01...1101.
So the idea is to XOR all the elements in set.In the result xor, all repeating elements would nullify each other. The result would contain the set bits where two non-repeating elements differ.
Now, if we take any set bit of the result xor and again do XOR of the subset where that particular bit is set, we get the one non-repeating element.And for other non-repeating element we can take the subset where that particular bit is not set.
We have chosen the rightmost set bit of the xor as it is easy to find out.
How to check whether given number is prime or not
Primality Test
Given an input number n, check whether any integer m from 2 to n − 1 divides n. If n is divisible by any m then n is composite, otherwise it is prime. However, rather than testing all m up to n − 1, it is only necessary to test m up to root of n. if n is composite then it can be factored into two values, at least one of which must be less than or equal to root of n. The efficiency can also be improved by skipping all even m except 2, since if any even number divides n then 2 does. It can be improved further by observing that all primes are of the form 6k ± 1, with 2 and 3 being the only exceptions. This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 . This is 3 times as fast as testing all m.
Method to find Square Root
Algorithm:
This method can be derived from (but predates) Newton–Raphson method.
1 Start with an arbitrary positive start value x (the closer to the
root, the better so take x=n/2) .
2 Initialize y = 1.
3. Do following until desired approximation is achieved.
a)Get the next approximation for root using average of x and y
b)Set y = n/x
Implementation:
/*Returns the square root of n. Note that the function */
float squareRoot(float n)
{
/*We are using n itself as initial approximation
This can definitely be improved */
float x = n/2; //n/2 can be closest one.
float y = 1;
float e = 0.000001; /* e decides the accuracy level*/
while(x - y > e)
{
x = (x + y)/2;
y = n/x;
}
return x;
}
/* Driver program to test above function*/
int main()
{
int n = 50;
printf ("Square root of %d is %f", n, squareRoot(n));
getchar();
}
Example:
n = 4 /*n itself is used for initial approximation*/
Initialize x = 4, y = 1
Next Approximation x = (x + y)/2 (= 2.500000),
y = n/x (=1.600000)
Next Approximation x = 2.050000,
y = 1.951220
Next Approximation x = 2.000610,
y = 1.999390
Next Approximation x = 2.000000,
y = 2.000000
Terminate as (x - y) > e now.
For a perfect square number this e would be equal to 0.
Given an array and a sum S output all combination of elements that sum to S
Example: 1 2 3
sum = 3
1+1+1,
2+1
3
Program:
int arr[] = {1,2,3};
void printcombination(int n, int index, int i)
{
static int a[100];
int j;
// sum is equal to zero print all numbers that form the sum.
if(n == 0)
{
for(j =0;j 0)
{
for(j = i; j < 3;j++)
{
a[index] = arr[j];
// call printcombination only when the difference is greater than or equal to zero
if(n-arr[j] >= 0)
printcombination(n-arr[j], index + 1, j);
}
}
}
main()
{
int sum = 3;
printcombination(sum, 0, 0);
return 0;
}
Find the Missing Number
You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.
Example:
I/P [1, 2, 4, ,6, 3, 7, 8]
O/P 5
METHOD 1(Use sum formula)
Algorithm:
1. Get the sum of numbers
total = n*(n+1)/2
2 Subtract all the numbers from sum and
you will get the missing number.
METHOD 2(Use XOR)
1) XOR all the array elements, let the result of XOR be X1.
2) XOR all numbers from 1 to n, let XOR be X2.
3) XOR of X1 and X2 gives the missing number.
Thursday, September 1, 2011
Pattern matching in given String
KMP Algorithm : KMP Algo
To see how to construct failure function examples refer Examples for constructing failure function
To see how to construct failure function examples refer Examples for constructing failure function
Find common elements in an Array
Suppose two arrays are given , we need to find the common elements. case 1 : two arrays are sorted . case 2 : two arrays are unsorted . Answer : case 1 : Do a search as we just move through them as we would merge them. As they are sorted , while searching the element in the 2nd array with the element in the 1st array , we can store the index where it the 1st array element exceeds the 2nd array element. Such that the next search can begin at this stored index. case 2 : Hash both the arrays , wherever collision occurs its a common element.
Tree Traversals without using Recursion
/* Inorder traversal with out using recursion */
int top = -1;
struct node *arr[100];
struct node
{
char data;
struct node *left;
struct node *right;
int visited;
};
static int postIndex = 6;
int search(char in[],int inStrt, int inEnd, char data);
struct node *buildTree(char in[], char pre[], int inStrt, int inEnd);
struct node* newNode(char data);
int search(char arr[], int inStrt, int inEnd, char data)
{
int i;
for(i = inStrt; i <= inEnd; i++)
{
if(arr[i] == data)
{
return i;
}
}
}
struct node *buildTree(char post[], char in[], int inStrt, int inEnd)
{
if(inStrt > inEnd)
return NULL;
// pick the last node from post-order traversal
// which happens to be the root
struct node *tNode = newNode(post[postIndex--]);
// if this node has no childern then return
if(inStrt == inEnd)
return tNode;
// find the index of this node in in-order traversal
int inIndex = search(in, inStrt, inEnd, tNode->data);
tNode->right = buildTree(post, in, inIndex+1, inEnd);
tNode->left = buildTree(post, in, inStrt, inIndex -1);
return tNode;
}
struct node* newNode(char data)
{
struct node *node = (struct node *)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->visited = 0;
return node;
}
void push (struct node *root)
{
arr[++top] = root;
}
struct node *pop(void)
{
return arr[top--];
}
/* Inorder traversal without using recursion */
void printInorder(struct node *root)
{
struct node *temp;
if(root == NULL)
return;
// Push all node onto the stack
while(root != NULL)
{
push(root);
root = root->left;
}
while(top != -1)
{
temp = pop();
printf("%c \t", temp->data);
temp = temp->right;
while(temp != NULL)
{
push(temp);
temp = temp->left;
}
}
printf("top inorder : %d\n", top);
}
/* Pre-order traversal without using recursion */
void printPreorder(struct node *root)
{
struct node *temp;
if(root == NULL)
return 0;
while(root != NULL)
{
printf("%c \t", root->data);
push(root);
root = root->left;
}
while(top != -1)
{
temp = pop();
temp = temp->right;
while(temp != NULL)
{
printf("%c\t", temp->data);
push(temp);
temp= temp->left;
}
}
}
/* Post-order traversal without using recursion */
void printPostorder(struct node *root)
{
struct node *temp;
if(root == NULL)
return 0;
while(root != NULL)
{
push(root);
root = root->left;
}
while(top != -1)
{
temp = pop();
push(temp);
//printf("%c %d\n", temp->data, temp->visited);
temp = temp->right;
while(temp != NULL && temp->visited == 0)
{
temp->visited = 1;
push(temp);
temp= temp->left;
}
temp = pop();
printf("%c\t", temp->data);
}
}
main()
{
char post[] = {'C', 'F', 'G', 'D', 'B', 'E', 'A'};
char in[] = {'C', 'B', 'F', 'D', 'G', 'A', 'E'};
int len = sizeof(post)/sizeof(post[0]);
int i;
struct node *root = buildTree(post, in, 0, len-1);
printf("Print the in order traversal\n");
printInorder(root);
printf("Print the pre-order traversal\n");
printPreorder(root);
printf("\nPrint the post-order traversal\n");
printPostorder(root);
}
Find the 8 digit number
Find a 8-digit number, where the first figure defines the count of zeros in this number, the second figure the count of numeral 1 in this number and so on.... Start with 8 digit number, starting from left to right, first digit indicate number of 0's in 8 digit number, second digit indicate number of 1's in 8 digit number. Similary 7th digit indicate number of 7's in 8 digit number. 70000000 //8 digit number 7 indicate number of 0's in the number. 70000001 //As number of 7's = 1 so 7th place is 1 60000001 //As due to 1 on 7th place number of zeros = 6 60000010 //As 6 is present so 7th place, number of 6's = 1; number of 7's = 0 61000010 //As 1 is present on 7th place ; number of 1's = 1 so 2nd place there should be 1 51000010 //As number of 0's = 5 51000100 //As 5 is present so 6th place is 1 number of 6's = 0; number of 7's = 0 52000100 //As number of 1's = 2 52100100 //As 2 is present on 1st place so 3rd place is 1 42100100 // As number of 0's = 4 so 1st place is 4 42101000 // As 4 is present so 5th place is 1; number of 5's, 6's and 7's = 0; We got the answer as 4210 1000.
Reverse the order of words in a string
For example: Input string is " This is my first post"
Output string will be "post first my is This";
first reverse each word.(complexity o(n))
finally reverse the whole string.(complexity O(n))
total O(n)+O(n) = O(n)
How about pushing tokens using stack and then popping all.
Number of Trailing zeros in n!
We use the fact that zeros occurs only when multiple of 5 gets multiplied to an even number. So it boils down to a problem of finding power of 5 in prime factorization of n!.
int countOfPrimeFactors(int n,int k) // This method gives count of prime factors of k for a given n in n! .
{
int count=0;
while(n>=k)
{
count+=n/k;
k= k*k;
}
return count;
}
main()
{
int n = 20;
printf("Number of zeros : %d\n", countOfPrimeFactors(n,5)); // Find prime factors of 5 in n! .
}
Construct Tree from given Inorder and Preorder traversals
Let us consider the below traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.
A
/ \
/ \
D B E F C
We recursively follow above steps and get the following tree.
A
/ \
/ \
B C
/ \ /
/ \ /
D E F
Algorithm: buildTree()
1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.
/* program to construct tree using inorder and preorder traversals */
#include
#include
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
char data;
struct node* left;
struct node* right;
};
/* Prototypes for utility functions */
int search(char arr[], int strt, int end, char value);
struct node* newNode(char data);
/* Recursive function to construct binary of size len from
Inorder traversal in[] and Preorder traversal pre[]. Initial values
of inStrt and inEnd should be 0 and len -1. The function doesn't
do any error checking for cases where inorder and preorder
do not form a tree */
struct node* buildTree(char in[], char pre[], int inStrt, int inEnd)
{
static int preIndex = 0;
if(inStrt > inEnd)
return NULL;
/* Pick current node from Preorder traversal using preIndex
and increment preIndex */
struct node *tNode = newNode(pre[preIndex++]);
/* If this node has no children then return */
if(inStrt == inEnd)
return tNode;
/* Else find the index of this node in Inorder traversal */
int inIndex = search(in, inStrt, inEnd, tNode->data);
/* Using index in Inorder traversal, construct left and
right subtress */
tNode->left = buildTree(in, pre, inStrt, inIndex-1);
tNode->right = buildTree(in, pre, inIndex+1, inEnd);
return tNode;
}
/* UTILITY FUNCTIONS */
/* Function to find index of value in arr[start...end]
The function assumes that value is present in in[] */
int search(char arr[], int strt, int end, char value)
{
int i;
for(i = strt; i <= end; i++)
{
if(arr[i] == value)
return i;
}
}
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(char data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
/* This funtcion is here just to test buildTree() */
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%c ", node->data);
/* now recur on right child */
printInorder(node->right);
}
/* Driver program to test above functions */
int main()
{
char in[] = {'D', 'B', 'E', 'A', 'F', 'C'};
char pre[] = {'A', 'B', 'D', 'E', 'C', 'F'};
int len = sizeof(in)/sizeof(in[0]);
struct node *root = buildTree(in, pre, 0, len - 1);
/* Let us test the built tree by printing Insorder traversal */
printf("\n Inorder traversal of the constructed tree is \n");
printInorder(root);
getchar();
}
Time Complexity: O(n^2). Worst case occurs when tree is left skewed. Example Preorder and Inorder traversals for worst case are {A, B, C, D} and {D, C, B, A}.
Wednesday, August 31, 2011
Egg Floor Puzzle
http://classic-puzzles.blogspot.com/2006/12/google-interview-puzzle-2-egg-problem.html
Maximum sum such that no two elements are adjacent
Question: Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way. Using Dynamic Programming : you have to maintain an array maxsum[] such that maxsum[i] has the maximum sum till the ith element. and maxsum[i]=max(maxsum[i-2],maxsum[i-3])+arr[i]; and the catch is that we have to include either the 1st element or the 2nd element in the maxsum so maxsum[0]=arr[0]; maxsum[1]=arr[1]; maxsum[2]=arr[0]+arr[2]; now apply the recursive structure from the 4th element onwards. This would take O(n) time and then find the maximum element of maxsum. O(n).
Count number of bits to be flipped to convert A to B
Question: You are given two numbers A and B. Write a program to count number of bits needed to be flipped to convert A to B.
Solution:
1. Calculate XOR of A and B.
a_xor_b = A ^ B
2. Count the set bits in the above calculated XOR result.
countSetBits(a_xor_b)
XOR of two number will have set bits only at those places where A differs from B.
Example:
A = 1001001
B = 0010101
a_xor_b = 1011100
No of bits need to flipped = set bit count in a_xor_b i.e. 4
Find whether a number is power of two
1. A simple method for this is to simply take the log of the number on base2,if you get an integer then number is power of 2. 2. Another solution is to keep dividing the number by two, i.e, do n = n/2 iteratively. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2. #include#define bool int /* Function to check if x is power of 2*/ bool isPowerOfTwo(int n) { if(n == 0) return 0; while(n != 1) { n = n/2; if(n%2 != 0 && n != 1) return 0; } return 1; } /*Driver program to test above function*/ int main() { int test_no = 31; if(isPowerOfTwo(test_no)) printf("%d is a power of 2", test_no); else printf("%d is not a power of 2", test_no); getchar(); } 3. All power of two numbers have only one bit set. So count the no. of set bits and if you get 1 then number is a power of 2.
Find the Number Occurring Odd Number of Times others Even number of times
Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space. Example: I/P = [1, 2, 3, 2, 3, 1, 3] O/P = 3 Algorithm: Do bitwise XOR of all the elements. Finally we get the number which has odd occurrences. Program: #includeint getOddOccurrence(int ar[], int ar_size) { int i; int res = 0; for(i=0; i < ar_size; i++) res = res ^ ar[i]; return res; } /* Diver function to test above function */ int main() { int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2}; printf("%d", getOddOccurrence(ar, 13)); getchar(); }
Add 1 to a given number without arithmetic operators
Write a program to add one to a given number. You are not allowed to use operators like ‘+’, ‘-’, ‘*’, ‘/’, ‘++’, ‘–’ …etc.
Examples: Input: 12 Output: 13 Input: 6 Output: 7 We can use bitwise operators to achieve this. Following are different methods to achieve same using bitwise operators. Method 1 To add 1 to a number x (say 0011000111), we need to flip all the bits after the rightmost 0 bit (we get 0011000000). Finally, flip the rightmost 0 bit also (we get 0011001000) and we are done. #includeint addOne(int x) { int m = 1; /* Flip all the set bits until we find a 0 */ while( x & m ) { x = x^m; m <<= 1; } /* flip the rightmost 0 bit */ x = x^m; return x; } /* Driver program to test above functions*/ int main() { printf("%d", addOne(13)); getchar(); return 0; } Method 2 We know that the negative number is represented in 2′s complement form on most of the architectures. We have the following lemma hold for 2′s complement representation of signed numbers. Say, x is numerical value of a number, then ~x = -(x+1) [ ~ is for bitwise complement ] (x + 1) is due to addition of 1 in 2′s complement conversion To get (x + 1) apply negation once again. So, the final expression becomes (-(~x)). int addOne(int x) { return (-(~x)); } /* Driver program to test above functions*/ int main() { printf("%d", addOne(13)); getchar(); return 0; } Example, assume the machine word length is one *nibble* for simplicity. And x = 2 (0010), ~x = ~2 = 1101 (13 numerical) -~x = -1101 Interpreting bits 1101 in 2′s complement form yields numerical value as -(2^4 – 13) = -3. Applying ‘-’ on the result leaves 3. Same analogy holds for decrement. Note that this method works only if the numbers are stored in 2′s complement form.
Monday, August 29, 2011
Dijkstra's Algo
Algorithm
Illustration of Dijkstra's algorithm search for finding path from a start node to a goal node in a robot motion planning problem. Open nodes represent the "tentative" set. Filled nodes are visited ones, with color representing the distance: the greener, the further. Nodes in all the different directions are explored uniformly, appearing as a more-or-less circular wavefront as Dijkstra's algorithm uses a heuristic identically equal to 0. Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step. Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. Mark all nodes except the initial node as unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node. For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded distance, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set. When we are done considering all of the neighbors of the current node, mark it as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal. The next current node will be the node marked with the lowest (tentative) distance in the unvisited set. If the unvisited set is empty, then stop. The algorithm has finished. Otherwise, set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.Pseudo Code
function Dijkstra(Graph, source): for each vertex v in Graph: // Initializations dist[v] := infinity ; // Unknown distance function from source to v previous[v] := undefined ; // Previous node in optimal path from source end for ; dist[source] := 0 ; // Distance from source to source Q := the set of all nodes in Graph ; // All nodes in the graph are unoptimized - thus are in Q while Q is not empty: // The main loop u := vertex in Q with smallest dist[] ; if dist[u] = infinity: break ; // all remaining vertices are inaccessible from source end if ; remove u from Q ; for each neighbor v of u: // where v has not yet been removed from Q. alt := dist[u] + dist_between(u, v) ; if alt < dist[v]: // Relax (u,v,a) dist[v] := alt ; previous[v] := u ; decrease-key v in Q; // Reorder v in the Queue end if ; end for ; end while ; return dist[] ; end Dijkstra.
Sunday, August 28, 2011
Segregate 0s and 1s in an Array
You are given an array of 0s and 1s in random order. Segregate 0s on left side and 1s on right side of the array. Traverse array only once. Input array = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] Output array = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]This method is also called as Dutch National Flag Problem. With this approach , we can segregate 0s 1s 2s also. *** Refer Dutch National Flag ( Segregation of numbers).Method 1 (Count 0s or 1s)
1) Count the number of 0s. Let count be C. 2) Once we have count, we can put C 0s at the beginning and 1s at the remaining n – C positions in array. Time Complexity: O(n) The method 1 traverses the array two times. Method 2 does the same in a single pass.Method 2 (Use two indexes to traverse)
Maintain two indexes. Initialize first index left as 0 and second index right as n-1. Do following while left < right a) Keep incrementing index left while there are 0s at it b) Keep decrementing index right while there are 1s at it c) If left < right then exchange arr[left] and arr[right]
Longest consecutive substring of 0 and 1
Given and Array of A[1..n] bits, find the length of longest consecutive substring of 0 and 1 such that number of 0s and 1s are equal
temp=0;
1. For each index i, Just +1(the value of temp) when '1' is encountered; -1 in the other case and store in B[i];
2. Go through B, get each distinct value's min and max index
3. The biggest max - min is the result.
Sample:
Input: 1 0 0 0 0 1 1 1 0 0 1 0 1
B: 1 0 -1 -2 -3 -2 -1 0 -1 -2 -1 -2 -1
1: Min = Max = 0
0: Min = 1; Max = 7
-1: Min = 2; Max = 12
-2: Min = 3; Max = 11
-3: Min = Max = 4
The result is 10 : 0 0 1 1 1 0 0 1 0 1
Merging two sorted linked lists
Node* MergeLists(Node* list1, Node* list2){
Node* mergedList;
if(list1 == null && list2 ==null){//if both are null, return null
return null;
}
if(list1 == null){//if list1 is null, simply return list2
return list2;
}
if(list2 == null){//if list2 is null, simply return list1
return list1;
}
if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
mergedList = list1;
}else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
mergedList = list2;
}
while(list1!=null && list2!=null){
if(list1.data < list2.data){
mergedList->next = list1;
list1 = list1->next;
}else{
mergedList->next = list2;
list2 = list2->next;
}
}
if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
mergedList->next = list2;
}else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
mergedList->next = list1;
}
return mergedList;
}
Merging two Sorted Arrays
public void merge(int[] A, int[] B, int[] C) {
int i, j, k, m, n;
i = 0;
j = 0;
k = 0;
m = A.length;
n = B.length;
while (i < m && j < n) {
if (A[i] <= B[j]) {
C[k] = A[i];
i++;
} else {
C[k] = B[j];
j++;
}
k++;
}
if (i < m) {
for (int p = i; p < m; p++) {
C[k] = A[p];
k++;
}
} else {
for (int p = j; p < n; p++) {
C[k] = B[p];
k++;
}
}
}
Reverse a Linked List
/* a function to sort reverse list */
struct node *reverse(struct node *p)
{
struct node *prev, *curr,*next;
prev = NULL;
curr = p;
while (curr != NULL)
{
next = curr-> link;
curr-> link = prev;
prev = curr;
curr = next;
}
return(prev);
}
Saturday, August 27, 2011
Find nth largest in an Array
You have an array of numbers; you need to find the nth largest in the array in 0(n) Solution
Conventional Algo to find Max and Second Max : 1. First element becomes max and second MAX 2. For all elements in Array you compare each element with MAX if it's greater than MAX=element; and SECONDMAX=MAX; else if element > SECONDMAX then second=element.
Tournament Principle :
From the above picture we can see that we have found the max in the array. Now we know 9 is MAX but we can't say 7 is SECOND MAX since that would be wrong. Number of Comparison's to find MAX = (n/2) + logn(n) = (n-1) in the above case so the above algo is also optimal for finding MAX ; since conventional algo also takes the same. To find SECOND MAX take the players that were directly defeated by MAX. i.e. 9 DIRECTLY DEFEATED BY MAX = 8, 3, 7 If we play the above tournament among 8, 3, 7 we get 8 as second MAX we for this tournament we needed just 2 comparison's Total comparisons to find MAX and second MAX using tournament principle = (n/2) + log(n) + log(n) = (n-1) + log(n) Now to find kth MAX we can play (k/2) such tournaments since in one tournament we get MAX and second MAX..then exclude them and play the tournament again(k/2) times So total comparisons to find kth MAX using above method = (k/2) ((n-1) + log(n)) However in the conventional algo it would be (k/2 passes of array)(2n comparisons to find MAX and second MAX) = k * n So tournament algo is more optimal eg:: if k = 4 and n = 8 Comparison's by conventional algo = 4 * 8 = 32 Comparison's by Tournament algo = (4/2) ((7) + 3) = 2 * 10 = 20
Conventional Solution2: Using MAX HEAP Build a max heap in O(n) ; Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. So total time complexity = O(k logn) To understand building MAX heap in O(n) check http://en.wikipedia.org/wiki/Binary_heap
Conventional Algo to find Max and Second Max : 1. First element becomes max and second MAX 2. For all elements in Array you compare each element with MAX if it's greater than MAX=element; and SECONDMAX=MAX; else if element > SECONDMAX then second=element.
Tournament Principle :
From the above picture we can see that we have found the max in the array. Now we know 9 is MAX but we can't say 7 is SECOND MAX since that would be wrong. Number of Comparison's to find MAX = (n/2) + logn(n) = (n-1) in the above case so the above algo is also optimal for finding MAX ; since conventional algo also takes the same. To find SECOND MAX take the players that were directly defeated by MAX. i.e. 9 DIRECTLY DEFEATED BY MAX = 8, 3, 7 If we play the above tournament among 8, 3, 7 we get 8 as second MAX we for this tournament we needed just 2 comparison's Total comparisons to find MAX and second MAX using tournament principle = (n/2) + log(n) + log(n) = (n-1) + log(n) Now to find kth MAX we can play (k/2) such tournaments since in one tournament we get MAX and second MAX..then exclude them and play the tournament again(k/2) times So total comparisons to find kth MAX using above method = (k/2) ((n-1) + log(n)) However in the conventional algo it would be (k/2 passes of array)(2n comparisons to find MAX and second MAX) = k * n So tournament algo is more optimal eg:: if k = 4 and n = 8 Comparison's by conventional algo = 4 * 8 = 32 Comparison's by Tournament algo = (4/2) ((7) + 3) = 2 * 10 = 20 Conventional Solution2: Using MAX HEAP Build a max heap in O(n) ; Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. So total time complexity = O(k logn) To understand building MAX heap in O(n) check http://en.wikipedia.org/wiki/Binary_heap
Code For 3rd largest
int third_biggest(int *arr, int size)
{
int first = INT_MIN, second = INT_MIN, third = INT_MIN;
for(int i=0;i first)
{
third = second;
second = first;
first = arr[i];
}
else if(arr[i] > second)
{
third = second;
second = arr[i];
}
else if(arr[i] > third)
{
third = arr[i];
}
}
return third;
}
Reverse a pair of elements in a linked list.
reverse a pair of elements in a linked list. abcd - badc
// returns head of new list
public Node reverseInPairs(Node head) {
Node first = head;
Node second = first.next;
if (first == null || second == null) {
return head;
// can't reverse a singleton/empty list. head remains the same
}
while (first != null && second != null) {
temp = first.next.next;
second.next = first;
first.next = temp;
first = temp;
second = first.next;
}
return head.next;
}
Detect Loop in a Linked List (faster)
In the last post we discussed about the regular two pointer approach and a bit about its background. Lets look into how we can make it a bit faster.
What can you do here to make it faster. In the regular approach, the faster pointer goes 2 nodes at a time and the slower pointer goes 1 node per iteration. You cannot really change the speed of the slower pointer, because you definitely need to check every node at least once. But what about the fast pointer? Why just have it go 2 nodes per iteration? Why not 3 or more? And what improvements can you get here? Well. the faster it goes the lesser, the number of assigments and null checks when you traverse the faster pointer. This will be helpful, especially when the cycle (loop) is large. But how can fast do can you go. Since you don’t really know, you could do an exponential advancement. What this means is that, start with 2 nodes per iteration, and see if the slower pointer meets it. If not, traverse 4 nodes in the next iteration, and then 8, 16, 32…
Here’s some sample code that illustrates this.
void LinkedList::IsLooped2() {
LNode* first=head;
LNode* second=head;
int i=0;
int k=1;
while(first) {
first=first->next;
i++;
if(second==first) {
cout < < "Found Loopn";
return;
}
if(i==k) {
second=first;
k*=2;
}
}
}
CODE
/* Function to remove loop. Used by detectAndRemoveLoop() */
void removeLoop(struct node *, struct node *);
/* This function detects and removes loop in the list
If loop was there in the list then it returns 1,
otherwise returns 0 */
int detectAndRemoveLoop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;
while (slow_p && fast_p && fast_p->next)
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p)
{
removeLoop(slow_p, list);
/* Return 1 to indicate that loop is found */
return 1;
}
}
/* Return 0 to indeciate that ther is no loop*/
return 0;
}
How to Remove the loop
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.
/* Function to remove loop.
loop_node --> Pointer to one of the loop nodes
head --> Pointer to the start node of the linked list */
void removeLoop(struct node *loop_node, struct node *head)
{
struct node *ptr1 = loop_node;
struct node *ptr2 = loop_node;
// Count the number of nodes in loop
unsigned int k = 1, i;
while (ptr1->next != ptr2)
{
ptr1 = ptr1->next;
k++;
}
// Fix one pointer to head
ptr1 = head;
// And the other pointer to k nodes after head
ptr2 = head;
for(i = 0; i < k; i++)
ptr2 = ptr2->next;
/* Move both pointers at the same pace,
they will meet at loop starting node */
while(ptr2 != ptr1)
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
// Get pointer to the last node
ptr2 = ptr2->next;
while(ptr2->next != ptr1)
ptr2 = ptr2->next;
/* Set the next node of the loop ending node
to fix the loop */
ptr2->next = NULL;
}
Detect Loop in a Single Linked List
The Trivial solutions either took too long or eat more memory. Here is a classic well known appraoch the does constant space O(1) and 0(n) space. This is based of Floyd’s cycle-finding algorithm published in the Journal of ACM is his paper Non-Deterministic Algorithms in 1967. There are many variants and improvements to this original solution. These alogrithms can be used for finding cycles in different Data Strucutres. I will explain how it works when applied to Linked Lists
The idea is to use 2 pointers P1 and P2 intialized to the head. Then traverse the two pointers starting from the head, with P1 moving 1 node at a time and P2 moving 2 nodes at a time. If there is indeed a cycle, the nodes will meet inside the loop, otherwise they will reach the tail.
The code below is a simple straightforward illustration of this. There are ways to make this more efficient. I will discuss this in the next post.
bool LinkedList::IsLoopedTwoPointer1() {
LNode* first=head;
LNode* second=head;
while(first && second &&
first->next && second->next &&
second->next->next)
{
first=first->next;
second=second->next->next;
if(first==second)
{
cout < < "Found Loop" << endl;
return true;
}
}
return false;
}
Bread First Search
- Enqueue the root node.
- Dequeue a node and examine it.
- If the element sought is found in this node, quit the search and return a result.
- Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
- If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
- If the queue is not empty, repeat from Step 2.
Depth First Search
- Push the root node onto a Stack.
- Pop a node from the stack and examine it.
- If the element sought is found in this node, quit the search and return a result.
- Otherwise push all its successors (child nodes) that have not yet been discovered onto the stack. ( *Push Right first then Left )
- If the stack is empty, every node in the tree has been examined – quit the search and return "not found".
- If the stack is not empty, repeat from Step 2.
Doubly Linked Lists
To insert a node to the left of node M :
get_node(N)
N.right_link := M
N.left_link := M.left_link
M.left_link.right_link := N
M.left_link := N
To delete a node N :
N.left_link.right_link := N.right_link
N.right_link.left_link := N.left_link
get_node(N)
N.right_link := M
N.left_link := M.left_link
M.left_link.right_link := N
M.left_link := N
To delete a node N :
N.left_link.right_link := N.right_link
N.right_link.left_link := N.left_link
Inverting a Linked List
We can invert a linked list in place using three pointers:
procedure INVERT(X)
p := X, q := 0
while p \= 0 do
r := q;
q:= p;
p := p.link
q.link := r
end X := q
end INVERT
procedure INVERT(X)
p := X, q := 0
while p \= 0 do
r := q;
q:= p;
p := p.link
q.link := r
end X := q
end INVERT
Subscribe to:
Posts (Atom)