Facebook is a social networking company. It builds engaging products that enables people to connect and share through mobile devices and personal computers. The Company offers various services focused on p... read more Menlo Park, California, United States (USA)

Is this your company?

Claim Account Filter interviews by
Designation

Select Designation

Clear

33 results found

### Interview Rounds

Coding Test

Video Call

I was interviewed in Jul, 2021.

### Interview Questions

• Q1. Longest Increasing Path In A 2D Matrix

#### For example :

``````3 2 2
5 6 6
9 5 11

In the given matrix, 3 →  5 →  6 and 3 →  5 →  9 form increasing paths of length 3 each.
``````
##### Input Format :
``````The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Then the test case follows.

The first line of each test case contains two space-separated integers 'N', 'M' where 'N' and 'M' denote the number of rows and columns of the matrix, respectively.

From the second line of each test case, the next 'N' lines represent the rows of the MATRIX. Every row contains 'M' single space-separated integers.
``````
##### Output Format :
``````For each test case, print the length of the longest increasing path.

Print the output of each test case in a separate line.

Note :
You do not need to print anything; it has already been taken care of. Just implement the function.
``````
##### Constraints :
``````1 <= T <= 100
1 <= N <= 50
1 <= M <= 50
0 <= MATRIX[i] <= 10^5

Time Limit: 1sec
``````
• Q2. Saving Money

#### Ninja likes to travel a lot, but at the same time, he wants to save as much money as possible. There are ‘N’ Stations connected by ‘M’ Trains. Each train that he boards starts from station ‘A’ and reaches destination station ‘B’ with a ticket price ‘P’. Your task is to find the cheapest price from the given ‘source’ to ‘destination’ with up to ‘K’ stops. If there is no such route, print ‘-1’.

##### Input Format :
``````The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two space-separated integers N and M, the number of stations and the number of trains respectively.
The next ‘M’ line of each test case contains three space-separated integers, the source stations, the destination station, and the ticket price for traveling from this source to this destination.
The final line of each test case contains three space-separated integers, the source station, the destination station, and ‘K’, the maximum number of stations at which Ninja can stop.
``````
##### Output Format :
``````For every test case, the only line of output should contain an integer P, the cheapest price from the given ‘source’ to ‘destination’ with up to ‘K’ stops, else if no such route exists print ‘-1’

The output of each test case will be printed in a new line.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 100
0 <= M <= N*(N-1)/2
0 <= K <= N - 1

Time limit : 1 sec
``````
• Q3. K - Sum Path In A Binary Tree

#### Note:

``````1. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

2. Output the paths in the order in which they exist in the tree from left to right. Example: In the below example, path {1,3} is followed by {3,1} and so on.
``````

#### Example:

``````For K = 4 and tree given below:
`````` ``````The possible paths are:
1 3
3 1
-1 4 1
4
-1 5

The sum of values of nodes of each of the above-mentioned paths gives a sum of 4.
``````
##### Input format
``````The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.

The first line of input contains the elements of the tree in the level order form separated by a single space.

If any node does not have a left or right child, take -1 in its place. Refer to the example below.

The second line of each test case contains an integer ‘K’ denoting the sum.
``````
##### Example:
``````Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :
`````` `````` 1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
``````

Explanation : Level 1 : The root node of the tree is 1

``````Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).
``````
##### Note :
``````The above format was just to provide clarity on how the input is formed for a given tree.

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
``````
##### Output format:
``````The output of each test case prints all the paths of the binary tree with the sum of nodes in the path as ‘K' in the order in which they exist in the tree from left to right.

The output of each test case is printed in a separate line.
``````
##### Note
``````You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
``````
##### Constraints:
``````1 <= T <= 50
1 <= N <= 10^2
-10^9 <= K <= 10^9
-10^7 <= DATA <= 10^7

Where ‘N’ is the number of nodes in the tree, ‘K’ denotes the sum, and 'DATA' denotes data contained in the node of a binary tree.

Time Limit: 1 sec
``````
• Q4. Combination Sum

#### For example:

``````Let the array ARR be [1, 2, 3] and B = 5. Then all possible valid combinations are-

(1, 1, 1, 1, 1)
(1, 1, 1, 2)
(1, 1, 3)
(1, 2, 2)
(2, 3)
``````
##### Input Format
``````The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

Then the first line of each test case contains two space separated integers  ‘N’ and ‘B’ denoting the number of elements in the array/list and the target sum respectively.

The second line of each test case contains N space separated integers the elements of array/list ARR.
``````
##### Output Format :
``````For each test case, print all possible valid combinations in separate lines. You can print combinations in any order. Elements in each combination must be in non-decreasing order.

Output for each test case will be printed in a new line.
``````

#### Note:

``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 5
1 <= N <= 15
1 <= B <= 20
1 <= ARR[i] <= 20

Time Limit: 1sec
``````
• Q5. Accounts Merge

#### After merging the accounts, you have to return an array/list of merged accounts where each account, the first element is the name of the person, and the rest elements are the email addresses in sorted order (non-decreasing). Accounts themselves can be in any order.

##### Input Format :
``````The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains an integer ‘N’ denoting the number of accounts.

Each of the next ‘N’ lines contains space-separated strings where the first string denotes the account holder’s name, and the rest of the strings represent the email addresses.
``````
##### Output Format :
``````For each test case, print the number of accounts after merging in the first line and then print the space-separated name and email address associated with each account in a separate line.

