# Facebook Interview Questions Set 1

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

Q1. Given the root of a binary tree containing integers, print the columns of the tree in order with the nodes in each column printed top-to-bottom.

Input:

6

/

3   4

/

5   1   0

/     /

9   2   8

7

Output:

9 5 3 2 6 1 7 4 8 0

Input:

1

/

2     3

/   /

4   5 6   7

When two nodes share the same position (e.g. 5 and 6), they may be printed in either order:

Output:

4 2 1 5 6 3 7

or:

4 2 1 6 5 3 7

Q2. Given an array and a number, add it in such a way where the array is [0,0,1] and the number is 4 output will be [0,0,5]

Example 2 :

the array is  and the number is 9 output will be [1,0]

Q3. Given a set of numbers {x1, x2, x3, x4, …, xN} (N>=3) a set of its pairwise sums is {x1+x2, x1+x3, x1+x4, x2+x3,x2+x4,x3+x4, …,}. (That is s_k = x_i + x_j where i != j)

Restore a set of numbers given a set of its pairwise sums.

Note: you don’t know given some k, to which I and j it refers, (i.e. input is given in undefined order)

EDIT: couldn’t comment, so here is a clarification

Example:

S = {1, 5, 10, 100} (n elements)

P = {6, 11, 101, 15, 105, 110} (n * (n – 1) / 2 elements)

Given P you have to restore S.

Note here means that if you knew which element in P corresponded to which pair of indices in S, you could just solve a simple linear equation

