61–70 of 243 posts
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…
I hope this article takes off so that my company will have to change its initial code screen. We make no use of xor in our rather large codebase (I’ve checked) yet pin a lot on whether an interviewee is aware of this trivia.
You have a single question that is always present in your "initial code screen"? XOR-only questions are poor unless you're interviewing someone for a very specific kind of role.
He never claimed that. It could just be part of the screen
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 works: Node * previous=(Node * )current.xored XOR (Node * ) next.
The first and last node can use 0 as previous or next node, or you make a circular list. You do have to store a pointer to the first and last node, as usual.
I've never seen this used in the real world, which is probably a good thing. It also plays hell with garbage collectors like Boehm, as they can't derive the 2 used adresses.
UPDATE: And of course wikipedia knows everything: https://en.wikipedia.org/wiki/XOR_linked_list
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…
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…
$ python
>>> a, b = 1, 2
>>> bool(a) ^ bool(b)
False
>>> a, b = 1, 1
>>> bool(a) ^ bool(b)
False
>>> a, b = None, None
>>> bool(a) ^ bool(b)
False
>>> a, b = None, 1
>>> bool(a) ^ bool(b)
True
(Note: this doesn't work if a value can be 0, because bool(0) is False in Python).
This helps to avoid having to write something like `(a is not None and b is not None) or (a is None and b is None)`.
> 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…
The "XOR trick" actually nearly sank me on an interview once, I'm assuming because the interviewer shared your opinion. One of the questions they asked me to solve was the "n - 1 numbers in a list" question the article talks about - I promptly came up with the XOR solution because I have more background in low-level work than the high-level finance role I was interviewing for. Turns out, they had never seen it before, didn't really understand how/why it worked, and they took a lot of convincing to accept it as correct.
I think I only still got the job was by then proceeding to also solve the problem the "normal" way.
Store predecessor XOR successor in each node.
I suspect this clicks already with everyone, and I don't need to explain forward and backward iteration.
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…
I sometimes use your "bug" on purpose in tests, when checking that two values are either both defined or both undefined, but not one defined and one undefined: $ python >>> a, b = 1, 2 >>> bool(a) ^ bool(b) False >>> a, b = 1, 1 >>> bool(a) ^ bool(b) False >>> a, b = None, None >>> bool(a) ^ bool(b) False >>> a, b = None, 1 >>> bool(a) ^ bool(b) True (Note: this doesn't work if a value can be 0, because bool(0) is Fa…
A = { 1, 2, ... , k, ..., n-1, n}, for 1 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 ca…
input zz(int)
0 0
1 2
2 4
3 6
-1 1
-2 3
zz(n int64) => (n > 63)
unzz(n int64) => (n >> 1) ^ (-(n & 0x1))
Edit: Fixed unzz, ref: https://github.com/lemire/FastIntegerCompression.js/blob/033...