Google Interview Question for Software Engineer / Developers


Country: Switzerland




Comment hidden because of low score. Click to expand.
16
of 16 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

- autoboli April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome, it works!

- spagaty April 23, 2015 | Flag
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.

- zsalloum April 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- autoboli April 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zsalloum April 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good thinking !

- um01 May 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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

- ningxiner April 30, 2015 | Flag Reply
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.

- autoboli April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- Anonymous April 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- coder April 23, 2015 | Flag
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)

}

- zsalloum April 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mbriskar May 09, 2015 | Flag
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

- ghirlwhocodes April 23, 2015 | Flag Reply
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;
		}
	}

- thecode272 April 23, 2015 | Flag Reply
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])[1]

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)

- Javeed April 23, 2015 | Flag Reply
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);
}

- kyduke April 24, 2015 | Flag Reply
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;
}

- ds April 24, 2015 | Flag Reply
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;
}

- aditya.eagle059 April 24, 2015 | Flag Reply
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;
}

- MM April 26, 2015 | Flag Reply
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[3];

        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[0];

        if (i == 2) return arr[0];

        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;
    }
}

- madno May 16, 2015 | Flag Reply
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);
    }

- ab2005 August 22, 2015 | Flag Reply
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>

- Anonymous August 10, 2016 | 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