Amazon Interview Question Applications Developers
Country: United States
As numbers are keep coming and also in ascending order, process(binary search) these numbers in chunks of fix or incremental size.Processing stop either binary search succeeded or processing of chunk whose last element is greater than the number we are looking for.
Still, you need to store all the numbers( same as if we use map) Binary search is performed that will take log(n). But if map is used complexity will be O(1).
For Binary search or map we will have to store these nos, why should not we compare the no received with desired no rather than storing. If last received no is greater than desired no then halt ur program.
We can use bit vector. Here we need to know about "Number" means, is it integer or it contains float as well. if it's integer, if we consider 4 bytes for integer, the possible integers are 2^32. mean 4 billions. This can be easly tracked by bit vector of 4 billion bits.
we can use byte[0XFFFFFFFF/2]. then if each byte can hold up to 8 integers. for e.g 6, byte[0] (0010 0000), the sixth bit of byte 0 is is set. if say 9 then byte[1] (0000 0010), second bit of byte 1 is set. so with this it takes O(1) time to check whether an integer is already exit by checking the specific bit set or not.
We can use bit vector. Here we need to know about "Number" means, is it integer or it contains float as well. if it's integer, if we consider 4 bytes for integer, the possible integers are 2^32. mean 4 billions. This can be easly tracked by bit vector of 4 billion bits.
we can use byte[0XFFFFFFFF/2]. then if each byte can hold up to 8 integers. for e.g 6, byte[0] (0010 0000), the sixth bit of byte 0 is is set. if say 9 then byte[1] (0000 0010), second bit of byte 1 is set. so with this it takes O(1) time to check whether an integer is already exit by checking the specific bit set or not.
@ Mallu your math is off... a 4 byte integer could only contain numbers 0-31 not 4 billion... you're using it as binary flags and not binary numbers.
Store the last number of the stream in a variable(say t). Keep checking the number with the given number. if it is greater than than the given number. Then check if given number is equal to the last number(t).
if(givenNumber>lastNumber){
if(givenNumber==t){
// It is present in the stream
}
else{
// not Present
}
}
t = lastNumber;
keep checking ur no with the last number if u find no to be greater than the last element print " no not present by this time" if number is < last element then perform binary search.
But, if the numbers keep on coming, wont you be needing infinite or at the least huge memory for the hash table?
We can use bit vector. Here we need to know about "Number" means, is it integer or it contains float as well. if it's integer, if we consider 4 bytes for integer, the possible integers are 2^32. mean 4 billions. This can be easly tracked by bit vector of 4 billion bits.
- Mallu May 12, 2012we can use byte[0XFFFFFFFF/2]. then if each byte can hold up to 8 integers. for e.g 6, byte[0] (0010 0000), the sixth bit of byte 0 is is set. if say 9 then byte[1] (0000 0010), second bit of byte 1 is set. so with this it takes O(1) time to check whether an integer is already exit by checking the specific bit set or not.