## Facebook Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

I am not sure this optimal or not,
1) we can construct graph from list of routes
2) then use Dijkstra's algorithm when he hit end, we stop the algorithm as Dikstra's gives shortest distance from start to all vertices but we just need till end here,
May be there is much easier way than what I wrote here :)

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

// Shortest-FlightRoute.cpp : Defines the entry point for the console application.
//Framed the graph with city names. added all the edges with time as the weigth of the edge.
//starting from the starting source city, run dfs. it will compute shorts paths to all destinations
//then return the shortest path to the destination city

#include "stdafx.h"
#include <unordered_map>
#include <vector>
#include <string>
#include <queue>

using namespace std;
struct dstwt
{
string point;
int time;
};
class Graph
{
vector<string> destinations;
public:
Graph(const vector<string>& destinations);
void AddEdge(string src, string dst, int time);
int SP(string src, string dst);
};

Graph::Graph(const vector<string>& dests)
{
for (auto dest : dests)
destinations.push_back(dest);
}

void Graph::AddEdge(string src, string dst, int time)
{
{
}
else
{
}

{
adj[dst] = { { src,time } };
}
else
{
}
}

int Graph::SP(string src, string dst)
{
unordered_map<string, dstwt> distances;
for (auto dest : destinations)
{
distances[dest] = { {},9999 };
}
//set the starting point as 0
distances[src] = { {},0 };

auto comparefn = [](const dstwt& lhs, const dstwt& rhs) {return lhs.time > rhs.time; };

priority_queue<dstwt, vector<dstwt>, decltype(comparefn)> min_heap(comparefn);
min_heap.push({ src,0 });

while (!min_heap.empty())
{
auto u = min_heap.top();
min_heap.pop();
{
string v = c.point;
int time = c.time;
if (distances[v].time > distances[u.point].time + time)
{
distances[v].time = distances[u.point].time + time;
min_heap.push({ v,distances[u.point].time + time });
}
}
}

return distances[dst].time;

}

int main()
{
Graph g({ "sea","sfo","la","ord","nyc","dfw" });
int result = g.SP("sea", "ord");
return 0;
}

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

``````// Shortest-FlightRoute.cpp : Defines the entry point for the console application.
//Framed the graph with city names. added all the edges with time as the weigth of the edge.
//starting from the starting source city, run dfs. it will compute shorts paths to all destinations
//then return the shortest path to the destination city

#include "stdafx.h"
#include <unordered_map>
#include <vector>
#include <string>
#include <queue>

using namespace std;
struct dstwt
{
string point;
int time;
};
class Graph
{
vector<string> destinations;
public:
Graph(const vector<string>& destinations);
void AddEdge(string src, string dst, int time);
int SP(string src, string dst);
};

Graph::Graph(const vector<string>& dests)
{
for (auto dest : dests)
destinations.push_back(dest);
}

void Graph::AddEdge(string src, string dst, int time)
{
{
}
else
{
}

{
adj[dst] = { { src,time } };
}
else
{
}
}

int Graph::SP(string src, string dst)
{
unordered_map<string, dstwt> distances;
for (auto dest : destinations)
{
distances[dest] = { {},9999 };
}
//set the starting point as 0
distances[src] = { {},0 };

auto comparefn = [](const dstwt& lhs, const dstwt& rhs) {return lhs.time > rhs.time; };

priority_queue<dstwt, vector<dstwt>, decltype(comparefn)> min_heap(comparefn);
min_heap.push({ src,0 });

while (!min_heap.empty())
{
auto u = min_heap.top();
min_heap.pop();
{
string v = c.point;
int time = c.time;
if (distances[v].time > distances[u.point].time + time)
{
distances[v].time = distances[u.point].time + time;
min_heap.push({ v,distances[u.point].time + time });
}
}
}

return distances[dst].time;

}

int main()
{
Graph g({ "sea","sfo","la","ord","nyc","dfw" });
int result = g.SP("sea", "ord");
return 0;
}``````

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

``````function findShortestPath(start, end, routes)
{
getRoutesFrom = function(start)
{
return this.routes.filter(function(item){ return (item.from == start)});
};
this.VisitedRoutes = [];
this.routes = routes;
this.allRoutes = [];
findRoute = function(routeSoFar, totalTime, currentPlace, destination)
{
var localRoutes = routeSoFar.slice();
localRoutes.push(currentPlace);
this.VisitedRoutes.push(currentPlace);
if (currentPlace==destination)
this.allRoutes.push({'Path': localRoutes, 'timeTaken': totalTime});
else
{
var outgoingRoutes = getRoutesFrom(currentPlace);
for(var i=0; i<outgoingRoutes.length; i++)
{
if (VisitedRoutes.indexOf(outgoingRoutes[i].end) < 0)
findRoute(localRoutes, totalTime+outgoingRoutes[i].time, outgoingRoutes[i].to,destination);
}
}
}

findRoute([],0,start,end);
this.allRoutes.sort(function(a,b){return (a.timeTaken - b.timeTaken)});
console.log(this.allRoutes[0]);
}

findShortestPath('A','Z', [{from: 'A', to: 'B', time:24},{from: 'A', to: 'C', time:31},{from: 'B', to: 'Z', time:5},{from: 'C', to: 'D', time:15},{from: 'D', to: 'E', time:21},{from: 'E', to: 'Z', time:10}, {from: 'A', to: 'D', time:6}, {from: 'D', to: 'B', time:9}])``````

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.