How to prepare for Facebook Hacker Cup?

Facebook hacker cup is an annual algorithmic programming contest organized by Facebook. Be it, students, professionals, or experts it attracts numerous programming enthusiasts from all around the globe. Top contenders are eligible for the interview call from Facebook for the Software Developer role.  

What is the process?

Facebook Hacker cup is particularly known for its different environments used for Judging and the variety of problems. It is conducted in many rounds where the difficulty of algorithmic challenges keeps on increasing. Registration Link

What are the prizes? (May vary year to year)

The 25 finalists will receive the following prizes (in USD:

• 1st Place: $20,000 USD
• 2nd Place: $10,000 USD
• 3rd Place: $5,000 USD
• 4th Place: $3,000 USD
• 5th Place: $1,000 USD
• 6th-10th Place: $500 USD
• 11th-15th Place: $300 USD
• 16th-25th Place: $200 USD

Organized in the month of August Facebook Hacker cup is conducted in 4 series round:

1. Qualification round: This is the easiest round in which at least 1 problem needs to be solved successfully in order to advance to the next round. This round lasts for 72 hours.
2. Round 1: The selected candidates participate in round 1 which lasts for 24 hours and must gain at least a certain number of points ( decided accordingly every year) to qualify for round 2. This round is fairly more difficult than the qualification round.
3. Round 2: Candidates selected from round 1 advance to participate in round 2 and compete in a 3-hour format contest. The top 200 participants advance to Round 3 and the top 500 participants are awarded Hackercup T-shirts.
4. Round 3: Top 200 participants compete in this 3-hour format contest and the top 25 qualify for Onsite Final. From now on the problem set gets tough.
5. Onsite Final: Top 25 participants from all over the globe compete for winning the title and trophy of the Facebook hacker cup at its headquarters. Problems are quite challenging and are good enough to make the contestants sweat head to toe. The time limit for the final round is 4hrs, the winner of the final round will be the Hacker Cup champion.

And the 1st person on the leaderboard bags the title and basks in glory.

Format and Environment

The judging format of the Facebook hacker cup is quite different from other annual programming contests like ACM-ICPC or IOI.

• When the contest begins users are required to login into the website.
• After logging in they are presented with the problem set. After you think you have solved a problem and are sure about its correctness, you have to download an input test file.
• As soon as the input test file is downloaded a timer of 6 minutes commences and in that window of time you are required to run the input test file over your code and form a test file. Within 6 minutes you need to submit both the code and the output text file.
• You can submit more than once and only the last correct submission will be used for evaluation.
• Once the timer expires you will be unable to submit the solution for that problem again. A time penalty is the sum of the submission times of a problem.

How to prepare?

Facebook Hacker cup is particularly famous for its innovative and mind-tickling algorithmic challenges. Inclined more towards mathematics and a combination of various concepts hacker cups test knowledge, implementation, accuracy, speed, conceptuality, and almost everything by its different rounds. You need to be fast in order to survive further rounds and innovative to survive the initial long-timed rounds. These are the main topics that should be done thoroughly as problems are generally asked from more than 1 topic combined.

Number Theory

1. Euclidian and extended Euclidian algorithm
2. Modular Arithmetic and modular inverse
3. Prime generation (Sieve and Segmented Sieve)
4. Fermat`s theorem
5. Euler Totient function
6. Miller Rabin primality test
7. Chinese remainder Theorem
8. Lucas theorem.

 Greedy Algorithms

1. Activity selection problem
2. Kruskal`s Algorithm
3. Prim`s Algorithm.

Binary search

1. TopCoder-Binary Search
2. Binary Search
3. Ubiquitous Binary Search – Get a grasp of discrete and continuous binary search.

Data Structures

1.  Linked lists
2. Binary search tree
3. Binary Indexed Tree or Fenwick tree
4. Segment Tree (RMQ, Range Sum, and Lazy Propagation)
5. Red-Black trees
6. Hashing

An extensive list of Data structures

Graph Algorithms

1. Breadth-First Search (BFS)
2. Depth First Search (DFS)
3. Shortest Path from source to all vertices **Dijkstra**
4. Shortest Path from every vertex to every other vertex **Floyd Warshall**
5. Minimum Spanning tree **Prim**
6. Minimum Spanning tree **Kruskal**
7. Topological Sort
8. Johnson’s algorithm
9. Articulation Points (or Cut Vertices) in a Graph
10. Bridges in a graph

All Graph Algorithms

String Algorithms

Learning library functions for String actually proves very helpful (C++: See this and this, String in Java).

1. KMP algorithm
2. Rabin Karp
3. Z’s algorithm
4. Aho Corasick String Matching
5. Suffix Arrays
6. Trie
7. Finite Automata

Dynamic programming

1. Dynamic Programming – w3wiki
2. Dynamic Programming – Codechef

Dynamic programming is quite important and can be infused and asked with various other topics. Some different types of DP concepts are: Classic DP

1. Longest Common Subsequence
2. Longest Increasing Subsequence
3. Edit Distance
4. Minimum Partition
5. Ways to Cover a Distance
6. Longest Path In Matrix
7. Subset Sum Problem
8. Optimal Strategy for a Game
9. 0-1 Knapsack Problem
10. Assembly Line Scheduling

All DP Algorithms

Computational geometry

1. Convex hull algorithms
2. Geometric Algorithms

All in all Facebook Hacker cup is a very challenging contest and a person needs a gigantic amount of training and perseverance and all the standard topics need to be etched and understood. Practice is the only way to do so! Extra Points:

1. Practice on Codeforces (especially the GYM section) and TopCoder Arena. This will truly help in basic understanding.
2. Facebook Hacker Cup’s problems have a different style than Codeforces and Topcoder, probably the best comparison would be with Google Code Jam which has a similar format.
3. Go through previous Facebook – HackerCup questions and get familiar with the format of the contest.