Print the output of each test case in a separate line.
``````
##### Note:
``````You are not required to print the expected output; it has already been taken care of. Just implement the function.
``````
##### Constraints :
``````1 <= T <= 50
1 <= N <= 100
1 <= |accounts[i]| <= 10
1 <= |accounts[i][j]| <= 30

Time limit: 1 sec
``````
• Q6. Construct Binary Tree From Inorder and Preorder Traversal

#### You have been given the preorder and inorder traversal of a binary tree. Your task is to construct a binary tree using the given inorder and preorder traversals.

##### Note:
``````You may assume that duplicates do not exist in the given traversals.
``````
##### For example :
``````For the preorder sequence = [1, 2, 4, 7, 3] and the inorder sequence = [4, 2, 7, 1, 3], we get the following binary tree.
`````` ##### Input Format:
``````The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains an integer ‘N’ denoting the number of nodes in the binary tree.

The second line of each test case contains ‘N’ integers denoting the preorder traversal of the binary tree.

The third line of each test case contains ‘N’ integers denoting the inorder traversal of the binary tree.
``````
##### Output Format:
``````For each test case, print the level order traversal of the constructed binary tree separated by a single-space.

For example, the output for the tree depicted in the below image would be :
`````` ``````Level Order Traversal:
1
2 3
4 5 6
7

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null
Right child of 4 = 7
Left child of 5 = null
Right child of 5 = null
Left child of 6 = null
Right child of 6 = null

Level 5 :
Left child of 7 = null
Right child of 7 = null
``````
##### Note :
``````Here, if the node is null, print nothing. The above format was just to provide clarity on how the output is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the output will be:

1 2 3 4 5 6 7

The output of each test case will be printed in a separate line.
``````
##### Note :
``````You do not need to print anything; it has already been taken care of. You just need to return the root node of the constructed binary tree.
``````
##### Constraints:
``````1 <= T <= 100
1 <= N <= 3000
1 <= data <= 10^4

Where ‘T’ is the number of test cases, and ‘N’ is the total number of nodes in the binary tree, and “data” is the value of the binary tree node.

Time Limit: 1sec
``````
##### Follow-up:
``````Can you solve this in O(N) time complexity?
``````
• Q7. OS Question

Explain Demand Paging .

• Q8. System Design Question

How does Facebook store likes/dislikes ?

• Q9. System Design Question

How does Facebook implement graph search ?

• Q10. System Design Question

How does Facebook Chat works ?

### Interview details

Proposed: Eligibility criteriaAbove 7 CGPA
Facebook interview Rounds:Round 1
Round type - Online Coding Test
Round duration - 90 minutes
Round difficulty - Hard
Round description -

This was an online coding round where we had 2 questions to solve under 90 minutes . Both the questions were preety hard according to me . One has to have a fair share of knowledge in Data Structures and Algorithms to pass this round .

Round 2
Round type - Video Call
Round duration - 60 Minutes
Round difficulty - Medium
Round description -

This Round was DS and Algo round and it started with formal introduction, followed by 2 problems. We first dicussed the
approach the time complexity and proper code covering all cases.

Round 3
Round type - Video Call
Round duration - 50 Minutes
Round difficulty - Medium
Round description -

This Round was DS/Algo + Core round and it started with formal introduction, followed by 3 problems. We first dicussed
the approach the time complexity and proper code covering all cases for the 2 coding problems . The last question was
related to OS and was a bit theoretical .

Round 4
Round type - Video Call
Round duration - 60 minutes
Round difficulty - Medium
Round description -

This was a preety intense round as I was grilled more on my System Design concepts but eventually I was able to
asnwers all the questions with some help from the interviewer.

General Tip : While preparing for Facebook Interviews , make sure you read and understand some of the most important features that Facebook incorporates like Graph Search , Adding a friend , Removing a friend , Storing Likes/Dislikes and so on.
All these features are important to learn because at their core they are nothing but Data Structures used and implemented very elegantly . So before your next Facebook interview , do read these topics and be confident about your LLD as well as HLD skills.

Facebook interview preparation:Topics to prepare for the interview - Data Structures, Algorithms, System Design, Aptitude, OOPSTime required to prepare for the interview - 4 MonthsInterview preparation tips for other job seekers

Tip 1 : Must do Previously asked Interview as well as Online Test Questions.
Tip 2 : Go through all the previous interview experiences from Codestudio and Leetcode.
Tip 3 : Do at-least 2 good projects and you must know every bit of them.

Application resume tips for other job seekers

Tip 1 : Have at-least 2 good projects explained in short with all important points covered.
Tip 2 : Every skill must be mentioned.
Tip 3 : Focus on skills, projects and experiences more.

Final outcome of the interviewSelected
View More  ### Interview Rounds

Coding Test

Face to Face

I was interviewed before Dec, 2020.

### Interview Questions

• Q1. Count Ways

#### Note:

``````1. Include the source node as a destination also.
2. There are no cycles in the given graph.
``````
##### Input Format:
``````The first line of input will contain three integers 'V', 'E', and ‘S’, separated by a single space.

From the second line onwards, the next 'E' lines will denote the directed edge of the graphs.

Every edge is defined by two single space-separated integers 'A' and 'B', which signifies a directed edge from vertex 'A' to vertex 'B'.
``````
##### Output Format:
``````For each input, print a single line containing a single integer denoting the total number of ways modulo 10 ^ 9 + 7.
``````
##### Constraints:
``````1 <= 'S', 'V' <= 10 ^ 5
0 <= 'E' <= 2 * 10 ^ 5

