Facebook Interview Question
SDE1sCountry: United States
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
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];
}
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;
class Link {
public:
Node *adjacent_node_;
double share_;
Link(Node *adjacent_node, double share)
{
adjacent_node_ = adjacent_node;
share_ = share;
}
};
class Node {
public:
Node(char name)
{
name_ = name;
}
void AddLink(Node *adjacent_node, double share)
{
links_.push_back(Link(adjacent_node, share));
}
char name_;
vector<Link> links_;
};
class Graph {
public:
~Graph()
{
for (auto n : nodes_) {
delete n;
}
}
void AddLink(char name1, char name2, double share)
{
Node *n1 = GetNode(name1);
Node *n2 = GetNode(name2);
n1->AddLink(n2, share);
}
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:
StackEntry(Link link, int offset) : link_(link), offset_(offset) {};
Link link_;
int offset_;
};
vector<vector<Link>> paths;
vector<StackEntry> st;
Link start_link(source, 0);
st.push_back(StackEntry(start_link, 0));
while (!st.empty()) {
StackEntry e = st.back();
st.pop_back();
Node *n = e.link_.adjacent_node_;
if (n) {
if (n == target) {
vector<Link> path{e.link_};
for (int i = st.size() - 1; i > 0; --i) {
path.push_back(st[i].link_);
}
paths.push_back(path);
} else if (e.offset_ < n->links_.size()) {
st.push_back(StackEntry(e.link_, e.offset_ + 1));
st.push_back(StackEntry(n->links_[e.offset_], 0));
}
}
}
return paths;
}
int main()
{
Graph g;
g.AddLink('A', 'B', 10);
g.AddLink('A', 'C', 2);
g.AddLink('B', 'C', 5);
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) {
path_share *= link.share_ / 100.0;
}
share += path_share;
}
cout << share << "\n";
return 0;
}
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");
companyA.shares.add(new Share(companyB, 10));
companyA.shares.add(new Share(companyC, 2));
companyB.shares.add(new Share(companyC, 5));
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);
}
return totalShares;
}
}
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
I am not understanding the question. Is following calculation correct ? it can't be this simple but just checking.
- KD May 11, 2017A = 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