Sunday, July 31, 2011

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 onDon't forget to restart your secure browser.

Saturday, July 30, 2011

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

Friday, July 29, 2011

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.

Thursday, July 28, 2011

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)

Tuesday, July 26, 2011

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

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

Monday, July 25, 2011

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?

Sunday, July 24, 2011

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.


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

Saturday, July 23, 2011

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

Friday, July 22, 2011

Fermi problems

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

Thursday, July 21, 2011

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?

Wednesday, July 20, 2011

Merge of nodes

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

Tuesday, July 19, 2011

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.

Monday, July 18, 2011

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


Sunday, July 17, 2011

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.

Saturday, July 16, 2011

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)

Friday, July 15, 2011

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?

Thursday, July 14, 2011

Wednesday, July 13, 2011

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)

Tuesday, July 12, 2011

Minimum distance in an array

Given an unsorted array arr[] and two numbers x and y, find the minimum distance between x and y in arr[]. This is in linear time.

Monday, July 11, 2011


You throw a coin. If you get head you stop, if you get tail you throw again. What is the proportion of heads and tail you will get?

Sunday, July 10, 2011

Overlap in the clock

How many times the hands will overlap in a clock? 22. why?

12 is the first
1am will not overlap at 1.05 but a bit later (because when you get 5min, the 1 has already moved a bit)
2am will not overlap at 2.10 but a bit later (because when you get 5min, the 1 has already moved a bit more)
11am is the last one and this point of overlap is very close to 12

So out of 12, there are 11 points of overlap. In 24hours are 22, with 2 "missing".

How much is a bit more? 1/11  because they are uniformly distributed

So 12, 1+1/11, 2+2/11, 3+3/11

Saturday, July 9, 2011

Find the minimum positive sum in an array

You are given an array of integers A and you have to find out the minimum positive sum of array(not necessarily continuous).

PS: I have a solution but not sure it is optimal

Friday, July 8, 2011

numbers of 1 in an integer n

Can you compute the number of 1 bits in a number N in O(N)? how about O(log N) and what about O(1)?

Thursday, July 7, 2011

Similarity between BSTs

Given 2 number streams, find whether they will create the same BST or not

Wednesday, July 6, 2011

Find intersection among social friends

Facebook has a feature which allows to discover the friends in common among two users. How would you implement it in a social graph?

Tuesday, July 5, 2011

Max sum of elements

Given a sequence of integers, find a continuous subsequence which maximizes the sum of its elements, that is, the elements of no other single subsequence add up to a value larger than this one.

Monday, July 4, 2011

UK audience for overseas news titles grows

"Meanwhile, Bing News has more than doubled its UK audience in the last year to 1.43m, up 141%, while Google News has dipped 56% to 1.23m, down from 2.82m last May."


News sites

Sunday, July 3, 2011

Personalization: to hide or to select on your behalf.

I am slightly disappointed by this video because there is no scientific evidence for assuming that something is intentionally hidden. According to  to hide means  "prevent from being seen discovered", or "to conceal from knowledge or exposure". It does not seem to me  that this is the case. Obviously, here we are not discussing about censorship for different countries which is a different topic.

  1. Facebook selects your friends' postings according to your closeness to their point of view. In doing so, they simply try to help you in selecting the most interesting stories. You can question what is the algorithmic definition of "interesting" but nothing is prevented from being discovered and nothing is deleted. Indeed, you can still access the full list of postings just by selecting the "Most recent" order view.
  2. Google can indeed provide different views of their results to different users, for the same query and at the same moment of time. This can be either a form of personalization (e.g. again trying to adapt to different users' tastes), or the fact that you are served by different machines which have different dataset, or the fact that you are in a limited deployed experiment where different algos are tested. Again no scientific evidence that anything is concealed from knowledge or exposure. The information is still there and searchable but different views are provided.
  3. All the other big kids on the block follow more or less a similar set of principles.
Still, the idea of exposing in your ranked results something "surprising" and "un-expected" is quite appealing and it's a part of intense machine learning research. In ML jargon, this is the "exploration" part where you get something new for learning something unknown and never observed before. Exploration is opposite to "exploitation". In Exploitation,  you use what you have learned from the past to personalize your future flow of information.

Saturday, July 2, 2011

Commerce answer

Our Wroclaw colleagues shipped commerce answer in UK and FR. Congratulation to my team in Poland. Well done guys! you rock.

Friday, July 1, 2011