Where ‘S’ represents the value of a given source node, ‘V’ represents the number of vertices and ‘E’ represents the number of edges.

Time Limit: 1 sec.
``````
• Q2. Course Schedule II

#### Your task is to return the ordering of courses you should take to finish all courses.

##### Note:
``````If it is impossible to finish all courses, return an empty array. If there are multiple answers, return any one.
``````
##### Input Format:
``````The first line of input contains an integer 'T' representing the number of the test case.

The first line of each test case contains an integer ‘N’ representing the number of courses.

The second line of each test case contains a given integer ‘M’ representing the number of prerequisite pairs.

The next ‘M’ lines in each test case contain a matrix ‘PREREQUISITES’ containing two integers denoting a prerequisite pair.
``````
##### Output Format:
``````For each test case, print a single integer 1 if the returned order of the courses is correct otherwise we return 0.
``````
##### Note:
``````You don't need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 5
2 <= N <= 100
1 <= M <= min(100,N(N-1)/2)
1 <= PREREQUISITES[i], PREREQUISITES[i] <= N

Where ‘PREREQUISITES’ denotes the prerequisites matrix.

Time limit: 1 sec
``````
• Q3. Merge Intervals

#### For example:

``````For the given 5 intervals - [1, 4], [3, 5], [6, 8], [10, 12], [8, 9].

Since intervals [1, 4] and [3, 5] overlap with each other, we will merge them into a single interval as [1, 5].

Similarly, [6, 8] and [8, 9] overlap, merge them into [6,9].

Interval [10, 12] does not overlap with any interval.

Final List after merging overlapping intervals: [1, 5], [6, 9], [10, 12].
``````
##### Input Format:
``````The first line of input contains an integer N, the number of intervals.

The second line of input contains N integers, i.e. all the start times of the N intervals.

The third line of input contains N integers, i.e. all the end times of the N intervals.
``````
##### Output Format:
``````Print S lines, each contains two single space-separated integers A, and B, where S is the size of the merged array of intervals, 'A' is the start time of an interval and 'B' is the end time of the same interval.
``````

#### Note

``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= N <= 10^5
0 <= START, FINISH <= 10^9

Time Limit: 1sec
``````
• Q4. Longest Route

#### You are given a source cell and a destination cell. You need to find the length of the longest possible path from source to destination, given you can only move in 4 possible directions north(i.e from (i,j) to (i-1,j)), south(i.e from (i,j) to (i+1,j)), east(i.e from (i,j) to (i,j-1)), and west(i.e from (i,j) to (i,j+1)), and without visiting a cell twice.

##### Note:
``````1. If the move isn’t possible you remain in that cell only.
``````
##### Input Format:
``````The first line of the input contains two space-separated integers 'N' and ‘M’, denoting the number of rows and columns of the matrix respectively.

Next, there will be N lines each containing M space-separated integers denoting the description of the matrix.

The next line contains two space-separated integers ‘Sx’, ‘Sy’ denoting the indexes of the source cell

The next line contains two space-separated integers ‘Dx’, ‘Dy’ denoting the indexes of the destination cell
``````
##### Output Format:
``````If a path exists then print the length of the longest possible path from source to destination.
Otherwise, print -1.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= N, M <= 12 , such that N+M <=12
0 <= Mat[i][j]  <= 1 ,
0 <= Sx, Dx <= N-1
0 <= Sy, Dy <= M-1
Where Mat[i][j] is the value at position i,j in the matrix.
``````
• Q5. Longest Increasing Subsequence

#### Strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.

##### For example:
``````[1, 2, 3, 4] is a strictly increasing array, while [2, 1, 4, 3] is not.
``````
##### Input format:
``````The first line of input contains an integer 'N', representing the size of the array.

The second line of input contains 'N' space-separated integers, representing the elements of the array.
``````
##### Output Format:
``````The only output line contains one integer representing the length of the longest increasing subsequence.
``````
##### Note:
``````You do not need to print anything; it has already been taken care of. Just implement the given functions.
``````
##### Input Constraints
``````1 <= N <= 10^5
-10^5 <= element <= 10^5

Time Limit: 1sec
``````
• Q6. Search In Rotated Sorted Array

#### Note :

``````1. If ‘K’ is not present in ARR then print -1.
2. There are no duplicate elements present in ARR.
3. ARR can be rotated only in the right direction.
``````

#### For example, if ARR = [12, 15, 18, 2, 4] and K = 2, then the position at which K is present in the array is 3 (0-indexed).

``````Can you do this in Logarithmic time and constant additional space?
``````
##### Input Format
``````The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two single-space separated integers ‘N’ and ‘K’, respectively.

The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array/list ARR.
``````
##### Output Format :
``````For each test case return the index at which K is present in ARR.
``````
##### Note:
``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= N <= 5000
0 <= K <= 10^5
0 <= ARR[i] <= 10^5

Time Limit : 1 second
``````
• Q7. Rank from Stream

#### Note:

``````The rank of any element in ‘ARR’ is equal to the number of smaller elements than ‘ARR[K]’ on its left side.
``````

#### For example :

``````Input :
Let ‘ARR’’ = [6, 2, 9, 7] and ‘X’ = 3.
We can see there are two smaller elements than ‘ARR’ = 7 on its left side
Output: 2
``````

#### Follow Up :

``````Try to find rank in less time complexity than O(N), you may use some data structure to implement this.
``````

