## Amazon Interview Question for Applications Developers

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

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 (0010 0000), the sixth bit of byte 0 is is set. if say 9 then byte (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.

Comment hidden because of low score. Click to expand.
0

Bt setting the bits of the vector will take O(n) time for n numbers?

Comment hidden because of low score. Click to expand.
0

Bt setting the bits of the vector will take O(n) time for n numbers?

Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't understand this question. As number keeps coming, just compare them to the number to be found.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Good answer. The other answers miss the point of streaming algorithm requirements.

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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 (0010 0000), the sixth bit of byte 0 is is set. if say 9 then byte (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.

Comment hidden because of low score. Click to expand.
0

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 (0010 0000), the sixth bit of byte 0 is is set. if say 9 then byte (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.

Comment hidden because of low score. Click to expand.
0

@ 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.

Comment hidden because of low score. Click to expand.
0

a 4 byte integer can contain number up to 2^32 - 1 which is 4B -1 so in total it can represent 4 B numbers..0 to 4B- 1

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we store the numbers in a bitmap and check if the bits are set if a number exists ?

Comment hidden because of low score. Click to expand.
0

Bit map is possible if we know the range of numbers.

Comment hidden because of low score. Click to expand.
0
of 0 vote

How to store using map?

Comment hidden because of low score. Click to expand.
0
of 0 vote

How to store using map?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

Comment hidden because of low score. Click to expand.
0

I think it shld be
if(givenNumber < lastNumber )

Comment hidden because of low score. Click to expand.
0
of 0 vote

how about breaking at stream for ex 1,2,3 in int[1,2,3] and put it in treemap where it sort on it own using comparator and then we can always check with the last element of map if the request element is > last element, not yet found but if < last element it in map.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

Use map to store the numbers. complexity: O(1).

Comment hidden because of low score. Click to expand.
0

But, if the numbers keep on coming, wont you be needing infinite or at the least huge memory for the hash table?

Comment hidden because of low score. Click to expand.
0

How to store using map?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.