Two Equivalent Bitwise Exps

(a & b) | (a & c) | (b & c)

(a | b) & (a | c) & (b | c)

at each bit of a, b and c, at least two of them should have 1.


Updates: [tested]
in Java, this applies for types like int, char, Integer, long, etc
Doesn't work for float, String, double.

Swap Variables with Zero Space Requirement

void zero_space_swap(int* x, int *y){
     *(x) ^= *(y);
     *(y) ^= *(x);
     *(x) ^= *(y);
}

Online selection algorithm. Random Selection in Linked Lists with Unknown Length

Question: Given a finite linked list with unknown length(in terms of nodes count), select one item(multiple nodes) with equal possibility for every node in the linked list.

* One item only.
Assuming the input list has k nodes. The possibility for each node to be selected is 1/k. We need to guarantee that after we visiting m nodes, the possibility for each node is 1/m.



Proof of correctness:
When i = 0, node 0 is selected with 100% possibility.
When i = 1, node 1 has 50% chance to replace node 0 as selection result. Both of node 1 and node 0 will have equal chance to be chosen.
When i = n(which means we are testing the (n+1)th node), before line 3 is executed, all nodes from node 0 to node n-1 have possibility of 1/n to be selected. The (n+1)th node has 1/(n+1) possibility to be selected at line 3. For the previous selected node, it has a possibility of n/(n+1) to survive this round. Multiplying with its chance to be selected: 1/n, we get 1/(n+1) as well,

*Extended: Multiple items.
Assuming we have k nodes in the list and we are targeting a result set of size m,
each node will have possibility of m/k to be added to the result set.