Re:That XOR Trick (2020)
by all2 on Monday January 18, 2021 @09:52AM
(#25822313)
A = { 1, 2, ... , k, ..., n-1, n}, for 1<=k<=n, and we're given integer n.
sum({1..n}) = n(n-1) / 2
sum(A) = n(n-1) / 2 - k
k = n(n-1) / 2 - sum(A)
Is the interview question looking for a "clever" solution? I'm confused as to why someone would ask this question in an interview? It seems like the more challenging question would be "Find a method of summing a range 1..n in less than O(n) time/space complexity." [edit] I have a dumb. This calculation can happen in O(1). Because of n(n-1)/2, we know the sum of the range, no need to examine each value in the range. [/edit]
Or, even more fun, limit the functions/instructions the interviewee can use (ex, some 4 or 5 instructions of x86/WASM/etc. machine instructions, max 1 or 2 registers, etc.) to complete the task.
sum({1..n}) = n(n-1) / 2
sum(A) = n(n-1) / 2 - k
k = n(n-1) / 2 - sum(A)
Is the interview question looking for a "clever" solution? I'm confused as to why someone would ask this question in an interview? It seems like the more challenging question would be "Find a method of summing a range 1..n in less than O(n) time/space complexity." [edit] I have a dumb. This calculation can happen in O(1). Because of n(n-1)/2, we know the sum of the range, no need to examine each value in the range. [/edit]
Or, even more fun, limit the functions/instructions the interviewee can use (ex, some 4 or 5 instructions of x86/WASM/etc. machine instructions, max 1 or 2 registers, etc.) to complete the task.