Problem - 1: Find the median of two sorted arrays with minimum possible memory and time complexity?
This algorithm is slight modification of quick sort. Suppose we are having two arrays A and B of length Na and Nb respectively. The median of these two arrays would be the element at (Na+Nb)/2 of sorted combination array (A+B).
Let us say M ( Na+Nb )/2. Now to figure out M without using any extra memory we will use divide and conquer approach. Since arrays are already sorted we can take the benefit of this information and we will try to locate Mth largest element in combined array. If median of array A is greater than median of array B that means median lies in Array A[M..Na] and B[1..M] otherwise median will lie in A[1..M] and B[M..Nb]. Now recurs this until we find median M. Here is the implementation for the case where Na = Nb.
declare NOT_FOUND = -1
Median(A, B):
n = length [X] // is same for B
median = FindMedian(A, B, n, 1, n)
if median = NOT_FOUND then
median = FindMedian(B, A, n,1, n)
return median
FindMedian(A, B, n, low, high):
if low > high then
return NOT_FOUND
else
K=(low+high)/2
if(2*k == n and A[n] <= B[1]) then
return A[n]
else if (k < n and B[n-k] <= A[k] <= B[n-k+1]) then
return A[k]
else if( A[k] > B[n-k+1]) then
return FindMedian(A, B, n, low, k-1)
else
return FindMedian(A, B, n, k+1, high)
Time complexity : O(log n)
Space complexity : O(1), constant
Problem - 2: Given an array of N elements initially sorted then it is rotated right K times where 0 <= K <= N. Write a algorithm to find out number of rotation made i.e. K?
To solve this problem we will again use divide and conquer approach. We will apply the same algorithm as Binary search to find out the point where smallest and largest element meet (transition point).
FindNumberOfRotations(A):
1. if (A[0] < A[n-1]) then
There is no rotation made return 0
2. low = 0, high =1
3. mid = (low + high)/2
4. if(A[mid] < A[high]) then
transition lies in left half of the array
if A[mid-1] > A[mid] then return mid
else
high = mid-1
Go to step 3.
else
transition lies in right half of array
if(A[mid] > A[mid+1]) then return mid+1
else
low = mid+1
Go to step 3
Time complexity : O(log n)
Space complexity : O(1), constant
Problem - 3: Find out kth smallest element in two sorted arrays of different size?
We will again use divide and conquer approach and binary search algorithm to solve this problem. We are going to use following information in below algorithm
1. Check if K is smaller or larger than (sizeA+sizeB)/2
2. If k is smaller that means if we sort these two array kth element will be in A otherwise B.
3. Now compare the median of these two array.
4 No we can divide our search based on the information we got from #3.
5. Suppose median of B is greater than median of A. now we can eliminate B[(c+d)/2 - d] elements since kth element is in either A or rest half of B
6. Repeat #5 till we get kth element.
Let us assume we have two arrays A[a..b] and B[c..d]Search (A[a..b], B[c..d], k)
{
sizeA = b - a + 1; sizeB = d - c + 1
if sizeA == 1 then
{
//apply binary search of A[a] in array B[c..d], determine the kth smallest number based on the return location of search
}
else if sizeB == 1 then
{
//apply binary search of B[c] in array A[a..b], determine the kth smallest number based on the return location of search
}
else // both subarrays have at least two elements
{
midA = A[(a+b)/2] // the middle value of subarray A
midB = B[(c+d)/2] // the middle value of subarray B
if midA <= midB then
{
if k <= sizeA/2 + sizeB/2 then
// search the kth smallest but eliminate the right half of B
search(A[a..b], B[c..(c+d)/2], k)
else
// search the (k-(a+b)/2)th smallest but eliminate the left half of A
search(A[(a+b)/2+1..b], B[c..d], k - (a+b)/2)
}
else // if midA > midB
{
if k <= sizeA/2 + sizeB/2 then
// search the kth smallest but eliminate the right half of A
search(A[a..(a+b)/2], B[c..d], k)
else
// search the (k- (c+d)/2)th smallest but eliminate the left half of B
search(A[a..b], B[(c+d)/2+1..d], k-(c+d)/2)
}
}
}
Time complexity : O(log n)
Space complexity : O(1), constant
Problem - 4: We need to show that the elements of A' form a permutation of the elements of A.
Approach - 1
Multiply and add all the elements in both that array, If M = M' and S = S', Yes they form the permutation
+ Complexity would be O(n)
- This can cause multiplication overflow and multiplication is costly operation
Approach - 2
1. Get X-OR of all elements of A and A', X and X' --- O(n) operations
2. for each element i of A
X =^ A[i]
X' =^ A[i]
if X != X'
print "do not form permutation"
break;
+ Complexity would be O(n)
Approach - 3
Sort A and A' if A = A' they form permutation
+ No overflow, Simple approach
- complexity will be O(nlogn)
Problem - 5: Dutch National Flag problem, Three color problem : Partition the given integer array in three parts such that all the elements of part P1 < Part p2 < part p3. (Two color problem sort binary array)
A[N] = { "blue", "red", "red", "green", "red", "green", "blue", "red"};
Partition (A[N]):
_blue = 0;
_red = 0;
_green = N-1;
while(_red <= _green)
{ if (A[_red] == "blue") {
Swap(A[_blue], A[_red])
_blue++, _red++;
}
else if (A[_red] == "red")
_red++;
else {
Swap(A[_green], A[_red])
_green--;
}
}
To solve two color / Binary array problem remove inner 'if else'
Time complexity : O(n)
Space complexity : O(1), constant
Problem - 6: Merge two sorted array
Set A[n] = {2, 11, 54, 87, 99}
Set B[2*n] = = {4, 9, 34, 67, 98, 0, 0, 0, 0, 0}
Merge(B[2n], n ) : indexA=n -1
indexB=n -1
index_new=2n -1
while (index_new >= 0) {
if (A[indexA] < B[indexB]) {
B[index_new] = B[indexB];
indexB--;
index_new--;
}
else {
B[index_new] = A[indexA];
indexA--;
index_new--;
}
// Optimization if A or B can be directly copied if (!(indexB+1)) {
while((index_new+1))
B[index_new--] = A[indexA--];
break;
}
else if (!(indexA+1))
break;
}
Time complexity : O(n)
Space complexity : O(n)
Problem - 7: Check if S has tow elements that sums upto X
Approach - 1
1. Sort the elements in S. Time complexity: O(n log n)
2. Form the set S'= {z : z = x − y for some y ∈ S}. Space complexity: O(n)
3. Sort the elements in S'. Time complexity: O(n log n)
4. If any value in S appears more than once, remove all but one instance. Do the same for S'. Time complexity: O(n)
5. Merge the two sorted sets S and S'. Time complexity: O(n)
6. There exist two elements in S whose sum is exactly x if and only if the same value appears in consecutive positions in the merged output.
Time complexity: O(n)
Total Time complexity : O(n log n)
Total Space complexity : O(n)
Approach -2
One more approach to this is - sort the array and keep to pointers one at beg and one at end
if A[beg]+A[end] > sum then end--
else if A[beg]+A[end] < sum beg++
else return (beg, end)
Total Time complexity : O(n log n)
Total Space complexity : O(1), constant
Problem -8: You have an array. Find the maximum and minimum numbers in less number of comparisons.
We will keep dividing the array in to two parts while we reached below threshold(say 10 elements or whatever u feel comfortable ). return max and min from each array. Comparision 3N/2 - 2
Problem - 9: Sorting for arrays
BubbleSort( A : list of sortable items ) defined as:
n := length( A )
do
swapped := false
n := n - 1
for each i in 0 to n - 1 inclusive do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
swapped := true
end if
end for
while swapped
End
Total Time complexity : O(n2 )
Total Space complexity : O(1), constant
InsertionSort(array A)
begin
for i := 1 to length[A] - 1 do
begin
value := A[i];
j := i - 1;
while j >= 0 and A[j] > value do
begin
A[j + 1] := A[j];
j := j - 1;
end;
A[j + 1] := value;
end;
end;
Total Time complexity : O(n2 )
Total Space complexity : O(1), constant
QuickSort (int[] a, int lo, int hi)
Total Space complexity : O(1), constant
+ It is in place sorting with good avg complexity -
Quick Sort can result into stack overflow because of excessive recursion
MergeSort(int lo, int hi)
// copy back remaining elements of first half (if any)
while (k
a[k++]=b[i++];
}
Total Space complexity : O(n)
This algorithm is slight modification of quick sort. Suppose we are having two arrays A and B of length Na and Nb respectively. The median of these two arrays would be the element at (Na+Nb)/2 of sorted combination array (A+B).
Let us say M ( Na+Nb )/2. Now to figure out M without using any extra memory we will use divide and conquer approach. Since arrays are already sorted we can take the benefit of this information and we will try to locate Mth largest element in combined array. If median of array A is greater than median of array B that means median lies in Array A[M..Na] and B[1..M] otherwise median will lie in A[1..M] and B[M..Nb]. Now recurs this until we find median M. Here is the implementation for the case where Na = Nb.
declare NOT_FOUND = -1
Median(A, B):
n = length [X] // is same for B
median = FindMedian(A, B, n, 1, n)
if median = NOT_FOUND then
median = FindMedian(B, A, n,1, n)
return median
FindMedian(A, B, n, low, high):
if low > high then
return NOT_FOUND
else
K=(low+high)/2
if(2*k == n and A[n] <= B[1]) then
return A[n]
else if (k < n and B[n-k] <= A[k] <= B[n-k+1]) then
return A[k]
else if( A[k] > B[n-k+1]) then
return FindMedian(A, B, n, low, k-1)
else
return FindMedian(A, B, n, k+1, high)
Time complexity : O(log n)
Space complexity : O(1), constant
Problem - 2: Given an array of N elements initially sorted then it is rotated right K times where 0 <= K <= N. Write a algorithm to find out number of rotation made i.e. K?
To solve this problem we will again use divide and conquer approach. We will apply the same algorithm as Binary search to find out the point where smallest and largest element meet (transition point).
FindNumberOfRotations(A):
1. if (A[0] < A[n-1]) then
There is no rotation made return 0
2. low = 0, high =1
3. mid = (low + high)/2
4. if(A[mid] < A[high]) then
transition lies in left half of the array
if A[mid-1] > A[mid] then return mid
else
high = mid-1
Go to step 3.
else
transition lies in right half of array
if(A[mid] > A[mid+1]) then return mid+1
else
low = mid+1
Go to step 3
Time complexity : O(log n)
Space complexity : O(1), constant
Problem - 3: Find out kth smallest element in two sorted arrays of different size?
We will again use divide and conquer approach and binary search algorithm to solve this problem. We are going to use following information in below algorithm
1. Check if K is smaller or larger than (sizeA+sizeB)/2
2. If k is smaller that means if we sort these two array kth element will be in A otherwise B.
3. Now compare the median of these two array.
4 No we can divide our search based on the information we got from #3.
5. Suppose median of B is greater than median of A. now we can eliminate B[(c+d)/2 - d] elements since kth element is in either A or rest half of B
6. Repeat #5 till we get kth element.
Let us assume we have two arrays A[a..b] and B[c..d]Search (A[a..b], B[c..d], k)
{
sizeA = b - a + 1; sizeB = d - c + 1
if sizeA == 1 then
{
//apply binary search of A[a] in array B[c..d], determine the kth smallest number based on the return location of search
}
else if sizeB == 1 then
{
//apply binary search of B[c] in array A[a..b], determine the kth smallest number based on the return location of search
}
else // both subarrays have at least two elements
{
midA = A[(a+b)/2] // the middle value of subarray A
midB = B[(c+d)/2] // the middle value of subarray B
if midA <= midB then
{
if k <= sizeA/2 + sizeB/2 then
// search the kth smallest but eliminate the right half of B
search(A[a..b], B[c..(c+d)/2], k)
else
// search the (k-(a+b)/2)th smallest but eliminate the left half of A
search(A[(a+b)/2+1..b], B[c..d], k - (a+b)/2)
}
else // if midA > midB
{
if k <= sizeA/2 + sizeB/2 then
// search the kth smallest but eliminate the right half of A
search(A[a..(a+b)/2], B[c..d], k)
else
// search the (k- (c+d)/2)th smallest but eliminate the left half of B
search(A[a..b], B[(c+d)/2+1..d], k-(c+d)/2)
}
}
}
Time complexity : O(log n)
Space complexity : O(1), constant
Problem - 4: We need to show that the elements of A' form a permutation of the elements of A.
Approach - 1
Multiply and add all the elements in both that array, If M = M' and S = S', Yes they form the permutation
+ Complexity would be O(n)
- This can cause multiplication overflow and multiplication is costly operation
Approach - 2
1. Get X-OR of all elements of A and A', X and X' --- O(n) operations
2. for each element i of A
X =^ A[i]
X' =^ A[i]
if X != X'
print "do not form permutation"
break;
+ Complexity would be O(n)
Approach - 3
Sort A and A' if A = A' they form permutation
+ No overflow, Simple approach
- complexity will be O(nlogn)
Problem - 5: Dutch National Flag problem, Three color problem : Partition the given integer array in three parts such that all the elements of part P1 < Part p2 < part p3. (Two color problem sort binary array)
A[N] = { "blue", "red", "red", "green", "red", "green", "blue", "red"};
Partition (A[N]):
_blue = 0;
_red = 0;
_green = N-1;
while(_red <= _green)
{ if (A[_red] == "blue") {
Swap(A[_blue], A[_red])
_blue++, _red++;
}
else if (A[_red] == "red")
_red++;
else {
Swap(A[_green], A[_red])
_green--;
}
}
To solve two color / Binary array problem remove inner 'if else'
Time complexity : O(n)
Space complexity : O(1), constant
Problem - 6: Merge two sorted array
Set A[n] = {2, 11, 54, 87, 99}
Set B[2*n] = = {4, 9, 34, 67, 98, 0, 0, 0, 0, 0}
Merge(B[2n], n ) : indexA=n -1
indexB=n -1
index_new=2n -1
while (index_new >= 0) {
if (A[indexA] < B[indexB]) {
B[index_new] = B[indexB];
indexB--;
index_new--;
}
else {
B[index_new] = A[indexA];
indexA--;
index_new--;
}
// Optimization if A or B can be directly copied if (!(indexB+1)) {
while((index_new+1))
B[index_new--] = A[indexA--];
break;
}
else if (!(indexA+1))
break;
}
Time complexity : O(n)
Space complexity : O(n)
Problem - 7: Check if S has tow elements that sums upto X
Approach - 1
1. Sort the elements in S. Time complexity: O(n log n)
2. Form the set S'= {z : z = x − y for some y ∈ S}. Space complexity: O(n)
3. Sort the elements in S'. Time complexity: O(n log n)
4. If any value in S appears more than once, remove all but one instance. Do the same for S'. Time complexity: O(n)
5. Merge the two sorted sets S and S'. Time complexity: O(n)
6. There exist two elements in S whose sum is exactly x if and only if the same value appears in consecutive positions in the merged output.
Time complexity: O(n)
Total Time complexity : O(n log n)
Total Space complexity : O(n)
Approach -2
One more approach to this is - sort the array and keep to pointers one at beg and one at end
if A[beg]+A[end] > sum then end--
else if A[beg]+A[end] < sum beg++
else return (beg, end)
Total Time complexity : O(n log n)
Total Space complexity : O(1), constant
Problem -8: You have an array. Find the maximum and minimum numbers in less number of comparisons.
We will keep dividing the array in to two parts while we reached below threshold(say 10 elements or whatever u feel comfortable ). return max and min from each array. Comparision 3N/2 - 2
Problem - 9: Sorting for arrays
BubbleSort( A : list of sortable items ) defined as:
n := length( A )
do
swapped := false
n := n - 1
for each i in 0 to n - 1 inclusive do:
if A[ i ] > A[ i + 1 ] then
swap( A[ i ], A[ i + 1 ] )
swapped := true
end if
end for
while swapped
End
Total Time complexity : O(n2 )
Total Space complexity : O(1), constant
InsertionSort(array A)
begin
for i := 1 to length[A] - 1 do
begin
value := A[i];
j := i - 1;
while j >= 0 and A[j] > value do
begin
A[j + 1] := A[j];
j := j - 1;
end;
A[j + 1] := value;
end;
end;
Total Time complexity : O(n2 )
Total Space complexity : O(1), constant
QuickSort (int[] a, int lo, int hi)
{
// lo is the lower index, hi is the upper index
// of the region of array a that is to be sorted
int i=lo, j=hi, h;
int x=a[(lo+hi)/2];
// partition
do
if (lo
// lo is the lower index, hi is the upper index
// of the region of array a that is to be sorted
int i=lo, j=hi, h;
int x=a[(lo+hi)/2];
// partition
do
{
while (a[i]
while (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
// recursionwhile (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
if (lo
if (i
Total Time complexity : Avg- O(n log n ), Worst Case - O(n2 )
}
}
Total Space complexity : O(1), constant
+ It is in place sorting with good avg complexity -
Quick Sort can result into stack overflow because of excessive recursion
MergeSort(int lo, int hi)
{
if (lo
Merge(int lo, int m, int hi)if (lo
{
int m=(lo+hi)/2;
mergesort(lo, m);
mergesort(m+1, hi);
merge(lo, m, hi);
}
}int m=(lo+hi)/2;
mergesort(lo, m);
mergesort(m+1, hi);
merge(lo, m, hi);
}
{
int i, j, k;
i=0; j=lo;
// copy first half of array a to auxiliary array b
while (j<=m)
b[i++]=a[j++];
i=0; k=lo;
// copy back next-greatest element at each time
while (k
int i, j, k;
i=0; j=lo;
// copy first half of array a to auxiliary array b
while (j<=m)
b[i++]=a[j++];
i=0; k=lo;
// copy back next-greatest element at each time
while (k
if (b[i]<=a[j])
a[k++]=b[i++];
else
a[k++]=a[j++];
a[k++]=b[i++];
else
a[k++]=a[j++];
// copy back remaining elements of first half (if any)
while (k
a[k++]=b[i++];
}
Total Space complexity : O(n)
C Implementation :
Bubble Sort:extern "C" void Bubble_Sort(int* A, int n)
{
for(int i = 0; i < n; i++)
for( int j= 0; j < n ; j++)
if (A[ j ] > A[ j + 1 ])
swap( A[ j ], A[ j + 1 ] );
}
Selection Sort:
extern "C" void Selection_Sort(int* A, int n)
{
for(int i = 0; i < n; i++)
for( int j= i; j < n ; j++)
if (A[ i ] > A[ j ])
swap( A[ i ], A[ j ] );
}
Insertion Sort:
extern "C" void Intertion_Sort(int* A, int n)
{
int key,i;
for(int j=1;j
{
key=A[j];
i=j-1;
while(A[i]>key && i>=0)
{
A[i+1]=A[i];
i--;
}
A[i+1]=key;
}
}
Quick Sort: Very efficient version optimized for worst case and stack over flow
inline int median3(const int &x, const int &y, const int &z)
{ return x
int partition (int* A, int n)
{
int key = median3(A[0], A[n/2], A[n-1]);
int i = 0;
int j = n-1;
while(--n)
{
while(A[i] < key)i++;
while(A[j] > key)j--;
if(i < j) SWAP(A[i], A[j]);
else return j;
}
}
extern "C" void Quick_Sort(int* A, int n)
{
while(true)
{
if(n < 8)
{
Selection_Sort(A, n);
return;
}
int p = partition(A, n);
int ln = p+1;
int rn = n-ln;
if(ln > rn)
{
Quick_Sort(A+ln, rn);
n = ln;
}
else
{
Quick_Sort(A, ln);
n = rn;
A += ln;
}
}
}
Merge Sort:
void Merge(int* A, int lo, int mid, int hi)
{
int indexB = mid + 1;
int indexA = mid;
int lenA = hi+1;
int lenB = hi - indexB +1;
int * B = new int [lenB];
for(int i = 0; i < lenB; i++)
B[i] = A[indexB+i];
indexB = lenB-1;
while (hi >= 0)
{
if(A[indexA] > B[indexB] )
A[hi--] = A[indexA--];
else
A[hi--] = B[indexB--];
if(indexA < 0)
{
while(indexB >= 0)
A[hi--] = B[indexB--];
break;
}
else if(indexB < 0)
break;
}
delete B;
}
extern "C" void Merge_Sort(int* A, int lo, int hi)
{
if(lo < hi)
{
int mid = (lo+hi)/2;
Merge_Sort(A, lo, mid);
Merge_Sort(A, mid+1, hi);
Merge(A, lo, mid, hi);
}
}
Bubble Sort:extern "C" void Bubble_Sort(int* A, int n)
{
for(int i = 0; i < n; i++)
for( int j= 0; j < n ; j++)
if (A[ j ] > A[ j + 1 ])
swap( A[ j ], A[ j + 1 ] );
}
Selection Sort:
extern "C" void Selection_Sort(int* A, int n)
{
for(int i = 0; i < n; i++)
for( int j= i; j < n ; j++)
if (A[ i ] > A[ j ])
swap( A[ i ], A[ j ] );
}
Insertion Sort:
extern "C" void Intertion_Sort(int* A, int n)
{
int key,i;
for(int j=1;j
{
key=A[j];
i=j-1;
while(A[i]>key && i>=0)
{
A[i+1]=A[i];
i--;
}
A[i+1]=key;
}
}
Quick Sort: Very efficient version optimized for worst case and stack over flow
inline int median3(const int &x, const int &y, const int &z)
{ return x
int partition (int* A, int n)
{
int key = median3(A[0], A[n/2], A[n-1]);
int i = 0;
int j = n-1;
while(--n)
{
while(A[i] < key)i++;
while(A[j] > key)j--;
if(i < j) SWAP(A[i], A[j]);
else return j;
}
}
extern "C" void Quick_Sort(int* A, int n)
{
while(true)
{
if(n < 8)
{
Selection_Sort(A, n);
return;
}
int p = partition(A, n);
int ln = p+1;
int rn = n-ln;
if(ln > rn)
{
Quick_Sort(A+ln, rn);
n = ln;
}
else
{
Quick_Sort(A, ln);
n = rn;
A += ln;
}
}
}
Merge Sort:
void Merge(int* A, int lo, int mid, int hi)
{
int indexB = mid + 1;
int indexA = mid;
int lenA = hi+1;
int lenB = hi - indexB +1;
int * B = new int [lenB];
for(int i = 0; i < lenB; i++)
B[i] = A[indexB+i];
indexB = lenB-1;
while (hi >= 0)
{
if(A[indexA] > B[indexB] )
A[hi--] = A[indexA--];
else
A[hi--] = B[indexB--];
if(indexA < 0)
{
while(indexB >= 0)
A[hi--] = B[indexB--];
break;
}
else if(indexB < 0)
break;
}
delete B;
}
extern "C" void Merge_Sort(int* A, int lo, int hi)
{
if(lo < hi)
{
int mid = (lo+hi)/2;
Merge_Sort(A, lo, mid);
Merge_Sort(A, mid+1, hi);
Merge(A, lo, mid, hi);
}
}
Problem 10: Give an efficient algorithm to determine whether two sets (of size m and n, respectively) are disjoint. Analyze the worst-case complexity in terms of m and n, considering the case where m is substantially smaller than n. n>m.
Approach -1
1. First sort the big set.Time complexity O(n log n)
2. We can now do a binary search with each of the m elements in the 2nd sorted set, looking to see if it exists in the big one.Time complexity O(m log n )
Total Time complexity : O((n+m) log n )
Approach -2
1. First sort the small set. Time complexity O(m log m)
2. We can now do a binary search with each of the n elements in the big set, looking to see if it exists in the small one. Time complexity O(n log n)
Total Time complexity : O((n+m) log m )
Approach - 31. Sort both sets.Time complexity O(m log m + n log n)
2. Observe that once the two sets are sorted, we no longer have to do binary search to detect a common element. We can compare the smallest elements of the two sorted sets, and discard the smaller one if they are not identical. By repeating this idea recursively on the now smaller sets, we can test for duplication in linear time after sorting. Time complexity O(m)Total Time complexity : O(n log n +m log m + m)
Problem - 11: Suppose that you are given a sorted sequence of distinct integers {a1, a2, . . . , an}. Give an O(lg n) algorithm to determine whether there exists an i index such as A[i] = i. For example, in {−10,−3, 3, 5, 7}, a3 = 3. In {2, 3, 4, 5, 6, 7}, there is no such i.
Apply Binary search
beg = 0
end = n-1
Search (A, beg, end):
if(beg > end)
return -1
mid = (beg+end)/2
if(mid > A[mid])
Search(A, beg, mid-1)
else if(mid < A[mid])
Search(A, mid+1, end) else
return mid
End
Total Time complexity : O(log n )
Total Space complexity : O(1), constant
Approach -1
1. First sort the big set.Time complexity O(n log n)
2. We can now do a binary search with each of the m elements in the 2nd sorted set, looking to see if it exists in the big one.Time complexity O(m log n )
Total Time complexity : O((n+m) log n )
Approach -2
1. First sort the small set. Time complexity O(m log m)
2. We can now do a binary search with each of the n elements in the big set, looking to see if it exists in the small one. Time complexity O(n log n)
Total Time complexity : O((n+m) log m )
Approach - 31. Sort both sets.Time complexity O(m log m + n log n)
2. Observe that once the two sets are sorted, we no longer have to do binary search to detect a common element. We can compare the smallest elements of the two sorted sets, and discard the smaller one if they are not identical. By repeating this idea recursively on the now smaller sets, we can test for duplication in linear time after sorting. Time complexity O(m)Total Time complexity : O(n log n +m log m + m)
Problem - 11: Suppose that you are given a sorted sequence of distinct integers {a1, a2, . . . , an}. Give an O(lg n) algorithm to determine whether there exists an i index such as A[i] = i. For example, in {−10,−3, 3, 5, 7}, a3 = 3. In {2, 3, 4, 5, 6, 7}, there is no such i.
Apply Binary search
beg = 0
end = n-1
Search (A, beg, end):
if(beg > end)
return -1
mid = (beg+end)/2
if(mid > A[mid])
Search(A, beg, mid-1)
else if(mid < A[mid])
Search(A, mid+1, end) else
return mid
End
Total Time complexity : O(log n )
Total Space complexity : O(1), constant
Problem - 12: You are given an array contaning +ve integers(a[n]). Find a sub-array from the given array whose sum is maximum.
constraint-: You can't chose 2 consecutive numbers.
Problem - 13: You have an unordered array X of n integers. Find the array M containing n elements where Mi is the product of all integers in X except for Xi. You may not use division. You can use extra memory.
ARRAY - A B C D E F
PASS 1- 1 A AB ABC ABCD ABCDE Now multiply from end of the array
pASS2 - 1.FEDCB AFECD ABFED ABCFE ABCDF ABCDE.1
Problem - 14: Design an O(n) algorithm that, given a list of n elements, finds all the elements that appear more than n/2 times in the list.
Assume the numbers appear in an array nums[n]:
1. Find majority element in 'nums' like below- Time complexity : O( n )
MajorityElement (nums): candidate = nums[0]
count = 1
for i = 1 to n-1 {
if nums[i] == candidate {
count = count+1
} else {
count = count-1
}
if count == 0 {
candidate = nums[i]
count = 1
}
End
2. Now we need to prove that 'candidate' repeats more than n\2 times. There could be only one element in set that can repeat more than n\2 times. since 'candidate' is in majority. count 'candidate' in array.
constraint-: You can't chose 2 consecutive numbers.
Problem - 13: You have an unordered array X of n integers. Find the array M containing n elements where Mi is the product of all integers in X except for Xi. You may not use division. You can use extra memory.
ARRAY - A B C D E F
PASS 1- 1 A AB ABC ABCD ABCDE Now multiply from end of the array
pASS2 - 1.FEDCB AFECD ABFED ABCFE ABCDF ABCDE.1
Problem - 14: Design an O(n) algorithm that, given a list of n elements, finds all the elements that appear more than n/2 times in the list.
Assume the numbers appear in an array nums[n]:
1. Find majority element in 'nums' like below- Time complexity : O( n )
MajorityElement (nums): candidate = nums[0]
count = 1
for i = 1 to n-1 {
if nums[i] == candidate {
count = count+1
} else {
count = count-1
}
if count == 0 {
candidate = nums[i]
count = 1
}
End
2. Now we need to prove that 'candidate' repeats more than n\2 times. There could be only one element in set that can repeat more than n\2 times. since 'candidate' is in majority. count 'candidate' in array.
Time complexity : O( n )
Sub Problem: What if array is sorted?
If array is sorted we can find that element in log(n) time. It Won't be O(1) because you have you don't know whether median repeats n\2 time or not.
1) Let x = A[N/2]
2) Perform binary search for x-1. Let n1 be the position where x-1 fits in i.e. A[n1] <= x-1 < A[n1+1]
3) Perform binary search for x+1. Let n2 be the position where x+1 fits in i.e. A[n2] < x+1 <= A[n2+1]
4) If n2 - n1 -1 >= N/2, then A[N/2] is the element that occured more than N/2 times; else there doesn't exist any such element in the array.
Time complexity : O(log n )
Sub Problem: Design an O(n) algorithm that, given a list of n elements, finds all the elements that appear more than n/4 times.
Approach -1 Count sort can be applied but the space complexity will be huge. TBD -Ajeet Singh 7/1/10 12:44 PM
Approach - 2 There could be only three possible element, If we can do partition of array around these three we can prove the problem easily.
TBD -Ajeet Singh 7/1/10 12:44 PM
Problem - 15: Show that n positive integers in the range 1 to k can be sorted in O(n log k) time. The interesting case is when k << n.
Approach -1 Use a temporary array of size (k-1) and scan the whole array to record the count of each element. rewrite the whole array. Time complexity : O( n )
Space complexity : O( k )Approach - 2 We know the range of elements (1 to k) now partition the array on median (k\2).
a) then again apply quicksort on 1st half with k/4 and for second half use 3k/4.
repeat (a) until beg < end
Time complexity : O( n log k )
Space complexity : O( 1), constant
Sub Problem: What if array is sorted?
If array is sorted we can find that element in log(n) time. It Won't be O(1) because you have you don't know whether median repeats n\2 time or not.
1) Let x = A[N/2]
2) Perform binary search for x-1. Let n1 be the position where x-1 fits in i.e. A[n1] <= x-1 < A[n1+1]
3) Perform binary search for x+1. Let n2 be the position where x+1 fits in i.e. A[n2] < x+1 <= A[n2+1]
4) If n2 - n1 -1 >= N/2, then A[N/2] is the element that occured more than N/2 times; else there doesn't exist any such element in the array.
Time complexity : O(log n )
Sub Problem: Design an O(n) algorithm that, given a list of n elements, finds all the elements that appear more than n/4 times.
Approach -1 Count sort can be applied but the space complexity will be huge. TBD -Ajeet Singh 7/1/10 12:44 PM
Approach - 2 There could be only three possible element, If we can do partition of array around these three we can prove the problem easily.
TBD -Ajeet Singh 7/1/10 12:44 PM
Problem - 15: Show that n positive integers in the range 1 to k can be sorted in O(n log k) time. The interesting case is when k << n.
Approach -1 Use a temporary array of size (k-1) and scan the whole array to record the count of each element. rewrite the whole array. Time complexity : O( n )
Space complexity : O( k )Approach - 2 We know the range of elements (1 to k) now partition the array on median (k\2).
a) then again apply quicksort on 1st half with k/4 and for second half use 3k/4.
repeat (a) until beg < end
Time complexity : O( n log k )
Space complexity : O( 1), constant
Problem - 16: We seek to sort a sequence S of n integers with many duplications, such that the number of distinct integers in S is O(log n). Give an O(n log log n) worst-case time algorithm to sort such sequences.
TBD -Ajeet Singh 7/1/10 12:44 PM
TBD -Ajeet Singh 7/1/10 12:44 PM
Problem - 17: Implement an algorithm that takes an input array and returns only the unique elements in it.
Construct a balanced BST using n elements . Each node can keep a counter . If the key value is already present then we can just increment the counter . Once the BST is constructed , we can scan the original array and for each element in the array we search it in the BST . We check its count value . If it is one then it is accepted otherwise we decrement its count and take the next element from the array . Thus the order of the elements can be preserved .
Problem - 18: You are given an array (unsorted) and for every element i, find the first occurrence of an element j (in the remaining array) that is greater than or equal to i. If no such j occurs then print -1.
Eg: Input---> A={1,3,5,7,6,4,8}
Output---> 3 5 7 8 8 8 -1
if (stack is empty)
push element;
else if(element > stack.top)
{
while - stack is not empty & stack.top < element
{
a = pop;
if (a < element)
print element
}
push element;
}
else
{
push element;
}
Time complexity : O( n )
Space complexity : O( n)
Problem - 19: Finding Kth Max or Min (median) in unsorted array O(Kn) time
function partition(list, left, right, pivotIndex)
pivotValue := list[pivotIndex]
swap list[pivotIndex] and list[right] // Move pivot to end
storeIndex := left
for i from left to right-1
if list[i] < pivotValue
swap list[storeIndex] and list[i]
storeIndex := storeIndex + 1
swap list[right] and list[storeIndex] // Move pivot to its final place
return storeIndex
function select(list, left, right, k)
select pivotIndex between left and right
pivotNewIndex := partition(list, left, right, pivotIndex)
if k = pivotNewIndex
return list[k]
else if k < pivotNewIndex
return select(list, left, pivotNewIndex-1, k)
else
return select(list, pivotNewIndex+1, right, k)
Total Time complexity : O(Kn )
Total Space complexity : O(1), using system stack
Problem - 20: you are given a matrix which is sorted row wise and column wise.You have to print the matrix in sorted order in O(n) without using extra space. Pronlem and Solution: Young tableau
Construct a balanced BST using n elements . Each node can keep a counter . If the key value is already present then we can just increment the counter . Once the BST is constructed , we can scan the original array and for each element in the array we search it in the BST . We check its count value . If it is one then it is accepted otherwise we decrement its count and take the next element from the array . Thus the order of the elements can be preserved .
Problem - 18: You are given an array (unsorted) and for every element i, find the first occurrence of an element j (in the remaining array) that is greater than or equal to i. If no such j occurs then print -1.
Eg: Input---> A={1,3,5,7,6,4,8}
Output---> 3 5 7 8 8 8 -1
if (stack is empty)
push element;
else if(element > stack.top)
{
while - stack is not empty & stack.top < element
{
a = pop;
if (a < element)
print element
}
push element;
}
else
{
push element;
}
Time complexity : O( n )
Space complexity : O( n)
Problem - 19: Finding Kth Max or Min (median) in unsorted array O(Kn) time
function partition(list, left, right, pivotIndex)
pivotValue := list[pivotIndex]
swap list[pivotIndex] and list[right] // Move pivot to end
storeIndex := left
for i from left to right-1
if list[i] < pivotValue
swap list[storeIndex] and list[i]
storeIndex := storeIndex + 1
swap list[right] and list[storeIndex] // Move pivot to its final place
return storeIndex
function select(list, left, right, k)
select pivotIndex between left and right
pivotNewIndex := partition(list, left, right, pivotIndex)
if k = pivotNewIndex
return list[k]
else if k < pivotNewIndex
return select(list, left, pivotNewIndex-1, k)
else
return select(list, pivotNewIndex+1, right, k)
Total Time complexity : O(Kn )
Total Space complexity : O(1), using system stack
Problem - 20: you are given a matrix which is sorted row wise and column wise.You have to print the matrix in sorted order in O(n) without using extra space. Pronlem and Solution: Young tableau
Since matrix is sorted row and col wise -
For Example - M (4*4)
1 5 8 20
2 6 9 24
10 12 15 30
14 16 23 40
We know min M (0, 0) and Max M (P, Q).
PrintMatrix(M[P*Q]):
Max = M [P,Q]
while (M[0, 0] < Max)
print M[0, 0]
M[0, 0] = Max+1
rearrange M[0, 0]
After calling re arrange except M(0,0) everything else is in proper condition. Now we will try to swap M(0,0) to MinimumOf(M - M(0, 0))
Rearrange(M[p*Q], i, j):
if(i+j > p+Q)
return
newI = i
newJ = j
if ((i + 1 <= P) && (M [newI, newJ] > M [i+1, j])
newI = i + 1
newJ = j
if ((j+1 <= Q) && (M [newI, newJ] > M[i,j+1])
newI = i
newJ = j + 1
if ((newI != i) || (newJ != j))
swap( M[i, j], M[newI, newJ])
Rearrange(M, newI, newJ)
No comments:
Post a Comment