#### Input Format:

``````The first line of input contains a single integer T’, representing the number of test cases.
Then the ‘T’ test cases follow.

The first line of each test case contains two single space-separated numbers, ‘N’ and ‘K’, denoting the size of ‘ARR’, and the position of integer for which we have to find rank respectively.

The second line contains ‘N’ space-separated distinct integers denoting the array elements.
``````

#### Output format:

``````For each test case, return a single integer representing the rank of ‘ARR[K]’.
``````

#### Note :

``````You don’t have to print anything, it has already been taken care of. Just implement the given function.
``````

#### Constraints

``````1 <= T <= 100
1 <= N <= 10^4
1 <= K <= N
0 <=  ARR[i] <= 10^5

Time limit: 1 sec
``````
• Q8. LRU Cache Implementation

#### Design and implement a data structure for Least Recently Used (LRU) cache to support the following operations:

``````1. get(key) - Return the value of the key if the key exists in the cache, otherwise return -1.

2. put(key, value), Insert the value in the cache if the key is not already present or update the value of the given key if the key is already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting the new item.
``````
##### You will be given ‘Q’ queries. Each query will belong to one of these two types:
``````Type 0: for get(key) operation.
Type 1: for put(key, value) operation.
``````
##### Note :
``````1. The cache is initialized with a capacity (the maximum number of unique keys it can hold at a time).

2. Access to an item or key is defined as a get or a put operation on the key. The least recently used key is the one with the oldest access time.
``````
##### Input Format :
``````The first line of input contains two space-separated integers 'C' and 'Q', denoting the capacity of the cache and the number of operations to be performed respectively.

The next Q lines contain operations, one per line. Each operation starts with an integer which represents the type of operation.

If it is 0, then it is of the first type and is followed by one integer key.

If it is 1, it is of the second type and is followed by two space-separated integers key and value(in this order).
``````
##### Output Format :
``````For each operation of type 0, print an integer on a single line, denoting the value of the key if the key exists, otherwise -1.
``````
##### Note :
``````You don't need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= C <= 10^4
1 <= Q <= 10^5
1 <= key, value <= 10^9

Time Limit: 1 sec
``````
##### Sample Input 1 :
``````3 11
1 1 1
1 2 2
1 3 3
1 4 5
0 3
0 1
0 4
1 2 3
0 1
0 3
0 2
``````
##### Sample Output 1 :
``````3
-1
5
-1
3
3
``````
##### Explanation to Sample Input 1 : ``````Initializing a cache of capacity 3, LRUCache cache = new LRUCache(3);
Then each operation is performed as shown in the above figure.
cache.put(1,1)
cache.put(2,2)
cache.put(3,3)
cache.put(4,5)
cache.get(3)      // returns 3
cache.get(1)      // returns -1
cache.get(2)      // returns 2
cache.put(5,5)
cache.get(4)      // returns -1
cache.get(3)      // returns 3
``````
##### Sample Input 2 :
``````2 6
1 1 1
1 2 2
0 2
1 3 3
0 3
0 1
``````
##### Sample Output 2 :
``````2
3
-1
``````

### Interview details

Proposed: Eligibility criteriaAbove 7 CGPA
Facebook interview Rounds:Round 1
Round type - Online Coding Test
Round duration - 90 minutes
Round difficulty - Hard
Round description -

This was an online coding round where we were supposed to solve 2 questions under 90 minutes . Both the questions in my set were related to Graphs and were quite tricky and heavy to implement.

Round 2
Round type - Face to Face
Round duration - 60 Minutes
Round difficulty - Medium
Round description -

This was a Data Structures and Algorithms round with some standard questions . I was expected to come up with an
efficient approach and code it as well .

Round 3
Round type - Face to Face
Round duration - 50 Minutes
Round difficulty - Medium
Round description -

This was also a DSA round where I was asked to code only one of the questions but I eventually ended up coding both
as I had some spare time and explained my approches very smoothly to the interviewer . This round went preety well .

Round 4
Round type - Face to Face
Round duration - 50 Minutes
Round difficulty - Medium
Round description -

This was also a DSA round with 2 questions of Medium to Hard difficulty . I was expected to follow some clean code and OOPS principles to write the code in this round .

Facebook interview preparation:Topics to prepare for the interview - Data Structures, Algorithms, System Design, Aptitude, OOPSTime required to prepare for the interview - 4 MonthsInterview preparation tips for other job seekers

Tip 1 : Must do Previously asked Interview as well as Online Test Questions.
Tip 2 : Go through all the previous interview experiences from Codestudio and Leetcode.
Tip 3 : Do at-least 2 good projects and you must know every bit of them.

Application resume tips for other job seekers

Tip 1 : Have at-least 2 good projects explained in short with all important points covered.
Tip 2 : Every skill must be mentioned.
Tip 3 : Focus on skills, projects and experiences more.

Final outcome of the interviewSelected
View More  ### Interview Rounds

Face to Face

I was interviewed before Dec, 2020.

### Interview Questions

• Q1. K Closest Points To Origin

#### Note:

``````The distance between two points on a plane is the Euclidean Distance.
``````
##### For Example:
``````If N = 2, K = 1 and the points are {2,3}, {-1, 2}.

Then the distance of the first point from the origin is sqrt((2 - 0) ^ 2 + (3 - 0) ^ 2) = sqrt(13).

