Facebook Interview Questions
- -1of 1 vote
AnswersThere is a list of rectangles and a list of points in a 2d space. Note that the edge of each rectangle are aligned to XY axis. question is how to find rectangles with point or points inside
- rjrush December 15, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 4of 4 votes
AnswersGiven a list of strings, return a list of lists of strings that groups all anagrams.
- tirelative December 13, 2014 in United States
Ex. given {trees, bike, cars, steer, arcs}
return { {cars, arcs}, {bike}, {trees, steer} }
m = # of words
n = length of longest word
I solved this in O(m * n * log n) time.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 0of 0 votes
AnswersArray of size (n-m) with numbers from 1..n with m of them missing. Find one all of the missing numbers in O(log). Array is sorted.
- suu December 05, 2014 in United States
Example:
n = 8
arr = [1,2,4,5,6,8]
m=2
Result has to be a set {3, 7}.| Report Duplicate | Flag | PURGE
Facebook SDE1 - 0of 0 votes
AnswersYou are given an array of non-negative integers (0, 1, 2 etc). The value in each element represents the number of hops you may take to the next destination. Write a function that determines when you start from the first element whether you will be able to reach the last element of the array.
- Anon80 December 02, 2014 in United States
if a value is 3, you can take either 0, 1, 2 or 3 hops.
For eg: for the array with elements 1, 2, 0, 1, 0, 1, any route you take from the first element, you will not be able to reach the last element.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 7of 7 votes
AnswersGiven an array of integers.
- Victor November 27, 2014 in United States
Move all non-zero elements to the left of all zero elements.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 2of 2 votes
AnswersThere's a new language which uses the latin alphabet. However, you don't know the order among letters.
- Victor November 27, 2014 in United States
It could be:
a b c d ...
as it could also be:
b e z a m i ...
You receive a list of words lexicographically sorted by the rules of this new language. From this list, derive one valid particular ordering of letters in this language.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 3of 3 votes
AnswersWrite a program to find pattern.
- pritishshah.it November 20, 2014 in United States
0: 1
1: 11
2: 21
3: 1211
4: 111221
5: 312211
Iterate over the previous number, and find count for same number number. Append that count before number.
e.g.,
public String pattern(int input){}
If input = 4, function should return 111221.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 3 votes
AnswersLet's say there is a double square number X, which can be expressed as the sum of two perfect squares, for example, 10 is double square because 10 = 3^2 + 1^2
- baudday November 17, 2014 in United States for Emerging Markets
Determine the number of ways which it can be written as the sum of two squares| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 3 votes
Answerswrite an algorithm to decide weather a string is a palindrome.
- shanik November 14, 2014 in Israel
Ignore any non-letter characters in the the string.
Ignore capital/lower case.
Space complexity O(1)
for example, the following should return true:
A man, a plan, a canal -- Panama!| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - -6of 10 votes
AnswersSuppose we have array of N numbers. We will define N functions on this array. Each function will return the sum of all numbers in the array from Li to Ri ( Li is left index, Ri is right index). Now we have 2 types of queries:
- anotherandres November 12, 2014 in United States
Type1: 1 x y Change the xth element of the array to y
Type2: 2 l r Return the sum of all functions from m to n.
Input type:
First Line is the size of the array i.e. N
Next Line contains N space separated numbers Ai denoting the array
Next N line follows denoting Li and Ri for each functions.
Next Line contains an integer Q , number of queries to follow.
Next Q line follows , each line containing a query of Type 1 or Type 2
Here is an example:
Input:
5
1 2 3 4 5
1 2
3 4
1 4
1 5
3 5
5
1 1 5
2 2 4
2 1 3
1 4 5
2 1 5
Output:
40
28
63
Explanation:
Function 1 is sum of values from index 1 to index 2 = 1+2=3
So , F1=3
Similarly, F2=3+4=7
F3=1+2+3+4=10
F4=15
F5=12
Now when I query 1 1 5
means it is type 1 query, so we replace value at index 1 by 5.
So our new array is,
5 2 3 4 5
and
F1=7
F2=7(unchanged)
F3=14
F4=19
F5=12(unchanged)
Then next query is 2 2 4
means give sum of all functions from index 2 to 4.
So, ans= 7+14+19 =40 (output 1)
Similarly are other 2 outputs.
Index are 1 based in example.
Comment me if you are not clear with question.
Edit: I know one can do it with naive approach or using segment tree. But they wanted more faster way to do it.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 4of 10 votes
AnswersSuppose we are given a set L of n line segments in the plane, where the endpoints of each
- polo November 01, 2014 in United States
segment lie on the unit circle x^2 + y^2 = 1, and all 2n endpoints are distinct. Describe
and analyze an algorithm to compute the largest subset of L in which no pair of segments
intersects.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 5of 5 votes
AnswersGiven two strings, return boolean True/False, if they are only one edit apart.Edit can be insert/delete/update of only one character in the string. Eg:
- abkr990 October 31, 2014 in United States
-True
xyz,xz
xyz, xyk
xy, xyz
-False
xyz, xyz
xyz,xzy
x, xyz| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 3 votes
AnswersYou're given a dictionary of strings, and a key. Check if the key is composed of an arbitrary number of concatenations of strings from the dictionary. For example:
- davelee71047 October 25, 2014 in United States
dictionary: "world", "hello", "super", "hell"
key: "helloworld" --> return true
key: "superman" --> return false
key: "hellohello" --> return true| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 0of 0 votes
AnswersHaving a home-defined linked list with the following structure, where the next will point to the next node in the list and the random will point to a random node in the list (not null).
- mikeldi10 October 24, 2014 in United States
Create a copy of the structure (the data field in each node is not unique for different nodes):
/*
Example:
Having the list:
1 -> 2 -> 3 -> X
With random pointers to:
1: 3
2: 2
3: 1
Create the list:
1' -> 2' -> 3' -> X
1': 3'
2': 2'
3': 1'
*/
class Node {
int data;
Node next;
Node random;
}| Report Duplicate | Flag | PURGE
Facebook Algorithm - 3of 5 votes
AnswersYou're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of values that satisfy A+B = C + D, where A,B,C & D are integers values in the array.
- omair.ahmed08 October 09, 2014 in United States
Eg: Given [3,4,7,1,2,9,8] array
The following
3+7 = 1+ 9 satisfies A+B=C+D
so print (0,2,3,5)| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm Arrays Data Structures - 2of 2 votes
Answers(To write in Objective-C; I will write the EXACT question)
- matteogobbi.jobs August 26, 2014 in United States
Given a dictionary of words, return an array of the words whose match. (i.e. pattern "c.t" match with "cat", "cut", etc. because the dot notation stand for ANY character).
SUGGEST: use suffix tree, for(for()) is not a good solution.| Report Duplicate | Flag | PURGE
Facebook iOS Developer Algorithm - 1of 5 votes
AnswersGiven an array of positive integers that represents possible points a team could score in an individual play. Now there are two teams play against each other. Their final scores are S and S'. How would you compute the maximum number of times the team that leads could have changed?
- maomaofixer August 17, 2014 in United States
For example, if S=10 and S'=6. The lead could have changed 4 times:
Team 1 scores 2, then Team 2 scores 3 (lead change);
Team 1 scores 2 (lead change), Team 2 score 0 (no lead change);
Team 1 scores 0, Team 2 scores 3 (lead change);
Team 1 scores 3, Team 2 scores 0 (lead change);
Team 1 scores 3, Team 2 scores 0 (no lead change).| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 12of 12 votes
AnswersGiven a mapping of alphabets to integers as follows:
- skrish August 13, 2014 in United States
1 = A
2 = B
3 = C
...
26 = Z
Given any combination of the mapping numbers as string, return the number of ways in which the input string can be split into sub-strings and represented as character strings. For e.g. given
"111" -> "AAA", "AK", "KA" -> 3
Valid combinations are ({1,1,1}, {1,11},{11,1}) = 3
"11" -> "AA", "K" -> 2
Valid combinations are ({1,1},{11}) = 2
"123" -> "ABC", "LC", "AW" -> 3
Valid combinations are ({1,2,3},{1,23},{12,3}) = 3
You don't have to return all the mappings, only the number of valid mappings.| Report Duplicate | Flag | PURGE
Facebook Senior Software Development Engineer String Manipulation - 2of 4 votes
AnswersFind the maximum depth of binary tree?
- skrish August 13, 2014 in United States
Once I wrote the code for this, interviewer asked me next question| Report Duplicate | Flag | PURGE
Facebook Senior Software Development Engineer Algorithm - 5of 15 votes
AnswersGiven a function
- mabid.mahmood July 15, 2014 in United States
getRandomTripplet()
which returns a random triplet of letters from a string. You don't know the string using calls to this function you have to correctly guess the string. the length of the string is also given.
Lets say the string is helloworld the function getRandomTriplet will return things like
hlo
hew
wld
owo
the function maintains the relative order of the letters. so it will never return
ohl since h is before o in the string.
owe since w is after e
The string is not known you are only given length of the string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 3 votes
AnswersGive a function
- mabid.mahmood July 15, 2014 in United States
getRandomTripplet()
which returns a random triplet of letters from a string. You don't know the string using calls to this function you have to correctly guess the string. the length of the string is also given.
Lets say the string is helloworld the function getRandomTriplet will return things like
hlo
hew
wld
owo
the function maintains the relative order of the letters. so it will never return
ohl since h is before o in the string.
owe since w is after e
The string is not known you are only given length of the string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 1of 3 votes
AnswersPower set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.
If S has n elements in it then P(s) will have 2^n elements
- 4661 July 12, 2014 in United Statespublic List<List<int>> ComputePowerSet(int[] nums) { List<List<int>> powerSet = new List<List<int>>(); if (nums == null) return powerSet; bool[] bits = new bool[nums.Length]; bool overFlowBit = false; while (!overFlowBit) { List<int> lst = new List<int>(); for (int i = 0; i < nums.Length; i++) { if (bits[i]) lst.Add(nums[i]); } //function PlusOne returns false if the end is reached i.e. 2^n if (!PlusOne(bits)) overFlowBit = true; powerSet.Add(lst); } return powerSet; } public bool PlusOne(bool[] bits) { bool carry = true; //add i i.e. true to the bits int i = bits.Length-1; while (i >= 0 && carry) { bool b = bits[i]; bits[i] = b ^ carry; carry = b & carry; i--; } //if carry is true implies reached the end i.e. 1111 + 1 = 0000, carry = 1 return !carry; }
| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer - 5of 5 votes
AnswersLet's say you have 10,000 servers, each with a billion integers. How do you find the median?
- 352905 July 03, 2014 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 4of 4 votes
AnswersImplement a method called printNonComments() which prints out a extract of text with comments removed.
- Ash June 30, 2014 in UK
For example, the input:
hello /* this is a
multi line comment */ all
Should produce:
hello
all
You have access to a method called getNextLine() which returns the next line in the input string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 2of 4 votes
Answers/*
- friendlytechs June 25, 2014 in United States
Write an algorithm that brings all nonzero elements to the left of the array, and returns the number of nonzero elements.
Example input: [ 1, 0, 2, 0, 0, 3, 4 ]
Example output: 4
[1, 4, 2, 3, 0, 0, 0]
* The algorithm should operate in place, i.e. shouldn't create a new array.
* The order of nonzero elements does not matter
*/| Report Duplicate | Flag | PURGE
Facebook Android test engineer - 6of 6 votes
AnswersCode a function that receives a string composed by words separated by spaces and returns a string where words appear in the same order but than the original string, but every word is inverted.
Example, for this input string@"the boy ran"
the output would be
@"eht yob nar"
Tell the complexity of the solution.
- diegum June 06, 2014 in United States for iOS| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer String Manipulation - 2of 2 votes
AnswersDesign an HTTP downloader that caches results and doesn't block execution (i.e., enables simultaneous downloads).
- diegum June 06, 2014 in United States for iOS| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Object Oriented Design - 3of 3 votes
AnswersCode a function that gets two strings representing binary numbers (so the only possible characters are '1' and '0', and returns a third string representing the sum of the input. The input strings don't necessarily have of the same length.
- diegum June 06, 2014 in United States for iOS
Tell the complexity of the solution.| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer String Manipulation - 2of 2 votes
AnswersCode a function that receives an array with duplicates and returns a new array keeping the original order of the elements but with the duplicates removed.
For example, if the input were@[ @"dog", @"cat", @"dog", @"fish" ]
the output would be
@[ @"dog", @"cat", @"fish" ]
Tell the complexity of the solution.
- diegum June 06, 2014 in United States for iOS| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Arrays