# Facebook Interview Questions Set 2

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

Q1. Design a data structure that supports a kind of full-text search but in numbers.

We are given a file with a lot of 10-digit numbers, for example:

1234 567 890

4124 123 123

3123 123 322

On a given number X we should return all numbers that contain X.

For example, if the number 123 was given, we should return all numbers (from the list above) because 123 is in all of them.

If the number 41 was given we should return only the middle number – because the number 41 is only in it.

[[ 0, 2, 3], ] (0,2,3 are the same person and 1 is another one)

Q3. Search in a sorted rotated array.

Q4. Merge K sorted singly linked list

Q5. paint a list of N houses and M colors, each combination has a cost, minimizing the total cost without color in a row.

Q6. Given array A of size N, using function Random(returns a random number between 0 and 1) implement function that will return an array of size N with randomly shuffled elements of the array A.

You should give only algo.

Q7. We know a string is Palindrome if it is the same reading from both sides. Now we define the following string also Palindrome:

A man, a plan, a canal, Panama!

Write a code that returns if a string is a palindrome and it should return true for the above input. (Without directly saying, I should conclude that I have to only consider alphanumerical characters in a string). In addition, we assume the string is very long and we can not keep a copy of this string or even a copy of the preprocessed version of this string. Therefore the result should be returned with the first sweep of the string.

Q8. Given a singly linked list, swap the list items in pairs (reconnect the pointers, not simply swap the values). For example:

Before: A->B->C->D

After: B->A->D->C

Q9. you have an interface called Op and a Filter interface

interface Op {

public boolean hasNext();

public boolean next();

interface Filter {

public boolean filter(T1 t1, T2 t2);

design a MutualOp that has the below API, MutualOp should return the ops that combine op1 and op2, also should meet with the filter

class MutualOp implements Op{

public MutualOp(Op left, Op right, Filter filter) {

this.left = left;

this.right = right;

this.filter = filter;

public boolean hasNext {

……

public T next {

……

}

Q10. Calculate the minimum h-index for a sorted integer array(http://en.wikipedia.org/wiki/H-index)

Q11. Given a machine, you can try to guess the word, and the machine will return how many characters have been matched by your guess. Design a system to crack the word.

Q12. Permutate a list of string

this question is supposed to permutate the characters instead of who string,

as input example {“red”, “fox”, “super” }, the expected output is

rfs

rfu

rfp

rfe

rfr

ros

rou

rop

roe

ror

rxs

rxu

rxp

rxe

rxr

efs

efu

efp

efe

efr

eos

eou

eop

eoe

eor

exs

exu

exp

exe

exr

dfs

dfu

dfp

dfe

dfr

dos

dou

dop

doe

dor

dxs

dxu

dxp

dxe

dxr

Q13. A 2D array filled with an integer defines a flow from one point to its neighbor only if the value of the current point is not less than its neighbor’s value. Consider the up edge and left edge as the east coast, the bottom edge and right edge as the west coast, and find all positions that it can flow to the east coast and west coast both

Q14. Sort an integer array with three functions: findMin(), findMedium(), findMax().

Q15. /**

Find if the given list of recurring weekly intervals covers the

entire time. Times are given up to a second.

You can take the input intervals in the number of seconds since

the beginning of the week or any other format you prefer.

—Example 1—

Input:

Tuesday 9AM – Sunday 9AM

Sunday 8:00:20AM – Wednesday 3AM

Output

true

—Example 2—

Input:

Tuesday 9AM – Sunday 9AM

Sunday 8:00:20PM – Tuesday 8AM

Output

false

/

Q16. /*

For each node in a binary tree find the next right node on the same depth. Write a function that takes the root node and populates “next” with the answer for each node.

/

B -> C

/ /

D -> F-> G

/

H -> I

class Node {

Node left;

Node right;

Node next; // <– answer should be stored here

};

B.next = C

D.next = F

F.next = G

H.next = I

{A, C, G, I}.next = null

*/

Q17. Pangram

Q18. In-place Palindrome Check

Q19. Dutch national flag w/ get rank followup

Q20. Given an array (list) of integers return true(boolean function) if two of the numbers add to 12.

Q21. N queen problem.

In NXN chess board, you have to arrange N queens such that they do not interfere with each other. Following is how you define interference of queens.

1. Two queens cannot be on the same diagonal

2. Two queens cannot be in the same horizontal or vertical line

3. Queen can jump like a knight. So, two queens cannot be in a position where they can jump two and a half steps like a knight and reach the other queen.

You should return the possible ways to arrange N queens on a chess board.

This was a tech screen, but since I was local, they called me into their office rather than a phone interview.

Q22. I needed to develop the next system:

We have a lot of servers. Every server generates logs. Every log has two data types: the first is numeric metrics. These numeric metrics are integers. The second is strings. We need to collect logs from all servers on another server (storage). Then we have to execute queries and get some data from storage. In our queries, we have to use numeric metrics and strings as well. For numerics metrics, we have to be able to get aggregation data as well.

Develop Storage server and database. Describe how will you scale this system, what database will you use, how will you save data and how will you execute these queries.

Q23. Given an array such that every next element differs from the previous by +/- 1. (i.e. a[i+1] = a[i] +/-1 ) Find the local max OR min in O(1) time. The interviewer mentioned one more condition that the min or max should be non-edge elements of the array

Example: 1 2 3 4 5 4 3 2 1 -> Local max is 5

1 2 3 4 5 -> No local max or min exists

5 4 3 2 1 -> No local max or min exists

Q24. Write a function that calculates the minimum number of meeting rooms that can accommodate given schedules

input: same

Output: # of rooms

Also back to back events are allowed e.g. {2,5} {5,9} correct o/p:1

Q25. Write a function that detects conflicts in given meeting schedules

input: a list of intervals, [(s1, e1), (s2, e2), ]

output: return True if there’s any conflict, False otherwise

Q26. Given a tokenized PHP file, give me a map from class to a list of functions

Q27. There are 3 rooms in which the party is going on let’s say room A, B, C. Guests are coming one by one and you have to tell the guest

which room to enter. At any point in time, each room has to maintain a percentage Let’s say the percentage that each room has to maintain is

A- 20%, B-30%, C- 50%. You can maintain a total count of each room and keep on adding the count to the respective room as the new guest enters each room.

How would you go about it? What formula would you use?

Give a general formula so that it works if no. of rooms increases.

Q28. You are given a 2nd rectangular array of positive integers representing the height map of a continent. The “Pacific ocean” touches the left and top edges of the array and the “Atlantic ocean” touches the right and bottom edges.

– Find the “continental divide”. That is the list of grid points where water can flow either to the Pacific or the Atlantic.

Water can only flow from one cell to another one with a height equal to or lower.

Example:

Pacific ~ ~ ~ ~ ~ |__

~ 1 2 2 3 (5) ~

~ 3 2 3 (4)(4) ~

~ 2 4 (5) 3 1 ~

~ (6)(7) 1 4 5 ~

__ (5) 1 1 2 4 ~

|~ ~ ~ ~ ~ Atlantic

The answer would be the list containing the coordinates of all circled cells:

[(4,0), (3,1), (4,1), (2,2), (0,3), (1,3), (0,4)]

Q29. Implement stairs(N) that (collect the solutions in a list) print all the ways to climb up an N-step-stairs

where one can either take a single step or a double step.

Well use 1 to represent a single step, and 2 to represent a double step.

stairs(3)

111

12

21