Amazon Interview Question
Country: United States
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.
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.
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.
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.
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.
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?
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?
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).
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.
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
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?
lets the stream is 1 2 3 4 5 6 7 8 9 10, initially count = 0, is number of data read so far
- algos October 26, 20121. 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