Facebook Interview Questions
- 5of 5 votes
AnswersGiven a self-balancing tree (AVL), code a method that returns the median.
- Diego May 16, 2014 in United States
(Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is
2, 7, 4, 9, 1, 5, 8, 3, 6
then the median is 5.)| Report Duplicate | Flag | PURGE
Facebook iOS Developer Trees and Graphs - 3of 3 votes
AnswersCreate the data structure for a component that will receive a series of numbers over the time and, when asked, returns the median of all received elements.
(Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is
2, 7, 4, 9, 1, 5, 8, 3, 6
then the median is 5.)
Model the data structure for a component that would have these two methods:@interface SampleHandler { - (void)addNumber:(NSNumber*)number; - (NSNumber*)median; }
Justify your decisions. Calculate the complexity of each method.
- Diego May 16, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook iOS Developer Data Structures - 10of 10 votes
AnswersYou want to create a staff to use in your martial arts training, and it has to meet some specific requirements.
- krvangala98 April 25, 2014 in United States
1. 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.
2. 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 Software Engineer / Developer Algorithm - 3of 3 votes
Answers/**
- g April 23, 2014 in United States
* Implement a function OneEditApart with the following signature:
* bool OneEditApart(string s1, string s2)
*
* OneEditApart("cat", "dog") = false
* OneEditApart("cat", "cats") = true
* OneEditApart("cat", "cut") = true
* OneEditApart("cat", "cast") = true
* OneEditApart("cat", "at") = true
* OneEditApart("cat", "acts") = false
* Edit is: insertion, removal, replacement
*/| Report Duplicate | Flag | PURGE
Facebook Algorithm - 2of 2 votes
AnswersGiven an array of words, write a method that determines whether there are any words in this array that are anagrams of each other.
- valheru April 23, 2014 in United States
Sample #1: @[@"bag", @"bat", @"tab"]; // output TRUE
Sample #2: @[@"gab", @"bat", @"laf"]; // output FALSE| Report Duplicate | Flag | PURGE
Facebook iOS Developer Algorithm - 0of 0 votes
AnswersAn UIView A2 is subclassed from the same parent as an UIView A1.
- valheru April 23, 2014 in United States
Given inputs of A1, A2, and an UIView that is in the tree of UIViews of A1 somewhere, return the exact UIView that mirrors this in A2.
Example setup:
A1------------
| |
UIView UIView
|
UIView <-- Given this
A2------------
| |
UIView UIView
|
UIView <-- Find/return this| Report Duplicate | Flag | PURGE
Facebook iOS Developer Trees and Graphs - 1of 1 vote
AnswersGiven a list of n sorted lists of numbers, write a method that returns one giant list of all the numbers in order.
- valheru April 23, 2014 in United States
Example input:
NSArray* input = @[
@[@2, @5, @10],
@[@25, @100, @105],
@[@7, @56, @42],
.......
];| Report Duplicate | Flag | PURGE
Facebook iOS Developer Sorting - 4of 4 votes
AnswersGiven the following hashmap for numeric to alpha translation of a telephone keypad:
- valheru April 23, 2014 in United States
NSDictionary* dict = @{@2: @[@"A", @"B", @"C"],
@3: @[@"D", @"E", @"F"],
@4: @[@"G", @"H", @"I"],
@5: @[@"J", @"K", @"L"],
@6: @[@"M", @"N", @"O"],
@7: @[@"P", @"Q", @"R", @"S"],
@8: @[@"T", @"U", @"V"],
@9: @[@"W", @"X", @"Y", @"Z"]};
Write a method that takes a phone number as input and returns all possible letter combinations for that phone number.| Report Duplicate | Flag | PURGE
Facebook iOS Developer Algorithm - 4of 4 votes
AnswersGiven a current absolute path, e.g., "/usr/bin/mail", and a relative one, e.g, "../../../etc/xyz/../abc" return the absolute path created from the combination of the first two paths. In the example strings, the answer should be "/etc/abc".
- meh March 24, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 3 votes
AnswersPrint all paths of a binary tree from root to leaf.
- meh March 23, 2014 in United States
Later, extend the solution to work with graphs, careful attention to cycles which you should print as paths as well (without printing visited nodes twice).| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Data Structures - 1of 3 votes
AnswersGiven two extremely large numbers - each number is stored in a Singly Linked list, with the MSB at the head. You are not allowed to reverse the Linked lists. Write a program to multiply them in optimum space and time.
- arjunsharmacool1 March 17, 2014 in United States for Infrastructure| Report Duplicate | Flag | PURGE
Facebook Member Technical Staff - 11of 13 votes
Answersinput [2,3,1,4]
- balahana March 07, 2014 in United States
output [12,8,24,6]
Multiply all fields except it's own position.
Restrictions:
1. no use of division
2. complexity in O(n)| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 4of 4 votes
AnswersGiven a matrix with 1's and 0's, a rectangle can be made with 1's. What is the maximum area of the rectangle.
- bharadwaj.tanikella23 March 05, 2014 in United States
00010
11100
11110
11000
11010 In this test case the result needs to be 8.
How:
00010 00010
11100 11 100
11110 11 110
11000 11 000
11010 11 010
If you see above the 11's are used from the first two columns and last four rows making the area or count of 1's to be 8.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 2of 4 votes
AnswersImagine x is an operand and * is a binary operator. We say a string of x and * follows Reverse Polish notation if it is a postfix notation.
- mahdi.oraei March 03, 2014 in United States
For example strings xx*, x, and xx*xx** follow Reverse Polish notation.
Given a string of x and *, how many insert, delete, and replace operations are needed to make the string follow the RPN.
For example, xx* need 0 operation to follow RPN since it already follows RPN.
x*x needs two operations to become xx* which follows RPN.
*xx* needs one operation to become xx* which follows RPN.
Your algorithm should work for a string of size up to 100.| Report Duplicate | Flag | PURGE
Facebook Developer Program Engineer - 7of 15 votes
AnswersWAP to modify the array such that arr[I] = arr[arr[I]].
- praveen February 28, 2014 in United States
Do this in place i.e. with out using additional memory.
example : if a = {2,3,1,0}
o/p = a = {1,0,3,2}
Note : The array contains 0 to n-1 integers.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 6of 8 votes
AnswersGiven a linked list where apart from the next pointer, every node also has a pointer named random which can point to any other node in the linked list. Make a copy of the linked list.
- Interviewee February 27, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 9of 9 votes
AnswersMicrosoft Excel numbers cells as 1...26 and after that AA, AB.... AAA, AAB...ZZZ and so on.
- Interviewee February 27, 2014 in United States
Given a number, convert it to that format and vice versa.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 1of 1 vote
AnswersDesign question: Say you have hacked in to a network and can deploy your bot thousands of machines, how would you design your bot so that all the machines work together to download a website, say wikipedia. There should be load balancing and a page should be queryable given its URL.
- Interviewee February 27, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 1of 1 vote
AnswersGiven a matrix of letters and a word, check if the word is present in the matrix. E,g., suppose matrix is:
- Interviewee February 27, 2014 in United States
a b c d e f
z n a b c f
f g f a b c
and given word is fnz, it is present. However, gng is not since you would be repeating g twice.
You can move in all the 8 directions around an element.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 2of 2 votes
AnswersGiven a matrix consisting of 0's and 1's, find the largest connected component consisting of 1's.
- Interviewee February 27, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 1of 1 vote
AnswersGiven two arrays of sorted integers, merge them keeping in mind that there might be common elements in the arrays and that common elements must only appear once in the merged array.
- Interviewee February 27, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 2of 2 votes
AnswersGiven a normal binary tree, write a function to serialize the tree into a string representation (returning the string), and also a function to deserialize a serialized string into the original binary tree.
- Microwish February 25, 2014 in China| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - -2of 2 votes
AnswersGiven a normal binary tree, write a function to serialize it into a string representation (returning a string), and also a function to deserialize the string into the original binary tree
- Microwish February 25, 2014 in China| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 5 votes
AnswersA professor wants to see if two students have cheated when writing a paper. Design a function : hasCheated(String s1,String s2, int N) that evaluates to true if two strings have a common substring of length N. Additional question after implementation. Assume you don't have the possibility of using String.contains() and String.substring(). How would you implement this?
- dke.ade February 25, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Java - 4of 4 votes
AnswersGiven a list of 4 billion integers, find an integer not in the list using 4MB of memory. (interview was in Java)
- dke.ade February 25, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Java - 4of 4 votes
AnswersWrite atof in Java, which converts a string representation of a float (like "342.18E-10") to an actual float without using any built-in parsing functions.
- dke.ade February 25, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 3of 5 votes
AnswersGiven a Binary Tree (balanced or not) write a method that transforms the tree in a degenerate tree (basically a data structure like a sorted linked list where each node has the left child null) and returns the new root. This must be made in place, no external memory usage is allowed.
- Ray February 23, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Trees and Graphs - -14of 14 votes
AnswersIdea student
- manojsainitoda February 22, 2014 in United States for single| Report Duplicate | Flag | PURGE
Facebook Student student Ideas - -12of 12 votes
AnswersI idea student for facebook.
- manojsainitoda February 22, 2014 in United States for single| Report Duplicate | Flag | PURGE
Facebook Student student Ideas - -9of 11 votes
AnswersWhat are the screen dimensions of various iPhone models?
- thinkrightthru February 20, 2014 in India| Report Duplicate | Flag | PURGE
Facebook iOS Developer Graphics