I generally start with a very simple question with my interview candidates. I ask the for writing a program for giving the integer average of 2 integers using only integer type variables. Assume that input will always be with in integer limits.

The definition of integer average is the highest smaller integer if average is floating point number. Also the condition if that they can not use any typecasting or any datatype other than int.

**Example:**

a = 4, b = 5, avg = 4

a = 4, b = 6, avg = 5

a = -4, b = -6, avg = -5

a = 4, b = -5, avg = -1

a = -4, b = -5, avg = -5

95% of candidates smell some issues in this problem and when I say nothing is there they don't even ask any clarification and come up with something like this:

int get_average(int a, int b) { return (a+b)/2; }

Then I ask them to have a look if this is correct on definition and then they see that it is. But there test failed on very first floating point negative average. Then most of them do a quick fix and come up with something below:

int get_average(int a, int b) { int sum = (a+b); if (sum < 0) return sum/2 - 1; return sum/2; }

The above solution is obviously wrong if sum if a even negative number. I am disheartened to see why do these candidates just solve a test case and show the solution. They don't even care to run this with some examples.

On pointing this, most of them correct the code. Others face the rejection at this stage.

int get_average(int a, int b) { int sum = (a+b); if (sum < 0 && sum%2 != 0) return sum/2 - 1; return sum/2; }

Now I ask them to make it production worthy and taking care of boundary conditions. Many of them are not able to do so but some of them go through it for my second question.

Though I expect this problem to be concluded within 30 minutes depending of their experience but candidates do a lot of silly mistakes and stretch.

Lets see if you can code this correctly.

#include <iostream> using namespace std; int get_average (int a, int b) { int a_half = a/2; int b_half = b/2; bool a_even = a%2==0? true:false; bool b_even = b%2==0? true:false; if (a>=0 && b>=0) { if (!a_even && !b_even) return a_half + b_half + 1; return a_half + b_half; } else if (a<0 && b<0) { if (a_even && b_even) return a_half + b_half; return a_half + b_half - 1; } else { int sum = a+b; if (sum < 0 && sum%2 != 0) return sum/2 - 1; return sum/2; } } int main() { int n, a, b; cout << "number of test cases: "; cin >> n; for (int i=0; i<n; i++) { cout << endl << "Enter a and b: "; cin >> a >>b; cout << "average = " << get_average(a,b) << endl; } }

**Edit:**We get a more efficient and concise solution in comments. Please go through it.

Notably most of the solution for binary search are wrong because of above reason. This bug was fixed in Java SDK after 9 years. Please read more about it here.

**Subscribe**- To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
AnonymousThank you for the puzzle. I think I have a solution that seems to be a bit shorter and more systematic, although I'm not so sure if it is easier to understand; so please feel free to critique, OK?

My test set was as follows:

checkintAverage(4, 5, 4);

checkintAverage(4, 6, 5);

checkintAverage(4, 7, 5);

checkintAverage(-4, -5, -5);

checkintAverage(-4, -6, -5);

checkintAverage(-4, -7, -6);

checkintAverage(4, -7, -2);

checkintAverage(4, -8, -2);

checkintAverage(5, -8, -2);

checkintAverage(5, -9, -2);

checkintAverage(7, -7, 0);

checkintAverage(4, -4, 0);

checkintAverage(4, -3, 0);

checkintAverage(4, -5, -1);

checkintAverage(7, -4, 1);

checkintAverage(8, -4, 2);

checkintAverage(8, -5, 1);

checkintAverage(9, -5, 2);

Hope this is correct. One, shorter, solution would only be 100% correct in Java or on major C compilers (because the left shift on negatives is generally undefined) yet it's worth mentioning:

(a>>1) + (b>>1) + (a&b&1)

A more conservative solution is somewhat longer:

int intAverage(int a, int b) {

int rem_a = (a&1)==0 ? 0 : a<0 ? -1 : 1;

int rem_b = (b&1)==0 ? 0 : b<0 ? -1 : 1;

return a/2 + b/2 + (rem_a + rem_b-1)/2;

}

What I didn't quite like about the posted solution is that it had two different code paths depending on whether a and b are of the same sign. But this is subject to discussion!

Thank you for your excellent site.

AnonymousThere was a typo in my function; here is what it should look like:

int intAverage(int a, int b) {

int rem_a = a%2==0 ? 0 : a<0 ? -1 : 1; // i.e., a - a/2*2

int rem_b = b%2==0 ? 0 : b<0 ? -1 : 1;

return a/2 + b/2 + (rem_a + rem_b + 2)/2 - 1;

}

The idea is to calculate the term correction due to truncation in the integer division, which could only be 1, 0, or -1; averaging those cannot possibly overflow. The trick of adding 2 and then subtracting 2/2 = 1 in the end is to ensure that we are summing non-negative values, otherwise the rounding direction could be incorrect.

Akash Agrawal@Anonymous:

What you presented is just awesome. Thanks a lot for a more efficient and concise solution.

Though my post was inclined towards how people in a interview approach the problem and go around it.

maaniUsually I do not read post on blogs, but I would like to say that this write-up very forced me to try and do it! Your writing style has been surprised me. Great work admin..Keep update more blog..

Web development company in Chennai

Guarantee Bullion Tipsgood info about pragramming interview,thanks for this blog.

Mcx Silver TipsSagar ShahSagar ShahSagar ShahThe following should work well for all test cases -

int average(int a,int b)

{

return (a+b)>>1;

}

vinu priyaWonderful blog.. Thanks for sharing informative blog.. its very useful to me..

Android App Development Company in India