Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

That XOR Trick (2020)

florian.github.io

Post reply on HN
Print view View original

91–100 of 243 posts

Re: That XOR Trick (2020)

#91

Post by abhishekjha »

dragontamer wrote: post #56
exabrial wrote: post #21

> There are a whole bunch of popular interview questions As a very personal strong opinion, this makes me groan. I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). I'd rather know w…

> I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). Erasure correction is a very useful trick for data-engineers. I don't think this is a microcontroller trick, as much as a data-r…

I guess I will fail your interview as well.

Re: That XOR Trick (2020)

#92

Post by shiftingleft »

dragontamer wrote: post #56
exabrial wrote: post #21

> There are a whole bunch of popular interview questions As a very personal strong opinion, this makes me groan. I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). I'd rather know w…

> I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). Erasure correction is a very useful trick for data-engineers. I don't think this is a microcontroller trick, as much as a data-r…

I think in erasure coding you typically know the locations of the erasures: If a disk fails, you know which one failed.

However, I don't see how you would know the locations in this problem?

Maybe you can elaborate on how this problem relates to erasure coding?

Re: That XOR Trick (2020)

#93

Post by [deleted] »

simias wrote: post #46

Careful 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…

[deleted]

Re: That XOR Trick (2020)

#94

Post by smlckz »

abalaji wrote: post #89
johnfn wrote: post #53

Earlier quoted context omitted.

Err... if you sum all the numbers that’s O(n) as well.

right but OP’s solution for this part of the problem is assumed to be instantaneous (ie O(0))

What is O(0)? Computation that takes 0 time? Does that make any sense?

Re: That XOR Trick (2020)

#95

Post by virgilp »

Strilanc wrote: post #64
virgilp wrote: post #33

Slightly disappointed at the "two missing values" solution: First: one needs to realize that you can solve the "missing number" problem just as well with sums. So, if you're trying to find the "one missing number" between 1 and n, you simply subtract all values from n*(n+1)/2 (the sum of all said numbers) and you end up with the missing one. (using wrap-around semantics, you don't even need to have more bits of memor…

The xor, sum pair can't distinguish missing 11, 0 from missing 10, 1.

Ah, you're right, I didn't think it through. It does feel like there must be a way to play with the bits so that you can retrieve it in a single pass, though - that'd be a much more interesting problem :).

(of course, you can do it with sum + product, but that's going to be fairly expensive for large numbers)

Re: That XOR Trick (2020)

#96

Post by Thorham »

simias wrote: post #46

Careful 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…

You're wrong. Remember that XOR works on individual bits. If what you're saying was true, then swapping bits that are both set to 1 would also fail, which means this algorithm wouldn't work at all.

Edit: Ignore this post, I misread the original post as saying swapping the same values would fail.

Re: That XOR Trick (2020)

#97

Post by shiftingleft »

dragontamer wrote: post #48
jenwkejnwjkef wrote: post #37

Earlier quoted context omitted.

Nobody wants to see the XOR solutions. These questions are really basic and only filter out the non-programmers. Any decent programmer should be able to solve all of these without a problem.

I wouldn't say "nobody" wants to see the XOR-trick solution. Its just that those who DO care about it is asking about the general solution: Reed-Solomon codes, or maybe a more modern (harder to understand) variant: like LDPC or Tornado codes. Anyone who needs to recover *ONE* symbol from a data-stream with noise actually needs to recover two, three... four... symbols in the general case. One symbol of erasure recover…

I don't see how the problem corresponds to erasure coding. Typically in erasure coding you know the locations of the erasures. Here, you don't know the location.

Maybe you can elaborate on how it relates to erasure coding?

Re: That XOR Trick (2020)

#98

Post by jng »

I've known of XOR tricks since the 80s, when you would "undraw" a graphic on the screen by redrawing it with XOR. But only recently I learned that the implementation of multiport memory for CPU caches and the likes often uses a design based on multiple storage copies and XOR to get the last valid written result. Amazed that the CPU's cache is doing that kind of trick all the time just during regular code execution.

Re: That XOR Trick (2020)

#99

Post by dragontamer »

abhishekjha wrote: post #91
dragontamer wrote: post #56

Earlier quoted context omitted.

> I'm not concerned If someone happens to know some esoteric trick that they could Google search (Unless of course you're applying for a position at a company that manufactures very low level devices like microcontrollers or embedded systems and questions like this are _actually relevant_). Erasure correction is a very useful trick for data-engineers. I don't think this is a microcontroller trick, as much as a data-r…

I guess I will fail your interview as well.

Lol. Well, that's why I ended with:

> But at that point, I'm interviewing for someone who has passed a data communications class.

This is basic data-communications stuff. But there's a reason why data-communications isn't exactly a commonly taught subject: its niche and not really generally applicable IMO.

My main point is that the XOR-trick is a decent data-communications question. But I don't know how generally applicable it is to other programming fields.

Re: That XOR Trick (2020)

#100

Post by azhenley »

simias wrote: post #46

Careful 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…

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
Post reply on HN