Geek
BAN USER 0of 0 votes
AnswersHow will you Design Twitter Trends. Suggest Algorithm for this
 Geek in India Report Duplicate  Flag  PURGE
Walmart Labs Algorithm
The goal should be , put empty the biggest jar into biggest jar in another set so that you dnt hv to pour a jar from initial container set twice.
To Achieve this , make a max heap of both container sets ,
pop out 1 container from each heap.
pour the water from a to b.
Now if both empty , discard them or if either of them has some water left , put them back in heap again. Increase a counter to C.
Complexity  X*(Logx+ LogY)
Use , a queue a doubly linked list and a hash map , every thing will be O(1). Insert every new element in queue and
insert a new element to head of linked list if it is greater then the head. maintain pointer from queue to node of linked list so that you can delete an element from linked list when it gets popped from queue.
head of l;inked list will have maximum all the times ,.
you can maintain one more doubly linked list in similar fashion to tell you minimum./
Don't let the size of queue exceed k
There is a very good solution which is (n^2) .
it is similar to the solution of finding palindromes in n^2 (not the DP one)
just cponsider each number as an average then start from i1 and i+1 if the verage ius same include them else do incement decrement pointers according to your need
Here comes the logic , doing bfs from the arbitrary node gurantees to give you one end of the diameter because , while doing bfs once you come to a node in diameter , now its similar to starting of bfs from a point in diameter , so whichever end it is farther from it will print that node it the end (and all other nodes will be nearer that it otherwise those would have become the diameter)
 Geek January 21, 2013//before calling this function check if the greatest possible number from x is greater then y or not , if it is gthen a hovernum exist.
// has the numbers of x in sorted form
//compv is a function which compares digits of vectors one by one till digitlevel and if it finds any digit of v1 > v2 it returns 1 , if v1<v2 returns 1 , if all equal then returns 0
bool nextNum(set<int> &sx , vector<int> &y , vector<int> &result){
static int digitlevel = 0;
set<int>::iterator it;
if(digitlevel+1 == y.size()){
result.push_back(*it);
if(compv(result , y , digitlevel) <=0){ //returns 0 if vectors are equal from 0 to digitlevel
result.pop_back();
return 1;
}else{
return 0;
}
}
if(compv(result , y , digitlevel) == 0){
it = sx.lowerbound(y[digitlevel]);
}
for(;it!=sx.end();){
result.push_back(*it);
sx.erase(it++);
digitlevel++;
if(!nextNum(sx,y,result)) return true;
digitlevel;
sx.insert(result.back());
result.pop_back();
}
return 1;
}

Geek
January 20, 2013 Open Chat in New Window
This is how LRU is implemented .
 Geek July 20, 2014