# Facebook Interview Questions Set 3

Facebook latest placement papers of December are listed in Indiahires.in. Get your latest Facebook placement questions from Indiahires.

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, and 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 letters, digits, and other characters, write a function to check palindrome for only letters and digits. The implementation needs to be in place, no extra memory is allowed to create another string or array.

For example:

“ABA” is a palindrome

“A!#A” is a palindrome

“A man, a plan, a canal, Panama!” is a palindrome

Q5. Write a program that answers YES/NO search queries containing * placeholders. Example: if the data you have is (Hazem, Ahmed, Moustafa, or fizo), then you should answer as follows:

â€¨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:

Input:

1) list of Ranges that don’t overlap (not sorted)

2) new range 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 an In Order traversal circular list re-purposing the node’s 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 a pattern for 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 the body of the 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 a simple question.

You are at the latest version of the committed code.  assume one branch of code. The Code version is in sorted order. It is corrupted by the bug. You have fun isBug(VerNumber) which returns True or False. Find the version in which the bug was introduced. This can be solved by linearly checking each version or modified binary search. The person asked to write test cases? This is where I struggled. how do you write a test case for this question? Do you guys use framework syntax or something else?

Q13. Place reverse a sentence

You are 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 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, and 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)

The 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. Everyone else knows this person

You are given the following helper function:

bool knows(i, j);

Returns:

True: If I know 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 3 numbers are 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, and 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 is aligned to the XY axis. question is how to find rectangles with points or points inside

– rush December 15, 2014, in the United States | Report Duplicate | Fl