January 2011
8 posts
Hacker Cup - Problem #2 - Peg Game Solution
The brute force solution solved the sample inputs in a timely manner, which should not be a surprise given that the largest grid in the test set is only 5x4. After I constructed a test set with a 100x100 matrix, things took a predictable turn for the worse. I allowed it run for 30 minutes without result, and didn’t stick around to see the final outcome. Remember, we only have 6 minutes after...
Jan 10th
Hacker Cup - Problem #2 - Peg Game
I was saving this problem for last because I suspected it would give me the most trouble. Turns out that intuition was spot on.  Part of the problem, is that the requirements aren’t 100% clear. Read on through the Facebook problem statement and then rejoin at the bottom for my commentary. ———————— Peg Game At the arcade, you can play a...
Jan 10th
Hacker Cup - Double Squares - Solution
At the end of my last post, I mentioned I was going to run my code against the sample set to see if it works and then try out the worst-case dataset. Well, it worked well against the sample and simply would not complete in the worst case because of my crappy non-algorithm. Let’s think about what I was doing wrong. My approach was to try and sum the squares of every combination of numbers...
Jan 8th
Hacker Cup - Problem #1 - Double Squares
Into the next one. I’m going to save the second one for last because after a brief glance it seems to be the most difficult from a logic context. Again, straight from the FB: ———————- Double Squares A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 3^2...
Jan 8th
Hacker Cup - Studious Student Submitted
I implemented a two-core Concurrent Sort in Java and cut the time in half to 38 seconds for the worst-case scenario. Proof positive that this is a viable avenue for tackling future sort algorithms depending on how it scales. Soon I would like to refactor this code to use an arbitrary number of cores and allow for threshold configuration so that I wouldn’t have to spin up 8 threads just to...
Jan 8th
Hacker Cup - Studious Student Optimization
The way this round works is that once you’ve chosen to download the Facebook-provided data, you have 6 minutes from the time of download to paste the output from your program into the Hack Cup web form. As I mentioned in my previous post, I’m able to execute the worst-case scenario - 100 rows of 9 words of 10 characters in length - in 78 seconds. That may be fast enough for the...
Jan 8th
1 tag
Facebook Hacker Cup - Problem #3 - Studious...
I’ve decided to start working problem #3 first… Here is the problem statement Copy & Pasted directly from the site: Studious Student You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is...
Jan 8th
1 tag
Facebook Hacker Cup - Qualification Round →
I’ll be participating in the Qualification Round of the Facebook Hacker Cup. They’re giving you 72 hours to work through 3 problems. In order to advance to the next round, you need only answer 1 of the problems correctly. As I work through the problems, I’ll be posting here with live updates.
Jan 8th