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.
Q2. Design Facebook Messenger backend
[[ 0, 2, 3], [1]] (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.
A
/
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