Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Facebook interview experience Real time questions & tips from candidates to crack your interview

Facebook

5 rounds | 10 Coding
problems

Preparation

Duration: 5 Months

Topics: Data Structures, Algorithms, System Design, Aptitude, OOPS

Tip

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 process

Where: Campus

Eligibility: Above 7 CGPA

Resume tip

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.

01

Round

Medium

Face to Face

Duration60 Minutes

Interview date5 Jun 2015

Coding problem2

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 .

```
The distance between two points on a plane is the Euclidean Distance.
```

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

Problem approach

I solved it using priority queue with a custom comparator that compares points according to their Euclidean Distance with respect to the Origin.

Steps :

1) Initiliase a priority queue with a custom comparator.

2) Push all the points to the priority queue.

3) Pop the first k elements of the priority queue and store it in vector called answer.

4) Finally output the contents of answer vector

TC : O(N*Log(N))

SC : O(N)

```
If we are given an array ARR=[1,2,3] then the power set P(ARR) of the set ARR is: [ [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] ]
```

```
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,2], [3], [1,3], [2,3], [1,2,3] ]
P2(ARR) = [ [], [1], [1,2,3], [2], [1,2], [3], [1,3], [2,3] ]
P3(ARR) = [ [], [1], [2], [1,2], [3], [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.
```

Problem approach

Given,a set of n elements I was supposed to print all the subsets of this set . I was famiiar with this question and had already solved it in LeetCode and CodeStudio so coding it in the first go was not so hard for me .

Approach : I solved it using bitmasking . The main intuition was if I have a binary number like 1001 , I would take only the 0th element and the 3rd element of the array .

Steps :

1) Run a loop from 0 to (2^n)-1 (as we have 2^n subsets for a set of n elements)

2) For every number , run a loop again from 0 to n-1 to check if the ith bit is set or not.

3) To check if the ith bit is set or not , simply check if (number & 2^i) > 0 or not

(where i ranges from 0 to n-1)

4) If (num & 2^i)==0 , ith bit is 0 i.e., do not take the ith element into the subset . Else if (num &2^i)>0 , ith bit is 1 i.e., take the ith element into the subset.

5) Finally put all the subsets into a vector and output the answer vector

TC : O(2^n)

SC : O(2^n)

02

Round

Hard

Face to Face

Duration50 Minutes

Interview date5 Jun 2015

Coding problem2

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 .

```
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
```

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

Problem approach

This question was preety straightforward and was asked to check my implementation skills and how well do I handle some Edge Cases . So I was expected to directly code it shortly after explaining my approach .

Approach :

1) Initialise a Map and map all the standard roman numerals to their respective integer counterparts.

2) Run a loop till the length of the Roman Numeral and take substrings of length 2 and check if it is present or not in the map .

3) If the substring of lenght 2 is present simply add up its value from the map to my final answer

4) If it is not present then add up the value of the single character from the map to the final answer

5) Output the value of the answer

TC : O(N)

SC: O(1) , Since the map conatins oly 14 elements irrespective of the value N .

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

Problem approach

Initialize a list to store our results. For each element in the array 'ARR[i]', check if ('ARR[i]' + ‘ARR[j]’), equals to given sum or not, where ‘i’ < ‘j’ < ‘N’. If the condition matches, add the pair('ARR[i]', ‘ARR[j]’) to the list. Sort the list of pairs as per the given output format and return this list.

03

Round

Medium

Face to Face

Duration50 Minutes

Interview date5 Jun 2015

Coding problem2

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.

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

```
Consider string ‘expression’ = ‘((2+3)*(5/2))’.
Then it’s value after evaluation will be ((5)*(2)) = 10.
```

Problem approach

The problem statement was quite straight forward but I was asked to code the Space Optimised Approach. I had previously solved this question using a stack but without using any extra space required a liitle bit of observation that the input vector given can also be used as a stack .

Approach 1 (Using Stack ) :

1) If the current token is a operand (number), push it into the stack