The distance of the second point from the origin is sqrt((-1 - 0) ^ 2 + (2 - 0) ^ 2) = sqrt(5).
``````
``````Can you solve this in O(N log K) time complexity?
``````
##### Input format:
``````The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow.

The first line of each test case contains two integers 'N' and 'K' separated by a single space.

The second line of each test case contains 2 * N space-separated integers where for each i = 1 to 'N', the (2 * i - 1) th and the (2 * i) th element represents the x-coordinate and y-coordinate of ith point respectively.
``````
##### Output format:
``````For each test case, print a single line containing 2 * K space-separated integers where for each i = 1 to 'K', the (2 * i - 1) th and the (2 * i) th element represents the x-coordinate and y-coordinate of the i th point respectively. Print the output in sorted order.

The output of each test case will be printed in a separate line.
``````
##### Note:
``````You do not need to print anything or sort the final result. It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= K <= N <= 10 ^ 4
-10 ^ 4 <= POINTS[i], POINTS[i] <= 10 ^ 4

Time limit: 1 sec.
``````
• Q2. Power Set

#### You have to return the array of subsets. The elements in the subset should be sorted in ascending order. The order of subsets in the array does not matter. Hence there can be more than 1 possible solution for a given array.

##### For example :
``````If we are given an array ARR=[1,2,3] then the power set P(ARR) of the set ARR is: [ [], , , [1,2], , [1,3], [2,3], [1,2,3] ]
``````
##### Note :
``````For every subset 'X' present in power set P(ARR) of set ARR, X must be sorted i.e. in the example above:
P1(ARR) =  [ [], , , [1,2], , [1,3], [2,3], [1,2,3] ]
P2(ARR) =  [ [], , [1,2,3], , [1,2], , [1,3], [2,3] ]
P3(ARR) =  [ [], , , [1,2], , [1,3], [2,3], [2,3,1] ]
P1(ARR) and P2(ARR) will be considered correct power sets but P3(ARR) will not be considered correct because there the last subset [2, 3, 1] is not sorted.
``````
##### Input Format :
``````The first line contains a number 'N' denoting the size of the array.
The second line contains 'N' space-separated distinct integer denoting the elements of the array.
``````
##### Output format :
`````` For each given 'N' print 2^N separate lines each denoting a subset.
For each subset, print its element separated by space.
``````
##### Note :
``````You don’t have to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= N <= 15
1 <= ARR[i] <= 50
Time limit : 1 second
``````
• Q3. Roman Numeral To Integer

#### Roman numerals are represented by seven different symbols: I, V, X, L, C, D, and M.

##### Table of values:
``````Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
``````
##### For example:
``````3 is written as III in Roman numeral, just three ones added together. 13 is written as XIII, which is simply X + III. The number 25 is written as XXV, which is XX + V
``````
##### Note:
``````Do not print anything, just return an integer denoting the equivalent integer of the given roman number

It is guaranteed that the string input is one of the characters of I, V, X, L, C, D, M.

It is guaranteed that the integer value of the given roman number will not exceed 3999.
``````
##### Input format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.

The first line of each test case contains a string ‘roman’ representing the number's roman number representation.
``````
##### Output Format
``````For each test case, return a single integer denoting the integer value of the given roman number.
``````
##### Constraints:
``````1 <= T <= 50
1 <= roman.length <= 15

Time limit: 1 second
``````
• Q4. Pair Sum

#### Note:

``````Each pair should be sorted i.e the first value should be less than or equals to the second value.

Return the list of pairs sorted in non-decreasing order of their first value. In case if two pairs have the same first value, the pair with a smaller second value should come first.
``````
##### Input Format:
``````The first line of input contains two space-separated integers 'N' and 'S', denoting the size of the input array and the value of 'S'.

The second and last line of input contains 'N' space-separated integers, denoting the elements of the input array: ARR[i] where 0 <= i < 'N'.
``````
##### Output Format:
``````Print 'C' lines, each line contains one pair i.e two space-separated integers, where 'C' denotes the count of pairs having sum equals to given value 'S'.
``````
##### Note:
``````You are not required to print the output, it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= N <= 10^3
-10^5 <= ARR[i] <= 10^5
-2 * 10^5 <= S <= 2 * 10^5

Time Limit: 1 sec
``````
• Q5. Arithmetic Expression Evaluation

#### In Infix Notation, operators are written in-between their operands.

##### Note :
``````1. We consider the ‘/’ operator as the floor division.

2. Operators ‘*’ and ‘/’ expression has higher precedence over operators‘+’ and ‘-’

3. String expression always starts with ‘(‘ and ends with ‘)’.

4. It is guaranteed that ‘expression’ represents’ a valid expression in Infix notation.

5. It is guaranteed that there will be no case that requires division by 0.

6. No characters other than those mentioned above are present in the string.

7. It is guaranteed that the operands and final result will fit in a 32-bit integer.
``````
##### For example :
``````Consider string ‘expression’ = ‘((2+3)*(5/2))’.
Then it’s value after evaluation will be ((5)*(2)) = 10.
``````
##### Input format :
``````The first line of input contains an integer ‘T’ denoting the number of test cases.
The next T lines represent the ‘T’ test cases.

The first and only line of each test case contains the string ‘expression’.
``````
##### Output format :
``````For each test case, in a separate line print an integer representing the value of the given arithmetic expression after evaluation.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 50
3 <= |expression| <= 10^4

Time limit: 1 sec
``````
• Q6. Remove Duplicates from Sorted Array

