Facebook Interview Question
SDE1sCountry: United States
- 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
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)
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;
}
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" } });
}
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
- gw August 31, 2017