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

SDE - 1

Facebook
upvote
share-icon
5 rounds | 10 Coding problems

Interview preparation journey

expand-icon
Preparation
Duration: 5 Months
Topics: Data Structures, Algorithms, System Design, Aptitude, OOPS
Tip
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
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.

Interview rounds

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 .

1. K Closest Points To Origin

Moderate
25m average time
75% success
0/80
Asked in companies
AppleFacebookAmazon

Your house is located at the origin of a 2-D plane. You have 'N' neighbours who live at 'N' different points on the plane. You want to visit exactly 'K' different neighbours who live closest to your house, you are given a 2 - D matrix 'POINTS'. So, find out the coordinates of the neighbours you are going to visit. The answer is guaranteed to be unique.

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).
Follow Up:
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)

Try solving now

2. Power Set

Easy
15m average time
85% success
0/40
Asked in companies
Paytm (One97 Communications Limited)AdobeGoogle

You are given a sorted array of 'N' integers. You have to generate the power set for this array where each subset of this power set is individually sorted.

A set is a well-defined collection of distinct elements. Power set P(ARR) of a set 'ARR' is defined as a set of all possible subsets of 'ARR'.

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,2], [3], [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,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)

Try solving now
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 .

1. Roman Numeral To Integer

Easy
15m average time
85% success
0/40
Asked in companies
UberFacebookBarclays

You are given a string 's' that represents a Roman number. Convert the Roman number to an integer and return it.


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

Try solving now

2. Pair Sum

Easy
15m average time
90% success
0/40
Asked in companies
GrofersOlaJP Morgan

You are given an integer array 'ARR' of size 'N' and an integer 'S'. Your task is to return the list of all pairs of elements such that each sum of elements of each pair equals 'S'.

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

Try solving now
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. Arithmetic Expression Evaluation

Moderate
30m average time
70% success
0/80
Asked in companies
AdobeFacebookMicrosoft

You are given a string ‘expression’ consists of characters ‘+’, ‘-’, ‘*’, ‘/’, ‘(‘, ‘)’ and ‘0’ to ‘9’, that represents an Arithmetic Expression in Infix Notation. Your task is to evaluate this Arithmetic Expression.

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

Try solving now

2. Remove Duplicates from Sorted Array

Easy
15m average time
85% success
0/40
Asked in companies
WalmartAppleCognizant

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. 


For example:
'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)

Try solving now
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 .

1. System Design Question

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.

2. System Design Question

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.

1. Technical Question

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.

2. System Design Question

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

Skill covered: Programming

Which SQL keyword removes duplicate records from a result set?

Choose another skill to practice
Similar interview experiences
company logo
SWE Intern
2 rounds | 5 problems
Interviewed by Facebook
1132 views
0 comments
0 upvotes
company logo
SDE - Intern
2 rounds | 3 problems
Interviewed by Facebook
1409 views
0 comments
0 upvotes
company logo
SDE - 1
4 rounds | 8 problems
Interviewed by Facebook
766 views
0 comments
0 upvotes
company logo
SDE - 1
4 rounds | 10 problems
Interviewed by Facebook
1068 views
0 comments
0 upvotes
Companies with similar interview experiences
company logo
SDE - 1
5 rounds | 12 problems
Interviewed by Amazon
107832 views
24 comments
0 upvotes
company logo
SDE - 1
4 rounds | 5 problems
Interviewed by Microsoft
52129 views
5 comments
0 upvotes
company logo
SDE - 1
3 rounds | 7 problems
Interviewed by Amazon
32261 views
6 comments
0 upvotes