SDE - 1

This was one of the most interesting questions I faced in all my campus interviews . I was initially thinking of using recursion and then optimising it through memoisation but there was a risk of getting TLE . I then observed that this question can be transformed into a Topological Sort+DP question where I was required to find the length of the longest chain ending at a particular index . 

Steps :
1) Construct a graph (adjacency list) from the given matrix .
2) For every (i,j) check its 4 directions up,down,left,right .
3) If arr[i+1][j] > arr[i][j] , add a directed graph from (i,j) to (i+1,j).
4) Similarly, perform these steps for the other 3 directions.
5) Also , increment the indegree of the node to which we direct the edge
6) Now, initialise a queue of pair of int . Add all those nodes whose indegree was 0
7) Perform a standard BFS Topo Sort i.e., run a loop till my queue becomes empty and update the dp[node] (which stores the max length of a increasing chain ending at node) .
8) Finally, return the max value of dp[node] for all nodes.

It seems that Facebook loves Graph questions . This was also a Graph question particularly related to Bellman Ford Algorithm .

Steps :
1) Initiliase a DP array with all INT_MAX , where dp[i][j] stores the min distance to reach j from source using atmost i edges.
2) For all i from 0 to k+1 , dp[i][src]=0 as min distance to reach source (src) using any no. of edges is always 0 .
3) Run a loop from 1 to k+1 and then again an inner loop which loops through all the elements of the flights vector .
4) Now , if there is a flight from u to v that costs w then we have the following transiition for dp[i][v] i.e., the min distance to reach v using atmost i edges

If dp[u][i-1]!=INT_MAX , then dp[i][v]=min(dp[i][v] , dp[i-1][u]+w)

5) Finally, return dp[k+1][dist].

The idea is simple: along the path, record all prefix sums in a hash table. For current prefix sum x, check if (x - target)
appears in the hash table.
Steps :
1) We will be using a unordered map which will be filled with various path sum.
2) For every node we will check if current sum and root’s value equal to k or not. If the sum equals to k then
increment the required answer by one.
3) Then we will add all those path sum in map which differs from current sum+root->data value by a constant integer
k.
4) Then we will be inserting the current sum + root->data value in the map.
5) We will recursively check for left and right subtrees of current root
6) After the right subtree is also traversed we will remove the current sum + root->data value from the map so that it
is not taken into consideration in further traversals of other nodes other than the current root’s.
TC : O(n) where n is the total number of nodes in the tree
SC : O(n)

Since the constraints were small , I followed a recursive+backtracking approach for this problem

Approach :
1) Create a recursive function called recur (void recur(vector&arr , vectortmp , int target,int idx) ) which would eventually fill my answer vector with all the possible combination sums for the given target.

2) For every element , I have 2 choices -
2.1) To take that element and decrease my target by arr[idx] and again call the same recursive function 
recur for the remaining target.

2.2) To not take that element and simply call the recursive function for the same target but with an 
updated index idx+1.

3) For every element that we push into tmp , we should also pop it after step 2.1 as we may not end up using that element .

4) As target==0, push the tmp vector into my answer vector and simply return from the function 

5) One more base case : If idx>arr.size() or target<0 or (idx==n and target>0) , simply return from the function.


TC : O(2^n) where n=size of vector arr
SC : O(target)

My Interviewer took some time in explaining this problem to me as the problem statement of this question was quite long and complicated . After thoroughly understanding the question , my first observation was to apply DFS and solve this problem but some time later the thought of using Disjoint Set Union or DSU crossed my mind and then I was sure to implement my idea using DSU .

Approach :

1) Traverse over each account, and for each account, traverse over all of its emails. If we see an email for the first time, then set the group of the email as the index of the current account in emailGroup .

2) Otherwise, if the email has already been seen in another account, then we will union the current group (i) and the group the current email belongs to (emailGroup[email]).

3) After traversing over every account and merging the accounts that share a common email, we will now traverse over every email once more. Each email will be added to a map (components) where the key is the email's representative, and the value is a list of emails with that representative.

4) Traverse over components, here the keys are the group indices and the value is the list of emails belonging to this group (person). Since the emails must be "in sorted order" we will sort the list of emails for each group. Lastly, we can get the account name using the accountList[group][0]. In accordance with the instructions, we will insert this name at the beginning of the email list.

5) Store the list created in step 4 in our final result (mergedAccount).

TC : O(N*K*log(N*K)) where N is the number of accounts and K is the maximum length of an account.
SC : O(N*K)

This was a preety standard question and I had already solved it in platforms like LeetCode and CodeStudio so coding it was not so difficult for me . I first explained my intuition and approach to the interviewer and after that started coding it in my machine . After coding , we discussed its Time and Space Complexity . 

Approach :

The two key observations are:

1) Preorder traversal follows Root -> Left -> Right, therefore, given the preorder array preorder, we have easy access to the root which is preorder[0].

2) Inorder traversal follows Left -> Root -> Right, therefore if we know the position of Root, we can recursively split the entire array into two subtrees.

Steps :

1) Build a hashmap to record the relation of value -> index for inorder, so that we can find the position of root in constant time.
2) Initialize an integer variable preorderIndex to keep track of the element that will be used to construct the root.
3) Implement the recursion function arrayToTree which takes a range of inorder and returns the constructed binary tree:
3.1) if the range is empty, return null;
3.2) initialize the root with preorder[preorderIndex] and then increment preorderIndex;
3.3) recursively use the left and right portions of inorder to construct the left and right subtrees.
4) Simply call the recursion function with the entire range of inorder.

TC : O(N) where N=size of the input array
SC : O(N)

Demand paging is a method that loads pages into memory on demand. This method is mostly used in virtual memory.

In this, a page is only brought into memory when a location on that particular page is referenced during execution.

The following steps are generally followed:
1) Attempt to access the page.
2) If the page is valid (in memory) then continue processing instructions as normal.
3) If a page is invalid then a page-fault trap occurs.
4) Check if the memory reference is a valid reference to a location on secondary memory. If not, the process is terminated (illegal memory access). Otherwise, we have to page in the required page.
5) Schedule disk operation to read the desired page into main memory.
6) Restart the instruction that was interrupted by the operating system trap.

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.

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.

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.