#### You are given a sorted integer array' ARR' of size 'N'. You need to remove the duplicates from the array such that each element appears only once. Return the length of this new array.

##### Note:
``````Do not allocate extra space for another array. You need to do this by modifying the given input array in-place with O(1) extra memory.
``````
##### Input format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the array.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.
``````
##### Output format:
``````For each test case, return the length of the modified array.
``````
##### Note:
``````You don't need to print anything, it has already been taken care of. Just Implement the given function.
``````
##### Constraints :
``````1 <= T <= 5
1 <= N <= 10^5
-10^9 <= ARR[i] <=10^9

Where ‘ARR[i]’ is the value of elements of the array.

Time limit: 1 sec
``````
• Q7. System Design Question

How does Facebook store likes/dislikes ?

• Q8. System Design Question

How does Facebook implement graph search ?

• Q9. Technical Question

What is Hadoop and why is it used ?

• Q10. System Design Question

How does Facebook Chat works ?

### Interview details

Proposed: Eligibility criteriaAbove 7 CGPA
Facebook interview Rounds:Round 1
Round type - Face to Face
Round duration - 60 Minutes
Round difficulty - Medium
Round description -

This was a Data Structures and Algorithms round with preety good questions . I was expected to come up with an efficient approach and code it as well .

Round 2
Round type - Face to Face
Round duration - 50 Minutes
Round difficulty - Hard
Round description -

This was also a DSA round where I was asked to code only one of the questions but I eventually ended up coding both as I had some spare time and explained my approches very smoothly to the interviewer . This round went preety well .

Round 3
Round type - Face to Face
Round duration - 50 Minutes
Round difficulty - Medium
Round description -

This was also a DSA round with 2 questions . One was implementation heavy and the other was related to recursion and so I handled it carefully so that my code does not run into TLE or Segmentation Fault.

Round 4
Round type - Face to Face
Round duration - 50 Minutes
Round difficulty - Medium
Round description -

This was a typical System Design round where I was asked about the various features of Facebook and what sort of data structures and algorithms are used in implementing them .

Round 5
Round type - Face to Face
Round duration - 50 Minutes
Round difficulty - Medium
Round description -

This was a preety intense round as I was grilled more on my System Design concepts but eventually I was able to asnwers all the questions with some help from the interviewer.

Facebook interview preparation:Topics to prepare for the interview - Data Structures, Algorithms, System Design, Aptitude, OOPSTime required to prepare for the interview - 5 MonthsInterview preparation tips for other job seekers

Tip 1 : Must do Previously asked Interview as well as Online Test Questions.
Tip 2 : Go through all the previous interview experiences from Codestudio and Leetcode.
Tip 3 : Do at-least 2 good projects and you must know every bit of them.

Application resume tips for other job seekers

Tip 1 : Have at-least 2 good projects explained in short with all important points covered.
Tip 2 : Every skill must be mentioned.
Tip 3 : Focus on skills, projects and experiences more.

Final outcome of the interviewSelected
View More  ### Interview Rounds

Video Call

I was interviewed before Sep, 2020.

### Interview Questions

• Q1. Arithmetic Progression Queries

#### Given an integer array(ARR) of size N, the following operations need to be performed:

``````update(l, r, val) : Add (val + i) to arr[l + i] where, 0 <= i <= r - l.

rangeSum(l, r): return the sum of all elements in the array from index l to r, i.e., the sum of array arr[l...r].
``````

#### Two type of queries denote these operations:

``````Type 1: for update(l, r, val) operation.
Type 2: for rangeSum(l, r) operation.

Note: (1 based indexing) for the queries.
``````
##### Input Format:
``````The first line of input contains two space-separated integers N and Q, denoting the size of the input array and the number of operations to be performed, respectively.

The next Q lines contain operations, one per line. Each operation starts with an integer which represents the type of operation.

If it is 1, then it is of the first type and is followed by three single space-separated integers l, r, val(in this order).

If it is 2, it is of the second type and is followed by two single space-separated integers l r(in this order). The meanings of l, r, and val are well explained in the statement.
``````
##### Output Format:
``````For each operation of type 2, print an integer on the single line - the sum of the arr[l..r].

Output for each test case will be printed in a separate line.
``````
##### Note
``````You are not required to print anything, and it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= N <= 10^5
1 <= Q <= 10^5
1 <= l <= r <= N
0 <= val <= 10^6
0 <= arr[i] <= 10^6

where 'N' is the size of the array, 'Q' is the number of queries, and arr[i] denotes the ith element of the array.

Time Limit: 1 sec.
``````
• Q2. Arithmetic Expression Evaluation

#### In Infix Notation, operators are written in-between their operands.

##### Note :
``````1. We consider the ‘/’ operator as the floor division.

2. Operators ‘*’ and ‘/’ expression has higher precedence over operators‘+’ and ‘-’

3. String expression always starts with ‘(‘ and ends with ‘)’.

4. It is guaranteed that ‘expression’ represents’ a valid expression in Infix notation.

5. It is guaranteed that there will be no case that requires division by 0.

6. No characters other than those mentioned above are present in the string.

7. It is guaranteed that the operands and final result will fit in a 32-bit integer.
``````
##### For example :
``````Consider string ‘expression’ = ‘((2+3)*(5/2))’.
Then it’s value after evaluation will be ((5)*(2)) = 10.
``````
##### Input format :
``````The first line of input contains an integer ‘T’ denoting the number of test cases.
The next T lines represent the ‘T’ test cases.

