## Google Interview Question for Software Engineer / Developers

• 3

Country: Switzerland

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

The second problem:
Comparing to the first problem we are now also given 'min' and 'max'. Notice that min and max are actually two of the input integers a,b and c. One can use two important properties of the bitwise XOR operator:
a) If we XOR two identical numbers we get zero.
b) If we XOR any number with zero we get identity.

The solution is then to XOR all values. A sample code is shown below:

``````public static int median(int a, int b, int c, int min, int max) {
return a^b^c^min^max;
}``````

Example: Let say that min = c, max = b then it follows
a^b^c^min^max = a^(b^max)^(c^min) = a^0^0 = a

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

Awesome, it works!

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

Why did you assume that min and max are one of the initial a, b, c ??
This is not mentioned anywhere.

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

When I read the problem to me it was obvious that I have some extra information about the numbers a,b and c, its max and min values, and interviewer wants me to take advantage of this extra information. Otherwise the problem would be just to find median of five integers [ a b c d e f] which is far less interesting task and maybe something the interviewer does not want.

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

@autoboli
After giving it a second thought, you are right and your solution is very smart.
I give it a thumb up

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

Good thinking !

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

"^" should be safer than "+". Because "+" may cause overflow for big number.

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

The first problem: Maybe it is too simple but I would propse the following solution:

``````public static int median(int a, int b, int c) {
if ( (a <= b && b <= c) || (c <= b && b <= a) ) 	return b;
if ( (b <= a && a <= c) || (c <= a && a <= b) ) 	return a;
return c;
}``````

The question is how the function should behave if the input does not contain unique integers.

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

for input a = 10, b = 15, c = 5

in your first "if": c <= b && c <= a returns 15 which is false

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

for input a = 10, b = 15, c = 5
your method returns 15 (from the 1st "if") which is false

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

``````int median(int a, int b, int c){

return (a<b) ? Math.Min( b, Math.Max(a, c))
: Math.Min(a, c)

}``````

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

for A=3, B=2, C=1 you return C

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

This is what I did:

``````int median(int a, int b, int c){
//all zeros? all same?
int median;
if(a <= b) {
if(b <= c){
median = b;
}
else if( c <= b && a <= c){
median = c;
}
}
//else{
median = a;
//}

return median;
}``````

unfortunately I had the else still standing there while the interview

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

For the first problem: Assuming all the three numbers are distinct

``````int median(int a, int b, int c){
if((a-b) * (c-b) < 0)
return b;
else{
if((a-c) < 0)
return a;
else
return c;
}
}``````

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

the first one is straight forward enough, though maybe im a spoil-sport and wouldnt bother writing out all the logic if i had a choice.

Two ways in python, one with a built-in, the other done manually:

``````def get_median_shortcut(a, b, c):
return sorted([a,b,c])

def get_median(a, b, c):
if ((a<=b) and (a>=c)) or ((a<=c)and(a>=b)):
return a
elif ((b >= a) and ( b <= c)) or ((b <= a) and (b >= c)):
return b
else:
return c``````

In any case, both will work given all 0's, duplicates, etc.

You maybe should give some more detail on that second one, I can give it a shot but I'm not 100% certain what you mean by it. If I interpret correctly, the min and max equal whichever values in a,b, and c that are min and max respectively. Use of bitwise operations are easy enough here, but I prefer to do the obvious arithmetic: a+b+c - min - max will just leave behind whichever value is the median.

in python:

``````def get_median_min_max(a,b,c,min,max):
return a+b+c-min-max``````

If min and max are not included in a,b, and c, then the solution is to just call the other get_median function with a,b,c, i.e:

``````def get_median_min_max(a,b,c,min,max):
return get_median(a,b,c)``````

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

``````int median(int a, int b, int c) {
int x, y;
x = min(a, b);
y = min(b, c);
if (x == y) return min(a, c);
return max(x, y);
}``````

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

``````int median(int a, int b, int c) {
if (a > b) return median(b, a, c);
else if (b > c) return median(a, c, b);
return b;
}``````

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

``````Median(a,b,c)
{
return a+b+c - (Max(a,Max(b,c)) - Min(a,Min(b,c)));
}

Median(a,b,c,max,min)
{
return a^b^c^min^max;
}``````

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

``````Median(a,b,c,max,min)
{
return a+b+c - min - max;
}``````

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

``````class FunkyMedian {
public static void main(String[]args){
System.out.println(median(10, 1, 5, 0, 11));//...min(0)...1...5...10...max(11)
System.out.println(median(10, 1, 5, 2, 4));//...1...min(2)...max(4)...5...10...
System.out.println(median(10, 1, 5, 2, 11));//...1...min(2)...5...10...max(11)
}
public static Integer median(int a, int b, int c, int min, int max) {
if (min > max) return null;

int[] arr = new int;

int i = 0;

if (min <= a && a <= max) {
arr[i] = a;
++i;
}
if (min <= b && b <= max) {
arr[i] = b;
++i;
}
if (min <= c && c <= max) {
arr[i] = c;
++i;
}

if (i == 0) return null;

if (i == 1) return arr;

if (i == 2) return arr;

return median(a, b, c);
}

public static Integer median(int a, int b, int c) {
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
if (b < c) {
int tmp = b;
b = c;
c = tmp;
}
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
return b;
}
}``````

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

``````static int median(int a, int b, int c) {
int ab = (a - b - 1) >> 31; // a >= b
int bc = (b - c - 1) >> 31; // b >= c
int ca = (c - a - 1) >> 31; // c >= a
return (ab & bc & b)	| (bc & ca & c) | (ab & ca & a);
}``````

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

``````<pre>
public static void main(String[] args) {
System.out.println(median(10, 15, 5));
System.out.println(median(10, 15, 10, 10, 15));
}

public static int median(int a, int b, int c) {
if ( (a <= b && b <= c) || (c <= b && b <= a) ) 	return b;
if ( (b <= a && a <= c) || (c <= a && a <= b) ) 	return a;
return c;
}

public static int median(int a, int b, int c, int min, int max) {
if ((a == min && b == max) || (a == max && b == min)) 	return c;
else if ((c == min && b == max) || (c == max && b == min)) 	return a;
else return b;
}
</pre>``````

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.