Google Interview Question for SDE1s


Country: United States




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

@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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

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))

- rz November 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can there be a situation A->B, A->C, B->D, A->D, i.e D can be done if both A and B are done?

- Masiur November 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Alex November 30, 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