# Facebook Interview Questions Set 3

Posted on :12-03-2016

Q1. A robot has to move in a grid which is in the form of a matrix. It can go to
1.) A(i,j)--> A(i+j,j) (Down)
2.) A(i,j)--> A(i,i+j) (Right)

Given it starts at (1,1) and it has to go to A(m,n), find the minimum number of STEPS it has to take to get to (m,n) and write
public static int minSteps(int m,int n)

For instance to go from (1,1) to m=3 and n=2 it has to take (1, 1) -> (1, 2) -> (3, 2) i.e. 2 steps

Q2. Given an m x n matrix where each row element is sorted, but the columns do not appear in sorted order, write a function to print each matrix element in sorted order.

Example matrix:
matrix = [
[20, 40, 80],
[5, 60, 90],
[45, 50, 55]

Your function should print 5, 20, 40, 45, 50, 55, 60, 80, 90.

Add on: Assume that we are space-constrained such that we can only hold one row in memory at a time. Optimize your function to work under such constraints as efficiently as possible.

Q3. Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T
Example
[23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20
[1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8
[1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7

Q4. Given a string containing letter, digit, and other characters, write a function to check palindrome for only letter and digit. The implementation need to be in-place, no extra memory is allowed to create another string or array.

For example:

"ABA" is palindrome
"A!#A" is palindrome
"A man, a plan, a canal, Panama!" is palindrome

Q5. Write a program that answers YES/NO search queries containing * placeholders. Example: if the data you have is (hazem, ahmed, moustafa, fizo), then you should answer as follows for:
â€¨ahmed: YES
â€¨m**stafa: YES
â€¨fizoo: NO
â€¨fizd: NO
: YES
â€¨: YESâ€¨
NO
â€¨Your program should be able to answer each search query in O(1).

Q6. Input: A string equation that contains numbers, + and *
Output: Result as int.

For example:
Input: 3*5+8 (as String)
Output: 23 (as int)

Q7. Given a class Range
class Range {
public int begin;
public int end;
public Range(int begin, int end) {
this.begin = begin;
this.end = end;
}
}
The problem:
Intput:
1) list of Ranges that dont overlap (not sorted)
2) newRange that might overlap.
Output
list of merged Ranges

For example:

Input: [1..5] [9..13] [17..22]
new Range: [4..10]
Output: [1..13] [17..22]

Q8. Convert a binary tree into a In Order traversal circular list re-purposing the nodes pointers Left & Right as Previous and Next respectively.

Hint: A single node Left & Right points to itself.

Note: This is not a binary search tree.

Q9. You are given a set of unique characters and a string.

Find the smallest sub string of the string containing all the characters in the set.

ex:
Set : [a, b, c]
String : "abbcbcba"

Result: "cba"

Q10. First they did ask to find pattern of this
this is a test sentence => [t, h, i, s, i, s, a, t, e, s, t, s, e, n, t, e, n, c, e]
thiis iss a teest seentennce => [i, s, e, e, n]
thiiis iss aa teeest seentennnce => [i, e, n]
thiiiis iss a teeest seeentennncccce => [i, c]
after i have to do body of function
getLongestConsecutiveChar

Q11. Completely blew it on this question today.

1.) Given an array, find the maximum difference between two array elements given the second element comes after the first.

For example.

array = [1,2,3,4,5,6,7]

We can take the difference between 2 and 1 (2-1), but not the different between 1 and 2 (1-2).

Q12. It started with simple behavioral questions like, why facebook, cultural fit questions etc. They asked simple question.
You are at latest version of committed code.  assume one branch of code. Code version is in sorted order. It is corrupted with bug. You have fun isBug(VerNumber) which returns True or False. Find the version in which bug was introduced?This can be solved with linearly checking each version or modified binary search. Person asked to write test cases? This is where i struggled. how do you write test case for this question? Do you guys use framework syntax or something else?

Q13. Inplace reverse a sentence

You given a sentence of english words and spaces between them.
Nothing crazy:
1) no double spaces
2) no empty words
3) no spaces at the ends of a sentence
void inplace_reverse(char* arr, int length) {
}
Example:
input "I wish you a merry Christmas"
output "Christmas merry a you wish I"

Q14. The closest common ancestor in a tree forest.
class Node {
Node* parent; // == null for root of tree
Node* left;
Node* right;
}

Node* tree_forest[]; // array of pointers which points to roots of each tree respectively

Node* closest_common_ancestor(Node* n1, Node* n2) {
}
Example:
|    a     |   j
|   /    |  /
|  b   c   | h
| /   /  |
|d   e   f |
for e and d CCA is a
for e and f CCA is c
for e and c CCA is c
for h and d CCA is null

Q15. Design a URL system.
He even wanted to know what kind of algorithm to use, improve the speed, availability etc.

Q16. Given a 4 X 4 game slot that has random alphabets in all the slots
Write a function that takes the keyboard and the word as input and returns true if the word can be formed
False otherwise.

A word can be formed on the board by connecting alphabets adjacent to each other (horizontal, vertical and diagonally)
Same alphabet should not be reused.

Q17. Given a set of n people, find the celebrity.
Celebrity is a person who:
1. Knows only himself and no one else
2. Every one else knows this person

You are given the following helper function:
bool knows(i, j);
Returns:
True: If i knows j
False: otherwise

I proposed the O(n2) algorithm at first but he wanted me to improve on it. He wanted an O(n) algorithm

Q18. You have a list of words with ranking.
Now you need to create a function that will take this list as input and provide a way so that a T9 keyboard can provide three top results of probable words based on rankings for the numbers punched in.

Q19. Tree to List: convert a binary tree to a circular doubly-linked list

Q20. Roll two dice, what is the probability of rolling no sixes?

Q21. Given an array of integers, return true if therere 3 numbers adding up to zero (repetitions are allowed)
{10, -2, -1, 3} -> true
{10, -2, 1} -> true -2 + 1 +1 =0

Q22. Find the maximum number of non-intersecting events in a calendar.

Q23. Write a function to print the rows of a binary tree, terminating each row with a carriage return

Q24. Given a Tree:
A

B  C
/  /
D E    F G
Write a function that prints:
BC
DEFG

Q25. Given an array of ages (integers) sorted lowest to highest, output the number of occurrences for each age.
For instance:
[8,8,8,9,9,11,15,16,16,16]
should output something like:
8: 3
9: 2
11: 1
15: 1
16: 3

This should be done in less than O(n).

Q26. Print a BST such that it looks like a tree (with new lines and indentation, the way we see it in algorithms books).

Q27. Write a function that takes the following inputs and gives the following outputs.

Input: A list of points in 2-dimensional space, and an integer k
Output: The k input points closest to (5, 5), using Euclidean distance

Example:

Input: {(-2, -4), (0, 0), (10, 15), (5, 6), (7, 8), (-10, -30)}, k = 2
Output: {(5, 6), (7, 8)}

Q28. An efficient way to sort patient files in an array of just 3 types High-importance, Mid-importance, Low-importance which are in an arbitrary order (unsorted).

1. High-importance

2. Mid-importance

3. Low-importance

[high,low,low,med,high,low]

Q29. There is a list of rectangles and a list of points in a 2d space. Note that the edge of each rectangle are aligned to XY axis. question is how to find rectangles with point or points inside
- rjrush December 15, 2014 in United States | Report Duplicate | Fl

Microsoft
Yahoo
Amazon
Philips