## Google Interview Question for Software Engineer / Developers

Interview Type: Phone Interview

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

use Randomize selection algo or median of median Algorithm.
Median of median promises a tighter upperbound of O(n) as compare to randomize select O(n2)
But in practise randomize select is faster as compare to median of median as constants in median of median are large.

Edit:
In my opinion Median of Medians is slower as compare to QuickSelect with randomly chosen pivot in practice (never tested on large data).
Although worst case is O(N2) for Quickselect where as it is O(N) for median of Medians but it is near to impossible to produce worst case scenario for randomly chosen pivot.

I just posted an article on quick select on my blog, too lazy to explain it here as well, interested user can find the code + explanation + linear time complexity analysis (brief) at below link:
ms-amazon.blogspot.in/2013/10/quick-select-select-kth-smallest.html

In case I get some time, I'll post Median of Medians as well.
Hope it helps.
cheers :)

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

Yes, agreed. The same algo i recommended above. This much faster than QuickSelect or Selection algorithm.

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

Sort the array and find the mid point which will be the median of the series....
complexity : O(nlogn)

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

We can find median using random selection algorithm in linear time.

Actually here we are utilizing "5-random-elements method" to find a median in efficient way.

Pick 5 elements at random from
A[1..n], and set q to be their median.
What it is the probability that q is not a good pivot ?
• Let S be the elements of A[1..n] which are in the 10% smallest.
• The probability that an elements picked at random is in S is 0.1.
• q is in S only if at least 3 of the 5 elements that we pick are in S.
• The probability that this happens is
0.15 + 5•0.14 •0.9 + 10• 0.13 •0.92 =
all in S 4 in S,one not in S 2 not in S
= 0.00001 + 0.00045 + 0.00810=0.00856
• This is also the probability that q is in the 10% largest elements.
• In other words: with probability ≥98%, q is a good pivot.

Putting it together, during partition, each time that we need to find a pivot,
we use the “5 random elements” method.
With probability 98%, we find a good pivot.
The overall time that we spend on good partitions is much smaller than
the time we spent on bad partitions.

This algo can be apllied on QuickSelect or Selection algorithm.

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

_If_ the range of numbers, which are _integers_, is O(n) we can use:

``int count[range];  //array of counts (or adjust range if lower limit isn't 0 )``

Traverse your array whilst incrementing counts.

``i.e.,  count[array[i]]++  for each index i from 0 to N-1.``

Then linear sweep count array to find median in the obvious way.

``````accumulate=0;
for(i=0; i<range; i++)
if( 2*(accumulate += count[i] ) > N ) return i;``````

or maybe off by 1 errors above

O(n) guranteed, O(k) storage ( a priori ~ range is O(n) )

This is essentially bucket sort with bucket size=1 modified for finding medians (I just used the idea of quicksort -> quickselect). What would this be called? BucketOneSelect?

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

I don't think the limits of the range: O(n) is a valid assumption in general.
Even the assumption of integer number is questionable.

The method using quick select is a much better solution in practice that can use with any range of input and any type of input.

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

My post is one big implication, with hypotheses I stated :)
Yes, I'd use quickselect under "general" conditions.

Your comment runs fairly orthogonal to my post, and doesn't contradict it.

And careful with "better solution in practice" generalities.

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

Yes quick select is a common algorithm, but here we need to find the most efficient algorithm... that's why i recommended - "Random Selection Algorithm"

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

``````public int findMedian(int[] a) {
int len = a.length;
if (len % 2 == 1)
return quickSelect(a, 0, len, len/2 + 1);
else
return (quickSelect(a, 0, len, len/2) + quickSelect(a, 0, len, len/2 + 1))/2;
}

public int quickSelect(int[] a, int left, int right, int rank) {
int pivot = a[rand(left, right)];
int leftEnd = partition(a, left, right, pivot);
int leftSize = leftEnd - left + 1;

if (leftSize == rank)
return max(a, left, leftEnd);
else if (leftSize < rank)
return quickSelect(a, leftEnd+1, right, rank-leftSize);
else
return quickSelect(a, left, leftEnd, rank);
}

public int partition(int[]a, int left, int right, int pivot) {
while (true) {
while (left <= right && a[left] <= pivot)
left++;
while (left <= right && a[right] > pivot)
right--;

if (left > right)
return left-1;
swap(a, left, right);
}
}

public int max(int[] a, int left, int right) {
int max = Integer.MIN_VALUE;
for (int i = left, i <= right; i++) {
if (a[i] > max)
max = a[i];
}
return max;
}

public int rand(int low, int high) {
return low + Math.random() * (high-low+1);
}

public void swap(int[] a, int left, int right) {
int tmp = a[left];
a[left] = a[right];
a[right] = tmp;
}``````

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

Median of medians algorithm or more commonly known as 'quickselect'.

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

:) Careful

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

``````int quickselect(int a[], int n, int k)
{
assert(n >= k);
if (n==1) return a;
int i(0), lt(0), gt(n-1);
int p = median(a, a[n/2], a[n-1]);
while (i <= gt) {
if (a[i] == p) i++;
else if (a[i] < p) exch(i++, lt++);
else if (a[i] > p) exch(i, gt--);
}
if (k <= lt) return quickselect(a, lt, k);
if (k <= gt) return a[gt-1];
else return quickselect(a+gt+1, n-gt-1, k-gt-1);
}
int median(int a[], int n)
{
if (n&1) return quickselect(a, n, n/2+1);
else return (quickselect(a, n, n/2+1) + quickselect(a, n, n/2) ) /2.0;
}``````

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

