## Facebook Interview Questions

- 1of 1 vote

AnswersGiven a set of possibly overlapping rectangles in different levels (All of which are "not rotated", can be uniformly represented as (left-bottom,right-top) tuplets), return a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area.

- hulk February 09, 2017

The rectangle at lower level has more priority than at higher levels.| Report Duplicate | Flag | PURGE

Facebook Software Developer Algorithm Data Structures - 1of 1 vote

AnswersI got my interview yesterday and the problem they asked me was: Giving a method intToEnglish that receives an int as a parameter, how do you return its representation in english words. The number can be of any size but no more than around 2 billion since the parameter is an int 2ˆ32

- jorgevalbuena56 February 08, 2017 in United States| Report Duplicate | Flag | PURGE

Facebook Android Engineer Algorithm - 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 - 6of 6 votes

Answers/**

- aonecoding January 27, 2017 in United States

Given many coins of 3 different face values, print the combination sums of the coins up to 1000. Must be printed in order.

eg: coins(10, 15, 55)

print:

10

15

20

25

30

.

.

.

1000

*/| Report Duplicate | Flag | PURGE

Facebook Software Developer 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

AnswersGenerate square of numbers in an array example [1,3,5] should come out as [1,9,25].

- mallu.goswami92 January 19, 2017 in United States| Report Duplicate | Flag | PURGE

Facebook - 0of 0 votes

AnswersGiven an Array of N elements and Integer K, write a function that returns true if the sum of any 2 elements of Array is K, false otherwise.

- anonymus January 19, 2017 in United States| Report Duplicate | Flag | PURGE

Facebook Android Engineer Algorithm - 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 States`public 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 - 1of 1 vote

AnswersInterview Question: essentially given a bunch of sets in an array, print out the cross product of all of those sets

- ul December 22, 2016 in United States| Report Duplicate | Flag | PURGE

Facebook Software Engineer Intern - 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 - 1of 1 vote

AnswersGiven two (binary) trees, return the first pair of non-matching leaves

- bobshanely October 03, 2016 in United States

Tree 1: A, B, C, D, E, null, null

Tree 2: A, D, B

Output: (E,B)| Report Duplicate | Flag | PURGE

Facebook Intern Trees and Graphs - 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 - 0of 0 votes

AnswersDesign a HTTP response service that will allow sync and async download. What classes would you create and the methods used with paramerters and return types.

- MM September 10, 2016 in United States| Report Duplicate | Flag | PURGE

Facebook Software Developer Object Oriented Design - 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 - 1of 1 vote

AnswersHow do I find the longest possible route in a matrix?

- axaysd July 30, 2016 in United States

There are some hurdles in the path.

Details in image : https://s31.postimg.org/7nwp4gmzv/hurdle1.jpg| Report Duplicate | Flag | PURGE

Facebook SDE1 - 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 - 2of 2 votes

AnswersGiven an array of positive integers and a target total of X, find if there exists a contiguous subarray with sum = X

- falkon June 29, 2016 in United States

[1, 3, 5, 18] X = 8 Output: True

X = 9 Output: True

X = 10 Output: False

X = 40 Output :False| Report Duplicate | Flag | PURGE

Facebook - 2of 2 votes

AnswersA museum was represented by a square matrix that was filled with O, G, and W where O represented open space G represented guards, and W represented walls. Write a function that accepts the square matrix and returns another square matrix where all of the O's in the matrix are replaced with the number of how many spaces they are away from a guard, without being able to go through any walls.

- fire May 17, 2016 in United States| Report Duplicate | Flag | PURGE

Facebook Android 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 States`String 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 States`public int kthLargest(int array[], int k) { // ..... }`

| Report Duplicate | Flag | PURGE

Facebook Software Engineer Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window