Google Interview Question
Country: United States
Interview Type: Written Test
Sorry a small mistake... First we should calculate the max of 2 numbers and then min of max and third number.
Let x=5,y=8,z=6
int w= x^((x^y)&-(x<y)) /// w=Max(x,y)
int median= w^((z^w)&-(z<w)) /// Min(w,z)
Mn1 = (a<=b)?a:b; //min(a,b)
Mn2 = (b<=c)?b:c; //min(b,c)
median = (Mn1>=Mn2)?Mn1:Mn2; //Max(Mn1,Mn2)
int median (int a,int b,int c)
{
if (a <= b)
{
if (b <= c) return b; // a <= b <= c ; 2 ops
if (a <= c) return c; // a <= c < b ; 3 ops
return a; // c < a <= b ; 3 ops
}
// b < a
if (b => c) return b; // c <= b < a ; 2 ops
if (a <= c) return a; // b < a <= c ; 3 ops
return c; b < c < a ; 3 ops
}
e.g : median(5, 8, 4) == 5
int median (int a = 5, int b = 8, int c = 4)
{
if (a <= b) // 5 <= 8 : true
{
if (b <= c) return b; // a <= b <= c ; 2 ops
// 8 <= 4 : false
if (a <= c) return c; // a <= c < b ; 3 ops
// 5 <= 4 : false
return a; // c < a <= b ; 3 ops
// a==5 ; return 5 ; BINGO!
}
// b < a
if (b => c) return b; // c <= b < a ; 2 ops
if (a <= c) return a; // b < a <= c ; 3 ops
return c; b < c < a ; 3 ops
}
Let x=5,y=8,z=6
int w= y^((x^y)&-(x<y)) /// w=Min(x,y)
int median= z^((z^w)&-(z<w)) /// Max(w,z)
int median (int a,int b,int c)
{
if (a <= b)
{
if (b <= c) return b; // a <= b <= c ; 2 ops
if (a <= c) return c; // a <= c < b ; 3 ops
return a; // c < a <= b ; 3 ops
}
// b < a
if (b => c) return b; // c <= b < a ; 2 ops
if (a <= c) return a; // b < a <= c ; 3 ops
return c; b < c < a ; 3 ops
}
Sure! So in this question, you can use any operations except for directly calling a sort method. The requirement is to minimize the times of integer operating. For example, when I do
if (a>b) { if (c>a) {return a;}}, the times of integer operating is 2.
But something like a conditional branch instruction can be so much more expensive than some bitwise operations. Are we to take such things into account as well?
Hi, eugene.yarovoi, Could you show me how can I do it using bitwise operations? I only can come up with the compare operator and it is indeed very expensive. =)
- JancoderSS October 09, 2012