## Facebook Interview Questions

- 0of 0 votes
Given an array of integers greater than zero, find if it is possible to split it in two (without reordering the elements), such that the sum of the two resulting arrays is the same. Print the resulting arrays.

- 3of 3 votes
there is a bunch of tasks, each have different time to complete, task is independent, and then there are some workers,

How to allocate tasks to these workers to minimize the total time to complete all the task. The tasks can be randomly picked from the task list.

Example

Task: 2,2,3,7, 1

Worker: 2.

Return 8, because the first worker can work on the first three tasks : 2 + 2 + 3 = 7, and the second worker can work on the last two tasks : 7 + 1 = 8, so the total time to finish all the task is 8.

public int getMini(int[] tasks, int k)

- 0of 0 votes
We have a List of FlightRoute

`public static class FlightRoute { String from; String to; int time; .... }`

and write a function to find Shortest Path: findShorestPath(String start, String end, List<FlightRoute>routes)

- 0of 0 votes
Iterate over a singly linked list backwards. Call print on each node.

Example: The list A->B->C should print as

"C B A"`class Node { public Node next; public String value; }`

There are 4 solutions

1) recursive

2) iterative with O(n) memory

3) iterative with O(1) memory and O(n²) runtime

4) iterative with O(1) memory and O(n) runtime (for this solution the initial list may be modified)

Explain all 4 solutions and write the code for solutions 3 and 4

- 0of 0 votes
You are given an array of integers.

Write an algorithm that brings all nonzero elements to the left of the array, and returns the number of nonzero elements.

The algorithm should operate in place, i.e. shouldn't create a new array.

The order of the nonzero elements does not matter. The numbers that remain in the right portion of the array can be anything.

Example:

given the array [ 1, 0, 2, 0, 0, 3, 4 ],

a possible answer is [ 4, 1, 3, 2, ?, ?, ? ], 4 non-zero elements, where "?" can be any number.

Code should have good complexity and minimize the number of writes to the array.

- 1of 1 vote
Given:

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'

- 0of 0 votes
You have a string of numbers, i.e. 123. You can insert a + or - sign in front of ever number, or you can leave it empty. Find all of the different possibilities, make the calculation and return the sum.

For example;

+1+2+3 = 6

+12+3 = 15

+123 = 123

+1+23 = 24

...

-1-2-3 = 6

...

Return the sum of all the results.

- 0of 0 votes
Design a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)

- 0of 0 votes
Given the newest 100 entries of a person's facebook newsfeed. How would you rank the entries. The (for the user) most important ones should be ranked first. Which features would you use and how do you train/improve your model (machine learning)?

- -2of 6 votes
Q: 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

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?

- 2of 2 votes
given preorder traversal [5,3,2,4,8,7,9] of a BST, how do we identify the leaf nodes without building the tree ?

@Anonymous Thanks for the reply!

Please try other use cases like, only single leaf node

- 2of 2 votes
Given estimated stock quotes, in an array, print the maximum profit from a buy and sell. i.e [19, 22, 15, 35, 40, 10, 20] would show a profit of 25(40 -15). The sale must come after the buy. Solve this in O(N) time.

`<?php function print_max_profit($arr){ if(count($arr) < 1) return 0; $len = sizeof($arr); $profit = 0; $least = $arr[0]; for($i = 0; $i < $len; $i++){ $least = min($least,$arr[$i]); $profit = max($profit, $arr[$i] - $least); } return $profit; }`

- 1of 1 vote
Given 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.

The rectangle at lower level has more priority than at higher levels.

- 1of 1 vote
I 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

- 4of 4 votes
# 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

- 0of 0 votes
I 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!

`#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; }`

- 4of 4 votes
Find the median of an unsorted array.

Have to do better than O(nlogn) time.

e.g.

Given [2, 6, 1] return 2

Given [2, 6, 1, 4] return 3 which is sum of the two elements in middle over 2

- 3of 3 votes
/**

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

*/

- 0of 0 votes
Given an input string "aabbccba", find the shortest substring from the alphabet "abc".

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".

- 0of 0 votes
Given 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.

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

- 0of 0 votes
Given 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.

- 1of 1 vote
Write code to decode strings. For example, String str = "3[a2[bd]g4[ef]h]", the output should be "abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh".

My solution is as follows.`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; } }`

- 3of 3 votes
Print first pair of mis-matching leaves (first pair as in in-order) given two pre-order traversal arrays of BSTs.

e.g.`For 5 4 8 2 4 6 9 Pre-order Sequence as [5,4,2,4,8,6,9] & 5 3 8 2 4 7 9 Pre-order Sequence2 as [5,3,2,4,8,7,9] Print “4, 3”.`

@Kart

If you create the in-order sequences for the two trees, you'll be able to see that 4 and 3 comes far before 6 and 7.

In fact, in any of the three well-known types of tree traversal, there is NO way for a node in the right tree visited prior to the node in the left tree.

@anon

The question gives just enough detail for you to solve it. It does NOT matter if the trees are balanced or same size. It's said in the first sentence that 'find the first non-matching pair as in the IN-ORDER sequence', which is the ascending sequence in a BST.

- 1of 1 vote
Interview Question: essentially given a bunch of sets in an array, print out the cross product of all of those sets

- 3of 3 votes
Given a singly linked list: 1->2->3->4->5

Change it to 1->5->2->4->3 using O(1) space

- 0of 4 votes
Given two pre-order traversal arrays of two binary search tree respectively, find first pair of non-matching leaves.

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.

- 3of 3 votes
Finding biggest plus sign "+" in a sparse matrix(matrix with elements 0 and 1)

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

- 2of 2 votes
Define 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.

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)

- 1of 1 vote
Using that data structure, devise an algorithm to compute the dot product between two sparse matrices.