## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

How about this. Have an auxilary array to hold the frequencies of each input seen in the stream. This array will have size N if the range of input was [0..N-1]. Each input will arrive and get added to the auxilary array. A total counter will also increment.

{{
import java.util.stream.Stream;

public class MedianOfStream {
public static void main(String[] args) {
// assume range of each input int to be in 0.. N-1
final int MAX = 100;
final int [] aux = new int [MAX];
final int total [] = new int ;
Stream.of (0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12)
.forEach(x -> {total++; aux [x]++; });
System.out.println(findMedian (aux, total));

}

private static int findMedian(int[] aux, int tot) {

int i=0, j=0;
while ( i<aux.length ) {
j+=aux[i];
if ( j>=tot/2) return i;
i++;
}
return -1;

}
}

}}

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

As each element from the stream arrives it is added to a frequency table. The size of the frequency table = N if the input is restricted to range 0.. N-1. A total of the number of elements processed from the stream should also be maintained. The median can be read out from the frequency table by adding up frequencies from index=0 and moving to the right till the cumulative frequency = 1/2 (total)

``````import java.util.stream.Stream;

public class MedianOfStream {
public static void main(String[] args) {
// assume range of each input int to be in 0.. N-1
final int MAX = 100;
final int [] aux = new int [MAX];
final int total [] = new int ;
Stream.of (0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12)
.forEach(x -> {total++; aux [x]++; });
System.out.println(findMedian  (aux, total));

}

private static int findMedian(int[] aux, int tot) {

int i=0, j=0;
while ( i<aux.length ) {
j+=aux[i];
if ( j>=tot/2) return i;
i++;
}
return -1;

}
}``````

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

This has the o(nlogn) time complexity
Do rectify me if I am wrong .

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

Test

``test``

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

@ChrisK : There is an answer in the question thread which is correct. That was the answer interviewer was looking for

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

Here interviewer looking for whether you are using both min heap and max heap to solve the problem. Because the problem can be solved in O(n) time using both min heap and max heap.

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

If the interviewer didn't specify that all values are within 1..n, then, I'd use the max and min heaps solution, which would have time complexity for adding N numbers: O(N log N), and time complexity for getting the median: O(1).
Since they mentioned 1..n, probably they'd like to see something like below, with time complexity for adding N numbers: O(N), and time complexity for getting the median: O(N).

``````class Median {
public:
{
if (n >= data_.size()) {
data_.resize(max(n + 1, (uint32_t)(data_.size() * 2)));
}
++data_[n];
++size_;
}
double Get()
{
double median = 0;
if (size_ > 0) {
int idx = (size_ - 1) / 2;
uint32_t v1 = 0;
uint32_t v2 = 0;
GetVals(v1, v2, idx);
median = size_ % 2 == 0 ? (v1 + v2) / 2.0 : v1;
}
return median;
}

private:
void GetVals(uint32_t &v1, uint32_t &v2, int idx)
{
v1 = v2 = 0;
int count = 0;
for (uint32_t i = 0; i < data_.size(); ++i) {
count += data_[i];
if (count > idx) {
v1 = i;
v2 = count > idx + 1 ? i : i + 1;
return;
}
}
}

vector<int> data_;
int size_;
};``````

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

{2
5
3 5 2 4 1
3
9 15 0}

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

use insertion sort. Insertions sort tends to O(n) time for almost sorted arrays.

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

Use insertion sort. It tends to O(n) complexity for almost sorted list.

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

The following is an implementation in Java 8 (`n` is the upper bound of the range):

``````static int median(IntStream strm, int n) {
int[] save = new int[n];
strm.forEach(x -> save[x]++);
for(int i=0; i<n; i++) {
while (save[i] > 0) {
save[i]--;
}
}
return list.get(list.size() / 2);
}``````

And it's called: with:

``System.out.println(median(IntStream.of(1,2,3,4,5,6,7,8,9,10), 12));``

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

There is an algorithm to find the k-th order element in an unsorted array in time O(k) - its much like quicksort() but we recursively operate on just side part. its running time is O(k) amortized time.
since the Median is the K/2 ordered element, we simply activate the above mentioned algorithm on the input array.
if the stream isnt inside an array, we consume it into an array which is O(n).

so its amortized O(n) - not O(n)

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.