## Facebook Interview Question for SDE1s

• 0

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not understanding the question. Is following calculation correct ? it can't be this simple but just checking.

A = 0.02C (A has 2% of C)
B = 0.05C (B has 2% of C)
A = 0.1B (A has 10% of B)

A = 0.1B + 0.02C (total A has shares)
A = 0.1(0.05)C + 0.02C
A = (0.025)C

2.5% of C

Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not able to understand the question clearly but can I any one check if following calculation is correct? It can't be this simple but just wondering what else.

A = 0.02C (A has 2% of C)
B = 0.05C (B has 2% of C)
A = 0.1B (A has 10% of B)

A = 0.1B + 0.02C (total A has shares)
A = 0.1(0.05)C + 0.02C
A = (0.025)C

2.5% of C

Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming no cyclic ownership exists.
1. Topological sort the graph (from source company to destination company)
2. Now in the topological order calculate ownership as follows
own[B] += own[A] * weight(A, B)/100;
3. return own[C]

Time complexity O(|V| + |E|)
Space Complexity: O(|V|)

Comment hidden because of low score. Click to expand.
0
of 0 vote

the idea is that each depth-path contributes to total ownership, so we run DFS, and each time we reach final destination, we add value which is multiplication of weights of all edges in the path. For example

Start - (0.8) - B - (0.7) - C -(0,5)- Destination
\--(0.4)- E -(0.3)-/
will give us 0.8 * 0.7 * 0.5 + 0.8 * 0.4 * 0.3 of result

``````public static float getStockAmount(Dictionary<string, Dictionary<string, float>> stocks, string owner, string of)
{
var dej = new Dictionary<string, float>();
foreach (var key in stocks.Keys) dej.Add(key, 0);
dej[owner] = 1;
var stack = new Stack<String>();
// we run all possible DFS here
stack.Push(owner);
while (stack.Count > 0)
{
var current = stack.Pop();
var value = dej[current];
foreach (var child in stocks[current].Keys)
{
if (child == of)
// for destination we sum up values
dej[child] += (stocks[current][child] * value);
else
dej[child] = (stocks[current][child] * value);
stack.Push(child);
}
}
return dej[of];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming the graph is acyclic, we can find all paths from the source company to the target company. For each path we find a share, going through the path backward and applying the share percentage. Then, we sum the shares of the paths.

``````#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Node;

public:
double share_;
{
share_ = share;
}
};

class Node {
public:
Node(char name)
{
name_ = name;
}
{
}
char name_;
};

class Graph {
public:
~Graph()
{
for (auto n : nodes_) {
delete n;
}
}
{
Node *n1 = GetNode(name1);
Node *n2 = GetNode(name2);
}
Node *GetNode(char name)
{
auto it = name_to_node_.find(name);
if (it != name_to_node_.end()) {
return it->second;
}
Node *n = new Node(name);
nodes_.push_back(n);
name_to_node_[name] = n;
return n;
}
vector<Node *> nodes_;
private:
unordered_map<char, Node *> name_to_node_;
};

vector<vector<Link>> AllPaths(Graph &g, Node *source, Node *target)
{
class StackEntry {
public:
int offset_;
};
vector<StackEntry> st;
while (!st.empty()) {
StackEntry e = st.back();
st.pop_back();
if (n) {
if (n == target) {
for (int i = st.size() - 1; i > 0; --i) {
}
paths.push_back(path);
} else if (e.offset_ < n->links_.size()) {
}
}
}
return paths;
}

int main()
{
Graph g;

vector<vector<Link>> paths = AllPaths(g, g.GetNode('A'), g.GetNode('C'));

double share = 0;
for (auto const &path : paths) {
double path_share = 100;
for (auto const &link : path) {
}
share += path_share;
}
cout << share << "\n";

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ShareHoldingGraph {

public static void main(String[] args) {
Company companyA = new Company("A");
Company companyB = new Company("B");
Company companyC = new Company("C");
List<Company> companyList = Arrays.asList(companyA, companyB, companyC);

System.out.println("CompanyA -> C " + companyA.getPercentage(companyC));
clearVisisted(companyList);
System.out.println("CompanyB -> C " + companyB.getPercentage(companyC));
clearVisisted(companyList);
System.out.println("CompanyA -> B " + companyA.getPercentage(companyB));
}

private static void clearVisisted(List<Company> companyList) {
for(Company company : companyList)
company.visited = false;
}

private static class Company {
String name;
List<Share> shares = new ArrayList<>();
boolean visited;
Company(String name) {
this.name = name;
}

double getPercentage(Company company) {
if (this == company)
return 100;

if (visited)
return 0;

this.visited = true;
double totalShares = 0;
for(Share share : shares) {
if (share.company == company)
totalShares += share.percentage;
else
totalShares += share.company.getPercentage(company) * (share.percentage/100);
}
}
}

private static class Share {
Company company;
double percentage;

Share(Company company, double percentage) {
this.company = company;
this.percentage = percentage;
}
}
}``````

Prints:

``````CompanyA -> C 2.5
CompanyB -> C 5.0
CompanyA -> B 10.0``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.