2) If the token is a operator, pop the top two operands from the stack. Find the result of the operation using the operator and two operands and push the result back into stack

3) Finally, the stack will contain the result of evaluated reverse polish expression.

TC : O(N)

SC: O(N)

Approach 2 (Without using stack ) :

If we are allowed to modify the input vector, we can optimize the space usage by using the input vector itself as a stack rather than an explicit stack.

1) Here, we will maintain a pointer top which will point to the top index of tokens (our implicit stack).

2) Everytime we receive a integer token, we will push it at the index pointed by top.

3) Similarly, when we receive an operator, we can pop the top two operands and after computing the result on them, push it back into tokens.

The only important thing here is properly maintaining the top pointer, so that we correctly access the elements the operands.

TC : O(N)

SC: O(1)

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

```
'n' = 5, 'arr' = [1 2 2 2 3].
The new array will be [1 2 3].
So our answer is 3.
```

Problem approach

I solved this problem using recursion . From the given problem itself , it is clear that if I solve the same problem for a smaller string say the subtring from 1 to n (call it s). I will simply append all the mappings of the first character to all the strings that would come from the substring s .

Approach :

1) Create a recursive function (vectorrecur(string s)) which would return all the possible strings for the string s

2) Call the same recursive function but for the substring s starting from index 1 . Store its answer on vector called v .

3) Now initialise a vector answer and append all the mappings of s[0] to all the strings of v . Store all these strings in the answer vector

4) Return answer vector

5) Note : Base Case : For an empty string i.e., when s.size()==0 simply return a vector with an empty string in it.

TC : O(k1*k2*k3*..kn) where k1=number of mappings of char c1 , k2=number of mappings of char c2 and so on.

SC : O(k1*k2*k3*...kn)

04

Round

Medium

Face to Face

Duration50 Minutes

Interview date5 Jun 2015

Coding problem2

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 .

How does Facebook store likes/dislikes ?

Problem approach

Approach :

1) We can keep one counter variable which counts the overall likes in that same document where the post's data is present.

2) And store the details/uids of people who liked it in different documents( this way, when we tap on details, then only we'll need to fetch these docs) and, we can setup a cloud func whch updates that counter whenever someone likes/dislikes.

3) To check that user has liked or not, we can just check if the current user's uid is present in the likes/dislikes.

How does Facebook implement graph search ?

Problem approach

Answer :

1) Facebook graph search, can be considered as a complex graph with entities like people, pages, photos and videos, while the edges are relationships among all of these entities.

2) Unicorn- standard inverted index system optimized for the needs of Facebook is used for having all the information on the main memory so the query processing doesn't involve any disk access.

3) Unicorn processes queries that select a section of the social graph.

4) Unicorn is essentially built like a standard search engine that maps terms to sets of documents; unlike a text search engine, the terms aren't words, but connections in the social graph (for example, "friend:4" maps to the ids of all users who are friends with the user with id 4; similar terms for "photos taken by user id 4", "users who like page with id 25" etc).

On top of this, there are other layers (parsing natural language queries, ranking, privacy filtering, rendering the results, etc) but Unicorn sits at the core.

05

Round

Medium

Face to Face

Duration50 Minutes

Interview date5 Jun 2015

Coding problem2

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.

What is Hadoop and why is it used ?

Problem approach

Answer :

Hadoop is an open source framework from Apache and is used to store process and analyze data which are very huge in volume. Hadoop is written in Java and is not OLAP (online analytical processing). It is used for batch/offline processing.It is being used by Facebook, Yahoo, Google, Twitter, LinkedIn and many more. Moreover it can be scaled up just by adding nodes in the cluster.

Modules of Hadoop:

1) HDFS: Hadoop Distributed File System. Google published its paper GFS and on the basis of that HDFS was developed. It states that the files will be broken into blocks and stored in nodes over the distributed architecture.

2) Yarn: Yet another Resource Negotiator is used for job scheduling and manage the cluster.

3) Map Reduce: This is a framework which helps Java programs to do the parallel computation on data using key value pair. The Map task takes input data and converts it into a data set which can be computed in Key value pair. The output of Map task is consumed by reduce task and then the out of reducer gives the desired result.

