Facebook Interview Question for SDE1s


Country: United States




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

public static List<string> GetImagesToBuild(Dictionary<string, string> edges)
{
    var roots = edges.Select(x => x.Key)
        .Where(x => !edges.Values.Contains(x))
        .ToList();

    var result = new List<string>();

    foreach (var root in roots)
    {
        // check for cycle
        string curr = root;
        var visited = new HashSet<string>();
        var sequence = new List<string>();

        for (;;)
        {
            string next;

            if (!edges.TryGetValue(curr, out next))
            {
                // no cycle!
                sequence.Reverse();
                result.AddRange(sequence);
                break;
            }
            else if (!visited.Add(next))
            {
                // cycle
                break;
            }

            sequence.Add(curr);
            curr = next;
        }
    }


    // first find the start node -- can't be in a cycle
    return result;
}

- gw August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Why not just do a topological sort using the standard "start with a vertex with no ancestors, remove it from the graph, continue" algorithm? Then you're done when there are no ancestor-free vertexes; all of the other vertexes participate in a cycle, right?

- sar September 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Parse the input
- Build a directed graph ( which might have cycles )
- Figure out the start node
- Transverse from the start node until null next while printing the node value

In code here is a sample implementation:

function Node(val, next, parent) {
  this.val = val;
  this.next = next;
  this.parent = parent;
}

function buildGraphFromInput(input) {
  var instanceMap = {};
  for(var i = 0; i < input.length; ++i) {
    var entry = input[i];
    var image = entry[0];
    var dep = entry[1];
    
    var node = instanceMap[image] || new Node(image);
    var next = instanceMap[dep] || new Node(dep);
    node.next = next;
    next.parent = node;
    
    instanceMap[image] = node;
    instanceMap[dep] = next;
  }
  return instanceMap;
}

function getStartNode(input, instanceMap) {
  var isVisited = {};
  for(var i = 0; i < input.length; ++i) {
    var image = input[i][0];
    var node = instanceMap[image];
    if (!isVisited[node.val]) {
      var ancestor = getAncestorIfNoCycle(node, isVisited);
      if (ancestor) {
        return ancestor;
      }
    }
  }
  return null;
}

function getAncestorIfNoCycle(node, isVisited) {
  var rootParent = getAncestor(node);
  var current = rootParent;
  while(current) {
    if (!isVisited[current.val]) {
      isVisited[current.val] = true;
      current = current.next; 
    }else {
      //cycle
      return null;
    }
  }
  return rootParent;
}

function getAncestor(node) {
  var seen = {};
  while(!seen[node.val] && node.parent) {
    seen[node.val] = true;
    node = node.parent;
  }
  return node;
}


function getExecutionOrder(node) {
  var result = [];
  while(node) {
    result.unshift( node.val );
    node = node.next;
  }
  return result;
}

var inputWithCycle = [
  ['b','c'],
  ['c','d'],
  ['a','b'],
  ['d','e'],
  ['e','c'],
  ['f','g']
];
var inputWithCycle2 = [
  ['python', 'numpy'],
  ['numpy', 'python'],
  ['tenstorflow', 'ubuntu']
];

var inputWithoutCycle = [
  ['master','ubuntu'],
  ['numpy', 'master'],
  ['tensorflow', 'numpy']
];

var test = [inputWithoutCycle, inputWithCycle, inputWithCycle2]
test.forEach(function(input, testNumber){
  var instanceGraph = buildGraphFromInput( input );
  var startNode = getStartNode(input, instanceGraph );
  var result = getExecutionOrder( startNode );
  console.log('testNumber: ' + testNumber + ' = ' + result.join('<-'));
});

Outputs:

"testNumber: 0 = ubuntu<-master<-numpy<-tensorflow"
"testNumber: 1 = g<-f"
"testNumber: 2 = ubuntu<-tenstorflow"

JSBin: jsbin.com/zaqehej/1/edit?js,console

- tnutty2k8 August 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import networkx as nx

""" For each tuple (a, b) in the input add nodes 'a' and 'b' and an edge
(b, a) to the directed graph. Next, do a toplogical sort on the graph 
after removal of cycles  ( and the edges that form the cycle)
"""
g = nx.DiGraph()
# example 1
# deps =[['master', 'ubuntu'], ['numpy', 'master'], ['tensorflow', 'numpy']]
# example 2
#deps = [ ['p', 'n'], ['n', 'p'], ['t', 'u']]
# example 3
deps = [['b', 'c'], ['c', 'd'], ['a', 'b'], ['d', 'e'], ['e', 'c'], ['f', 'g']]

