Amazon Interview Question


Country: United States




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

lets the stream is 1 2 3 4 5 6 7 8 9 10, initially count = 0, is number of data read so far
1. enqueue data into queue, increment count
2. if count is ODD then MID is just read the data at front of the queue
3. if count is EVEN then MID is read the data at front and dequeue that data
4. if count >= M/2 then return

- algos October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you need queue here. Can't we go ahead with simple array and count(if m is not such large). so that at any point of time we can find N/2th element in O(1) complexity as it's just finding the index out of the current count variable. here deletion operation seems to be not considered, So insert and N/2th lookup takes O(1) time.

- Eswar October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you cannot store the numbers , got it

- geek December 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 5 vote

I guess its just like same as finding middle element of given Singly linked list.

- Andi October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Linked list you will have stored data, where as stream data is keep coming and it is not stored anywhere, so you need to store it somewhere and then calculate the middle element.

- algos October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

we can use same strategy,
we can use queue to store data, every time, we read 2 data into the queue, than remove 1 data out of queue,
so at the end of the stream. we will get the middle element in front of the queue, and we need to store n/2 element.

- suwei19870312 June 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

as i don't know m, may be it is a big number and n is less compare to m then it is not good to store the element into array so for that we need to store data into linklist .
take two pointer one slow and one fast pointer . when fast pointer move two step then slow pointer move one step . so just insert the element into linklist (always next to the fast pointer) and modified both fast pointer and slow pointer as i mention above and at the end of the stream the slow pointer should be point to the n/2th position.
let me know if things r not good.

- raunak.gupta29 October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The maximum number of integers that you will need to store is M/4 + 1, which happens when you have encountered M/2 integers. To make this concrete, let M = 8. When you encounter the 4th element, the possible values for N are 4, 5, 6, 7, and 8, so the possible values for N/2 are 2, 3, and 4, so you need to hold on to the 2nd, 3rd, and 4th elements.

From a pragmatic standpoint, one of the other posters pointed out that you might as well pre-allocate an array of M/2 integers, to avoid having to resize the array as N increases and early values are no longer relevant. Keeping things simple is always sound advice, and this program is gonna require linear space for sure.

If you really want to save space, I'd recommend a circular queue. A circular queue is a perfect data structure for a queue that you know will never exceed a certain capacity, which is exactly in the wheelhouse of this problem.

- showell30@yahoo.com October 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

We can start with keeping pointer on 1st node. Every second element comes in stream we can increment the pointer.

- jenish.shah October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Take an array of size M/2. (fast pointer slow pointer approach)Start keeping the stream into the array. Slow index is 0 and Fast index is also 0 in the start. Once fast index is incremented twice then increment slow index once. When the fast pointer reach the end of the array of size M/2(At this point slow will be at M/4). After this point we don't need to write anything just increment the slow index for every two element of the stream read. Finally you will have the slow index at the N/2 element.

- hjain1011 October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

we sould use sizeof function to get the size of the array.
and then divide by 2.
get the value of the middle number.
is that right?

- sandy October 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this ans actually answers what the question asks.

- Daru October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Isn't this question about "space" complexity? I see everyone's discussing time complexity and/or something else. O(M) is the obvious answer, can anyone come up with anything better?

- Chris October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For any n elements currently in the stream, we don't care about any elements less than n/2, so we have to keep the upper n/2 elements in memory. If n>M/2, the index of our middle element is at maximum M/2 and at minimum n/2 so we only have to keep M/2 - n/2 elements in memory. So for n<M/2, efficiency is O(n), and for n>M/2, efficiency is O(M-n).

- Sam November 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You could use an array of M elements, keep the count of the number of elements coming from the stream and just return the N/2th. That would be O(1) in time complexity indeed, but the question is about space complexity.

algos' algorithm is correct. Use a linked list, push the elements from the stream one by one at the back of that list and keep a counter N of the number of elements you read.
If it is the end of the stream, return the front element of the list. Otherwise, and if N is even, delete the first element from the list.

That algorithm uses a N/2 size list.

That being said, resizing a list is O(N) time complexity, so you might as well declare a M/2 size list to prevent any resizing.

However, if the stream is only "numbers" as in "decimals" in [0;9], I would use a size M string and return the middle element. Not sure how linked lists are handled internally but it doesn't seem right to use one to store something that fits on a byte.

- Victor October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def stream(n):
    for i in range(n):
        yield 100 * (i + 1)

def find_mid_value(m, data):
    # Take advantage of the fact that
    # we can overwrite early values, so
    # we use an array that is just
    # a little bigger than m / 4.
    max_mid = (m+1) / 2 - 1
    arr_size = (max_mid/2) + 2
    arr = []
    n = 0
    for value in data:
        if n <= max_mid:
            if n < arr_size:
                arr.append(value)
            else:
                arr[n - arr_size] = value
        n += 1
    mid_pos = (n + 1) / 2 - 1
    return arr[mid_pos % arr_size]

for n in [1, 2, 3, 4, 5]:
    for m in range(n, 20):
        data = stream(n)
        mid = find_mid_value(m, data)
        print n, mid, m

- showell30@yahoo.com October 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use fast and slow pointers... O(n) complexity
- Initialize two pointers p,q to point to the first element... at every iteration, increment p by 2 and q by 1. When p reaches the end, q will point to the middle element...

- Rahul Arakeri December 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not just cache the element you think is the middle compared to the number of elements you've read? Like, first element is middle and every odd entry you discard the first you had saved.

1 --> 1 middle
1 2 3 --> discard 1 and 2 is the middle
2 3 4 5 --> discard 2 and 3 is the middle
3 4 5 6 7 --> discard 3 and 4 is the middle

With that the space complexity would be O(N/2).. wouldnt it?

- Ed Morales June 12, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More