wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Facebook Puzzles
        
(Message started by: ThudanBlunder on Apr 30^th, 2007, 9:51am)

Title: Facebook Puzzles
Post by ThudanBlunder on Apr 30^th, 2007, 9:51am

Thought you might like these (http://www.facebook.com/jobs_puzzles/).

Title: Re: Facebook Puzzles
Post by R0B1N on May 7^th, 2007, 8:10am

i wonder if we can do 'Prime Bits" puzzle in better than O(M Log N) time ?

M::number of integers between a and b
N::number of bits used to represent integers ::)

Title: Re: Facebook Puzzles
Post by towr on May 7^th, 2007, 8:23am

on 05/07/07 at 08:10:40, R0B1N wrote:

i wonder if we can do 'Prime Bits" puzzle in better than O(M Log N) time ?

M::number of integers between a and b
N::number of bits used to represent integers ::)

I think you probably can, although I'm not entirely sure yet how.
If a-1 and b are powers of two, I can see a fairly easy way to get the answer though. Possibly it can be extended for the general case.
[hide]Say b is 2^k, then you want the sum of the number of (unique) permutations of p 1-bits and k-p 0-bits over all prime p <= k. This is simple enough to calculate.[/hide]

Title: Re: Facebook Puzzles
Post by Eigenray on May 7^th, 2007, 2:52pm

I'm sure it's polynomial in the number of bits k.

[hideb]For each prime p <= k, find A and B, the smallest numbers greater than or equal to a and (b+1), respectively, which have exactly p bits set (B might not exist, but that's easy to handle). To do this, if a has t < p bits set, just flip the rightmost p-t 0s of a to get A. And if t > p, find the rightmost 0 to the left of the rightmost (t-p+1) 1s, make it a 1, clear everything to the right, and then add the appropriate number of 1s (from the right).

Now just increment the count by r(B) - r(A), where r(A) is the lexicographic rank of A as a p-set. Compute r recursively: if A = 2^s + A', where A' < 2^s, then r_p(A) = C(s,p) + r_p-1(A').[/hideb]

Title: Re: Facebook Puzzles
Post by jesse on May 8^th, 2007, 5:40pm

Hey everyone. I stumbled across this forum and thought I'd share my solutions (http://20bits.com/tag/facebook) to two of the puzzles ("Prime Bits" and "Korn Shell"). Facebook asked me to obscure the solutions -- I used to have all the code posted publicly -- but the reasoning is still all three.

Only go there if you want the solutions.

Cheers, and let me know what you think.

Title: Re: Facebook Puzzles
Post by towr on May 9^th, 2007, 12:32am

on 05/08/07 at 17:40:59, jesse wrote:

For the two-character case of "Korn Shell", you wrote down 3 cycles where it ought to be just 11 and 15 (rather than 3, 5 and 11)

A nice and clear write-up of the solution though.

It might be fun to use template meta-programming in C++ to give a solution. You'd be able to calculate all the cases at compile time (rather than doing it in a seperate program beforehand) and still return answers in optimal run-time. Although I wouldn't claim it's easy :P

Title: Re: Facebook Puzzles
Post by jesse on May 9^th, 2007, 10:07am

Oops, yes. I got 165 and then just blindly wrote down the prime factors.

Title: Re: Facebook Puzzles
Post by Barukh on May 10^th, 2007, 3:23am

Jesse, I liked very much your analysis of the "Prime Bits" problem.

Well done! :D

Title: Re: Facebook Puzzles
Post by Barukh on May 13^th, 2007, 3:31am

For any n, estimate the number of "Prime Bits" numbers in the range [1, 2ⁿ].

8)

Title: Re: Facebook Puzzles
Post by Eigenray on May 13^th, 2007, 6:54pm

Let f(n) = the number of prime-bit numbers between 1 and 2ⁿ.

Here's f(n)/[hide]2ⁿ/log(n/2)[/hide].

The dashed red line is based on a sampling of [http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(n/2+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn) - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(n/2-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn)]/[2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn / log(n/2)], where http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif(n) is the prime counting function.