Facebook Hacker Cup Online Qualification Round Begins Now!

Facebook decided to launch Hacker Cup, a programming contest to attract the world’s best talents to their HQ. The qualification round started on Friday 4pm (US’s PST timezone) and continues for 72 hours, so go ahead and join now.

Facebook’s Hacker Cup, equivalent to Google’s Code Jam. The cheapest way to attract the best talents from all over the world.

Just finished Facebook Hacker Cup Online Qualification Round and thought that I might share some of my thoughts about it.

Just like Google’s CodeJam, this round consisted a total of three problems, and you would need to solve just one of the problem correctly to qualify for the next round.

I admit, I had a lot of fun in this round (which had a lot of hidden surprise in the problems), but the contest’s interface totally suck the hell out of a rhino’s @$$. And seemed like I am not the only one who agrees on this.

The first glitch that really got on my nerves —
As you download the input file, the timer starts to countdown, without you knowing about it. Then, I found a little notice on the corner saying that you would have to refresh the browser after downloading the input file to see the timer. I don’t know why, but this seemed stupid and unacceptable to me.

I totally missed this notice box. Guess they don’t want many people to know that there is actually a little timer.

Second, when you want to submit the answer, it opens up a small text box (by small I mean something like 10×100 pixels), and you are suppose to paste your program’s output to that little text box. What a FAIL — They could have done much better.

No kidding. This is the original size of the text box where you are suppose to paste your answer into.

Third, after you submitted the answer, there is a message box that mentioned that you would need to wait until the contest is over to find out if your answer is correct. Oh well… On the other hand, the timer just continue on ticking until it says “Time expired”. You get multiple chances to submit your answer, but ONLY within the limited time. I learned the hard way. My advice to you is test your code carefully for edge cases before downloading the input. During the limited time you won’t be able to do much about it if you find that your code has a bug.

Time expired… Grrr…

Anyway, enough ranting and let’s move on to the fun part, which are the problems itself.

Double Squares:
This is a really fun problem with a little surprise behind it. While you are reading the problem, you would notice a little subtitle under the main title “Facebook Hacker Cup” that says “Too hard for brute force, switching to dp“. It’s there for a purpose. I knew I did not get this correct because of their timer display requires a browser reload…

Peg Game:
You need to read this problem carefully. Don’t worry, you won’t need much from theory of probability. Reminds me of the binomial theorem. If there are no missing pegs, then the probability of each column could be calculated easily using binomial coefficients. This problem is pretty straight forward, but you need to be some what careful.

Studious Student:
This is a fun problem. It is easy to understand the problem statement and it is also easy to fall into a trap. This problem is not as straight forward as you think it might be.

I will post my analysis and solution after the contest is over. Till then have fun solving the problems!

VN:F [1.9.22_1171]
Rating: 4.0/5 (1 vote cast)
Facebook Hacker Cup Online Qualification Round Begins Now!, 4.0 out of 5 based on 1 rating

