John
BAN USER- 0of 0 votes
AnswersGiven the interface below, implement a task scheduler.
interface Task { void Run(); Set<Task> GetDependencies(); }
Additionally, the task scheduler should follow two rules.
- John in United States
1. Each task may only be executed once.
2. The dependencies of a task should be executed before the task itself.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm
The solution, any solution, to this problem will only work on a DAG. It is true that the current answers don't take into account that the input could contain cycles and would thus fail horribly on such inputs.
The running time is O(V + E), which for unfortunate choices of sets could lead to weak performance. But I fail to see the O(n!) runtime complexity, please follow up by giving an example set.
This set:
{t5, t4, t3, t2, t1}
t5 -> {}
t4 -> {t5}
t3 -> {t4, t5}
t2 -> {t3, t4, t5}
t1 -> {t2, t3, t4, t5}
Will consider all edges of all vertices, but it will still execute each vertex and it's dependencies only once. Even if we only consider the number of visits it shouldn't even come close to O(n!).
Original code (flawed):
void mark_tasks(vec_task_t & tasks) {
for (Task * t : tasks) {
mark_map_t::iterator it;
if ((it = mark_map.find(t)) == mark_map.end()) {
mark_map.insert({ t, 0 });
} else {
it->second++;
}
mark_tasks(t->getDependencies());
}
}
Improved code:
void mark_tasks(vec_task_t & tasks, vec_task_t::size_type d = 0) {
for (Task * t : tasks) {
mark_map_t::iterator it;
if ((it = mark_map.find(t)) == mark_map.end()) {
mark_map.insert({ t, d });
} else {
it->second += d;
}
mark_tasks(t->getDependencies(), d+1);
}
}
Even slightly more optimized (doesn't traverse dependencies if parent count didn't increase, counter grows slower):
void mark_tasks(vec_task_t & tasks, vec_task_t::size_type d = 1) {
for (Task * t : tasks) {
mark_map_t::iterator it;
if ((it = mark_map.find(t)) == mark_map.end()) {
it = mark_map.insert({ t, 0 }).first;
}
if (it->second < d) {
it->second = d;
mark_tasks(t->getDependencies(), d+1);
}
}
}
You're absolutely right, there's an issue with the way the algorithm increments the counts. I'll update my answer with a fix.
To be honest, during my interview I took a completely different approach, which was a simple extension of the initial algorithm relying on concurrent sets and latches.
This one's a little bit more tricky, let's start out with the same C++ abstract class as before.
class Task {
public:
virtual void run() = 0;
virtual vector<Task *> & getDependencies() = 0;
};
And the original solution to this problem:
class TaskScheduler {
using vec_task_t = vector<Task *>; // Input
using mark_set_t = unordered_set<Task *>; // Hash set of task
mark_set_t marked_tasks;
public:
void runTasks(vec_task_t & tasks) {
for (Task * t : tasks) {
if (marked_tasks.find(t) == marked_tasks.end()) {
runTasks(t->getDependencies());
t->run();
marked_tasks.insert(t);
}
}
}
};
Now the tricky thing is of course that you can't just slab a thread on the run call and be done. You have to take into account that all dependencies should be executed first. That's not an issue at all actually, but it requires you to generalize the marked set to something that can be used to identify the ordering of tasks based upon their rate of dependency.
The set allows the property task -> bool or task -> [0, 1]. A map however allows the property task -> [0, n].
A map would need to be used instead of the set to get a dependency count. Use a hash map (unordered_map), because it allows relatively fast lookup.
However, this map doesn't allow ordering. To order the tasks by their dependency count you could use a multimap, which allows multiple values for the same key. This is necessary because you could have tasks with the same dependency count. For example, a set of tasks with no dependencies will have the same dependency count.
After ordering the tasks you can batch them up by executing same-keyed tasks in parallel and awaiting their completion, which takes as long as the longest running task for that dependency count. Starting with the highest key you'll execute all tasks which have no dependencies and are the most depended upon. Key 0 will map to tasks that are never depended upon.
class TaskScheduler {
using vec_task_t = vector<Task *>; // Input
using mark_map_t = unordered_map<Task *, vec_task_t::size_type>; // Uniquely keyed hash map of task -> dependency count
using order_map_t = multimap<vec_task_t::size_type, Task *, greater<vec_task_t::size_type>>; // Descending order non-uniquely keyed map of dependency count -> task
mark_map_t mark_map;
order_map_t order_map;
// O(N) where N = tasks in input.
void mark_tasks(vec_task_t & tasks, vec_task_t::size_type d = 1) {
for (Task * t : tasks) {
mark_map_t::iterator it;
if ((it = mark_map.find(t)) == mark_map.end()) {
it = mark_map.insert({ t, 0 }).first;
}
if (it->second < d) {
it->second = d;
mark_tasks(t->getDependencies(), d+1);
}
}
}
// O(K*log(K)) where K = unique tasks in input.
void order_tasks() {
for (auto & e : mark_map) {
order_map.insert({e.second, e.first});
}
}
// Run tasks between two iterators in parallel and await their completion.
void runParallel(order_map_t::iterator front, order_map_t::iterator back) {
std::vector<std::thread> threads;
while (front != back) {
threads.push_back(thread([](Task * task){
task->run();
}, front->second));
++front;
}
for (auto & t : threads) {
t.join();
}
}
public:
// Mark and order tasks in O(N + K*log(K)).
// Execute same-keyed tasks in parallel and await completion before executing next set of same-keyed tasks.
void runTasks(vec_task_t & tasks) {
mark_tasks(tasks);
order_tasks();
auto it = order_map.begin();
// Run same-keyed tasks in parallel blocks.
while (it != order_map.end()) {
auto front = it;
auto back = order_map.upper_bound(it->first);
runParallel(front, back);
it = back;
}
}
};
This one's a little bit more tricky, let's start out with the same C++ abstract class as before.
class Task {
public:
virtual void run() = 0;
virtual vector<Task *> & getDependencies() = 0;
};
And the original solution to this problem:
class TaskScheduler {
using vec_task_t = vector<Task *>; // Input
using mark_set_t = unordered_set<Task *>; // Hash set of task
mark_set_t marked_tasks;
public:
void runTasks(vec_task_t & tasks) {
for (Task * t : tasks) {
if (marked_tasks.find(t) == marked_tasks.end()) {
runTasks(t->getDependencies());
t->run();
marked_tasks.insert(t);
}
}
}
};
Now the tricky thing is of course that you can't just slab a thread on the run call and be done. You have to take into account that all dependencies should be executed first. That's not an issue at all actually, but it requires you to generalize the marked set to something that can be used to identify the ordering of tasks based upon their rate of dependency.
The set allows the property task -> bool or task -> [0, 1]. A map however allows the property task -> [0, n].
A map would need to be used instead of the set to get a dependency count. Use a hash map (unordered_map), because it allows relatively fast lookup.
However, this map doesn't allow ordering. To order the tasks by their dependency count you could use a multimap, which allows multiple values for the same key. This is necessary because you could have tasks with the same dependency count. For example, a set of tasks with no dependencies will have the same dependency count.
After ordering the tasks you can batch them up by executing same-keyed tasks in parallel and awaiting their completion, which takes as long as the longest running task for that dependency count. Starting with the highest key you'll execute all tasks which have no dependencies and are the most depended upon. Key 0 will map to tasks that are never depended upon.
class TaskScheduler {
using vec_task_t = vector<Task *>; // Input
using mark_map_t = unordered_map<Task *, vec_task_t::size_type>; // Uniquely keyed hash map of task -> dependency count
using order_map_t = multimap<vec_task_t::size_type, Task *, greater<vec_task_t::size_type>>; // Descending order non-uniquely keyed map of dependency count -> task
mark_map_t mark_map;
order_map_t order_map;
// O(N) where N = tasks in input.
void mark_tasks(vec_task_t & tasks) {
for (Task * t : tasks) {
mark_map_t::iterator it;
if ((it = mark_map.find(t)) == mark_map.end()) {
mark_map.insert({ t, 0 });
} else {
it->second++;
}
mark_tasks(t->getDependencies());
}
}
// O(K*log(K)) where K = unique tasks in input.
void order_tasks() {
for (auto & e : mark_map) {
order_map.insert({e.second, e.first});
}
}
// Run tasks between two iterators in parallel and await their completion.
void runParallel(order_map_t::iterator front, order_map_t::iterator back) {
std::vector<std::thread> threads;
while (front != back) {
threads.push_back(thread([](Task * task){
task->run();
}, front->second));
++front;
}
for (auto & t : threads) {
t.join();
}
}
public:
// Mark and order tasks in O(N + K*log(K)).
// Execute same-keyed tasks in parallel and await completion before executing next set of same-keyed tasks.
void runTasks(vec_task_t & tasks) {
mark_tasks(tasks);
order_tasks();
auto it = order_map.begin();
// Run same-keyed tasks in parallel blocks.
while (it != order_map.end()) {
auto front = it;
auto back = order_map.upper_bound(it->first);
runParallel(front, back);
it = back;
}
}
};
Transformed the Java interface into a C++ abstract class.
class Task {
public:
virtual void run() = 0;
virtual vector<Task *> & getDependencies() = 0;
};
The implementation is quite easy, however take note of the first rule. A task could contain dependencies that are also a dependency of another task. Mark each task as you traverse through the tasks, so you won't execute a task twice.
class TaskScheduler {
using vec_task_t = vector<Task *>; // Input
using mark_set_t = unordered_set<Task *>; // Hash set of task
mark_set_t marked_tasks;
public:
void runTasks(vec_task_t & tasks) {
for (Task * t : tasks) {
if (marked_tasks.find(t) == marked_tasks.end()) {
runTasks(t->getDependencies());
t->run();
marked_tasks.insert(t);
}
}
}
};
Transformed the Java interface into a C++ abstract class.
class Task {
public:
virtual void run() = 0;
virtual vector<Task *> & getDependencies() = 0;
};
The implementation is quite easy, however take note of the first rule. A task could contain dependencies that are also a dependency of another task. Mark each task as you traverse through the tasks, so you won't execute a task twice.
class TaskScheduler {
using vec_task_t = vector<Task *>; // Input
using mark_set_t = unordered_set<Task *>; // Hash set of task
mark_set_t marked_tasks;
public:
void runTasks(vec_task_t & tasks) {
for (Task * t : tasks) {
if (marked_tasks.find(t) == marked_tasks.end()) {
runTasks(t->getDependencies());
t->run();
marked_tasks.insert(t);
}
}
}
};
The first version represents what I intended to implement with the flawed code. For my test inputs it generates the same ordering as the second version, but it could be that under certain conditions it will fragment the ordering more so than the second version. I haven't looked into that though. Performance of the second version is definitely better.
- John March 09, 2015I like your approach and I can definitely see and acknowledge that it achieves a higher level of paralllelism (optimal even). Very cool!
Example set for readers:
1 -> { 2,3,4,5 }
2 -> { 6 }
3 -> { 4 }
4 -> { 6 }
5 -> { 7 }
6 -> { 7 }