CareerCup

How trie?

but if the number is say 9999 u will have to use dat much space..isnt it?

Use a set.

Just curious, what does it mean by O(1)
O(1) for worst case? or average case?

we can use dynamic hashing:
hash table will be of size 10 here... that is, the index of the array will be from 0 to 9 .. and the remaining is same as trie...

Use hashtable implementation with Seperate Chaining !! If the Hash Function is gud(perfect Hashing :P) one can do all these operations in O(1) time ...Otherwise Worst case time will be O(n) but expected time is O(1)...Using tries Expected time will also be O(n) So wont do here

Question must be refined , its not for searching it is get any active element . The answer to this question is combination of Hashing and double linked list approach . after Much discussion i came to this answer , he accepted the answer

int MaximumContigiousSumInACircle(int *A, int *n)
{
int MaxSumInRegularArray = MaximumContigiousSum(A,n);
int MaxContigiousSumFromZeroInARun = A[0], MaxContigiousSumFromZero = 0, FirstIndex = 0;
for(int i = 1; i < n; i++)
{
if(MaxContigiousSumFromZeroInARun + A[i] > A[i])
{
MaxContigiousSumFromZeroInARun += A[i];
if(MaxContigiousSumFromZero < MaxContigiousSumFromZeroInARun)
{
MaxContigiousSumFromZero = MaxContigiousSumFromZeroInARun;
FirstIndex = i;
}
}
else
break;
}
int MaxContigiousSumFromLast = 0, MaxContigiousSumFromLastInARun = A[n - 1];
for(int i = n - 2; i >= 0 && i > FirstIndex; i--)
{
if(MaxContigiousSumFromLastInARun + A[i] > A[i])
{
MaxContigiousSumFromLastInARun += A[i];
if(MaxContigiousSumFromLastInARun > MaxContigiousSumFromLast)
MaxContigiousSumFromLast = MaxContigiousSumFromLastInARun;
}
else
break;
}
if(MaxContigiousSumFromLast + MaxContigiousSumFromZero > MaxSumInRegularArray)
return MaxContigiousSumFromLast + MaxContigiousSumFromZero;
else
return MaxSumInRegularArray;

}

int MaximumContigiousSum(int *A, int n)
{
int MaxSumInARun = A[0], MaxSum = 0;
for(int i = 1; i < n; i++)
{
if(MaxSumInARun + A[i] > A[i])
MaxSumInARun += A[i];
else
MaxSumInARun = A[i];
if(MaxSum < MaxSumInARun)
MaxSum = MaxSumInARun;
}

return MaxSum;
}

Key: Hash code of data
Value: Memory address of this data

If data isn't stored in a single memory cell, then value must has all memory cell addresses which data stored in.

LinkedHashMap

Obviously hashing can solve this issue without any doubt but I would have to answer it to be a Trie..