Travelling a lot? Secure your connection with SOCK and safe DNS requests.

Sometime it is useful to setup a secure connection and here I share my simple method.

Suppose you have a secure server with no traffic limitation. In this case, you can setup a SOCK connection to this server by using Putty and the "Connection | SSH | Tunnels" menu. You will add a rule like the following: source port = 7070, destination = localhost: 7070, with dynamic option (see here for more details). Then,  you have to setup your browser for using of this sock proxy (for instance firefox or internet explorer). Now all your web connections are secure and will be tunnelled trough the SOCK proxy. No one can listen to them.  Well sort of..

Still DNS requests will go through your local DNS server and there is a risk that your traffic will be spoofed or that some name resolution requests will be filtered according to local policy. In order to avoid this situation, you may want to solve all the DNS requests from the other side of the sock tunnel. In firefox you can get this by using network.proxy.socks_remote_dns on. Don't forget to restart your secure browser.

From rand5() to rand6()

Given a uniform random generator in range [1..5] rand5(), write your own rand6().

a plus: evaluate the space and the complexity

A classical one: mutex or semaphore

What is the difference between a mutex and a semaphore? and which one would you use to make a counter multithread.

Learn how to select a display ads

Quite interesting talk by the way of Andrei. Particularly impressed by how good the linear regression works for this problem. (well, linear regression is always working well and it's so simple)

In a country in which people only want boys…

…every family continues to have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in the country?

This one is particularly intriguing:

a.  given that we have N families we will have N males
b.  how many kids do we have?


1, 1 boy   -> N/2 kids
10, 1 boy, 1 girl -> possible combinations are 01, 10 -> 2 * N / 4 (01 has N/4 chances)
100, 1 boy, 2 girls -> possible combinations are 3 * N / 8
1000, 1 boy, 3 girls -> possible combinations are 4 * N / 16
10000 100000 

N ( 1/2 + 2/4 + 3/8 + 4/16 + ... ) ; N ( 1/2 + 2/4 + 3/8 + 4/16 +  + n / 2^n ) 


now that above recurrence is the one used for saying that the time for building an heap is linear (if you remember the demonstration) and this should give you an hint for the solution

1/2 + 2/4 = 1
3/8 + 4/16 + ... + n / 2^n = 1

the total number of kids is 2N

3. So the number of females must be 2N - N = N

bob sending a message to eve

You need to check that your friend Bob has your correct phone number, but you cannot ask him directly. You must write the question on a card and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read the phone number?

I found it on internet and it's cool. At first glance you'll try to encrypt. But this is just about checking and Eve cannot change the message (this is not an hypothesis). So you can leverage this property

a XOR b XOR b = a

and send this message "XOR the number with this string".  Cool XOR isn't it?

A classical puzzle: 2 eggs

This is frequently asked by Goldman and Sachs: You are given 2 eggs.You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process.

Solution:

1st attempt: linear search. 100 tentatives, why 2 eggs?

2nd attempt: binary search, if it breaks go linear with the second one. this means 1+ 49

3rd attempt:

start at floor x, if it breaks make a sequential search 1.. x -1, else go to x+x-1 because you have already used one egg (-1) --> x + x - 1 + x - 2 + ... + 1 = x ( x + 1 ) / 2 = 100 --> x = 14

You're the captain of a pirate ship…

…and your crew gets to vote on how the gold is divided up. If fewer than half of the pirates agree with you, you die. How do you recommend apportioning the gold in such a way that you get a good share of the booty, but still survive?

Hint: start with a concrete example of 5 pirates and 100 coins, and try to maximize your gain.

step 1: 100 to you, you die
step 2: 50 to you, 50 to other 2 pirates. if one says no, then you die and 4 pirates have to divide 100 coins
...
...

Fermi problems

Enrico Fermi studied in Pisa, and it was also interested in puzzles and created the typical Fermi Problem class

Every man in a village of 100 married couples has cheated on his wife…

Every wife in the village instantly knows when a man other than her husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village visits and announces that at least one husband has been unfaithful. What happens?

Solution: clearly if there > 1 man cheating, but they must be all cheating otherwise they would have been discovered.

Persistent tree

You need to build a tree and keep it persistent in memory. What approach would you use?

Merge of nodes

Two lists merge at some node. Find it in optimal time.

what degree is the angle when it's 3:15?

1 hour is 360 / 12 = 30 degrees,  in 1 hour will move of 30 degrees. Therefore in 15 minutes, 0.4 x 30 = 7.5 degrees. The key observation is that the hour will move when you go to 15 mins.

Sort a trillion of integers, how many seconds?

1 trillion = 1 million * 1000 * 1000 = 10 ^ 6 * 10 ^ 6 = 10 ^ 12

O(10 ^ 12 log 10 ^ 12) ; log 10 ^ 12 = 12 log 10 =~ 30, now assuming 1 billion operations per sec

...

Given a circular list with ascending numbers.

The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36. Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list.

the list is rotated by a factor k, so in linear time you find how long is this k. Then you apply a selection shifted by this k in modulo, and each # will cost log (N) with N size of list.

Car in an highway

probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?

As usual, it's convenient to consider the opposite (i.e. the probability of not observing any car for 30 minutes = 0.05, which is the equivalent to the probability x of not observing car for the first 10mins and the second 10 mins and the third 30 min and all of them are x^3 = 0.05 assuming uniform distribution -> x = cubic_root (0.05). So we know the probability of not observing cars for 10 minutes x, our answer is 1 - x , x = 0.37)

A room with 10 people

I give you 1$ for each person you find which has the birthday my same day, otherwise you give me 2$. Do you accept the bet?

In how many ways can one tile a 2 X N strip of square cells with 1 X 2 dominos?

found this on internet and wanted to solve. nice application.

A feature suggestion for facebook

I posted this status: "Klimt my favourite artist ever is 149 today.". It would be great to link a word to a search in my favourite search engine

Given two matrices M=[nxm] P=[pxq] of integers

Device an algorithm for matching P in M (hint: you can move P in all the direction and a positive result is a full overlap)