### Interview Rounds

Coding Test

Video Call

I was interviewed in Jul, 2021.

### Interview Questions

- Q1. Longest Increasing Path In A 2D Matrix
#### You have been given a MATRIX of non-negative integers of size N x M where 'N' and 'M' denote the number of rows and columns, respectively.

#### Your task is to find the length of the longest increasing path when you can move to either four directions: left, right, up or down from each cell. Moving diagonally or outside the boundary is not allowed.

#### Note: A sequence of integers is said to form an increasing path in the matrix if the integers when traversed along the allowed directions can be arranged in strictly increasing order. The length of an increasing path is the number of integers in that path.

#### 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`

View Answer (3)Collapse - 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`

View Answer (4)Collapse - Q3. K - Sum Path In A Binary Tree
#### You are given a binary tree in which each node contains an integer value and a number ‘K’. Your task is to print every path of the binary tree with the sum of nodes in the path as ‘K’.

#### 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`

View Answer (2)Collapse - Q4. Combination Sum
#### You are given an array/list ARR of N distinct positive integers. You are also given a non-negative integer B.

#### Your task is to find all unique combinations in the array whose sum is equal to B. A number can be chosen any number of times from array/list ARR.

#### Elements in each combination must be in non-decreasing order.

#### 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`

View Answer (2)Collapse - Q5. Accounts Merge
#### You have been given an array/list 'ACCOUNTS' where each element, i.e. ACCOUNTS[i] contains a list of strings, where the first element is the name of the account holder and the rest of the strings are emails representing the emails of the account.

#### Now, you are supposed to merge the accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that it may be possible that two accounts belong to the same name, but they may belong to different people as people could have the same name. And a person could have any number of accounts initially, but all their accounts definitely have the same name.

#### 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`

View Answer (3)Collapse - 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?`

View Answer (3)Collapse - Q7. OS Question
Explain Demand Paging .

View Answer (1)Collapse - Q8. System Design Question
How does Facebook store likes/dislikes ?

View Answer (1)Collapse - Q9. System Design Question
How does Facebook implement graph search ?

View Answer (1)Collapse - Q10. System Design Question
How does Facebook Chat works ?

View Answer (1)Collapse

### Interview details

**Proposed: Eligibility criteria**Above 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, OOPS

**Time required to prepare for the interview**- 4 Months

**Interview 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 interview**Selected