Google Interview Question
Software Engineer / DevelopersCountry: Switzerland
Why did you assume that min and max are one of the initial a, b, c ??
This is not mentioned anywhere.
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
After giving it a second thought, you are right and your solution is very smart.
I give it a thumb up
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.
for input a = 10, b = 15, c = 5
in your first "if": c <= b && c <= a returns 15 which is false
int median(int a, int b, int c){
return (a<b) ? Math.Min( b, Math.Max(a, c))
: Math.Min(a, c)
}
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)
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;
}
}
<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>
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:
Example: Let say that min = c, max = b then it follows
- autoboli April 23, 2015a^b^c^min^max = a^(b^max)^(c^min) = a^0^0 = a