Facebook Interview Question for SDE1s


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

- KD May 11, 2017 | Flag Reply
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

- KD May 11, 2017 | Flag Reply
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|)

- axg May 11, 2017 | Flag Reply
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];
        }

- Michael.Karn.Ivanov May 11, 2017 | Flag Reply
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;

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;
}

- Alex May 11, 2017 | Flag Reply
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");
        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

- kredible May 20, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More