for dep in deps:
    g.add_edge(dep[1], dep[0])
try:
    cycle = nx.find_cycle(g)
    nodes = set()
    for edge in cycle:
        nodes = nodes | {edge[0]}
        nodes = nodes | {edge[1]}
    for n in nodes:
        g.remove_node(n)
except:
    print('error')
finally:
    pass

ordering = nx.topological_sort(g)
print(ordering)

- Makarand August 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this a phone screen or on-site ?

As for the problem,
1. Remove back edges (cycles) using DFS
2. Topologically sort the graph

- Himesh August 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void parseInput(String[][] imagePrereqs,
                       Map<String, List<String>> imageToDependencies,
                       Map<String, Integer> imageToPrereqCount,
                       Set<String> images) {
    
    for(int i = 0; i < imagePrereqs.length; ++i) {
        String image = imagePrereqs[i][0];
        String prereqImage = imagePrereqs[i][1];
        
        images.add(prereqImage);
        
        imageToPrereqCount.put(image, imageToPrereqCount.getOrDefault(image, 0) + 1);
        
        imageToDependencies.putIfAbsent(prereqImage, new ArrayList<>());
        imageToDependencies.get(prereqImage).add(image);
    }
}

static void getIndependentImages(Queue<String> queue, Set<String> images,
                                 Map<String, Integer> imageToPrereqCount) {
    for(String image : images) {
        if(!imageToPrereqCount.containsKey(image)) {
            queue.add(image);
        }
    }
}

static List<String> topologicalSort(String[][] imagePrereqs) {
    Map<String, List<String>> imageToDependencies = new HashMap<>();
    Map<String, Integer> imageToPrereqCount = new HashMap<>();
    Set<String> images = new HashSet<>();
    parseInput(imagePrereqs, imageToDependencies, imageToPrereqCount, images);

    Queue<String> queue = new ArrayDeque<>();
    getIndependentImages(queue, images, imageToPrereqCount);

    List<String> imageOrdering = new ArrayList<>();
    while(!queue.isEmpty()) {
        String image = queue.remove();
        imageOrdering.add(image);
        if(!imageToDependencies.containsKey(image)) {
            continue;
        }
        for(String dependency : imageToDependencies.get(image)) {
            int newPrereqCount = imageToPrereqCount.get(dependency) - 1;
            if(newPrereqCount == 0) {
                queue.add(dependency);
                imageToPrereqCount.remove(dependency);
            } else {
                imageToPrereqCount.put(dependency, newPrereqCount);
            }
        }
    }

    return imageOrdering;
}

