Ways to get into Facebook

Facebook has some weird ways of getting its employees. Solve any of these puzzles they are currently facing and simply apply!

Some of the many puzzles...

Prime Bits

First, consider a function P(x) where:

  P(x) returns:
   true if the number of 1 bits set in the
     binary representation of x is prime,

   false otherwise.

For example, P(239) returns true, while P(51) returns false.

Next, consider the following function prime_bits:

  uint64_t prime_bits(uint64_t a, uint64_t b);

A call to prime_bits(a, b) returns the number of values between a and b inclusive for which P(x) is true. For example, prime_bits(4, 10) returns 5, while prime_bits(137, 31415926535897) returns 7753256197126. Your job is to implement the prime_bits function.

Your implementation should be efficient, and it should be wrapped up nicely such that one can specify a and b on the commandline when running your program. You may expect the range of a and b to be limited to non-negative 64-bit integers, though it would certainly be uncouth for your algorithm to break down for larger values.

Your implementation should have a running time faster than O(n), where n is b - a.

You may use any of the following programming languages:

• C++
• Java
• JavaScript
• OCaml/SML
• Perl
• PHP
• Python

For extra credit, you may submit additional solutions in the other languages as well as solutions in languages not listed here.

Please send your code and solutions (and a resume) to:

{ (0xFACEB00C >> 2) in decimal format } @ facebook.com

Please put [optimus] in the subject line.

Illegal Wiretaps

After uncovering years of government malfeasance, you are tasked with leading a team of government programmers to decode copious amounts of possibly illegal wiretaps. Your congressional hearing is coming up, and you need to have these wiretaps decoded as soon as possible so you can give as informative testimony as possible (and clear your posterior of any wrong doing!). Unfortunately, government programmers are not the most well adjusted, sharpest tools in the shed, and they require decisive and firm leadership (e.g. you) to guide them. Programmers are assigned integer numbers to protect their classified identities, while wiretap victims are referred to by their first names (a name is defined as a sequence of alphabetical characters).

Due to OSHA regulations, you will always have exactly the same number of programmers as wiretap victims, and each programmer decodes exactly one wiretap. Because this is the government, to decode a wiretap it takes at least 1 server hour per letter in the victim's name. All programmers share the same secured government terminal and they can only work one at a time. Once signed in, programmers must stay at the terminal until they are finished decoding a wiretap. To make things worse, each programmer has certain personality quirks and foibles which can alter their efficiency.

• Programmers with an even number suffer from vowelitosis, they require an additional 1.5 hours of work for every vowel (Note that the NEA only recognizes the letters A, E, I, O, and U as vowels) in the victim's name.
• Programmers with an odd number suffer from consonentia, they require an additional 1 hour of work for every consonant in the victim's name.
• Programmers whose numbers share prime factors with the number of letters in a victim's name are struck with a severe phobia, that requires an additional 2 hours of therapy per common factor. Due to DHS regulations, the programmer must stay at the terminal while under therapy, preventing others from using it. For example, it took programmer 12 (factors of 2 and 3) an extra 4 hours of therapy to decode NORMAN's file (factors of 2 and 3).

You are given 26 programmers, numbered from 1 through 26. The 26 wiretap victims are named as follows:

ANDROMEDA
BARBARA
CAMERON
DAGMAR
EKATERINA
FLANNERY
GREGORY
HAMILTON
ISABELLA
JEBEDIAH
KIMBERLEY
LARISSA
MEREDITH
NORMAN
OSWALD
PENELOPE
QUENTIN
RANDALL
SAVANNAH
 TABITHA
URSULA
VIVIENNE
WINONA
XAVIER
YVONNE
ZENOBIA

Write a program that tasks your team of programmers to the wiretap victims in a way that minimizes the total time necessary to crack all the wiretaps. Your program should run on the command line, and take as input a file containing the first names of all the wiretap victims (newline separated). The output should be the total time cost (in hours) of decoding all the wiretaps listed in the input file, in addition to your configuration of programmers and wiretaps. Your program should be able to handle both upper and lower case, be robust enough to handle or ignore malformed input, and it should work for as large a general case as possible. Remember, your congressional hearing is coming up and your lawyers may need more evidence to clear you of wrong doing!

You may use any of the following programming languages:

• C++
• Java
• JavaScript
• OCaml/SML
• Perl
• PHP
• Python

For extra credit, you may submit additional solutions in the other languages as well as solutions in languages not listed here.

Please send your code and solutions (and a resume) to:

{ (0xFACEB00C >> 2) in decimal format } @ facebook.com

Please put [wiretaps] in the subject line.

Superpatterns

A k-superpattern is defined to be the smallest combinatorial pattern that contains all k-subpatterns.

For example, [1 3 2] and [2 3 1] are 2-superpatterns, since they contain all 2-subpatterns, namely [1 2] and [2 1].

We also see that [2 5 3 1 4] is a 3-superpattern, containing within it all 3-subpatterns:

{ [1 3 2], [2 3 1], [1 2 3], [3 2 1], [3 1 2], [2 1 3] }

A better illustration is given of this example in the above Wikipedia link:

[C]onsider some 3-subpatterns, which we take from 25314: 253, 251, 234, 531, 534, 314. We renumber the selected subpatterns to get 132, 231, 123, 321, 312, 213. Notice that there are more: we could have also picked 514 for example, but that is just renumbered to 312 and is a repetition of one of the subpatterns already picked. In fact, we have selected all the 3-subpatterns, i.e. all 6 (3!) permutations of length 3.

From this, we can see that 25314 contains all possible 3-subpatterns. But, for it to be a 3-superpattern, it must be the smallest such combinatorial pattern.

Then, consider also that in order to have 123 and 321 in the same permutation, by the inclusion-exclusion principle we need a minimium of : 3 + 3 - 1 = 5 numbers (since only one number can be in both the largest increasing sequence and the largest decreasing sequence). This implies that any larger pattern which contains both 123 and 321 as substrings must be at least length 5. 25314 is such a pattern and is therefore a 3-superpattern of length 5.

It can also be easily verified that its reverse, [4 1 3 5 2], is also a 3-superpattern.

Interestingly, we can construct higher superpatterns out of lower ones:

First, consider that [7 2 6 8 3] is a 3-superpattern (a re-numbered version of [4 1 3 5 2]). Prepending "5 1 9 4" results in [5 1 9 4 7 2 6 8 3], a 4-superpattern. This can be verified by observing that 1 and 9 are to the left of the 3-superpattern, so it contains all 4-subpatterns that start with 1 or 4. One can also verify that the remaining 12 patterns are present.^[1]

Write a program to generate the lexicographically smallest k-superpatterns for k in { 5 ... 9 }. That is, we mean that the pattern [1 3 2] is lexicographically smaller than [2 3 1], and that [4 4 4] is smaller than both [10 10 10] and [2 2 2 2].

You may use any of the following programming languages:

• C++
• Java
• JavaScript
• OCaml/SML
• Perl
• PHP
• Python

For extra credit, you may submit additional solutions in the other languages as well as solutions in languages not listed here.

Please send your code and solutions (and a resume) to:
{ (0xFACEB00C >> 2) in decimal format } @ facebook.com
Please put [super] in the subject line

Check for more here.