4) Hadoop Common: These Java libraries are used to start Hadoop and are used by other Hadoop modules.

Hadoop Architecture:

1) The Hadoop architecture is a package of the file system, MapReduce engine and the HDFS (Hadoop Distributed File System).

2) The MapReduce engine can be MapReduce/MR1 or YARN/MR2.

3) A Hadoop cluster consists of a single master and multiple slave nodes.

4) The master node includes Job Tracker, Task Tracker, NameNode, and DataNode whereas the slave node includes DataNode and TaskTracker.

Advantages of Hadoop :

1) Fast: In HDFS the data distributed over the cluster and are mapped which helps in faster retrieval. Even the tools to process the data are often on the same servers, thus reducing the processing time. It is able to process terabytes of data in minutes and Peta bytes in hours.

2) Scalable: Hadoop cluster can be extended by just adding nodes in the cluster.

3) Cost Effective: Hadoop is open source and uses commodity hardware to store data so it really cost effective as compared to traditional relational database management system.

4) Resilient to failure: HDFS has the property with which it can replicate data over the network, so if one node is down or some other network failure happens, then Hadoop takes the other copy of data and use it. Normally, data are replicated thrice but the replication factor is configurable.

How does Facebook Chat works ?

Problem approach

I was asked to answer this question w.r.t 2 very important aspects on how a chat system becomes more engaging to its users.

Answer :

Real-time messaging :

1) The method FB chooses to get text from one user to another involves loading an iframe on each Facebook page, and having that iframe’s Javascript make an HTTP GET request over a persistent connection that doesn’t return until the server has data for the client.

2) The request gets re-established if it’s interrupted or times out. This is a variation of Comet, specifically XHR long polling, and/or BOSH.

3) Having a large-number of long-running concurrent requests makes the Apache part of the standard LAMP stack a dubious implementation choice.

Real-time presence notification :

1) The naive implementation of sending a notification to all friends whenever a user comes online or goes offline has a worst case cost of O(average friendlist size * peak users * churn rate) messages/second, where churn rate is the frequency with which users come online and go offline, in events/second.

2) Surfacing connected users’ idleness greatly enhances the chat user experience but further compounds the problem of keeping presence information up-to-date.

3) Each Facebook Chat user now needs to be notified whenever one of his/her friends (a) takes an action such as sending a chat message or loads a Facebook page (if tracking idleness via a last-active timestamp) or (b) transitions between idleness states (if representing idleness as a state machine with states like “idle-for-1-minute”, “idle-for-2-minutes”, “idle-for-5-minutes”, “idle-for-10-minutes”, etc.).

4) Approach (a) changes the sending a chat message / loading a Facebook page from a one-to-one communication into a multicast to all online friends, while approach (b) ensures that users who are neither chatting nor browsing Facebook are nonetheless generating server load.

Here's your problem of the day

Solving this problem will increase your chance to get selected in this company

Suppose list1 is [2, 133, 12, 12], what is max(list1) in Python?

Choose another skill to practice

Start a Discussion

Similar interview experiences

SWE Intern

2 rounds | 5 problems

Interviewed by Facebook

1071 views

0 comments

0 upvotes

SDE - Intern

2 rounds | 3 problems

Interviewed by Facebook

1347 views

0 comments

0 upvotes

SDE - 1

4 rounds | 8 problems

Interviewed by Facebook

726 views

0 comments

0 upvotes

SDE - 1

4 rounds | 10 problems

Interviewed by Facebook

996 views

0 comments

0 upvotes

Companies with similar interview experiences

SDE - 1

5 rounds | 12 problems

Interviewed by Amazon

105411 views

24 comments

0 upvotes

SDE - 1

4 rounds | 5 problems

Interviewed by Microsoft

50292 views

5 comments

0 upvotes

SDE - 1

3 rounds | 7 problems

Interviewed by Amazon

31315 views

6 comments

0 upvotes