121–130 of 141 posts
It's funny how the author fails to apply the XOR trick in the two missing values problem: > We can thus search for u by applying this idea to one of the partitions and finding the missing element, and then find v by applying it to the other partition. Since you already have u^v, you need only search for u, which immediately gives you v.
Earlier quoted context omitted.
> Ah, my least favorite technical interview question. The epitome of turning technical interviews into a trivia contest to make them feel smart. Because isn't that the point of a tech interview?
In what way is that question trivia? I believe you under-estimate what a good interviewer is trying to do with questions such as these: Either you've seen the trick before and you get an opportunity to show the interviewer that you're an honest person by telling him you have. Huge plus and the interview can move on to other topics. Either you haven't and you can demonstrate to the interviewer your analytical skills b…
You shouldn't expect it to be possible during the course of the interview for those who don't know it already, it makes no sense to expect that.
At best, the question will check if someone memorized such stuff. But I don't see a lot of value in that.
Very well written article! I used xor just as fast clear register :)
xor ax, ax
mov ax, 0hEarlier quoted context omitted.
You could make the problem harder with "you are given a stream of n - 1 integers". N could then be any number, unbound by available memory. That makes the problem harder which makes it more interesting, a lot of the solutions wouldn't work anymore (this isn't necessarily a good interview question though)
Even with the original formulation, the array doesn't have to fit in available memory. mmap exists.
It's funny how the author fails to apply the XOR trick in the two missing values problem: > We can thus search for u by applying this idea to one of the partitions and finding the missing element, and then find v by applying it to the other partition. Since you already have u^v, you need only search for u, which immediately gives you v.
How can you find u? That's what the author explains next.
tromp is saying the last step can be simplified. There is no need to use the "XOR of all elements" method on the second partition to find v, since the earlier steps have given us u^v and u, so simply XORing those two values together gives v.
It's funny how the author fails to apply the XOR trick in the two missing values problem: > We can thus search for u by applying this idea to one of the partitions and finding the missing element, and then find v by applying it to the other partition. Since you already have u^v, you need only search for u, which immediately gives you v.
Gray code is something semi-related. For hardware encoders of a position you want only one transition between states, that is, the XOR of the two to have only one bit set. Normal binary has multiple transitions between some values (e.g. three bit changes between 011 and 100). Gray code could be 000, 001, 011, 010, 110, 111, 101, 100.
This was a go to interview question to be solved in C# at a place I worked at a while back which had developers allocated to projects working on pretty standard line of business systems. The XOR solution was a valid answer, but not the only answer we would have happily accepted. The interview question was chosen such that it's very easy to understand and quick to solve, meaning it would indicate the candidate knew at…
you are missing the most obvious one, no? Sum both lists and take the difference, that's the missing number, since the items are guaranteed unique
a := a + b;
b := a - b;
a := a - b;
Earlier quoted context omitted.
How can you find u? That's what the author explains next.
The article says to use the "XOR of all elements" method to find u^v, then do the partitioning, then use the "XOR of all elements" method on the first partition to find u, then use the "XOR of all elements" method on the second partition to find v. tromp is saying the last step can be simplified. There is no need to use the "XOR of all elements" method on the second partition to find v, since the earlier steps have g…