Hmm, I would have used + and -, I suppose. The sum of 1..n is (n*(n+1))/2. Subtract from that all numbers in the array and what is left is the missing number.
That XOR Trick (2020)
151–160 of 243 posts
Re: That XOR Trick (2020)
#152A fun party trick not mentioned here is reducing storage in a doubly linked-ish list: Normally each node stores 2 pointers: struct Node {void * prev;void * next} The trick is to use only 1 'pointer', storing prev XOR next: struct Node {void* xored;} While traversing, you remember not only the current position, but also where you came from. So forward traversal goes: next= current.xored XOR previous. Backwards also wo…
That’s undefined behavior in C though: https://news.ycombinator.com/item?id=3928788
Your linked comment only quotes excerpts saying it's implementation-defined, rather than undefined. Can you point to the part that is undefined?
(You would use a uintptr_t for the xor'd prev-next pointers instead of void*.)
Re: That XOR Trick (2020)
#153Earlier quoted context omitted.
The code from the Wikipedia article for XOR swapping [1] checks if the values are equal. void XorSwap(int *x, int *y) { if (x != y) { *x ^= *y; *y ^= *x; *x ^= *y; } } [1] https://en.wikipedia.org/wiki/XOR_swap_algorithm
At that point it's probably almost always better to just use some temporary space, rather than dealing with all the overhead of a branch (what if it's mispredicted, what about the resources in the branch predictor tied up by this that might cause something else to be mispredicted). On the other hand there are many situations where you can guarantee that x and y are not the same space in memory (for example because th…
The xor swap truck is rarely better. It causes pipeline stalls, and so is likely to be significantly slower than the trivial swap. The temporary storage will be in a register, so it's (usually) not causing memory accesses.
Re: That XOR Trick (2020)
#154Earlier quoted context omitted.
It just surprises me that they aren't rotated out more frequently (annually?). I can think of a number of arguments for doing so and really only one small one against.
Could you share some of the arguments you have in mind?
The fact that not rotating questions makes it trivial for someone who’s been through the process to tip off future applicants. Sites like Glassdoor and leetcode already do this, but it’s tempered by the fact that most companies rotate these type of screener questions regularly.
It sounds like some of these questions are bad screeners anyway, but it makes them even worse if half the people going through the process are feigning surprise at the tricky question then quickly developing a “brilliant” solution.
Re: That XOR Trick (2020)
#155Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables alway…
> because the interviewer expected you to know how to find a duplicate in an integer list by using xor
Maybe they expect you to come up with a solution right there. This way they can see that you're curious and trying to solve a problem even if you don't know its solution beforehand. (And by looking at your attempts they your mind is even working in the right direction. They could give you small hints and observe how you process them.)
I never conducted interviews myself, but some years ago my supervisor asked me for advice on interview problems for his interns. He wanted something that will help spot a person inclined to algorithmic thinking, but the job was not 100% algorithmic, he needed programmers. If he asked me the same today, I would have advised him to look at these xor search problems.
Re: That XOR Trick (2020)
#156A fun party trick not mentioned here is reducing storage in a doubly linked-ish list: Normally each node stores 2 pointers: struct Node {void * prev;void * next} The trick is to use only 1 'pointer', storing prev XOR next: struct Node {void* xored;} While traversing, you remember not only the current position, but also where you came from. So forward traversal goes: next= current.xored XOR previous. Backwards also wo…
I looked up TAOCP (The Art of Computer Programming by Knuth), and (unsurprisingly) this trick is mentioned there, and already by the time of the first edition this trick was folklore, with its origins lost to antiquity: the last exercise in section 2.2.4:
> 18. [25] Devise a way to represent circular lists inside a computer in such a way that the list can be traversed efficiently in both directions, yet only one link field is used per node. [Hint: If we are given two pointers, to two successive nodes x_{i-1} and x_i, it should be possible to locate both x_{i+1} and x_{i-2}.]
Answer (in 1st edition [1968], second printing [1969]):
> 18. Let the link field of node x_i contain LOC{x_{i+1}) ⊕ LOC{x_{i-1}), where "⊕" denotes either subtraction or "exclusive or." Two adjacent list heads are included in the circular list, to help get things started properly. (The origin of this ingenious technique is unknown.)
The "either" is modified to "e.g." in the 2nd edition [1973], and further slightly modified in 3rd edition ([1997], first digital release [December 2013]):
> 18. Let the link field of node x_i contain LOC(x_{i+1}) ⊕ LOC(x_{i−1}), where “⊕” denotes “exclusive or.” Other invertible operations, such as addition or subtraction modulo the pointer field size, could also be used. It is convenient to include two adjacent list heads in the circular list, to help get things started properly. (The origin of this ingenious technique is unknown.)
With modern languages and compilers, even if doing these operations on your language's pointer type is implementation-defined/undefined behaviour as mentioned in some of the other comments, you can still use this trick with your own "pointers" (indexes in an array, as Knuth does in many of his programs: https://en.wikipedia.org/w/index.php?title=Pointer_(computer...), I guess.
Anyway, this gives me another point of appreciation about why the TAOCP series of books were so highly regarded: they were (are) encyclopedic and gathered/organized much of what was known at the time, in a highly compressed way (packed into exercises etc).
Re: That XOR Trick (2020)
#157Hmm, I would have used + and -, I suppose. The sum of 1..n is (n*(n+1))/2. Subtract from that all numbers in the array and what is left is the missing number.
I suppose one downside of this approach is that you need a bigger datatype to contain the result.
Re: That XOR Trick (2020)
#158Fun XOR trick: using it to move a cursor across the screen without having to keep a buffer of the contents under the cursor (and putting them back). It didn't always look great, but if you were moving a full-screen crosshair around, it was sufficient. Especially on hardware that was slow to move buffers to and from ram. Unfortunately, using this pure-math technique was also patented until 2007 [0], much to the surpri…
Really? Apple ][ vector shapes had a XOR mode built in for non-destructively moving shapes across the screen, often used for cursors, and that was released in 1977.
Re: That XOR Trick (2020)
#159Earlier quoted context omitted.
Thanks a lot for the detailed answer! I'm familiar with some subset of coding and number theory, so you can assume at least some more knowledge (Galois Fields, or basics of RS codes for example). Small nitpick: The Vandermonde matrix actually isn't square. It's a (k × n) matrix, (where typically k ≠ n). Therefore, it can't be invertible. I see that many codes contain a parity bit (for example the extended Golay code)…
https://www.backblaze.com/blog/reed-solomon/ In particular, these two images: * https://www.backblaze.com/blog/wp-content/uploads/2015/06/bl... * https://www.backblaze.com/blog/wp-content/uploads/2015/06/RS... Note: Backblaze here uses "vertical data" (G * data) instead of what I did earlier "horizontal data" in the form of (data*G). But otherwise, still a good blogpost. ------------ So if you have 5 data + 1 parity,…
I think we're talking about different things.
I would be interested in a way based on coding theory that solves the problem in the blog-post. Something of a form similar to this one would be a solution to me:
def find_missing_number(nums: List[int]):
# 1. Define some code C (possibly using nums)
# 2. Encode a message using C (or interpret nums as a word or codeword)
# 3. Do something with the word
# 4. Find the locations of the errors in the word
# 5. The locations of the errors tell us the missing number(s)
Re: That XOR Trick (2020)
#160Earlier quoted context omitted.
I agree, but I think back then I didn't know this trick. I also abuse blocks in Rust, but it's more in order to placate the borrow checker...
That's not necessarily abuse; it may be quite appropriate to explicitly limit something's lifetime.
Indeed! I somewhat over-use this in Rust to initialize an immutable variable with mutating code.
let var: Vec; // this one is immutable, will be initialized later
{
let mut var_; // mutable
… // initialize var_ with some mutating code
var = var_; // now move var_ to var, initializing the latter
}