8 ms·

This is an excellent interview question (I used it a lot). Reveals what the candidate knows about how the computers work. 90-95% of engineers don't even see a p

by mojuba 4y ago

This is an excellent interview question (I used it a lot). Reveals what the candidate knows about how the computers work. 90-95% of engineers don't even see a problem with (a + b) / 2 until you tell them about the overflow, let alone find a solution for it. The majority of programmers have no idea what an int is in their favorite language and what its range is (roughly). Then the majority come up with (a / 2) + (b / 2) until they run the unit tests and realize it's wrong. And so on and so forth, with this question you can uncover layers upon layers of trivial (non-)knowledge.

heavenlyblue 4y ago
> Then the majority come up with (a / 2) + (b / 2) until they run the unit tests and realize it's wrong. Why is that wrong?
- stevoski 4y ago
  If a=1 and b=1, the midpoint should be 1. But in computing, assuming we are only dealing with integers, 1/2 == 0. So 1/2 + 1/2 returns 0.
- scajanus 4y ago
  If a & b are both odd, you end up rounding twice vs. 0 times if you take the sum first.
- eloff 4y ago
  It's mathematically correct, but integers use truncating (floor) division. So you can lose a fractional 0.5 from both a/2 and b/2, which would have added up to 1, and now your result is off by one from (a+b)/2. In general, even with floating point numbers you can get different results by rounding implicitly or intentionally the intermediate values versus the end result.
- Jagerbizzle 4y ago
  The dev blog from Microsoft in a different comment covers this: "This will be too low if the original addition contained a carry from bit 0 to bit 1, which happens if bit 0 is set in both of the terms, so we detect that case and make the necessary adjustment." return (a / 2) + (b / 2) + (a & b & 1);
  - nick4780167 4y ago
    Maybe a little slower, but way more readable than the ones in the article.
  - bonzini 4y ago
    It's still wrong for signed integers if a/2 rounds towards zero. You need a>>1 and b>>1.
- nathell 4y ago
  Because, assuming / means integer division, this would return 6 as the midpoint between 7 and 7.
