Last week a friend asked me to help him prepare for a job-interview at FB. The first thing I did was pointing him to Cracking the Coding Interview which provides an excellent overview of all the main subjects an Engineer might be asked during an interview. My recommendation was to take the time and go through each and every chapter, and try to solve the questions. It’s very important not to “cheat” and try hard to solve them by yourself – otherwise you won’t improve!

Another important thing is, in case you weren’t able to solve a question and you checked out the answer – DO NOT try to memories it! instead, go on and continue solving other questions, and after a few days, try again to solve that same question. You might be surprised to find out that even though you saw the answer – it’s not always trivial to re-write it. Further, this is a good exercise that sharpens another important skill: being able to write code that expresses the algorithm we have in mind.

There’s plenty of good information available online, just Google it and you’ll find excellent blog posts such as this one, and many others.

Another smart thing my friend did was to go over job-interview websites and forums and copy questions that other candidates wrote they were asked during their interviews in FB. The following is a list of such questions:

1. Calculate the square root of a double
2. Given n intervals [si, fi], find the maximum number of overlapping intervals.
3. Print all the paths from root to every leaf in a binary tree.
4. Print the sum of all the numbers at every vertical level in a binary tree
5. Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum ?
6. Given 1 trillion messages on FB and each message has at max 10 words, how do you build the index table and how many machines do you need on the cluster to store the index table ?
7. Given an input array and another array that describes a new index for each element, mutate the input array so that each element ends up in their new index. Discuss the runtime of the algorithm and how you can be sure there won’t be any infinite loops.
8. Find all the anagrams in an array of strings
9. Combinations(n, k) – print all combinations of k out of n items
10. Printing a binary tree L-R,
11. Implementing a comparator function to sort files based on a certain naming convention.
12. Implement a LRU cache
13. Design FB newsfeed
14. How would you query for all the Places near a given coordinate? The focus is on how to scale this to a large number of places while keeping response time to within acceptable user expectations
15. Given a list of words, group anagrams.
16. Find all 3 items that sum to 0 in an array.
17. Write a function that calculates input strings with operators +,-,*,/ eg. “5+5*6″ should output 35
18. Printing the nodes of a linked list in reverse
19. Finding the longest palindrome in a given string
20. Finding maximum subarray sum (similar to Kadane’s Algorithm) with the constraint that two numbers in the array that form the max sum cannot be next to each other
21. How do you use Facebook app and what are the problems with it? How would you fix it?
22. Design a Facebook travel app
23. designing a system to do spam detection work and describing it in a huge flowchart, as might be done in an early but detailed product planning session. Be prepared to think on large scales.
24. Write a palindrome-checking function
25. Print a tree, level by level.
26. Write all solutions for a^3+b^3 = c^3 + d^3, where a, b, c, d lie between [0, 10^5]
27. Print a list in reverse
28. Compute maximum profit for buying selling a stock given an array of prices for n days.
29. Check if two binary trees are Isomorphic
30. How would you come to an agreement if you and another senior level engineer couldn’t agree on a technical design?
31. Write a function that takes 2 arguments: a binary tree and an integer n, it should return the n-th element in the inorder traversal of the binary tree.
32. Add up two big integers represented in arrays.
33. Design a system to support Facebook status update.
34. Design the recommendation system for search keywords
35. Given 2 very large numbers, each of which is so large it can only be represented as an array of integers, write a function to multiply them.
36. Write a function to display a JSON string in pretty format.
37. Write a function to check if polygon is simple based on given list of points
38. Function to compute the number of ways to climb a flight of n steps. Taking 1, 2, or 3 steps at a time. Do it in Linear time and constant space. Example:

    n = 3.
    1 1 1
    1 2
    2 1
    3
    Ans = 4

39. Interweave a linked list. Do it in Linear time and constant space.

    Input: A->B->C->D->E
    Output: A->E->B->D->C

40. Given a dictionary based simple password, create all possible (special character) passwords based on a provided mapping.

    Input: face
    Map: {a -> @, 4, A}
    Output: f@ce, f4ce, fAce

41. Get numeric number out of a roman string, linear time

    Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
    Input/Output:
    II = 2, III = 3, IV = 4
    VI, VII, VIII
    IX = 9
    XL = 40,
    XLIX = 49

42. Merge ‘k’ sorted arrays, each array may have max ‘n’ elements
43. What would you change in Facebook?
44. Given a sorted array, write a program to decide if two elements sum up to a third.
45. Determine the 10 most frequent words given a terabyte of strings

Good Luck!