save.the.w.
BAN USER1. Find length. (Let's call it n)
2. Do a hash for the first n/2 elements
3. Do a revers hash for the next n/2 elements
4. If they match then it's a palindrome.
The list it's not modified at all.
int update(node *x)
{
if (!x)
return 0;
return x->inf += (update(x->left) + update(x->right));
}
bool fibo(int start,int length)
{
if (start < 0)
{
cout << "Invalid start";
return false;
}
if (length < 0)
{
cout << "Invalid length";
return false;
}
if (length == 0)
{
cout << "Lenght = 0";
return true;
}
int a = 0;
int b = 1;
int nr = 1;
if (start == 0)
{
cout << a << " ";
length--;
}
if (start == 1)
{
cout << b << " ";
length--;
}
while (nr < start)
{
a += b;
b = a - b;
nr++;
}
while (length--)
{
a += b;
b = a - b;
cout << a <<' ';
}
return true;
}
only C and D. A can't be because it's a C object that means that watever object it is passed it should at least have all the C methods, and atributes, and A doesn't garantied to have.
- save.the.w. January 14, 2012It's o(N) the answer.
- save.the.w. January 14, 2012
Interesting approach with the heap but I was thinking of a different approach.
- save.the.w. August 13, 2018Same approach for 1H, 1D, etc.
Maintain a sorted array and a Map from word to position in the array.
For each insert you increment the count and move the value to the right into the array.
For expiring values you decrement the values and move the value to the left.
Problems:
1) Have the same count many times and worst case you have O(N) to move an item:
Solution: Keep another map that maps each value where the index is. So your move is O(1)
2) I have 1000s of words coming at the same time.:
We can use a optimistic locking where we keep track of the words we are modiffing right now and unless we are more than 2 count away from any of the words that are processed right then we are ok to modify the array. (No collisions). If not we wait until the +1 count or -1 count finished the change.
(We can also do some batch processing, if we don't want real time)
Interested of what you think about this approach.