eloff 4y ago
You don't necessarily need that actually, there are carry flags that are set on overflow that you can check to get that extra bit of precision. In Rust you can actually do this using the checked add/sub/etc methods. It's one of the things I really appreciate about the language. By default, it panics on overflow in debug builds. You have to use the wrapping variants to declare that's intentional. How about: if a > b { mid = (a-b)/2 } else { mid = (b-a)/2 } There must be a way to do it without the branch? edit: Yes, in the article, I'm an idiot.
- tromp 4y ago
  if a > b { mid = (a-b)/2 That only avoids overflow on unsigned types (where it would be called wraparound) ...
  - eloff 4y ago
    The point of the midpoint calculation is to find the mid-index usually (e.g. binary search, quicksort). So a and b would be unsigned. You're right about signed integers though.
TacticalCoder 4y ago
I have a question for the interviewer, maybe a bit metaphysical: what should your function return when one parameter is zero and the other is 1?
- roflyear 4y ago
  Just need to define your behavior there. It similar to why languages choose which rounding method to use.
roflyear 4y ago
It's good I guess if people use languages where it matters. Coming up with a real solution in C seems really annoying.
gjadi 4y ago
I wonder. IMHE this is the kind of edge that you know only because you've been bitten by a bug once. It's the same with floating point numbers. You may know that the representation is not absolute, that you can end up with NaN. But I found that I only knew it viscerally after I banged my head on bugs related to these. Of course, that could be provided by Comp Sci ou Comp Eng curriculum, but time is finite... In the 5-10% of engineers who saw the problem, how many had experienced it once themselves before?
- mojuba 4y ago
  It's not just about seeing the problem but also knowing what you are dealing with. The majority of engineers or whoever call themselves engineers, don't know what an int is. Some Java programmers I interviewed years ago think the range of an the int type is, I quote "256", or "65 thousand-something", these were literal answers. Let alone it's not even a range! So you are an Android engineer and you deal with ints a lot. Screen coordinates are ints on Android, so if you think the range of an int is "256" how do you think your app works at all? This question reveals to me one of the most important things I'm usually looking for when hiring: natural curiosity. A software engineer should be curious about things he or she is dealing with. And that starts with the most trivial things like "what is an int really?" and then moves on to other concepts like: under the hood, what is a function?, what is a virtual method? what does `await` really do? And so on. A good engineer should know how the computers work, and I don't know why this should be even questioned.
  - mostlylurks 4y ago
    > think the range of an the int type is, I quote [...] "65 thousand-something" Whether or not this is a completely ludicrous answer depends entirely on how you presented the question (i.e. whether or not it was clear that you're talking about java instead of asking a more general question). For example, in C, the int type can be as low as 16 bits in size, yielding "65 thousand-something" possible values in the worst case. So that could be a reasonable answer as the guaranteed range of values for an int. And even in an android interview, C(++) can conceivably be the assumed context if the previous questions have been NDK-related. > Let alone it's not even a range! I feel like it's not a particularly uncommon shorthand to refer to the extent of a range of values that something can take as "the range" of that something.
shkkmo 4y ago
(a / 2) + (b / 2) + ((a % 2) + ((b % 2)) / 2) works and can be extended from 2 to n to find the average of a set of integers.
- a1369209993 4y ago
  Note that this can equivalently[0] (and more readably) be written as `(a/2) + (b/2) + (a&b&1)`. 0: Assuming your language rounds integer division and modulo correctly, ie that `i%array_len` is reliably a valid array index. C has problems here when i (respectively: a or b) is signed, but that doesn't matter in the sensible case, where you always index everything with size_t.
robofanatic 4y ago
If its a known issue then why don't compilers spit a warning?
naasking 4y ago
> Then the majority come up with (a / 2) + (b / 2) until they run the unit tests and realize it's wrong. Seems like you can cover the corner case easily enough: x/2 + y/2 + (x & y & 0x01) A few more operations than the article though so not the most efficient solution.
- pksadiq 4y ago
  > x/2 + y/2 + (x & y & 0x01) This returns -1 for x = INT_MIN and y = INT_MAX were the answer should be 0 (for an example). so not a correct solution
  - slymon99 4y ago
    Isn't (32 bit) INT_MAX 2^31-1 and INT_MIN -2^31, so this is an acceptable solution (since the decimal average is -0.5)?
    - pksadiq 4y ago
      > since the decimal average is -0.5 The C standard says: When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded (This is often called ‘‘truncation toward zero’’). So it should be 0 (as per C standard, not sure what C++ standard says)
      - a1369209993 4y ago
        The question is midpoint, not division, so that's irrelevant in the first place, and even if were division, the standard is wrong.
msluyter 4y ago
My first real job was for a sdet position and I was asked how to test a function that takes 3 numbers representing lengths of sides of triangle, and determines whether the the numbers can form a possible triangle. E.g. (in python), def is_triangle(a, b, c) -> bool: ...etc... One of the things an ideal candidate would realize is that the triangle inequality needs to apply (a + b >= c (for all permutations of a,b,c)), and that if a developer naively implemented the above via: if a + b < c: return false it'd run into this exact problem. I'd thought this question had gotten stale / overdone, but perhaps it's still a great interview question.
- feoren 4y ago
  This is so fraught with problems. First of all, doesn't it also need to have the condition (c > a - b)? Maybe you just left this part out? Secondly, you're worried that (a + b) could overflow. The triangles in your applications are just THE MOST EXTREME! That's how cool your application is! You have the MOST EXTREME TRIANGLES! But wait! When are you dealing with integer lengths of triangles? You never specified they were integers. In 99.99% of all real-world applications dealing with triangles, their coordinates are floating-point. I think it's fair to say overflow isn't nearly your biggest arithmetic problem with floating points -- rather, once you get to extreme (and extremely different) exponent values, you have all sorts of accuracy and loss issues, long before overflow becomes an issue. Do you expect the candidate to also handle the case where one side is 1e-155 and another is 1e274? Because otherwise their code is "wrong"! So left unspecified, your "gotcha" is completely ridiculous and just a mind-reading trap to arbitrarily filter out people who don't think exactly (and erroneously) like you do! Or maybe you did mean that the sides of the triangle are constrained to integer lengths? That would be extremely unusual, so you absolutely need to specify that. But if you're constraining the side lengths to integers, are you also constraining the vertex coordinates to integers? It would be extremely strange to require integer lengths but allow floating-point coordinates; but it would also be extremely strange to only allow integer coordinates, as most triangles with integer coordinates have a least one non-integer side length! And it doesn't sound like a trivial problem at all to find whether a given set of integer lengths could form a triangle on an integer lattice, but that seems to be what you maybe think you're asking? Do you even know what you're asking? If integers are involved at all, it's far more likely that the coordinates are integers, but the side lengths are floating point. What a tremendously awful interview question. I really hope your description is just extremely limited and flawed and mis-remembered, because if that's the actual question, you are perpetuating the "arbitrary leetcode interviews" problem that competent software engineers always complain about when they look for jobs.
lesuorac 4y ago
> This is an excellent interview question (I used it a lot). Is it though? It just tells you if they know the trick or not. At that point you might as well have them fill out a form and use the score from that to hire/no hire. It doesn't tell you if they understand what RAM is or storage (HDD/SSD/etc) or the various buses on a motherboard or pretty much anything about how a computer works. For the example given in the article, it's pretty rare for (a+b)/2 to overflow since the default ints end up being 32 bit (article calls out 64bit tbh) and your parameters are [-1000,1000]. --- > 90-95% of engineers don't even see a problem with (a + b) / 2 until you tell them about the overflow, let alone find a solution for it. In my experience a similar percentage can't write a working DFS which I think is much more work related than midpoint.
brudgers 4y ago
Per Google (suddenly I feel a need to make it clear I didn't use chat GPT) 2^64 is 1.8446744e+19 To a first approximation, if your application is overflowing 64 bit integers, the problem is in the abstractions not sloppiness in low level details...something like doing arithmetic on IPv6 addresses. What I mean is that it's one think if you specify a 32-bit or 16-bit architecture because the job entails low level programming with that constraint. But entirely another think if it is used as a general test of software engineering skill because on the one hand, now I know the trick of the trick question and you wouldn't hire me based on my software engineering chops. And on the other hand, in the vast majority of cases, the solution that might overflow is not just the simplest thing that might work, but it will also work well enough for the business purpose and be easier to support and maintain in the code base. Finally, handling problems like this culturally during development and after-action debriefing is better healthier than how-many-golfballs at the interview stage...like I said, I know the answer.
- feoren 4y ago
  Completely agreed. The statement "that function is wrong because it could overflow" is putting one potential edge case on a pedestal while ignoring all other considerations for why you might prefer one alternative over another. The vast majority of the code in most business applications can perform straight arithmetic on 64-bit ints without worrying too much about overflow -- you just never encounter numbers like 2^63, and only rarely encounter numbers that wouldn't fit in a 32-bit signed integer. When you write a bit of code, you naturally have in mind the realistic range of values you'll be working with. Even if it's just within 4 orders of magnitude. You know whether you're dealing with thousands or quadrillions. In the extremely rare case it's the latter, then you start worrying about this. You just can't worry about being 10 orders of magnitude off in your assumptions all the time -- that's what Exceptions are for. Holy crap, this software is dealing with values ten orders of magnitude different than you programmed for!? Absolutely throw an exception in that case, because it requires a complete rewrite of that area of the code. Yes, if you're writing midpoint in a language-standard math library, it should work for all possible inputs. But the point of looking at toy problems in software engineering blogs is to inform us how to write our much more complicated, much more domain-specific code, and these lessons just don't cleanly transfer into that world.
DenisM 4y ago
So what sort of answer do you find satisfactory? It seems like the "right" solution is non-trivial bit twiddling, do you expect people to come up with that, or stop sooner than that?
- mojuba 4y ago
  People rarely come up with a working solution within 30 minutes. Any solution is good as long as it doesn't overflow (there are a few suboptimal ones). But the point of this question is, again, to understand what they know about how the computers work.
  - angrais 4y ago
    What sort of role is it for? I'm asking as I doubt "know about how computers work" is necessary for most tech roles. I get it, having technical expertise is important, but still ...
  - DenisM 4y ago
    Can you provide an example of a solution that someone without prior exposure could come up under 30 minutes? I'm having a hard time coming up with something that is not a monstrocity full of if s.
    - ErikCorry 4y ago
      Perhaps the bar is not as high as you think. Coming up with a solution that has lots of ifs in will still put you at the high end of the interview distribution. Discussing intelligently with the interviewer why it's not great and how it can be improved is a lot better than not coming up with an answer at all.
    - baobabKoodaa 4y ago
      min + (max - min) / 2 Edit: never mind, this can overflow too
      - stephencanon 4y ago

by mojuba 4y ago

heavenlyblue 4y ago

> Then the majority come up with (a / 2) + (b / 2) until they run the unit tests and realize it's wrong. Why is that wrong?

stevoski 4y ago
If a=1 and b=1, the midpoint should be 1. But in computing, assuming we are only dealing with integers, 1/2 == 0. So 1/2 + 1/2 returns 0.
scajanus 4y ago
If a & b are both odd, you end up rounding twice vs. 0 times if you take the sum first.
eloff 4y ago
It's mathematically correct, but integers use truncating (floor) division. So you can lose a fractional 0.5 from both a/2 and b/2, which would have added up to 1, and now your result is off by one from (a+b)/2. In general, even with floating point numbers you can get different results by rounding implicitly or intentionally the intermediate values versus the end result.
Jagerbizzle 4y ago
The dev blog from Microsoft in a different comment covers this: "This will be too low if the original addition contained a carry from bit 0 to bit 1, which happens if bit 0 is set in both of the terms, so we detect that case and make the necessary adjustment." return (a / 2) + (b / 2) + (a & b & 1);
- nick4780167 4y ago
  Maybe a little slower, but way more readable than the ones in the article.
- bonzini 4y ago
  It's still wrong for signed integers if a/2 rounds towards zero. You need a>>1 and b>>1.
nathell 4y ago
Because, assuming / means integer division, this would return 6 as the midpoint between 7 and 7.

eloff 4y ago

You don't necessarily need that actually, there are carry flags that are set on overflow that you can check to get that extra bit of precision. In Rust you can actually do this using the checked add/sub/etc methods. It's one of the things I really appreciate about the language. By default, it panics on overflow in debug builds. You have to use the wrapping variants to declare that's intentional. How about: if a > b { mid = (a-b)/2 } else { mid = (b-a)/2 } There must be a way to do it without the branch? edit: Yes, in the article, I'm an idiot.

tromp 4y ago
if a > b { mid = (a-b)/2 That only avoids overflow on unsigned types (where it would be called wraparound) ...
- eloff 4y ago
  The point of the midpoint calculation is to find the mid-index usually (e.g. binary search, quicksort). So a and b would be unsigned. You're right about signed integers though.

TacticalCoder 4y ago

I have a question for the interviewer, maybe a bit metaphysical: what should your function return when one parameter is zero and the other is 1?

roflyear 4y ago
Just need to define your behavior there. It similar to why languages choose which rounding method to use.

roflyear 4y ago

It's good I guess if people use languages where it matters. Coming up with a real solution in C seems really annoying.

gjadi 4y ago

I wonder. IMHE this is the kind of edge that you know only because you've been bitten by a bug once. It's the same with floating point numbers. You may know that the representation is not absolute, that you can end up with NaN. But I found that I only knew it viscerally after I banged my head on bugs related to these. Of course, that could be provided by Comp Sci ou Comp Eng curriculum, but time is finite... In the 5-10% of engineers who saw the problem, how many had experienced it once themselves before?

mojuba 4y ago
It's not just about seeing the problem but also knowing what you are dealing with. The majority of engineers or whoever call themselves engineers, don't know what an int is. Some Java programmers I interviewed years ago think the range of an the int type is, I quote "256", or "65 thousand-something", these were literal answers. Let alone it's not even a range! So you are an Android engineer and you deal with ints a lot. Screen coordinates are ints on Android, so if you think the range of an int is "256" how do you think your app works at all? This question reveals to me one of the most important things I'm usually looking for when hiring: natural curiosity. A software engineer should be curious about things he or she is dealing with. And that starts with the most trivial things like "what is an int really?" and then moves on to other concepts like: under the hood, what is a function?, what is a virtual method? what does `await` really do? And so on. A good engineer should know how the computers work, and I don't know why this should be even questioned.
- mostlylurks 4y ago
  > think the range of an the int type is, I quote [...] "65 thousand-something" Whether or not this is a completely ludicrous answer depends entirely on how you presented the question (i.e. whether or not it was clear that you're talking about java instead of asking a more general question). For example, in C, the int type can be as low as 16 bits in size, yielding "65 thousand-something" possible values in the worst case. So that could be a reasonable answer as the guaranteed range of values for an int. And even in an android interview, C(++) can conceivably be the assumed context if the previous questions have been NDK-related. > Let alone it's not even a range! I feel like it's not a particularly uncommon shorthand to refer to the extent of a range of values that something can take as "the range" of that something.

shkkmo 4y ago

(a / 2) + (b / 2) + ((a % 2) + ((b % 2)) / 2) works and can be extended from 2 to n to find the average of a set of integers.

a1369209993 4y ago
Note that this can equivalently[0] (and more readably) be written as `(a/2) + (b/2) + (a&b&1)`. 0: Assuming your language rounds integer division and modulo correctly, ie that `i%array_len` is reliably a valid array index. C has problems here when i (respectively: a or b) is signed, but that doesn't matter in the sensible case, where you always index everything with size_t.

robofanatic 4y ago

If its a known issue then why don't compilers spit a warning?

naasking 4y ago

> Then the majority come up with (a / 2) + (b / 2) until they run the unit tests and realize it's wrong. Seems like you can cover the corner case easily enough: x/2 + y/2 + (x & y & 0x01) A few more operations than the article though so not the most efficient solution.

pksadiq 4y ago
> x/2 + y/2 + (x & y & 0x01) This returns -1 for x = INT_MIN and y = INT_MAX were the answer should be 0 (for an example). so not a correct solution
- slymon99 4y ago
  Isn't (32 bit) INT_MAX 2^31-1 and INT_MIN -2^31, so this is an acceptable solution (since the decimal average is -0.5)?
  - pksadiq 4y ago
    > since the decimal average is -0.5 The C standard says: When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded (This is often called ‘‘truncation toward zero’’). So it should be 0 (as per C standard, not sure what C++ standard says)
    - a1369209993 4y ago
      The question is midpoint, not division, so that's irrelevant in the first place, and even if were division, the standard is wrong.

msluyter 4y ago

My first real job was for a sdet position and I was asked how to test a function that takes 3 numbers representing lengths of sides of triangle, and determines whether the the numbers can form a possible triangle. E.g. (in python), def is_triangle(a, b, c) -> bool: ...etc... One of the things an ideal candidate would realize is that the triangle inequality needs to apply (a + b >= c (for all permutations of a,b,c)), and that if a developer naively implemented the above via: if a + b < c: return false it'd run into this exact problem. I'd thought this question had gotten stale / overdone, but perhaps it's still a great interview question.

feoren 4y ago
This is so fraught with problems. First of all, doesn't it also need to have the condition (c > a - b)? Maybe you just left this part out? Secondly, you're worried that (a + b) could overflow. The triangles in your applications are just THE MOST EXTREME! That's how cool your application is! You have the MOST EXTREME TRIANGLES! But wait! When are you dealing with integer lengths of triangles? You never specified they were integers. In 99.99% of all real-world applications dealing with triangles, their coordinates are floating-point. I think it's fair to say overflow isn't nearly your biggest arithmetic problem with floating points -- rather, once you get to extreme (and extremely different) exponent values, you have all sorts of accuracy and loss issues, long before overflow becomes an issue. Do you expect the candidate to also handle the case where one side is 1e-155 and another is 1e274? Because otherwise their code is "wrong"! So left unspecified, your "gotcha" is completely ridiculous and just a mind-reading trap to arbitrarily filter out people who don't think exactly (and erroneously) like you do! Or maybe you did mean that the sides of the triangle are constrained to integer lengths? That would be extremely unusual, so you absolutely need to specify that. But if you're constraining the side lengths to integers, are you also constraining the vertex coordinates to integers? It would be extremely strange to require integer lengths but allow floating-point coordinates; but it would also be extremely strange to only allow integer coordinates, as most triangles with integer coordinates have a least one non-integer side length! And it doesn't sound like a trivial problem at all to find whether a given set of integer lengths could form a triangle on an integer lattice, but that seems to be what you maybe think you're asking? Do you even know what you're asking? If integers are involved at all, it's far more likely that the coordinates are integers, but the side lengths are floating point. What a tremendously awful interview question. I really hope your description is just extremely limited and flawed and mis-remembered, because if that's the actual question, you are perpetuating the "arbitrary leetcode interviews" problem that competent software engineers always complain about when they look for jobs.

lesuorac 4y ago

> This is an excellent interview question (I used it a lot). Is it though? It just tells you if they know the trick or not. At that point you might as well have them fill out a form and use the score from that to hire/no hire. It doesn't tell you if they understand what RAM is or storage (HDD/SSD/etc) or the various buses on a motherboard or pretty much anything about how a computer works. For the example given in the article, it's pretty rare for (a+b)/2 to overflow since the default ints end up being 32 bit (article calls out 64bit tbh) and your parameters are [-1000,1000]. --- > 90-95% of engineers don't even see a problem with (a + b) / 2 until you tell them about the overflow, let alone find a solution for it. In my experience a similar percentage can't write a working DFS which I think is much more work related than midpoint.

brudgers 4y ago

Per Google (suddenly I feel a need to make it clear I didn't use chat GPT) 2^64 is 1.8446744e+19 To a first approximation, if your application is overflowing 64 bit integers, the problem is in the abstractions not sloppiness in low level details...something like doing arithmetic on IPv6 addresses. What I mean is that it's one think if you specify a 32-bit or 16-bit architecture because the job entails low level programming with that constraint. But entirely another think if it is used as a general test of software engineering skill because on the one hand, now I know the trick of the trick question and you wouldn't hire me based on my software engineering chops. And on the other hand, in the vast majority of cases, the solution that might overflow is not just the simplest thing that might work, but it will also work well enough for the business purpose and be easier to support and maintain in the code base. Finally, handling problems like this culturally during development and after-action debriefing is better healthier than how-many-golfballs at the interview stage...like I said, I know the answer.

feoren 4y ago
Completely agreed. The statement "that function is wrong because it could overflow" is putting one potential edge case on a pedestal while ignoring all other considerations for why you might prefer one alternative over another. The vast majority of the code in most business applications can perform straight arithmetic on 64-bit ints without worrying too much about overflow -- you just never encounter numbers like 2^63, and only rarely encounter numbers that wouldn't fit in a 32-bit signed integer. When you write a bit of code, you naturally have in mind the realistic range of values you'll be working with. Even if it's just within 4 orders of magnitude. You know whether you're dealing with thousands or quadrillions. In the extremely rare case it's the latter, then you start worrying about this. You just can't worry about being 10 orders of magnitude off in your assumptions all the time -- that's what Exceptions are for. Holy crap, this software is dealing with values ten orders of magnitude different than you programmed for!? Absolutely throw an exception in that case, because it requires a complete rewrite of that area of the code. Yes, if you're writing midpoint in a language-standard math library, it should work for all possible inputs. But the point of looking at toy problems in software engineering blogs is to inform us how to write our much more complicated, much more domain-specific code, and these lessons just don't cleanly transfer into that world.

DenisM 4y ago

So what sort of answer do you find satisfactory? It seems like the "right" solution is non-trivial bit twiddling, do you expect people to come up with that, or stop sooner than that?

mojuba 4y ago
People rarely come up with a working solution within 30 minutes. Any solution is good as long as it doesn't overflow (there are a few suboptimal ones). But the point of this question is, again, to understand what they know about how the computers work.
- angrais 4y ago
  What sort of role is it for? I'm asking as I doubt "know about how computers work" is necessary for most tech roles. I get it, having technical expertise is important, but still ...
- DenisM 4y ago
  Can you provide an example of a solution that someone without prior exposure could come up under 30 minutes? I'm having a hard time coming up with something that is not a monstrocity full of if s.
  - ErikCorry 4y ago
    Perhaps the bar is not as high as you think. Coming up with a solution that has lots of ifs in will still put you at the high end of the interview distribution. Discussing intelligently with the interviewer why it's not great and how it can be improved is a lot better than not coming up with an answer at all.
  - baobabKoodaa 4y ago
    min + (max - min) / 2 Edit: never mind, this can overflow too
    - stephencanon 4y ago