The first and only line of each test case contains the string ‘expression’.
``````
##### Output format :
``````For each test case, in a separate line print an integer representing the value of the given arithmetic expression after evaluation.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 50
3 <= |expression| <= 10^4

Time limit: 1 sec
``````
• Q3. Interleaving Two Strings

#### 'C' is said to be interleaving 'A' and 'B', if the length of 'C' is equal to the sum of the length of 'A' and length of 'B', all the characters of 'A' and 'B' are present in 'C' and the order of all these characters remains the same in all three strings.

##### For Example:
``````If A = “aab”, 'B' = “abc”, 'C' = “aaabbc”
Here 'C' is an interleaving string of 'A' and 'B'. because 'C' contains all the characters of 'A' and 'B' and the order of all these characters is also the same in all three strings.
`````` ``````If 'A' = “abc”, 'B' = “def”, 'C' = “abcdefg”
Here 'C' is not an interleaving string of 'A' and 'B'. 'B'ecause neither A nor 'B' contains the character ‘g’.
``````
##### Input format:
``````The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first and only line of each test case contains three strings 'A', 'B' and 'C' each separated by a single space.
``````
##### Output format:
``````For each test, print True, if 'C' is an interleaving string of 'A' and 'B, otherwise print False in a separate line.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### 'C'onstraints:
``````1 <= T <= 10
1 <= |'A'|, |'B'| <= 150
1 <= |'C'| <= 300

where |A|, |'B'|, |'C'| denotes the length of string 'A', 'B' and 'C' respectively.
All the characters of the strings 'A', 'B' and 'C' contain lowercase English letters only.

Time limit: 1 sec
``````
• Q4. Get DFS Path

#### Find the path using DFS and print the first path that you encountered.

##### Note:
``````Vertices are numbered through 0 to V-1.
``````
##### Input Format :
``````The first line contains a single integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains two integers ‘V’ and ‘E’ denoting the number of vertices and edges in the graph.

The next ‘E’ lines of the test case contain two space-separated integers ‘a’ and ‘b’ denoting that there exists an edge between ‘a’ and ‘b’.

The last line of the test case contains two space-separated integers ‘v1’ and ‘v2’ denoting the starting vertex and ending vertex.
``````
##### Output Format :
``````For each test case, print the path from ‘v1’ to ‘v2’ in reverse order.

Output for each test case will be printed in a separate line.
``````
##### Note :
``````You are not required to print anything; it has already been taken care of. Just implement the function and return a list of paths.

If there is no path between the vertices return an empty list.If the path is valid then it will print true else it will print false.
``````
##### Constraints :
``````1 <= T <= 10
1 <= V <= 1000
1 <= E <= (V * (V - 1)) / 2
0 <= v1, v2 <= V-1

Time Limit: 1sec
``````
• Q5. Basic HR Questions

Why you wanna join Facebook?

Tell me an incident where you missed the deadline for assignment submission and how did you handle it?

### Interview details

Professional and academic backgroundI applied for the job as SWE Intern in LondonProposed: Eligibility criteriaN/A
Facebook interview Rounds:Round 1
Round type - Video Call
Round duration - 45 minutes
Round difficulty - Medium
Round description -

It was a 45 min coding interview which has 3 sections, the first 5 min are reserved for you & your interviewer to introduce each other. After which you're expected to solve 2-3 coding problems with bug-free code and while solving make sure you think out loud and discuss your approach with your interviewer before start coding.
At the end of the interview, you'll be asked to discuss any questions or doubts if you've any.

Round 2
Round type - Video Call
Round duration - 60 minutes
Round difficulty - Hard
Round description -

It was a 60 min interview of which the first 15 min were dedicated to behavioral questions and the remaining 45 min was the same as the last round.

The way behavioral round works is that your interviewer will give you a situation and will seek your inputs on how would you tackle this or may ask you to share some incidents from your past where you exhibited a few leadership skills. I would suggest being prepared upfront with 1-2 stories from your past internships or college life where you led a team or handled a tough situation.

Facebook interview preparation:Topics to prepare for the interview - Data Structures & Algorithms, Graph Theory, Binary/Interval Tree, Heaps, Probability, Randomised algorithms, and sometimes design problems.Time required to prepare for the interview - 5 MonthsInterview preparation tips for other job seekers

Tip 1 : Start as early as you can, and be consistent while you are practicing. It's like the Law of Inertia i.e initially it seems very hard but once you get into practice you'll start enjoying the process.
Tip 2 : If you have enough(3-4 months) time then try to solve problems in a Depth First manner i.e explore each topic before jumping to the next one.
Tip 3 : Make sure to cover company-specific problems before your final interview this would help you to find a pattern in what exactly the organization is seeking in a candidate. Also, if possible try to talk to people who have gone through the same process in the past.

Application resume tips for other job seekers

Tip 1 : Recruiters love seeing things that you have done other than your academics, so make sure you have good side projects to showcase, participate in Hackathons, and coding competition.
Tip 2 : Try contributing to open-source projects but don't limit yourself to just GSoC, RGSoC, or Outreachy. Contribute to projects that have a huge impact this would help your profile to stand out.

Final outcome of the interviewSelected
View More  ### Interview Rounds

Coding Test

Telephonic Call

I was interviewed before Sep, 2020.

### Interview Questions

• Q1. Bird and maximum fruit-gathering