40 thoughts on “Facebook Hacker Cup Online Qualification Round Begins Now!

  1. butler

    I found that reading the rules prior to the start of the competition helped me to fully understand what would happen during the competition. Who would have thought?

    VA:F [1.9.22_1171]
    0
  2. Anonymous

    can someone explain how the answer "0 0.375000"
    for 5 4 0 1 2 2

    if i am not wrong this shud be the pegs positions

    …x-x-x-x
    -x-x-x-
    x-x—x
    -x-x-x-
    x-x-x-x

    right ????

    please help!

    VA:F [1.9.22_1171]
    0
  3. 1337c0d3r

    @Anonymous:
    Your pegs' position should be correct. You are probably miscalculating your probability as 0.3333, which is a common error people made.

    VA:F [1.9.22_1171]
    0
  4. 1337c0d3r

    @…:
    All I can say is read the problem description properly again. I found their problem description for this question is not that clear, which is why most of you have problem understanding it.

    VA:F [1.9.22_1171]
    0
  5. Anthony

    Regarding the pegs, if there is a missing peg, does the ball fall vertically or does it carry on at and angle until it does hit a beg? If if goes at an angle what happens when it hits the side
    Also what happens if the ball is dropped straight into a hole?

    VA:F [1.9.22_1171]
    0
  6. 1337c0d3r

    @Anthony:
    Don't over-think. It does not go at an angle. It either drops to the left or to the right 50-50 when it hits a peg. It will then continue dropping vertically (not at an angle) until it hits another peg again.

    Yes, it is possible that the ball is dropped straight to the hole (no pegs in between), which means 100% chance of getting the ball to the hole.

    VA:F [1.9.22_1171]
    +1
  7. Anonymous

    am i wrong if i say i their very first example in description its not 50%?
    i count just 3 correct and 4 incorrect ways…

    VA:F [1.9.22_1171]
    +1
  8. ...

    This is the "map":

    X 0 X 1 X 2 X <—- Start in 0
    A X B X C X D
    X E X F – G X <—- Dash = missing peg
    H X I X J X K
    X 0 X 1 X 2 X <—- The target is 0

    Correct ways:

    0-A-E-H-0 = 0.5 * 1.0 * 0.5 * 1.0 = 0.25
    0-A-E-I-0 = 0.5 * 1.0 * 0.5 * 0.5 = 0.125
    0-B-E-H-0 = 0.5 * 0.5 * 0.5 * 0.125 = 0.125
    0-B-E-I-0 = 0.5 * 0.5 * 0.5 * 0.5 = 0.0625
    0-B-F-I-0 = 0.5 * 0.5 * 0.5 * 0.5 = 0.0625

    Total = 0.25 + 0.125 + 0.125 + 0.0625 + 0.0625 = 0.625

    I think that I'm right, but I'm not sure

    VA:F [1.9.22_1171]
    0
  9. Anonymous

    i did it differently, i count ways – possibilities
    in your map
    1. 0 – a – e – h – 0
    2. 0 – a – e – i – 0
    3. 0 – a – e – i – 1
    4. 0 – b – e – h – 0
    5. 0 – b – e – i – 0
    6. 0 – b – e – i – 1
    7. 0 – b – f – i – 0
    8. 0 – b – f – i -1
    9. 0 – b – f – j -1
    10. 0 – b – f – j – 2

    so thats all ways = 10 and 5 are correct. 5/10 = 0.5

    so who's right? probably neither of us cause the result:D

    VA:F [1.9.22_1171]
    0
  10. Anthony

    That's what I thought, hence asking about falling at angles. However, you can't go between the end peg and the side I don't think. So you may not use routes going via A or H.

    0-B-E-I-0 = 1 * 0.5 * 1 * 0.5 = 0.25
    0-B-F-I-0 = 1 * 0.5 * 0.5 * 0.5 = 0.125
    Total = 0.25 + 0.125 + 0.375

    It sounds weird but it works for all the test cases.

    VA:F [1.9.22_1171]
    0
  11. 1337c0d3r

    To all:
    If you are calculating the probability as the number of correct ways divide by total number of ways, this is incorrect, although it seems correct. This is because not each of the way is equally likely to reach the goal. Anthony's calculation is correct.

    VA:F [1.9.22_1171]
    0
  12. Anthony

    Also what about posting source code? There are a few comments on the event page saying you don't need to, however, none of the cite anything and the rules clearly contradict? How am I meant to submit the solution. Also how would I upload zip files? Finally is it ok to just read input.txt.

    Many thanks and good luck everyone.

    VA:F [1.9.22_1171]
    0
  13. 1337c0d3r

    @Anthony:
    You do not need to post source code for the qualification round, however you would need to do so from the next round onwards. This is confusing for so many people that most of them even tried appending the source code right after their answers.

    VA:F [1.9.22_1171]
    0
  14. Anonymous

    seems anthony is really right. thanks for hint:)

    you dont need to post source code in this round, only if you get to next, i read it somewhere in coments from admin on the wall

    VA:F [1.9.22_1171]
    0
  15. ...

    Yes, Anthony's calculation is correct….

    X 0 X 1 X 2 X <— Line 0
    A X B X C X D
    X E X F – G X
    H X I X J X K
    X 0 X 1 X 2 X <— Line 4

    in my map, the A, H, D and K should not be considered…. (in all maps the ends of lines 1, 3, 5…. should not be considered)

    VA:F [1.9.22_1171]
    0
  16. Anonymous

    Ok thanks.

    Just discovered that my program doesn't work for 100*100 grids (well it does but way too slow)

    VA:F [1.9.22_1171]
    0
  17. James

    Since its a smaller board, can someone explain the last sample input for Peg Game: 3 4 0 1 1 1

    This is what it looks like (i think)
    X-X-X-X
    -X—X-
    X-X-X-X

    I get .75. Someone want to explain how it's supposed to be .5?

    Facebook should definitely have a Q/A interface like Google during the code jam.

    Thanks

    VA:F [1.9.22_1171]
    0
  18. Rob

    According to what Anthony said about end pegs, it has to be something like:
    X _ X _ X _ X
    X _ _ _ X
    X _ X _ X _ X

    I'm still not sure how it got 0.5

    VA:F [1.9.22_1171]
    0
  19. Anonymous

    If we use Anthonys solutio, we'll get a tie for the second input:
    3 4 1 1 1 0

    Will give you those probabilities:
    0: 0.000000
    1: 0.500000
    2: 0.500000
    3: 0.000000

    But FB says that there are no ties. So something has to be wrong.
    As far as I checked on the net, that problem is quite common.
    Can someone show how they calculated this case?

    The other cases work fine, it's just that tie, that I don't get.
    Thanks

    VA:F [1.9.22_1171]
    0
  20. Habitaquo

    The problem is that the grid is not a grid, the correct layout is something like this:

    X 0 X 1 X 2 X <— Line 0
    X A X B X
    X C X D – E X
    X F X G X
    X 0 X 1 X 2 X <— Line 4

    VA:F [1.9.22_1171]
    0
  21. 1337c0d3r

    @Anonymous:
    Yeah I get a tie for that case "3 4 1 1 1 0" too. Does anyone know is this a FB being mistaken saying "There are no ties"?

    VA:F [1.9.22_1171]
    0
  22. Pingback: LeetCode | Technical interview solutions

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*