Facebook Interview Questions
- 4of 4 votes
AnswersGiven a singly linked list: 1->2->3->4->5
- rainnyforeverluv December 09, 2016 in United States
Change it to 1->5->2->4->3 using O(1) space| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 4 votes
AnswersGiven two pre-order traversal arrays of two binary search tree respectively, find first pair of non-matching leaves.
- wtcupup2017 November 27, 2016 in United States
Follow Up: If they are general binary trees instead of BSTs, could you solve it? give out your reason.
For the first question, I was thinking to construct two BSTs from pre-order traversal then do a leaf-level comparison. Any better solutions are welcome.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersFinding biggest plus sign "+" in a sparse matrix(matrix with elements 0 and 1)
- wtcupup2017 November 19, 2016 in United States
For example, the biggest plus sign for following matrix is located at (2,2), with length 1 for each edge(Yes, each edge should have same length)
0 0 1 0 0 1 0
1 0 1 0 1 0 1
1 1 1 1 1 1 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0
Hint: use DFS/BFS| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersDefine amazing number as: its value is less than or equal to its index. Given a circular array, find the starting position, such that the total number of amazing numbers in the array is maximized.
- wtcupup2017 November 13, 2016 in United States
Example 1: 0, 1, 2, 3
Ouptut: 0. When starting point at position 0, all the elements in the array are equal to its index. So all the numbers are amazing number.
Example 2: 1, 0 , 0
Output: 1. When starting point at position 1, the array becomes 0, 0, 1. All the elements are amazing number.
If there are multiple positions, return the smallest one.
should get a solution with time complexity less than O(N^2)| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersUsing that data structure, devise an algorithm to compute the dot product between two sparse matrices.
- Brookekelseyryan November 05, 2016 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersWhat data structure would you use to store the entries of a sparse matrix?
- Brookekelseyryan November 05, 2016 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 1of 1 vote
Answers/*
- cheeyim October 28, 2016 in Singapore
# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.
# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:
# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
# For example:
# input = [(1,4), (2,3)]
# > 3
# input = [(4,6), (1,2)]
# > 3
# input = [(1,4), (6,8), (2,4), (7,9), (10, 15)]
# > 11
*/| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
AnswersGiven: sorted array of integers
- 123georgedavid September 21, 2016 in United States
Return: sorted array of squares of those integers
Ex: [1,3,5] -> [1,9,25]
Integers can be negative.| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 2of 2 votes
AnswersConvert a number to English representation.
- coder145 August 09, 2016 in United States
Ex: Input : 100
Output : One Hundred.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersGiven Nodes such as
M-> N-> T-> D-> E | | | | C X Y L | | A Z
-> right pointer
- Raj July 14, 2016 in United States
| down pointer
Output should be
M->C->A->N->X->Z->T->Y->D-L>E
Write this to flatten
flatten(Node head) {
}
Node {
Node right;
Node down;
char a;
}| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersYou have an array of unique integer numbers and only one operation: MoveToFront(x) that moves given number to the beginning of the array.
- emb July 02, 2016 in United States
Write a program to sort the array using the minimum possible number of MoveToFront() calls.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersYou are given a string "abc" which is encoded like "123" where alphabets are mapped like a => 1 to z => 26. Now find out how many string can be formed by reverse engineering encode string "123".
- sachin323 May 16, 2016 in United States
For ex. given string "123" we can form 3 string "abc"(1,2,3), "lc" (i.e 12,3), "aw"(1,23).
for string "1234" we have following possible combinations, I might be missing some of them but you get the idea
{12, 3, 4}
{1, 23, 4}
{1, 2, 3, 4}| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
Answers// Reverse the words. Given a String that contains words separated by single space, reverse the words in the String. You can assume that no leading or trailing spaces are there.
// For example: "Man bites dog" => "dog bites Man”
- almunayer May 10, 2016 in United StatesString reverseWords(String value) { // Insert implementation }
| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersSelect Kth largest value in the array. Given an unsorted array of size n, and a value k. Select the kth largest value from the array.
For example:
Array is [5, 3, 9, 1], n is 4
k = 0 => 9
k = 1 => 5
k = 3 => 1
- almunayer May 10, 2016 in United Statespublic int kthLargest(int array[], int k) { // ..... }
| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswersGiven two sorted linked lists of integers write an algorithm to merge the two linked lists such that the resulting linked list is in sorted order. You are expected to define the data structure for linked list as well. Analyze the time and space complexity of the merge algorithm.
- vkoolkatz April 28, 2016 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 0of 0 votes
AnswersGiven an array and a number, add it in such a way where array is [0,0,1] and number is 4 output will be [0,0,5]
- Ipalibo February 25, 2016 in United Kingdom
Example 2 :
array is [1] and number is 9 output will be [1,0]| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersGiven a string where in each word letters were randomly shuffled and after that words were written without spaces (lets call it X). Also you have a dictionary. The task is to return all possible strings S that can be transformed into the string X and all words in S are from dictionary.
- golyjivan February 19, 2016 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswersGiven an undirected graph and a node, modify the graph into a directed graph such that, any path leads to one particular node.
- neer.1304 December 25, 2015 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersGiven integer k and a subset S of set {0, 1, 2, ..., 2^k - 1}
- emb December 13, 2015 in United States
Return the count of pairs (a, b) where a and b are from S and (a < b) and (a & b == a)
& here is bit-wise and.
Do it faster than O((2^k)^2), assume k <= 16
Example:
0b111
0b101
0b010
Answer: 2
0b110
0b011
0b101
Answer: 0| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswersGiven a dictionary containing a list of words, a starting word, and an ending word, return the minimum number of steps to transform the starting word into the ending word.
- ixnay October 28, 2015 in United States
A step involves changing one letter at a time to a valid word that is present in the dictionary.
Return null if it is impossible to transform the starting word into the ending word using the dictionary.
Example:
Starting word: cat
Ending word: dog
cat -> cot -> cog -> dog ('cot' and 'cog' are in the dictionary)
return 3| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswersYou are given a set of points on x axis (consumers)
- emb October 22, 2015 in United States
Also you are given a set of points on a plane (producer)
For every consumer print the nearest producer.
Wanted something better than O(n^2) time.
Example:
consumers: 1 5 7
producers: (0, 3), (1,1), (3, 2), (8, 10), (9, 100)
Answer:
for 1 nearest producer is (1, 1), for 5 nearest is (3, 2), for 7 nearest is (3, 2)
Follow-up question: now both sets are sorted by x coordinate. Could you come up with a linear algorithm?| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswersYou are given a permutation arr[N]. E.g. arr[3] = {2, 1, 0} or arr[5] = {0,1,2,4,3};
- emb October 05, 2015 in United States
Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, k-th order statistic on slice [a:b] of arr.
E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it - get [0,1,5] and take k-th element, that is - 5.
Implement request(a, b, k) function. You can preprocess input data, that is, assume there will be only one array and many request() calls.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersWrite Program for String Permutations using most efficient algorithm. Can you solve problem in O(n) time ?
- dev123 September 23, 2015 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 1of 3 votes
AnswersWrite a function to check if a string matches a regex patter. Note that you only have to deal with patterns containing "*". Also, note that the pattern can't start with "*".
- diwash.timilsina August 04, 2015 in United States
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a*”) → true
isMatch(“aa”, “*”) → true
isMatch(“ab”, “*”) → true
isMatch(“ab”, “*”) → true
isMatch(“b*a”, “a”) → true
isMatch(“a*a”, “a”) → true
isMatch(“aab”, “c*a*b”) → true| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 3of 3 votes
AnswersGiven an array of integer, find the maximum drop between two array elements, given that second element comes after the first one.
- diwash.timilsina August 04, 2015 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 1of 1 vote
AnswersFind the in-order successor of a node in BST
- Kiara July 20, 2015 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 2of 2 votes
AnswersDesign Facebook Messenger backend
- tested.candidate July 13, 2015 in UK| Report Duplicate | Flag | PURGE
Facebook Software Engineer System Design - 1of 3 votes
AnswersWe know a string is Palindrome if it is the same reading from both sides. Now we define the following string also Palindrome:
- amirtar May 05, 2015 in United States
A man, a plan, a canal, Panama!
Write a code that returns if an string is palindrome and it should return true for above input. (Without directly saying, I should conclude that I have to only consider alphanumerical characters in a string). In addition, we assume the string is very long and we can not keep a copy of this string or even a copy of preprocessed version of this string. Therefore the result should be returned with the first sweep of the string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm String Manipulation - 1of 1 vote
Answersyou have a interface called Op and a Filter interface
- HBY April 17, 2015 in United States
interface Op<T> {
public boolean hasNext();
public boolean<T> next();
}
interface Filter<T1, T2> {
public boolean filter(T1 t1, T2 t2);
}
design a MutualOp that has below API, MutualOp should return the ops that combine op1 and op2, also should meet with the filter
class MutualOp implements Op{
public MutualOp(Op left, Op right, Filter<Op, Op> filter) {
this.left = left;
this.right = right;
this.filter = filter;
}
public boolean hasNext {
......
}
public T next {
......
}
}| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
Answerscalculate minimum h-index for a sorted integer array(http://en.wikipedia.org/wiki/H-index)
- HBY April 17, 2015 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm