Thank you for raising the question Dear Facebook

Indian Statistical Institute and an inherant problem in hashing

Facebook_1

This is an interesting question formed in Indian Statistical Institute. Let us take it at a different angle.

26 letters of an alphabet from A to Z can have 26^7 combinations, including repeatations.

Now, number of combinations that COVFEFE can form is atmost  Factorial (7) / (Factorial (2) * Factorial(2)). Of all the occurances out of these 7 possible combinations of the 7-letter digit COVFEFE, COVFEFE occurs at a particular permutation.

Now, alphabetically, C comes before E, and E comes before F. Now, the number of occurances of the word COVFEFE will have basically C, E, F, O, V with E and F occurring twice in the word. The word COVFEFE will have Factorial (7)/ (Factorial (2) *Factorial (2)), that is, 1,260 occurances.

If we fix the first alphabet according to dictionary, then C will come first, and the rest of the alphabets will have their occurances. Let us fix C in the first place. Then, we need to find the rank of OVFEFE, after C.

Now after C, the alphabetical order will come as E, F, O and V. The combination of words will have Factorial (6) / (Factorial (2) * Factorial (2)), which is 180 in permutations, including repeatations. To start with O, there will be more than 180 + 180 or 180*2 permutations, which is 360.

Now, if we fix E at the first place, there will be Factorial (5) / Factorial (2) permutations, which is 60 in number. Similarly, there will be 60 more for F. Let us now fix O now. Then we will have F, E and V, with 5 occurances with F and E repeating twice.

Hence after 180 + 180 + 60 + 60, the word will occur, if we maintain the rank of the dictionary. This is after 480 occurances of the permutation of the letters given.

Now, let us find the permutations of EEFFV. If we fix the last alphabet V at the start, then E , F and V needs to be sorted according to the dictionary. Now for these 5 occurances, the number of alphabets Factorial(5)/ ( Factorial (2)* Factorial(2)), which is 60. Now for the order of dictionary, E and F come before V. Hence, 60 + 60, or 60*2 will happen before V comes to tyhe first place of EEFFV. The occurances will be like EEFFV, EFEFV, EFFEV, FEFEV, FEEFV, FFEEV, VEEFF, VEFEF, VFEFE.

Now, if we fix V, then there will be Factorial (4)/ (Factorial(2) * Factorial(2)), which will be 6 in occurance.   The combinations will be EEFF, EFEF, EFFE, FEEF, FEFE, FFEE. Here the number is 5th.

Hence, out of the total 1 ,260 combinations, this will have a rank of occurance. Hence the rank is = 180 + 180 + 60 + 60 + 5 = 485.

We need to open 484 arrangements of permutations based on that. It is a key concept in password matching, indexing or machine learning, popularly called in the paper as Mr. Trump! This is a key concept of algorithmic keys!

Now suppose, taking the machine as unbiased and regular in work, if we take 0.15 nanoseconds for analyzing, then the total time taken would be 0.15 * 485 = 72.75 nanoseconds! Thank you Facebook for raising such a nice question!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s