Question: Assuming you have two integers, x and y, with y bigger than x. Sum all the numbers from x to y.
The imprecision of the question itself bugs me, but I think the Geordi meme above has it right for the most reasonable reading of the question text.
Edit: Weird. On Jerboa, for me, this post has the image three times. On Lemmy-UI, only one. On both, the source text of the post is the same and doesn’t appear to ahve any duplication. Weird Jerboa bug, I guess.
Usually interview questions are designed to be imprecise. It is a great way to see how the candidate handles it. Do they ask follow-up questions? Or do they just assume the details?
I’m not a programmer, just an occasional hobbyist. Can you fill me in on why the second way is better? Is it because it’s asking for “all numbers between x and y” instead of “all integers between x and y”? I probably would have done it the first way assuming they meant integers, maybe incorrectly.
The really short version is that the first solution (with the for loop) can take “a long(er) time” depending on the values of x and y.
Say x is negative one million and y is positive one million. If the loop takes, say, a microsecond per iteration, the result would take roughly 2 seconds.
The second option is one decrement operation, one increment operation, two multiplication operations, one subtraction operation, and one division operation. No matter the values of x and y, the latter option will always take exactly the same amount of time.
There’s a concept of “Big-O notation”. If the amount of time an algorithm takes increases linearly as some value in the problem (in this case, the value of y minus x), we say that’s a “O(n)” runtime. That’s the case for the first solution I posted above. If the algorithm takes the same amount of time no matter what parameters are given, we say it’s “O(1)”. That’s the case for the second option above. (If it takes the square of some parameter, we say it’s “O(n^2)”. Exponential? “O(2^n)”. Etc.)
(And, I’m handwaving quite a bit of rigor and details here. But hopefully you get the basic idea.)
99% of the time, if you’ve got a choice between a O(n) algorithm and an O(1) algorithm, you’re better off to go with the O(1) algorithm. It is entirely possible that an O(n) algorithm could run faster than O(1) in some special cases, but those special cases are almost always when n is small and the runtime of either one is going to be negligible. If n is large, you can get some very large time savings.
(And again, I’m leaving out details, but there’s a lot online about Big-O notation or “asymptotic runtime bound”.)
The different Big-O classifications tell you how “quickly” the runtime increases based on the parameter. O(n^n) grows quicker than O(2^n) which grows quicker than O(n^2) (or even O(n^c) where c is any constant) which grows quicker than O(n*log(n)) which grows quicker than O(n) which grows quicker than O(log(n)) which grows quicker than O(1). And in general, picking an option that’s alter in this list is almost always better than picking one earlier.
Now, why the latter works. The sum of integers from 1 through n is the same as n*(n+1)/2. The sum of integers from x to y is just the sum of integers from 1 to y minus the sum of integers from 1 to x-1. y*(y+1)/2 - (x-1)*(x-1+1)/2 = y*(y+1)/2 - x*(x-1)/2 = (y*(y+1)-x*(x-1))/2.
Oh, and to your specific question, both of the solutions I posted in the meme assume that the question meant specifically all “integers” between x and y inclusive. So, no, doesn’t have to do with whether we read “numbers” there to mean integers or something else. Theoretically, the two solutions I posted should always give the same answer (so long as y >= x, which is a given in the question; perhaps also so long as no integer overflow/underflow occurs… I haven’t thought that one through fully yet. Heh.) The only reason the second is preferable is because it’s “quicker” and its runtime doesn’t depend on the value of the parameters. I guess one could also argue the latter, being a one-liner, is more terse, which may also be desirable.
The imprecision of the question itself bugs me, but I think the Geordi meme above has it right for the most reasonable reading of the question text.
Edit: Weird. On Jerboa, for me, this post has the image three times. On Lemmy-UI, only one. On both, the source text of the post is the same and doesn’t appear to ahve any duplication. Weird Jerboa bug, I guess.
Usually interview questions are designed to be imprecise. It is a great way to see how the candidate handles it. Do they ask follow-up questions? Or do they just assume the details?
I’m not a programmer, just an occasional hobbyist. Can you fill me in on why the second way is better? Is it because it’s asking for “all numbers between x and y” instead of “all integers between x and y”? I probably would have done it the first way assuming they meant integers, maybe incorrectly.
The really short version is that the first solution (with the for loop) can take “a long(er) time” depending on the values of x and y.
Say x is negative one million and y is positive one million. If the loop takes, say, a microsecond per iteration, the result would take roughly 2 seconds.
The second option is one decrement operation, one increment operation, two multiplication operations, one subtraction operation, and one division operation. No matter the values of x and y, the latter option will always take exactly the same amount of time.
There’s a concept of “Big-O notation”. If the amount of time an algorithm takes increases linearly as some value in the problem (in this case, the value of y minus x), we say that’s a “O(n)” runtime. That’s the case for the first solution I posted above. If the algorithm takes the same amount of time no matter what parameters are given, we say it’s “O(1)”. That’s the case for the second option above. (If it takes the square of some parameter, we say it’s “O(n^2)”. Exponential? “O(2^n)”. Etc.)
(And, I’m handwaving quite a bit of rigor and details here. But hopefully you get the basic idea.)
99% of the time, if you’ve got a choice between a O(n) algorithm and an O(1) algorithm, you’re better off to go with the O(1) algorithm. It is entirely possible that an O(n) algorithm could run faster than O(1) in some special cases, but those special cases are almost always when n is small and the runtime of either one is going to be negligible. If n is large, you can get some very large time savings.
(And again, I’m leaving out details, but there’s a lot online about Big-O notation or “asymptotic runtime bound”.)
The different Big-O classifications tell you how “quickly” the runtime increases based on the parameter. O(n^n) grows quicker than O(2^n) which grows quicker than O(n^2) (or even O(n^c) where c is any constant) which grows quicker than O(n*log(n)) which grows quicker than O(n) which grows quicker than O(log(n)) which grows quicker than O(1). And in general, picking an option that’s alter in this list is almost always better than picking one earlier.
Now, why the latter works. The sum of integers from 1 through n is the same as
n*(n+1)/2. The sum of integers from x to y is just the sum of integers from 1 to y minus the sum of integers from 1 to x-1.y*(y+1)/2 - (x-1)*(x-1+1)/2 = y*(y+1)/2 - x*(x-1)/2 = (y*(y+1)-x*(x-1))/2.Oh, and to your specific question, both of the solutions I posted in the meme assume that the question meant specifically all “integers” between x and y inclusive. So, no, doesn’t have to do with whether we read “numbers” there to mean integers or something else. Theoretically, the two solutions I posted should always give the same answer (so long as y >= x, which is a given in the question; perhaps also so long as no integer overflow/underflow occurs… I haven’t thought that one through fully yet. Heh.) The only reason the second is preferable is because it’s “quicker” and its runtime doesn’t depend on the value of the parameters. I guess one could also argue the latter, being a one-liner, is more terse, which may also be desirable.
Wow! Thanks for taking the time explain all of that. Makes complete sense.
I’d be perfectly happy for a candidate to do the second answer