x1+x2=a{k1} x2+x3 = a{k2}, …., x{n-1} + x{n} = a{k{n-1}, x{n} + x1 = a{k{n}}

Q4. Given a string where in each word letters were randomly shuffled and then words were written without spaces (let’s call it X). Also, you have a dictionary. The task is to return all possible strings S that can be transformed into the string X and all words in S are from the dictionary

Q5. Given two arrays/Lists (choose whatever you want to) with sorted and nonintersecting intervals. Merge them to get a new sorted nonintersecting array/list.

Eg:

Given:

Arr1 = [3-11, 17-25, 58-73];

Arr2 = [6-18, 40-47];

Wanted

Arr3 = [3-25, 40-47, 58-73];

Q6. Task schedule: given a sequence of tasks like A B C(means 3 different tasks), and a cold time, which means you need to wait for that much time to start the next [same] task. Now—-

Input: string, n

eg. input: AAA BBB, 2

Output: AB_AB_AB

( “_” represents do nothing and wait)

Q7. Given a decimal number, write a function that returns its negabinary (i.e. negative 2-base) representation as a string.

#!/usr/bin/env python3

assert solution(-15) == 110001

assert solution(2) == 110

assert solution(13) == 11101

Q8. Given a forest of balanced binary trees and two nodes, n1 and n2, find the closest common parent of n1 and n2. Nodes have parameters “parent”, “left” and “right”, and you cannot access the values of the nodes. If n1 and n2 are not on the same tree, return NULL.

Try to do this in O(log(n)) time and O(1) space.

Q9. Given an undirected graph and a node, modify the graph into a directed graph such that, any path leads to one particular node.

Q10. Given integer k and a subset S of set {0, 1, 2, …, 2^k – 1}

Return the count of pairs (a, b) where a and b are from S and (a < b) and (a & b == a)

& here is bit-wise and.

Do it faster than O((2^k)^2), assume k <= 16

Example:

0b111

0b101

0b010

0b110

0b011

0b101

Q11. Given a random string S and another string T with unique elements, find the minimum consecutive sub-string of S such that it contains all the elements in T.

example:

T=abc

Q12. Given a set of ranges:

(e.g. S = {(1, 4), (30, 40), (20, 91),(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)}.

And given a target range R (e.g. R = (3, 13) – meaning the range going from 3 to 13). Write an algorithm to find the smallest set of ranges that covers your target range. All of the ranges in the set must overlap in order to be considered as spanning the entire target range. (In this example, the answer would be {(3, 9), (9, 12), (11, 14)}.

Q13. Given an array of positive integers (excluding zero) and a target number. Detect whether there is a set of consecutive elements in the array that add up to the target.

Example: a = {1, 3, 5, 7, 9}

target = 8

output = true ({3, 5})

or target = 15

output = true : {3, 5, 8}

but if target = 6, the output would be false. since 1 and 5 are not next to each other.

Q14. Given an array of integers. Modify the array by moving all the zeros to the end (right side). The order of the other elements doesn’t matter.

Q15. Given a dictionary containing a list of words, a starting word, and an ending word, return the minimum number of steps to transform the starting word into the ending.

A step involves changing one letter at a time to a valid word that is present in the dictionary.

Return null if it is impossible to transform the starting word into the ending word using the dictionary.

Example

Starting word: cat

Ending word: dog

cat -> cot -> cog -> dog (cot and cog are in the dictionary)

return 3

Q16. Given predicted stock prices for the next n days for a stock e.g: 10, 30, 42, 15, 20, 50, 10, 25 find the maximum profit that can be made with a single buy-sell transaction. Suppose no profit can be made return 0. In the example buying at 15 and selling at 50 gives maximum profit. Note that the two prices are neither minimum nor maximum in the array.

Q17. We have an array of objects A and an array of indexes B. Reorder objects in array A with given indexes in array B. Do not change array As length.

example:

var A = [C, D, E, F, G];

var B = [3, 0, 4, 1, 2];

sort(A, B);

// A is now [D, F, G, C, E];

Q18. You are given a set of points on the x-axis (consumers)

Also, you are given a set of points on a plane (producer)

For every consumer print the nearest producer.

Wanted something better than O(n^2) time.

Example:

consumers: 1 5 7

producers: (0, 3), (1,1), (3, 2), (8, 10), (9, 100)

for 1 nearest producer is (1, 1), for 5 nearest is (3, 2), for 7 nearest is (3, 2)

Follow-up question: now both sets are sorted by x coordinate. Could you come up with a linear algorithm?

Q19. Given n, return 1 ^ 2 ^ 3 ^ … ^ n

Where ^ is binary xor.

Note: n is a 64-bit number, and 1<<63 is a valid n for this problem.

Examples:

>>> reduce(lambda a,b:a^b, [1,2,3])

0

>>> reduce(lambda a,b:a^b, [1,2,3,4])

4

>>> reduce(lambda a,b:a^b, [1,2,3,4,5,6,7])

0

>>> reduce(lambda a,b:a^b, [1,2,3,4,5,6,7,8,9])

1

Q20. Given an array of positive, unique, increasingly sorted numbers A, e.g. A = [1, 2, 3, 5, 6, 8, 9, 11, 12, 13]. Given a positive value K, e.g. K = 3. Output all pairs in A that differ exactly by K.

e.g. 2, 5

3, 6

5, 8

6, 9

8, 11

9, 12

What is the run time for your code?

Q21. You are given a permutation arr[N]. E.g. arr = {2, 1, 0} or arr = {0,1,2,4,3};

Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, kth order statistic on slice [a:b] of arr.

E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it – get [0,1,5] and take kth element, that is – 5.

Implement the request(a, b, k) function. You can pre-process input data, that is, assume there will be only one array and many request() calls.

Q22. Design Live comments. If your facebook.com homepage is open with a bunch of feeds and if someone comments on those feeds, the comments should automatically show up on the facebook.com home page without refreshing the page. Feeds could be a simple status update by a friend, a post in a group, a post by a person you’re following, a post on a page you’ve liked, etc.

Few things that they are looking for –

1. How do you solve it initially and how do you scale it?

2. How do you scale the push model in-case if you choose the PUSH model to solve it?

3. If push cannot scale how do you solve it?

4. How pull model solves it?

5. When will you use push vs pull?

Q23. Write a Program for String Permutations using the most efficient algorithm. Can you solve the problem in O(n) time?

Q24. Conflict resolution in Multi-Master systems.

Q25. Design a URL shortener service

Q26. Check a binary tree is a binary search tree

Q27. Write a function to check if a string matches a regex pattern. Note that you only have to deal with patterns containing “*”. Also, note that the pattern can’t start with “*”.

Some examples:

isMatch(â€œaaâ€,â€aâ€) â†’ false

isMatch(â€œaaâ€,â€aaâ€) â†’ true

isMatch(â€œaaaâ€,â€aaâ€) â†’ false

isMatch(â€œaaâ€, â€œa*â€) â†’ true

isMatch(â€œaaâ€, â€œ*â€) â†’ true

isMatch(â€œabâ€, â€œ*â€) â†’ true

isMatch(â€œabâ€, â€œ*â€) â†’ true

isMatch(â€œb*aâ€, â€œaâ€) â†’ true

isMatch(â€œa*aâ€, â€œaâ€) â†’ true

isMatch(â€œaabâ€, â€œc*a*bâ€) â†’ true

Q28. Given an array of integers, find the maximum drop between two array elements, given that the second element comes after the first one.

Q29. On a given array with N numbers, find a subset of size M (exactly M elements) that is equal to SUM.

Q30. Find the in-order successor of a node in BST