Median of Medians is not called quickselect.

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

Yeah median of medians is not called quickselect, but it is based on it.

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

You can also do this in O(n) time and O(n) space with two heaps -- a min heap and a max heap. Push the numbers onto the heaps keeping them equal in size or a max of 1 size difference. Median will be average of the tops of the two heaps if they are equal in size. If they are different sizes (max size difference of 1), median will be the top of the larger heap. This is also a way to continuously determine the median of a stream of integers of indeterminate size.

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

This will be O(n * log n ) time complexity.

This complexity can be minimized by using Median of Median method.

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

Here are the steps to find in linear ( o(n) time
1. Find the max and min elements of the list.
2. Take the avarage of the min and max element.
3. Now subtract the average element from the list.
4. Find the closest element which is close to 0, this will be the median of the list.

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

I don't think this works.

Consider: {2, 3, 1, 8, 19} which has median = 3.

The average of max and min = 10, and thus 8 will be closest to 0.

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

in C++ code

``````int FindNumber(int numbers[], int sequence, int start, int end)
{
if(sequence == start || sequence == end)
return numbers[sequence];
int m = numbers[sequence];
int l = start, r= end;
while(l < r)
{
while(numbers[l]>m)l++;
while(numbers[r]<m)r--;
int temp = numbers[l];
numbers[l] = numbers[r];
numbers[r] = temp;
}
if(sequence >= l) return FindNumber(numbers, sequence, l, end);
else return FindNumber(numbers, sequence, start, r);
}

int FindMedianNumber(int numbers[], int n)
{
return FindNumber(numbers, 4, 0, 9);
}

int numbers = {9,2,4,3,8,5,7,6,1};
cout<< FindMedianNumber(numbers, 9);``````

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

Use Quick Select,
You have to check in n -> even or n -> odd

``````public static float getMedian(int arr[], int n) {
int  p;
int low = 0;
int high = n-1;
p = partition(arr, low, high);
while(p != n/2) {
if(p < n/2) {
low = p+1;
} else {
high = p-1;
}
p = partition(arr, low, high);
}
int p1;
if (n % 2 == 1) {
return(arr[p]);
} else {
low = 0;
high = p-1;
p1 = partition(arr, low, high);
int n1 = n/2 - 1;
while(p1 != n1) {
if(p1 < n1)
low = p1 +1;
else
high = p1 -1;
p1 = partition(arr, low, high);
}
return((float)(arr[p] + arr[p1]) / 2);
}
}``````

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

#include<iostream>
using namespace std;

int sort(int * arr, int l,int h);
void partition(int * arr,int l, int h, int size);
void swap(int * arr, int a, int b);
void display(int * arr, int size);
void main()
{
cout<<"Enter the Size of arry"<<endl;
int size=0;
cin>>size;
int * arr=new int [size];
cout<<endl;
cout<<"Enter the array to sort"<<endl;
for (int i=0;i<size;i++)
cin>>arr[i];
display(arr, size);
partition(arr,0,size-1,size);

system("PAUSE");
}

void partition (int * arr,int l, int h, int size)
{

int pivot=0;
if(l>=h) return;

display(arr,size);
pivot=sort(arr,l,h);
partition(arr,l,pivot-1, size);
partition(arr,pivot+1,h, size);

}

int sort(int * arr, int l, int h)
{
int pivot=arr[l];
int i=l;
int j=h;

while(i<j)
{
while((pivot >= arr[i]) && (i<=h) )
i++;

while((pivot < arr[j]) && (j>=l) )
j--;

if(i<j)
swap(arr,i,j);
}

swap(arr,l,j);
return j;
}

void swap(int * arr, int a, int b)
{
int t=arr[a];
arr[a]=arr[b];
arr[b]=t;
}

void display(int * arr, int size)
{
for(int i=0; i<size;i++)
cout<<arr[i]<<",";
cout<<endl;
}

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

#include<iostream>
using namespace std;

int partition(int * arr, int l, int h,int m);
int search(int * arr, int l, int h);
void swap(int * arr,int a,int b);
void display(int * arr, int size)
{
for(int i=0;i<size;i++)
cout<<arr[i]<<",";
cout<<endl;
}

void main()
{
int size=0;
cout<<"Enter The Size of Array:"<<endl;
cin>>size;
int * arr=new int [size];

for(int i=0; i<size;i++)
{
cout<<"Enter the No::";
cin>>arr[i];
cout<<endl;
}

cout<<partition(arr,0, size-1,size/2);
cout<<endl;
display(arr,size);

system("PAUSE");
}

int partition(int * arr , int l , int h , int m)
{
int p=0;

p=search(arr,l,h);
if(p==m)
{
return arr[p];
}
else if(p<m)
{
partition(arr,p+1,h,m);
}
else
{
partition(arr,l,p-1,m);
}

}

int search(int * arr,int l,int h)
{
int p=arr[l];
int i=l;
int j=h;

while(i<j)
{

while(i<=h && p>=arr[i]) i++;
while(j>=l && p < arr[j]) j--;

if(i<j)
swap(arr,i,j);
}

swap(arr,l,j);
return j;

}

void swap(int * arr,int a,int b)
{
int t=arr[a];
arr[a]=arr[b];
arr[b]=t;
}

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.