Facebook Interview Questions
- 10of 10 votes
AnswersGiven a function KNOWS(A,B), which returns 1 if A knows B (and not necessarily the other way around) and 0 if A does not know B.
- asafiniu February 27, 2013 in United States
A Celebrity is one who does not know anyone,
and one who is known by everybody.
For a list of N people, find all celebrities in linear time.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 4of 4 votes
AnswersDescribe the actions performed by two functions:
- asafiniu February 27, 2013 in United States
Publish(user, msg) - publishes a new post on behalf of 'user'
GetNewsFeed(user) - gathers 30 posts from 'user's friends to show on his/her news feed.
I was asked to map out the relations required for holding large amounts of data.
As a followup, I had to calculate the number of machines facebook would have to initially buy to start off using this news feed.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer System Design - 0of 0 votes
AnswersConvert a string of Roman numerals to an integer in O(n) time
- asafiniu February 27, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - -1of 3 votes
AnswersThis Question was asked in written round on one of the online coding round, The Question was to code this. Question is as follows.
- raj February 25, 2013 in India
You want to create a staff to use in your martial arts training, and it has to meet some specific requirements.
You want it to be composed of two smaller staves of equal length so that you can either use it as a single staff or as two smaller ones.
You want the full sized staff's center of gravity to be exactly in the middle of the staff.
You have a very, very long branch from which you can cut the pieces for your staff. The mass of the branch varies significantly throughout it, so you use just any two pieces of the same length. Given a description of the mass throughout the branch, determine the longest staff you can make, then return three integers on a single line, the first two indicating the first index of each half-staff, and the third indicating the length of each half-staff.
The input will be given on a single line as a string of digits [1-9], each digit representing the mass of a section of the branch. All sections are the same size and the maximum length of the string is 500. Here is an example:
41111921111119
11119 11119
If the indicated sections are cut from the branch they will satisfy your requirements. They are both the same length, and they can be put together as either 9111111119 or 1111991111, both of which have a center of gravity exactly in the center of the staff.
Center of gravity can be determined by taking a weighted average of the mass of each section of the staff. Given the following distances and masses: Distance: 12345678 Mass: 22241211
Sum of the mass of each section: 2 + 2 + 2 + 4 + 1 + 2 + 1 + 1 = 15 Weighted sum of the masses: 2*1 + 2*2 + 2*3 + 4*4 + 1*5 + 2*6 + 1*7 + 1*8 = 60 Weighted sum / regular sum = 60 / 15 = 4
This means that the center of mass is in section 4 of the staff. If we wanted to use this staff the center of gravity would need to be (8+1)/2 = 4.5.
Here is an example problem:
131251141231 ---- ----
If we take the sections indicated we get 1312 and 1231. By reversing the first one and putting them together we get 21311231
Sum of the mass of each section: 2 + 1 + 3 + 1 + 1 + 2 + 3 + 1 = 14 Weight sum of the masses: 2*1 + 1*2 + 3*3 + 1*4 + 1*5 + 2*6 + 3*7 + 1*8 = 63 Weighted sum / regular sum = 63 / 14 = 4.5
This puts the center of mass exactly in the center of the staff, for a perfectly balanced staff. There isn't a longer staff that can be made from this, so the answer to this problem is
0 8 4
Because the half-staves begin at indices 0 and 8 (in that order) and each is of length 4| Report Duplicate | Flag | PURGE
Facebook Algorithm - 5of 13 votes
AnswersGiven n, output the numbers from 0 to 2^n-1 (inclusive) in n-bit binary form, in such an order that adjacent numbers in the list differ by exactly 1 bit.
- xxyyzz February 23, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 2of 2 votes
AnswersGiven an expression (in single variable) like 4x+13(x-(4x+x/3)) = 9, evaluate x
- chochim February 18, 2013 in India
The expression is a string and the variable is always x.| Report Duplicate | Flag | PURGE
Facebook Algorithm - 1of 1 vote
AnswersGiven a list of integer numbers, a list of symbols [+,-,*,/] and a target number N, provide an expression which evaluates to N or return False if that is not possible.
- chochim February 18, 2013 in India
e.g. let the list of numbers be [1,5,5] and the target number is 9, one possible solution could be 5+5-1.| Report Duplicate | Flag | PURGE
Facebook Algorithm - 1of 1 vote
AnswersDesign a realtime service that tells users which of their friends are currently online.
Your service must implement two functions:// Return a list of friends of `user_id` that are online List<user_id> getOnlineFriends(user_id) // Tell the service that `user_id` is online setOnline(user_id)
You may assume that you have access to the function `getFriendIds(user_id)` which returns you a list of all friend ids for a given user id
- trunks7j February 15, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer System Design - 5of 5 votes
AnswersGiven a hashmap M which is a mapping of characters to arrays of substitute characters, and an input string S, return an array of all possible mutations of S (where any character in S can be substituted with one of its substitutes in M, if it exists).
What is the time complexity? What is the space complexity? Can you optimize either?
- trunks7j February 15, 2013 in United StatesExample input: M = { f: [F, 4], b: [B, 8] } S = fab Expected output: [fab, Fab, 4ab, faB, FaB, 4aB, fa8, Fa8, 4a8]
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array of real numbers A of length n, and some integer k such that 0 <= k < n, write a function that returns the kth largest number in A, where k=0 refers to the largest number.
What is the time complexity? What is the space complexity? Can you optimize either?
- trunks7j February 15, 2013 in United StatesExample input: A = [0.5, 2.5, 1], n=3, k=1 Expected output: 1
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWrite a program to sum two binary numbers represented as strings.
- rodrigoreis22 February 11, 2013 in United States
Input: "110", "01101"
Output: "10011"
Method signature:
public String addBinaryNumbers(String num1, String num2);| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 5 votes
AnswersAs input, you are given two sets:
- kbex07 February 11, 2013 in United States
1) set R of n1 non-overlapping rectangles, whose sides are parallel to the x- and y-axes (ie: not rotated rectangles). Each rectangle denoted by bottom left & top right corner coordinates.
2) set P of n2 points
- let n = n1 + n2
For each point 'p' in set P, find the rectangle 'r_p' in set R that contains 'p'. If 'p' is not enclosed by any rectangle, then 'r_p' is undefined. Otherwise, 'r_p' is unique because of the non-overlapping set.
Goal: come up with a divide-and-conquer pseudocode to solve the general problem in O(n(logn)^2) time.
Asked about points that are on the edge of the rectangle, and they said it was up to me whether to include those or not, just a matter of "<" vs "<=", etc. comparisons. Because it's just pseudocode they were looking for, they were not too concerned with the actual structure of the return value, just that the D&C algorithm showed the logic.
Struggled with it for awhile and they simplified the problem to a ~special case with the constraint where all rectangles of R intersected a horizontal line 'L', and instead give a O(nlogn) algorithm to solve the same problem. I suspect this would've been a subproblem/subroutine of the more general case, but again got a bit lost.| Report Duplicate | Flag | PURGE
Facebook Algorithm - 0of 0 votes
AnswersPrint all the permutaion of a given string.
- adam2008 January 29, 2013 in United States
1) explain time\space complexity?
2) how can you improve time\space complexity?| Report Duplicate | Flag | PURGE
Facebook Ebay Software Engineer / Developer Algorithm Coding - 0of 0 votes
AnswersGiven an integer, return all sequences of numbers that sum to it. (Example: 3 -> (1, 2), (2, 1), (1, 1, 1)). Interview was for a php position.
- AnthonyKiedis January 23, 2013 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm PHP - 1of 1 vote
AnswersGot FB interview questions is not difficult, basically, he is asking to count number of identical chars in a given string with with some special case handling, and return the number with highest count, question is pretty long leaving you to dig an algorithm.
Etc, given string "coffee tuffee", should return 4.
I was having my usual interview brain freeze, and start doing initializing with int, how silly
well after interview when I cool down, it doesn't take long to figure out as code below, little over weighted algorithm but the most concise I can wrote, someone please give more efficient code.
- mailming December 08, 2012 in United Statesdef parseword(a_word): a_word=a_word.lower() count=list(map(a_word.count, a_word)) return (max(count))
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Python - 3of 3 votes
AnswersDesign a system for showing quotes on the web.
- Steve November 09, 2012 in United States
For example, when the user is looking at page A, part of which is reproduced in page B, the system could highlight part of page A present the user with a link to page B.
This is an open-ended system design question.
What constitutes a quote?
How do you find quotes?
How do you make it scale to the web?
How do you handle updates?
How would you arrange the servers?
What data structures would you use?
How much storage would you need?
How would the user agent present information about quotes?| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Application / UI Design - 0of 0 votes
AnswerImplement second/minute/hour/day counters Feb. 4, 2011 8:59pm
- Steve November 09, 2012 in United States
Implement the API that counts the number of events in the last sec/min/hr/day:
SMHDCounter {
void Increment();
int LastSecCount(); // also functions for minute, hour
int LastDayCount();
}
Additional requirements
- you require that the data be quite fresh
- how much storage will they take up
- make sure this works for an active counter, getting 100s of events a second.
- keep the implementation fast. E.g. under 10 mS. Or even better motivate by saying we might have 50 of these SMHD counters on a single status page, and ask the candidate how fast their solution should be.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Application / UI Design - 0of 0 votes
Answersconsider a B2C website like Amazon, which will receive thousands requests from buyer per minutes. How will you design the "shop cart " component for it? where should the customs' shop cart data stored?
- Steve November 07, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Application / UI Design - 0of 0 votes
Answergeneric HashMap implementation
- Steve November 07, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Application / UI Design - 0of 0 votes
AnswersDesign a scalable server for the hangman game
- Steve November 07, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Application / UI Design - 0of 0 votes
AnswersHow do you search thrgough huge flat file?
- Steve November 06, 2012 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Application / UI Design - 0of 0 votes
AnswersDetermining trending topics
- Steve November 04, 2012 in United States
How do you think Twitter determines trending topics?
If needed, explain that trending topics are N most common occurring substrings across all tweets in a given time window, which is constantly moving. Later you can expand the question by putting the scale constraint considering the rate at which tweets come in, etc.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Application / UI Design - 2of 2 votes
AnswersMcDonald’s sells Chicken McNuggets in packages of 6, 9 or 20 McNuggets. Thus, it is possible, for example, to buy exactly 15 McNuggets (with one package of 6 and a second package of 9), but it is not possible to buy exactly 16 McNuggets, since no non- negative integer combination of 6's, 9's and 20's add up to 16. To determine if it is possible to buy exactly n McNuggets, one has to find non-negative integer values of a, b, and c such that
- nishakothari62 November 03, 2012 in United States
6a+9b+20c=n
Write a function, called McNuggets that takes one argument, n, and returns True if it is possible to buy a combination of 6, 9 and 20 pack units such that the total number of McNuggets equals n, and otherwise returns False. Hint: use a guess and check approach.| Report Duplicate | Flag | PURGE
Facebook Developer Program Engineer Python - 1of 1 vote
AnswersWrite a recursive procedure, called laceStringsRecur(s1, s2), which also laces together two strings. Your procedure should not use any explicit loop mechanism, such as a for or while loop. We have provided a template of the code; your job is to insert a single line of code in each of the indicated places.
- nishakothari62 November 03, 2012 in United Statesdef laceStringsRecur(s1, s2): """ s1 and s2 are strings. Returns a new str with elements of s1 and s2 interlaced, beginning with s1. If strings are not of same length, then the extra elements should appear at the end. """ def helpLaceStrings(s1, s2, out): if s1 == '': #PLACE A LINE OF CODE HERE if s2 == '': #PLACE A LINE OF CODE HERE else: #PLACE A LINE OF CODE HERE return helpLaceStrings(s1, s2, '')
| Report Duplicate | Flag | PURGE
Facebook Developer Program Engineer Python - 0of 0 votes
AnswersYou are given an input form such as the following
- panoptic.biopower November 01, 2012 in United States
(1, (2, 3), (4, (5, 6), 7))
Each element is either a number or a list (whose elements may also be numbers or other lists).
Output the numbers as they appear, stripped down into a single list.
E.G. (1, 2, 3, 4, 5, 6, 7)
(Complication - how does your code handle the case of ((((5)))) vs just ( 5 ) ? )| Report Duplicate | Flag | PURGE
Facebook Intern Coding - 0of 0 votes
AnswersYou are given a string that is in roman numeral format.
- panoptic.biopower November 01, 2012 in United States
Output the integer representation.
E.G. You're given XIV
Output 14.| Report Duplicate | Flag | PURGE
Facebook Intern Coding - 0of 0 votes
AnswersYour test randomly changes the comparison operators in your conditionals. This is which kind of testing?
- paramjitmaan786 November 01, 2012 in India for ruby on rails
Mutation test
Glass-box test
Black-box test
Fuzz test| Report Duplicate | Flag | PURGE
Facebook Developer Program Engineer - 0of 0 votes
AnswerWhich of the following guarantees that you have exhaustively unit-tested a piece of code?
- paramjitmaan786 November 01, 2012 in India for ruby on rails
100% C0 (statement) coverage
100% C1 (branch) coverage
100% C2 (path) coverage
None of the above| Report Duplicate | Flag | PURGE
Facebook Developer Program Engineer - -2of 2 votes
AnswersFor a service like TMDb with an HTTP-based RESTful API, a Ruby wrapper library such as the ruby-tmdb gem is necessary in order to call the service from a Ruby app.
- paramjitmaan786 November 01, 2012 in India for ruby on rails
True
False| Report Duplicate | Flag | PURGE
Facebook Developer Program Engineer - 0of 0 votes
AnswersEstimate the # of unique strings with limited memory
- Steve October 28, 2012 in United States
Given a large array of strings S = [s1, s2, ... sN], determine Uniq(S) = how many unique strings there are in S.
(b) How large can N be to solve on one machine using only memory?
(c*) What if N is too large to fully fit in memory?| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Application / UI Design