Google Interview Question


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
13
of 15 vote

int median(int a, int b, int c){
   int m = min(a,b);
   int n = min(b,c);
   int o = min(c,a);
   return(m^n^o);
}

- JancoderSS October 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome solution @JancoderSS

- mytestaccount2 October 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

BUT BUT BIT Computations are not allowed...

- Anonymous October 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

AND HOW DO YOU IMPLEMENT MIN?

- Anonymous October 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 votes

IDIOT UPVOTERS.

- Anonymous October 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

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)

- Anonymous September 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So According to Ur solution:
if x =6 , y=8 , z=5
then w = 8 (as Max(6,8))
then median = 5 (as Min(8, 5))
Which is wrong ...

But median here is 6.

- SRB September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Mn1 = (a<=b)?a:b; //min(a,b)
Mn2 = (b<=c)?b:c; //min(b,c)
median = (Mn1>=Mn2)?Mn1:Mn2; //Max(Mn1,Mn2)

- SRB September 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if b is the min of three?

- Daru September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Mn1 = (a<=b)?a:b; //min(a,b)
Mn2 = (Mn1!=b)?((b<=c)?b:c):((a<=c)?a:c);
median = (Mn1>=Mn2)?Mn1:Mn2; //Max(Mn1,Mn2)

- SRB September 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We need to examine all possible pairs in order to handle all possible cases.

static int median(int a, int b, int c) {
		int m = (a<=b)?a:b; // min(a,b)
		int n = (a<=c)?a:c;  // min(a,c)
		m = (m>=n)?m:n;  // max(m,n)
		n = (b<=c)?b:c;  // min(b,c)
		return (m>=n)?m:n;  // max(m,n)
	}

- Daru September 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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
}

- ggm September 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The idea behind this algorithm is that there are 6 possible permutations of 3 numbers (a,b,c). One should be able to select one of the 6, using bisection, in 2 or 3 steps (simple comparisons), and return the middle element of the permutation.

- ggm September 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int diffab=a-b;
if(diffab*(a-c)<=0)
return a;
if(diffab*(b-c)>=0)
return b;

return c;

- vincent September 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we construct a binary search tree and in-order traverse the tree to get the median? Then we only need to compare at most 4 times.

- Rockie October 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int median(int a, int b, int c){
   int l = min(a,b);
   int m = min(b,c);
   int n = min(c,a);
   if(l==m){ return n;}
   else if(l!=m){ return max(l,m);}
}

- JamcoderSS October 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can construct a BST from these nodes. For 3 elements, it'll have total-order property.So, inorder traversal. qed!
total comparisons: 3
result : sorted order !

- random_coder October 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int med(int i, int j, int k) {
if (i == j)
return i;
else if (i == k)
return i;
else if (j == k)
return j;
else if (i > j) {
if (j > k)
return j;
else
return (i < k)? i : k;
}
else if (i > k)
return i;
else
return (j < k)? j : k;
}

- Dry November 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why people are using excessive integer and comparison operator?
when you can do it in just two comparison operator

- Anonymous November 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

min(a, b) = a^(((b-a) >> 31) ^ (a^b))

public int median(int a, int b, int c)
        {
                return a ^ (((b - a) >> 31) & (a ^ b)) ^
                        b ^ (((c - b) >> 31) & (b ^ c)) ^
                        a ^ (((c - a) >> 31) & (a ^ c));
        }

- dgbfs December 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int median(int a, int b, int c)
{
return min(a, b) ^ min(b, c) ^ min(c, a);
}

- Anonymous August 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

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)

- Anonymous September 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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
}

- ggm September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

one quick question: how about x=5,y=8,z=4

- Daru September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

It's not really clear what is allowed from the question. Can you please clarify?

- fizzybuzzer September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- gusuyucc September 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- eugene.yarovoi September 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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. =)

- gusuyucc September 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Subtract them and check the sign using nasty bit twiddling hacks

- Daru September 26, 2012 | Flag


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