7 ms·
I would not have though to use this formula. The sum of the integers grows as the square of n so if n is anything but small you will overflow and get an erroneo
by Znafon 4y ago
I would not have though to use this formula. The sum of the integers grows as the square of n so if n is anything but small you will overflow and get an erroneous answer.
This interview question has everything bad imo: no practical uses, test knowledge of math formulas (which every math/CS major would have but none of the self learning folks). It’s very easy to stress and fail when given such a test, and even already knowing I would have tried something else because of the overflow.
- bawolff 4y ago> test knowledge of math formulas (which every math/CS major would have but none of the self learning folks) I mean they might. Its a very famous formula, with a famous story attached, which is often covered in high school level math. Regardless its a stupid question.
- Sesse__ 4y ago> I would not have though to use this formula. The sum of the integers grows as the square of n so if n is anything but small you will overflow and get an erroneous answer. As long as you can get wraparound semantics, the overflow is actually unproblematic. (n(n+1)/2 + k) mod 2^32 - (n(n+1)/2 mod 2^32) = k mod 2^32 = k.
- Znafon 4y agoIndeed, somehow this went completely over my head.
- jwilk 4y agoEven with wraparound semantics, you can't compute n(n+1)/2 naively, because (n(n+1) mod N) / 2 ≠ n(n+1)/2 mod N. So actually not knowing the formula is kinda advantageous, because computing the sum as 1 + 2 + … + n (with every addition mod N) gives you the right answer (mod N).
- ppsreejith 4y agoYou could delay division by 2 until the end. I.e ((2 * S mod N - n*(n+1) mod N) mod N) / 2 Where S is the sum of the array achieved through iterative addition with every addition mod N and N > 2n.
- Sesse__ 4y agoOr you can assume N is less than 2^31, and clear out the top bit in the final answer (because that's the only place the wrong values can come from). Which is admittedly pretty hackish, but… Edit: The simplest solution is probably just doing (n/2)*(n+1) (assuming n is even; move the division for n odd).
- deleted 4y ago[deleted]
- vjerancrnjak 4y agoYes, it's a question with a silly trick. Completely useless if one knows the answer, hard to spot if the person feigns struggle. Although, n•(n+1)/2 formula is not necessary. One can start with an xor sum and find the duplicate by xor adding elements again. This is another silly trick.
- rocqua 4y agoWhat is the closed form solution of the xor-sum though?
- jwilk 4y agos(n) = • n if n mod 4 = 0, • 1 if n mod 4 = 1, • n + 1 if n mod 4 = 2, • 0 if n mod 4 = 3. Or alternatively: • s(4n) = 4n • s(4n + 1) = 1 • s(4n + 2) = 4n + 3 • s(4n + 3) = 0 Proof by induction: • s(4n + 1) = s(4n) ⊕ (4n + 1) = 4n ⊕ (4n + 1) = 1 • s(4n + 2) = s(4n + 1) ⊕ (4n + 2) = 1 ⊕ (4n + 2) = 4n + 3 • s(4n + 3) = s(4n + 2) ⊕ (4n + 3) = (4n + 3) ⊕ (4n + 3) = 0 • s(4n + 4) = s(4n + 3) ⊕ (4n + 4) = 0 ⊕ (4n + 4) = 4n + 4
- aliceryhl 4y agoYou already have to spend the time to go through the list. Just add up the xor as you iterate through the list.
- curiousgal 4y agoCould also just use a hashtable, the keys are the array elements and the items are the occurrence of each element, then return the one with an occurrence of 2.
- 3np 4y agoOr just a hashset and return when about to insert an existing element.
- Znafon 4y agoThat’s a very elegant solution. Hard looking problems that had simple, trick solutions were called Jewish Problems at the entrance of some universities. This would let the examiner fail a student for subjective reasons instead of academic success. The examiner would then be able to say « I failed them because of their skills, not because of their religions, look how easy the solution is ». Perhaps this is what we are reproducing as an industry with all our convoluted interview processes, and it may be a decorum to choose the candidates we want instead of using objective criteria.
- williamkuszmaul 4y agoUsing 64 bit integers, we can store the square of any 32 bit integer. Not that small...
- ciupicri 4y agoAlso it was 2004 and 64 bit machines weren't common. If I remember correctly you had only 2 GB available under Windows XP and if you wanted more, 3 GB to be more precise, you had to boot with a special parameter.
- saagarjha 4y ago32-bit machines generally 64-bit arithmetic of some sort; for example "long long" in C is mandated by the standard to be of a width greater than or equal to 64 bits.
- ciupicri 4y agoYeah, 64 bit integers were available under gcc on Linux, but the memory issue remained. The array had to fit in 2 GB, unless of course the problem stated otherwise, for example the numbers were read from a file.
- whiplash451 4y agoLet’s not overthink this. Microsoft is using this test as a low-pass filter to get rid of candidates who would: - not find any answer in a few minutes - find a wrong answer and argue about it in an obnoxious way Any reasonable answer would probably do. You would probably get more brownie points for asking what you need to optimize for (compute, storage) than providing what seems to be the best solution (using the sum trick).
- zwischenzug 4y agoExactly. It’s basically fizzbuzz. The fact that he thought about this in advance and had an answer ready to explain is also a green flag for such an early filter.
- deleted 4y ago[deleted]
- TheRealNGenius 4y agoTrue, but that doesn't matter at all given reasonable values of n. The number is in the range of n^2, but the algorithm is in the range O(1). Question is not that bad, my first thought was to use hash table to store what you see, then return when duplicate occurs. Don't like hash table fine, set an array of size n storing TRUE when you see the number. Notice it twice, then you've found the duplicate. No need for math, O(n) solution. Honestly if you're stressing over a question like this, combined with thinking that integer overflow is even remotely something that you need to be concerned about in a question like this, you're definitely not passing any leetcode interview problems tossed around in today's interviewing culture.
- zeroonetwothree 4y agoEvery solution is at least O(n).
- TheRealNGenius 4y agoWrong, calculating n(n-1)/2 is O(1)