peechus
BAN USER- 2of 2 votes
AnswersYou are given an array of both negative and positive integers. You need to rearrange the array such that positive and negative numbers alternate. Also, the order should be same as previous array and only O(1) auxiliary space can be used and time complexity boundation O(n).
- peechus in United States
eg. -2 3 4 5 -1 -6 7 9 1
result – 3 -2 4 -1 5 -6 7 9 1.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm
MIN-HEAP..!!
Given: array of N elements.
To Find: Top K elements.
-Take first K elements from array and build-min-heap --- O(K) time.
-Now take the rest (N-K) elements and compare with root element. IF greater than Root insert into min-heap and perform min-heapify--- O(log K) time.
-In worst case we need to do (N-K) times min-heapify ---O((N-K)log K).
Total worst case time --- O(K) + O((N-K)log K)
Well
### if there is no space constraint then just take an auxiliary array (just like we do in Counting sort). And keep adding one to the index value of elements present in this array.
{
arr1[5] = {2,3,2,4,1};
arr2[arr1[x]] ++;
arr2[5] = {1,2,1,1,0};
}
at the end just traverse the arr2[ ] for count greater than 1. The number of places where you get value greater than 1 is your answer.
### In other case if there is space constraint...then just use the XOR method.
THE BEST THAT WE CAN DO WITH MIN-HEAP..!!
Given: array of N elements.
To Find: Top K elements.
-Take first K elements from array and build-min-heap --- O(K) time.
-Now take the rest (N-K) elements and compare with root element. IF greater than Root insert into min-heap and perform min-heapify--- O(log K) time.
-In worst case we need to do (N-K) times min-heapify ---O((N-K)log K).
Total worst case time --- O(K) + O((N-K)log K)
This question is nearly impossible to solve in less than O(n)..
-Solving n! and etc. etc. is really hectic task.
-Still we can generalize questions like this with "k" missing numbers by using an extra arrays.
-Using one extra Arrays you would take O(n) time to find all the missing "K" numbers.
LOGIC:
1.)Initialize all the elements of extra array to zero.
2.)Traverse the given array form the beginning.
3.)Replace zero with one in the extra array at the index of the element found.
eg: if 57 is found in the given array then replace - extra[57] with 1.
4.)At the end traverse the extra array and note down the index values of the places having 0.
Logic...
-Get the value of (m+n)/2.
-Take two pointers initialise to the starting of both arrays. eg: p&q are two pointers to two arrays a&b.
-Keep on going in both the arrays simultaneously.
int count =0;
while(count != (m+n)/2){
if( a[p]>b[q] )
q++;
count++;
else if( a[p]<b[q] )
p++;
count++;
else // case when a[p] = b[q]
p++;
q++;
count++;
}
-Runtime --O((m+n)/2) to be accurate.
- peechus June 12, 2013Using Splay Trees would provide the best solution here...
-Reasons:
1.)As here we want to keep track of the latest data for the past 10 minutes. Splay trees will have it mostly in the 10 closest node to the root.
2.)Also it solves our problem of one user accessing multiple time by providing faster updates.B'coz Splay trees are designed to give faster 2nd time access which BST does not provide.
You can Google for Splay trees and check for there AWESOME properties...
We can determine this by performing Level Order traversal little carefully...
-Check every node that you dequeue -whether it has children or not.
-If not then it must be the first node of that level and all the nodes following it in the queue must not have children then
-else if - any node after this in the queue has children then the leaves can't be on same level.
I tried my best to explain ..still if any doubts feel free to discuss.
I guess we can use XOR operation here...
--First perform XOR inside each of the arrays independently---o(n)
--Then perform a XOR of the result of the two.
If the final result is zero--this means the arrays are equal.
int xor1=0,xor2=0;
for(int i=0;i<arr1.length;i++){
xor1^=arr1[i];
}
for(int j=0;j<arr2.length;j++){
xor2^=arr2[j];
}
int xor = xor1^xor2;
if(xor>0) printf("Arrays are not equal");
Could you please explain the algo.
- peechus July 29, 2014