#### You are given N and M (the total number of seconds the ninja bird has), and the fruit values of the trees. Your task is to maximize the total fruit value that the ninja bird can gather. The bird can start from any tree.

##### Note
``````All trees are in a circle.
``````
##### For Example:
``````Input: N = 7 M = 3
ARR[] = { 2, 1, 3, 5, 0, 1, 4 }

Output: 9

Explanation:
She can start from tree 1 and move to tree 2 and then to tree 3.
Hence, total number of gathered fruits = 1 + 3 + 5 = 9.
``````
##### Input Format
``````The first line of input contains a single integer ‘T’ denoting the number of test cases for the problem.

The first line of each test case in the input contains two space-separated integers ‘N’ and ‘M’ denoting the number of trees and the seconds given to collect the fruits from the trees.

And the second line contains 'N' single space-separated integers, denoting the fruits on each tree.
``````
##### Output Format:
``````For each test case, print a single line containing a single integer denoting the maximum number of fruits the ninja bird can gather in the given amount of time.

The output of each test case will be printed in a separate line.
``````
##### Note:
``````You do not need to print anything. It has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 100
1 <= M <= 5000
1 <= N <= 5000
1 <= ARR[i] <= 5000

Time Limit: 1 sec.
``````
• Q2. Base 58

#### Conversion Eg: ( according to above mapping).

``````Base 10 | Base 58
0       |     1
1       |     2
10      |     A
20      |     L
30      |     W
53      |     u
``````
##### Input Format:
``````The first line of the input contains ‘T’ denoting the number of test cases.

The first and the only line of each test case contains an integer N.
``````
##### Output Format:
``````For each test case, print a single line containing a single integer denoting the number in the base 58.

The output of each test case will be printed in a separate line.
``````

#### Note:

``````You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 50
0 <= N <= 10 ^ 4

Time limit: 1 sec.
``````
• Q3. Pair Sum

#### Note:

``````1. Pair (x,y) and Pair(y,x) are considered as the same pair.

2. If there exists no such pair with sum equals to 'TARGET', then return -1.
``````

#### Example:

``````Let ‘ARR’ = [1 2 3] and ‘TARGET’ = 4. Then, there exists only one pair in ‘ARR’ with a sum of 4 which is (1, 3). (1, 3) and (3, 1) are counted as only one pair.
``````
##### Input Format:
``````The first line of input contains an integer ‘T’ which denotes the number of test cases.

The first line of each test case contains two single space-separated integers ‘N’ and ‘TARGET’ representing the number of elements in the array/list ‘ARR’ and the required pair-sum respectively.

The next line of each test case contains ‘N’ single space-separated integers denoting the elements of  ‘ARR’.
``````
##### Output Format :
``````For each test case, return the numbers of pairs in  ‘ARR’ whose sum is equal to ‘TARGET’.
``````
##### Note:
``````You don't need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= ‘T’ <= 100
2 <= ‘N’ <= 5000
1 <= ‘ARR[i]’, ‘TARGET’ <= 10^5

Where ARR[i]’ represents the elements of array/list ‘ARR’.

Time Limit: 1 sec
``````
• Q4. Triplets with Given Sum

#### An array is said to have a triplet {ARR[i], ARR[j], ARR[k]} with sum = 'K' if there exists three indices i, j and k such that i!=j, j!=k and i!=j and ARR[i] + ARR[j] + ARR[k] = 'K'.

##### Note:
``````1. You can return the list of values in any order. For example, if a valid triplet is {1, 2, -3}, then {2, -3, 1}, {-3, 2, 1} etc is also valid triplet. Also, the ordering of different triplets can be random i.e if there are more than one valid triplets, you can return them in any order.
2. The elements in the array need not be distinct.
3. If no such triplet is present in the array, then return an empty list, and the output printed for such a test case will be "-1".
``````
##### Input Format:
``````The first line of the input contains an integer T, denoting the number of test cases.

The first line of each test case contains the integer N, denoting the size of the array.

The second line of each test case contains N space-separated integers denoting the array elements.

The third line of each test case contains the integer K, denoting the required sum for each triplet.
``````
##### Output Format:
``````For each test case, every line of output contains three spaced integers denoting a valid triplet as described in the statement. Refer to sample input 2 for more clarification.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <=  50
1 <= N <= 10^3
-10^6 <= ARR[i] <= 10^6
-10^9 <= K <= 10^9

Time Limit: 1 sec
``````

### Interview details

Professional and academic backgroundI applied for the job as SDE - Intern in DelhiProposed: Eligibility criteria8 CGPA above
Facebook interview Rounds:Round 1
Round type - Online Coding Interview
Round duration - 75 minutes
Round difficulty - Easy
Round description -

Timing it is around 11 am and Environment is good .

Round 2
Round type - Telephonic
Round duration - 45 mintues
Round difficulty - Medium
Round description -

Environment was very friendly but questions asked are hard

Facebook interview preparation:Topics to prepare for the interview - Linked List, Binary Search Tree ,Queue, Array ,DP ,Graph ,RecursionTime required to prepare for the interview - 3 monthsInterview preparation tips for other job seekers

Tip 1 : Practice Atleast 500 Questions
Tip 2 : Do atleast 1 good projects
Tip 3 : You should be able to explain your project

Application resume tips for other job seekers

Tip 1 : Have some projects on resume.
Tip 2 : Do not put false things on resume.

Final outcome of the interviewSelected
View More  Contribute to the growing community

Don’t worry. You can choose to be anonymous.