1. count odd num (xor) , exchange x and y
2. count bit num x&x-1
3. reverse the nth element double pointer
4. large number addition
5. max sum substring, sufficient and necessary condition
6. db group by
7. garbage collection: reference count and mark and sweep
8. newton-raphson
9. knuth-morris-pratt

A warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the 'On' or the 'Off' position. I am not telling you their present positions. The switches are not connected to anything.

"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none, either. Then he'll be led back to his cell.

"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.'

"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."

another prison puzzle

John and Dianne, two journalists (and experienced bridge players), are captured by some foreign government. The guardian says that he can free them, if they win the following game. First, Dianne must choose five random cards from a standard 52 card pack. Then, she must send one card at a time (through the guardian) to John. When John receives the fourth card, it must correctly guess the fifth card that Dianne still has. If he guesses correctly, they are both free. Otherwise, they will both stay in prison forever.

Can John and Dianne exit the prison in these conditions?

Assumptions:
- Before the actual game, John and Dianne can talk together for one day and decide their playing strategy. But, after that, they cannot communicate in any way - they are now completely isolated forever (or, at least, until they get out from the prison). Also, they are completely isolated from the outer world (no cell phones) etc. The only method to communicate between them will be through the cards that Dianne sends to John.
- The time interval between delivering the cards cannot be used as a method to communicate information. In fact, the guardian might randomly delay delivering the cards to John just to make sure that they are not using this trick to send additional information.
- Dianne cannot alter the cards the she sends in any way to send additional information. In fact, after receiving a card from Dianne, the guardian might send to John another (almost identical) card of the same type, to make sure that she didn't use the card to send additional clues to John.

back-of-envelope-calculation

The average number of customers in a stable system (over some time interval), N, is equal to their average arrival rate, λ, multiplied by their average time in the system, T, or:

Although it looks intuitively reasonable, it's a quite remarkable result, as it implies that this behavior is entirely independent of any of the detailed probability distributions involved, and hence requires no assumptions about the schedule according to which customers arrive or are serviced. The only assumption is that the system operates in a first-come-first-served manner (FCFS).

regarding binary search: watch the condition

find an O(n) complexity algorithm to find the kth big(or small) element; Hoare's algorithm based on quicksort

Newton iteration: simulate function by straight line: x(i+1) = x(i)-f(i)/f(i)'

basic principles of graph theory

1. The number I of loops in an arbitrary undirected connected graph is related to the number of its edges L and vertices N: I = L + 1-N

2. the clustering coefficient C of a vertex is the ratio between the total number y of the edges connecting its nearest neighbors and the total number of all possible edges between all these nearest neighbors, C = 2y/(z(z-1)). Thus, the clustering coefficient for tree is zero.