Towhid
BAN USERThere is a easy solution for this. Mix wine from 100 bottles to 1. So, there will be 10 bottles. If one rate die from any of the 10 bottles, the poison is in that 100 bottles. Then make another 10 bottles of win from 100 bottles. That means each bottle contains sample from 10 bottles. Now, one rat should die. Then you know which 10 bottle contains the poison one. Next step is make 5 bottles each contains 2 sample. Next step is easy. So, at most 4 rat will die to find out which one is poisoned.
- Towhid February 19, 2013I think it is possible to solve the problem with O(lgn) with extra memory and parent pointer. Here is the solution
TNode *LCA(TNode *u, TNode *v)
{
stack <TNode *> us, vs;
TNode *tmp_u= u, *tmp_v=v, *tmp_lca=NULL;
while (tmp_u->getParent()!=NULL)
{
us.push(tmp_u->getParent());
tmp_u=tmp_u->getParent();
}
while (tmp_v->getParent()!=NULL)
{
vs.push(tmp_v->getParent());
tmp_v=tmp_v->getParent();
}
while((us.empty()!=true) && ((vs.empty()!=true)) && (us.top()==vs.top()))
{
tmp_lca=us.top();
us.pop();
vs.pop();
}
return tmp_lca;
}
This problem is related to the time and space trade off.
1. Space/Memory is the issue, time is not a prime concern.
Steps:
a. Sort File -1 and File-2 using External sort.
b. Now merge the sorted file File 3.
Almost no extra space required. But it requires O(nlgn+mlgm) time.
2. If the time is the issue and memory is not factor at all.
Steps:
a. Create hash map that map keys to string.
b. Start with either File-1 or File-2. Pick a string and generate a hash key.
c. Store the string in the hash map with the key.
d. Write the string in the file.
e. Pick another string do the same.
f. If there is collision in the hash table, then compare the current string the existing string in the hash table. If they are same, then discard the current string.
g. If the current string and the string in the table is different, then add this current string using chaining method to the hash table. Write down the current string into the File -3.
Complexity:
Time complexity : O(n+m)
Space Complexity: If we take a hash table that can hold O(m) number of keys. Then, if there are lots of duplicates, then the size would be O(m). In worst case, if there is no duplicates, the the total entry in the hash table is O(n+m)
I think the following one is the optimum solution:
class TNode {
public: //declare public for code simplicity
int val;
TNode *left, *right;
}
queue <TNode *> NQ;
int BST(TNode *r)
{
if (r==NULL) return 0;
if ((r->left==NULL) && (r->right==NULL)) return 1;
if ((r->left==NULL) && (r->val>=r->right->val)) return 2;
if ((r->right==NULL) && (r->val>=r->left->val)) return 2;
if ((r->val<r->left->val) ||(r->val<r->right->val)) //Not a BST
{
NQ.add(r->left);
NQ.add(r->right);
return 0;
}
else return 3+BST(r->left)+BST(r->right);
}
TNode *Max(TNode *r){
int max = 0, count = 0;
TNode *tmp, *n;
NQ.add(r);
while (!NQ.empty())
{
n = NQ.front();
NQ.pop();
count = BST(n);
if (count=>max) //keep the first case alive
{
max = count;
tmp = n;
}
}
return tmp;
}
}
First of all, you may not need to sort the index. Because, the index is already sorted. Here is the hint from the question
- Towhid February 23, 2013"
such that the I-th disc is centered on (0,I)
"