## Facebook Interview Questions

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

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

- 2of 2 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; }`

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

- 1of 1 vote
/**

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

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

- -1of 3 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.

- 0of 0 votes
What data structure would you use to store the entries of a sparse matrix?

- 1of 1 vote
/*

# 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

*/

- 1of 1 vote
Given two (binary) trees, return the first pair of non-matching leaves

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

Tree 2: A, D, B

Output: (E,B)

- 3of 3 votes
Given: sorted array of integers

Return: sorted array of squares of those integers

Ex: [1,3,5] -> [1,9,25]

Integers can be negative.

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

- 2of 2 votes
Convert a number to English representation.

Ex: Input : 100

Output : One Hundred.

- 1of 1 vote
How do I find the longest possible route in a matrix?

There are some hurdles in the path.

Details in image : https://s31.postimg.org/7nwp4gmzv/hurdle1.jpg

- 0of 0 votes
Given Nodes such as

`M-> N-> T-> D-> E | | | | C X Y L | | A Z`

-> right pointer

| 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;

}

- 0of 0 votes
You have an array of unique integer numbers and only one operation: MoveToFront(x) that moves given number to the beginning of the array.

Write a program to sort the array using the minimum possible number of MoveToFront() calls.

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

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

X = 9 Output: True

X = 10 Output: False

X = 40 Output :False