- abcdefg August 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'd do a BFS to do topological sort and cycle detection. When I detect a cycle I delete the whole BFS tree I'm in and mark the modules as not buildable. When ever the BFS reaches a not buildable module it does the same as when it had entered the cycle directly (because it wouldn't further explore, I have the buildable flag)

Why ever the samples don't mention the last dependency, I print it as well.

e.g. master -> tensorflow -> numphy -> ubuntu

@majia: does FB meanwhile use TF?

#include <unordered_map>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

struct Module {
	string module_; // name of the module
	Module* parent_ = nullptr; // parent from DFS traversal tree
	bool buildable_ = true; // can be built
	size_t enter_ = 0; // DFS enter
	size_t leave_ = 0; // DFS leave
	vector<Module*> adj_; // dependencies
};

struct DFSStackItem {
	Module* module_;
	bool visited_;
	Module* parent_;	
};

void printBuildOrder(const vector<pair<string, string>>& dependencies)
{
	// 1. create adjacency list rep for graph
	unordered_map<string, Module> moduleDep;
	for (auto& dep : dependencies) {
		moduleDep[dep.first].module_ = dep.first;
		moduleDep[dep.second].module_ = dep.second;
		moduleDep[dep.first].adj_.push_back(&moduleDep[dep.second]);
	}

	// 2. perform dfs from each item, store departure time 
	size_t time = 1;
	for (auto moduleIt = moduleDep.begin(); moduleIt != moduleDep.end(); ++moduleIt) {
		if (moduleIt->second.enter_ != 0) continue;
		stack<DFSStackItem> stk({ {&moduleIt->second, false, nullptr} });
		while (!stk.empty()) {
			auto u = stk.top().module_;
			if (stk.top().visited_) {
				stk.pop();
				if (u->leave_ == 0) {
					u->leave_ = time++;
				}
			} else {
				if (!u->buildable_ ||
					(u->enter_ > 0 && u->leave_ == 0)) {
					// cycle or not buildable
					u->buildable_ = false;
					u = stk.top().parent_;
					stk.pop();
					while (u != nullptr) {
						u->buildable_ = false;
						u = u->parent_;
					}
				} else {
					stk.top().visited_ = true; // entered
					u->parent_ = stk.top().parent_; // visited from
					u->enter_ = time++;
					for (Module* v : u->adj_) {
						stk.push(DFSStackItem{ v, false, u });
					}
				}
			}
		}
	}

	// copy buildable Module into modules array
	vector<Module*> modules;
	for (auto& m : moduleDep) {
		if (m.second.buildable_) {
			modules.push_back(&m.second);
		}
	}
	// topological sort
	sort(modules.begin(), modules.end(), 
		[](Module* a, Module* b) { return a->leave_ > b->leave_; });
	// print
	for (Module* m : modules) {
		cout << m->module_ << " ";
	}
	cout << endl; 
}


int main()
{
	printBuildOrder({ { "master", "ubuntu" },{ "numpy", "master" },{ "tensorflow", "numpy" } });
	printBuildOrder({ { "python", "numpy" },{ "numpy", "python" },{ "tensorflow", "ubuntu" } });
	printBuildOrder({ { "b", "c" },{ "c", "d" },{ "a", "b" },{ "d", "e" },{ "e","c" },{ "f", "g" } });
}

- Chris August 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We use Topological sorting here:

#include <stdio.h>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <string.h>
#include <queue>
#include <functional>

struct N {
    enum eState { kNone, kTemp, kPerm };
    eState marker;
    std::string name;
    std::vector<N*> adjacents;
    N()
        : marker(kNone)
    {
    }
};

static std::unordered_map<std::string, N> G; // The graph
static std::vector<N*> L; // Contains the result

static N* GetNodeCreateIfNeeded(const std::string& name)
{
    if(G.count(name) == 0) {
        N node;
        node.name = name;
        G[name] = node;
    }
    return &G[name];
}

void Visit(N* node)
{
    if(node->marker == N::kPerm) return;
    if(node->marker == N::kTemp) throw std::string("Loop found!");
    node->marker = N::kTemp;
    std::for_each(node->adjacents.begin(), node->adjacents.end(), [&](N* adj) { Visit(adj); });
    node->marker = N::kPerm;
    L.insert(L.begin(), node);
}

void TopoSort(const std::vector<std::pair<std::string, std::string> >& items)
{
    L.clear();
    G.clear();
    std::for_each(items.begin(), items.end(), [&](const std::pair<std::string, std::string>& p) {
        N* node = GetNodeCreateIfNeeded(p.first);        // PluginSDK
        N* dependency = GetNodeCreateIfNeeded(p.second); // libCodeLite
        dependency->adjacents.push_back(node);
    });

    try {
        std::for_each(G.begin(), G.end(), [&](std::unordered_map<std::string, N>::value_type& vt) {
            if(vt.second.marker == N::kNone) {
                Visit(&(vt.second));
            }
        });
    } catch(std::string& e) {
        std::cout << "Error: " << e.c_str() << std::endl;
    }
    
    // Print the build order
    std::for_each(L.begin(), L.end(), [&](N* node) { std::cout << node->name << std::endl; });
}

int main(int argc, char** argv)
{
    //    std::vector<int> numbers = { 48, 20, 1, 3, 4, 6, 9, 24, 7, 8 };
    //    // std::sort(numbers.begin(), numbers.end(), [](int a, int b) { return a > b; });
    //    int minArrSize = getNumbers(numbers);
    //    std::cout << "The best match leaving us with an array of size: " << minArrSize << std::endl;
    //    return 0;

    // calculate_steps(10, 20, { { 5, 3 }, { 4, 3 }, { 7, 11 } }, { { 7, 19 }, { 4, 4 }, { 5, 5 }, { 3, 9 } }, { 8, 17
    // });
    TopoSort({ { "master", "ubuntu" }, { "numpy", "master" }, { "tensorflow", "numpy" } });
    TopoSort({ { "python", "numpy" }, { "numpy", "python" }, { "tensorflow", "ubuntu" } });
    return 0;
}

And the output:

ubuntu
master
numpy
tensorflow
Error: Loop found!
ubuntu
tensorflow

- PenChief September 09, 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