Google Interview Question
SDE1sCountry: United States
I assume:
- jobs are identified using an integer
- I get dependencies in the form of pairs (a, b) and the set of all a and all b
unioned gives me the set of all jobs.
- Semantics of the directed edge (a,b) is: in order to start b, a must be completed
- The dependencies form a DAG, no need to check for cycles
- you can call get_next_stage anytime and you will get the set of jobs that can
be started due to the calls of job_done since the last call of get_next_stage
(maybe a better name would be get_unlocked_jobs)
- you can only compete jobs that get_nextStage returned
- you can't complete a job twice
#include <vector>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;
ostream& operator <<(ostream& os, const vector<int>& v);
class JobScheduler
{
private:
unordered_map<int, unordered_set<int>> adjList_; // jobid -> list of dependent jobids
unordered_map<int, int> incidentDeg_; // job, in-degree, jobs that have
// in-degree 0 and are done are removed from HT
vector<int> nextStage_;
public:
JobScheduler(const vector<pair<int, int>>& deps) {
for (auto dep : deps) {
incidentDeg_[dep.first] += 0; // ensure they're in, don't change
if (adjList_[dep.first].insert(dep.second).second) {
incidentDeg_[dep.second]++; // skip dublicate dependencies
}
}
for (auto indeg : incidentDeg_) {
if (indeg.second == 0) {
nextStage_.push_back(indeg.first);
}
}
}
vector<int> get_nextStage() {
vector<int> res(move(nextStage_)); // clears nextStage_
return res;
}
void jobDone(int jobId) {
auto it = incidentDeg_.find(jobId);
if (it == incidentDeg_.end() || it->second != 0) throw "error"; // see assumptions
incidentDeg_.erase(it); //
for (auto next : adjList_[jobId]) {
if (--incidentDeg_[next] == 0) {
nextStage_.push_back(next);
}
}
}
};
int main()
{
JobScheduler s({
{1, 2},
{5, 2},
{2, 3},
{1, 2}, // dublicate dependency
{3, 4},
{4, 9},
{7, 4},
{2, 7},
{2, 4}, // redundant 2, 3 -> 3, 4
{2, 8} });
cout << s.get_nextStage() << endl; // {1, 5}
s.jobDone(1);
cout << s.get_nextStage() << endl; // {}
s.jobDone(5);
cout << s.get_nextStage() << endl; // {2}
s.jobDone(2);
cout << s.get_nextStage() << endl; // {8, 3, 7}
s.jobDone(8);
cout << s.get_nextStage() << endl; // {}
s.jobDone(3);
cout << s.get_nextStage() << endl; // {}
s.jobDone(7);
cout << s.get_nextStage() << endl; // {4}
s.jobDone(4);
cout << s.get_nextStage() << endl; // {9}
s.jobDone(9);
cout << s.get_nextStage() << endl; // {}
}
ostream& operator <<(ostream& os, const vector<int>& v)
{
os << "{";
bool first = true;
for (auto e : v) {
if (!first) os << "," << e;
else os << e;
first = false;
}
os << "}";
return os;
}
def get_next_stage(jobs, node):
if jobs is None: return []
if node is None: return []
return [v for k,v in jobs if k==node]
def job_done(jobs, node):
if jobs is None: return False
if node is None: return False
if len(get_next_stage(jobs, node)) == 0:
return True
return False
a = 'a'
b = 'b'
c = 'c'
d = 'd'
jobs = {(a,b), (a,c), (b,d)}
print(get_next_stage(jobs, a))
print(job_done(jobs, d))
Using topological sort.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Job {
public:
Job(char id)
{
id_ = id;
}
void AddDependentJob(Job *job)
{
children_.push_back(job);
}
char id_;
vector<Job *> children_;
};
class Dispatcher {
public:
Dispatcher(vector<Job *> const &jobs)
{
for (Job *j : jobs) {
for (Job *to_job : j->children_) {
++inbound_[to_job];
}
candidates_.insert(j);
}
}
vector<Job *> GetNextStageJobs()
{
for (Job *j : candidates_) {
if (inbound_[j] == 0) {
next_stage_jobs_.insert(j);
}
}
candidates_.clear();
return vector<Job *>(next_stage_jobs_.begin(), next_stage_jobs_.end());
}
void JobDone(Job *j)
{
next_stage_jobs_.erase(j);
for (Job *to_job : j->children_) {
--inbound_[to_job];
candidates_.insert(to_job);
}
}
private:
unordered_map<Job *, int> inbound_;
unordered_set<Job *> next_stage_jobs_, candidates_;
};
int main()
{
Job a('A'), b('B'), c('C'), d('D');
a.AddDependentJob(&b);
a.AddDependentJob(&c);
b.AddDependentJob(&d);
Dispatcher dis({&c, &b, &a, &d});
while (true) {
auto jobs = dis.GetNextStageJobs();
if (jobs.empty()) {
break;
}
for (Job *j : jobs) {
cout << "doing " << j->id_ << "\n";
dis.JobDone(j);
}
cout << "---\n";
}
}
@Masiur. Why not. E.g. to assemble a car (D) we need a door (B) ready and a coil of electrical wires (A) ready. Wires are used in the car and in the door. So, it's A->B, B->D, A->D. We are Ok as long as there are no cycles in the graph.
- Alex November 30, 2017