Facebook Interview Questions
- 3of 3 votes
Answers3.1 design: design fb inbox search —> just focus on the post
- aonecoding July 15, 2017 in United States
4.1 binary tree to circular double linked list.
4.2 two arrays, find the common elements of two sorted array. if one array is small, the other is very big.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
Answers2.1 career discussion
- aonecoding July 15, 2017 in United States
2.2 divide two numbers with no / or %| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 4of 4 votes
Answers1/4 round of FB on-site interview, Master Degree, Hired
- aonecoding July 15, 2017 in United States
1.1 diameter of tree
1.2 find the point which have the maximum overlap of intervals| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersGive you an unsorted integer iterator
- ajay.raj June 17, 2017 in United States
and a percentage that is expressed in double (for example, 0.4 for 40%),
and find the number of the sorted array at the percentage position.
Example: Enter [1 3 2 5 4 6 7 9 8 10], and 0.6, you will return 6
public int findNumber(Iterator<Integer> nums, double percent){
}| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 2of 2 votes
AnswersGiven a n*m size 2D array with integers from 1 to n*m - 1 in it.
- ajay.raj June 08, 2017 in United States
Integers are not sorted. The last position of the matrix stays a movable block.
For each time, you can swap the movable block with any adjacent number.
And eventually you will have the integers sorted and the movable block returned
to its starting position. Think about an approach to print the path.
(You can assume it always have at least a solution)| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 0of 0 votes
AnswersHow to get the repeating decimal pattern of a division? (e.g 1/3, 1/6)
- ajay.raj June 08, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 1of 1 vote
AnswersGiven a preorder traversal of a BST, print out the inorder transversal of the BST
- ajay.raj June 06, 2017 in United States
public void printInorder(int[] nums){}| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 1of 1 vote
AnswersImplement circular buffer with read & write functions
- aonecoding June 06, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 1of 1 vote
AnswersCoding III
- aonecoding June 06, 2017 in United States
Implement int divide(int a, int b) without division or mod operation.
## Round IV
Behavioral Questions + Project Walk Through + Coding (Validate BST)
## System Design V
Design memcache to enable read, write and delete (single server, non-distributed infrastructure).
Which data structure to go with?
Eviction rules?
How to minimize segmentation?
How to handle concurrency?
## Extra
After two weeks they called me to an extra round of system design.
How to store social graphs?
How to handle concurrent read/write requests(read heavy) on one server.| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 2of 2 votes
AnswersFind Famous person in the list of persons.
- Seeker June 01, 2017 in United States
A person is a famous person if he doesn't know anyone in the list and everyone else in the list should know this person.
The function isKnow(i,j) => true/ false is given to us. No need to worry about it.
Goal is to find the famous person in O(n) complexity.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersGiven a 2D character array of size NxN. Find if there is a path from the cell 'R' to the cell 'T'. You can go left, right, up, down from a cell and you cannot pass through any cell marked with 'X'.
- Thor May 25, 2017 in United States
Example input:
X__R_X
X_XXX_
______
_XX_XX
XT__X_
Output: true| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 0of 0 votes
AnswersPrint all permutations of a given string.
- Thor May 25, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 1of 1 vote
AnswersYou have a array with integers:
[ 1, -2, 0, 6, 2, -4, 6, 6 ]
You need to write a function which will evenly return indexes of a max value in the array.
- vu-doo-cok May 22, 2017 in UK
In the example below max value is 6, and its positions are 3, 6 and 7. So each run function should return random index from the set.
Try to implement with O(n) for computation and memory.
Try to reduce memory complexity to O(1).| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersYou have a binary tree which consists of 0 or 1 in the way, that each node value is a LOGICAL AND between its children:
0 / \ 0 1 / \ / \ 0 1 1 1
You need to write a code, which will invert given LEAF and put tree in a correct state.
- vu-doo-cok May 22, 2017 in UK| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 0of 0 votes
AnswersGiven a binary tree of integers, write code to store the tree into a list of integers and recreate the original tree from a list of integers.
- Null0 May 13, 2017
Here's what your method signatures should look like (in Java):
List<Integer> store(Node root)
Node restore(List<Integer> list)
Example Tree:
5
/ \
3 2
/ / \
1 6 1| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm Data Structures Java Trees and Graphs - 2of 2 votes
AnswersGiven an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.
- Anon April 29, 2017 in United States
Ex: "bedbathandbeyond" would be "bed bath and beyond" which are all dictionary words.| Report Duplicate | Flag | PURGE
Facebook Software Engineer String Manipulation - 0of 0 votes
AnswersFind the subarray within an array (containing at least TWO number) which has the largest sum.
- ajay.raj April 20, 2017 in United States
For example, given the array [-2,-1,-3,-4,-1],
the contiguous subarray [-2,-1] has the largest sum = -3.
try to do it in O(n) time
Followup, if input is stream, how to solve it
public int maxSubArray(int[] nums) {}| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 7of 7 votes
AnswersFacebook Senior Engineer On-site 2017
- aonecoding April 17, 2017 in United States
1st Round
Question 1: Binary tree to doubly linked list.
Question 2: Read 4 (Given the read4 API, read an entire file)
2nd Round
Culture fit. No coding.
3rd Round
Question: System Design POI (Point of Interest. Given a point, find things within a radius).
Lunch
4th Round
Question 1: Decode way
Question 2: Random max index
5th Round
Question: System design + component-wise design on download manager| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersGiven some email ids, and a similarity function which says whether two email ids are similar, determine all the sets of email ids that are similar to each other.
- Ray March 28, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersYou have a string consisting of open and closed parentheses, but parentheses may be imbalanced.
- Ray March 26, 2017 in United States
Make the parentheses balanced and return the new string.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersDesign a system which takes in latitude and longitude and returns back closest 5 locations.
- Ray March 26, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer System Design - 3of 3 votes
AnswersGiven:
- alvaroneirareyes March 12, 2017 in United States
a encoded to 1
b encoded to 2
....
z encoded to 26
You can translate a number to a string:
'123' can be translated to 'abc'
but also can be translated to 'aw','lc' which gives 3 total translations
'12' can be translated to 'ab' and 'l' -> 2 translations
Write a function to get the number of valid combinations from a number like '123123123'| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 1of 9 votes
AnswersQ: Weighted meeting room
Given a series of meetings, how to schedule them. Cannot attend more than a meeting at the same time. Goal is to find maximum weight subset of mutually non-overlap meetings.class Meeting: def __init__(self): self.startTime self.endTime self.weight
@concernedCoder
- aonecoding February 27, 2017 in United States
When you claim the questions as fake, provide evidence. These are no doubt questions asked in the coding interviews of the best companies and they definitely help interviewees to prepare for the interview.
Why do you have a problem with this?| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
Answersgiven preorder traversal [5,3,2,4,8,7,9] of a BST, how do we identify the leaf nodes without building the tree ?
- Raj February 16, 2017 in United States
@Anonymous Thanks for the reply!
Please try other use cases like, only single leaf node| Report Duplicate | Flag | PURGE
Facebook Software Engineer Data Structures - 4of 4 votes
Answers# 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.
- aonecoding February 08, 2017 in United States
# 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 - 0of 0 votes
AnswersI recently had a take home assignment for a optimization engineer position at FB. I got 24 hours to finish it however it was suggested to finish under 90 minutes. The problem was to calculate the dot product of sparse matrix (optimize for speed). I wrote following code but got dinged. Not sure what's wrong to not clear even first stage!
- Ad February 07, 2017 in United States for Advertisement optimization#include <iostream> #include <string> #include <map> #include <sstream> using namespace std; class SparseVector{ private: map<int, double> m_map; int m_size; public: SparseVector(int size){ this->m_size = size; this->m_map = *new map<int, double>(); } void setValue(int i, double value){ if( i < 0 || i > m_size) return; if(value == 0.0){ map<int, double>::iterator it = m_map.find(i); if(it != m_map.end()) m_map.erase(it); } else m_map[i] = value; } double getValue(int i){ if( i < 0 || i > m_size) return 0.0; else { map<int, double>::iterator it = m_map.find(i); if(it != m_map.end()) return it->second; else return 0.0; } } int getSize(){ return m_size; } static double s_dotProduct(SparseVector a, SparseVector b){ if (a.m_size != b.m_size) return 0.0; double sum = 0.0; if (a.m_map.size() <= b.m_map.size()) { for (map<int, double>::iterator it = a.m_map.begin() ; it != a.m_map.end(); it++) if ((b.m_map.find(it->first)) != b.m_map.end()) sum += a.getValue(it->first) * b.getValue(it->first); } else { for (map<int, double>::iterator it = b.m_map.begin() ; it != b.m_map.end(); it++) if ((a.m_map.find(it->first)) != a.m_map.end()) sum += a.getValue(it->first) * b.getValue(it->first); } return sum; } template <typename T> static string s_ToString(T val) { stringstream stream; stream << val; return stream.str(); } static string s_printSparseVector(SparseVector a) { string s = ""; for (map<int, double>::iterator it = a.m_map.begin(); it!= a.m_map.end(); it++) s += "(" + s_ToString(it->first) + ", " + s_ToString(it->second) + ") "; return s; } }; int main(int argc, char *argv[]){ int lenA = 0, lenB = 0, setValA = 0, setValB = 0; cout << "Enter length for Sparse vector A : " << endl; cin>> lenA; cout << "Enter length for Sparse vector B : " << endl; cin>> lenB; SparseVector v1 = SparseVector(lenA); SparseVector v2 = SparseVector(lenB); double y; int x; cout << "Enter number of set values for Sparse vector A : " << endl; cin >> setValA; cout << "Enter the set Index, Value pair in separate lines" << endl; for(int i = 0; i < setValA; i++){ cin >> x; cin >> y; v1.setValue(x, y); } cout << "Enter number of set values for Sparse vector B : " << endl; cin >> setValB; cout << "Enter the set Index, Value pair in separate lines" << endl; for(int j = 0; j < setValB; j++){ cin >> x; cin >> y; v2.setValue(x, y); } cout <<"Sparse Vector1 = " << SparseVector::s_printSparseVector(vectorA) << endl ; cout <<"Sparse Vector2 = " << SparseVector::s_printSparseVector(vectorB) << endl; cout <<"Dot product of two sparse vectors is = " << SparseVector::s_dotProduct(vectorA, vectorB) << endl; return 0; }
| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 1of 1 vote
AnswersGiven an input string "aabbccba", find the shortest substring from the alphabet "abc".
- shalu January 25, 2017 in United States
In the above example, there are these substrings "aabbc", "aabbcc", "ccba" and "cba". However the shortest substring that contains all the characters in the alphabet is "cba", so "cba" must be the output.
Output doesnt need to maintain the ordering as in the alphabet.
Other examples:
input = "abbcac", alphabet="abc" Output : shortest substring = "bca".| Report Duplicate | Flag | PURGE
Facebook Software Engineer String Manipulation - 1of 1 vote
AnswersGiven an array of integers, design an algorithm that moves all non-zero integers to the end of the array. Minimize the number of writes or swaps.
- pygrammer January 21, 2017 in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm Arrays - 1of 1 vote
AnswersWrite code to decode strings. For example, String str = "3[a2[bd]g4[ef]h]", the output should be "abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh".
My solution is as follows.
- yankeson2013 January 18, 2017 in United Statespublic class StringDecoder { public static void main(String[] args){ String s = "3[a2[bd]g4[ef]h]"; System.out.println(decode(s)); } public static String decode(String s){ if(s == null || s.length()==0) return s; int indexOfFirstNumber = findIndexOfFirstNumber(s); int indexOfFirstBracket = findIndexOfFirstBracket(s); int indexOfClosingBracket = findIndexOfClosingBracket(s, indexOfFirstBracket); if(indexOfFirstNumber == -1) return s; String subStr1 = s.substring(0, indexOfFirstNumber); String subStr2 = decode(s.substring(indexOfFirstBracket+1, indexOfClosingBracket)); String subStr3 = decode(s.substring(indexOfClosingBracket+1, s.length())); int duplicates = Integer.parseInt(s.substring(indexOfFirstNumber, indexOfFirstBracket)); StringBuilder sb = new StringBuilder(); sb.append(subStr1); while(duplicates>0){ sb.append(subStr2); duplicates--; } sb.append(subStr3); return sb.toString(); } public static int findIndexOfFirstNumber(String s){ int index = -1; for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(c>=47 && c<=58){ index = i; break; } } return index; } public static int findIndexOfFirstBracket(String s){ int index = -1; for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(c=='['){ index = i; break; } } return index; } public static int findIndexOfClosingBracket(String s, int indexOfBracket){ int index = -1; int numberOfBracket = 1; for(int i=indexOfBracket+1; i<s.length(); i++){ char c = s.charAt(i); if(c == '[') numberOfBracket++; if(c==']'){ numberOfBracket--; if(numberOfBracket==0){ index = i; break; } } } return index; } }
| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm