"There are at most eight servers in a data center. Each server has got a capacity/memory limit. There can be at most 8 tasks that need to be scheduled on those servers. Each task requires certain capacity/memory to run, and each server can handle multiple tasks as long as the capacity limit is not hit. Write a program to see if all of the given tasks can be scheduled or not on the servers?
Ex:
Servers capacity limits: 8, 16, 8, 32
Tasks capacity needs: 18, 4, 8, 4, 6, 6, 8, 8
For this example, the program should say 'true'.
Ex2:
Server capacity limits: 1, 3
Task capacity needs: 4
For this example, program should return false.
Got some idea that this needs to be solved using dynamic programming concept, but could not figure out exact solution."
2. Solution
As the interviewee indicated that dynamic programming will be a very good approach to tackle this problem. I think he/she is correct. As usual the key of dynamic programming is to find the sub problem.
Assuming given the problem as
Servers: {S1, S2, ......, Sn}
Tasks: {T1, T2, ......, Tm}
Try to assigned T1 to Si, i within [1, n], if T1 <= Si (the server has to have enough resource to accommodate the task). Then we have a sub-problem as,
Severs: {S1, S2, ..., Si-1, Si - T1, Si+1, ..., Sn}
Tasks: {T2, ......, Tm}
Corner Cases or Terminating Conditions:
- Task is empty then return true.
- If all resource available is less than all task required, then return false.
Sum(Si) < Sum(Tj)
Sum(Si) < Sum(Tj)
- If a task requires more resource than that any servers can provide, then return false.
Max(Tj) > Max(Si)
Max(Tj) > Max(Si)
- Any server that provides less resource than the least any task requires can be ignored
Si < Min(Tj)
- If the tasks comes a single task and can be accommodated by servers, then return true.
- If the tasks comes a single task and can be accommodated by servers, then return true.
They are all valid cases but not necessary to implement them all. In my solution I just implemented the 1st and the last and the solution works fine.
3. C++ Implementation
// Implementation
// ********************************************************************************
bool SchedulingSolutionDP(std::vector<int>& serverCenter,
const std::vector<int>& tasks, const size_t taskIndex)
{
if (tasks.empty()) {
return true;
}
if (taskIndex >= (tasks.size() - 1)) {
// the last corner case
for (size_t index = 0; index < serverCenter.size(); ++index) {
if (tasks[taskIndex] <= serverCenter[index]) {
return true;
}
}
return false;
}
for (size_t index = 0; index < serverCenter.size(); ++index) {
if (tasks[taskIndex] <= serverCenter[index]) {
// create sub-problem and call recursively
serverCenter[index] -= tasks[taskIndex];
if (SchedulingSolutionDP(serverCenter, tasks, taskIndex + 1)){
// recover to the original problem
serverCenter[index] += tasks[taskIndex];
return true;
}
// recover to the original problem
serverCenter[index] += tasks[taskIndex];
}
}
return false;
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestCases()
{
{
std::vector<int> serverCenter = { 8, 16, 8, 32 };
std::vector<int> tasks = { 18, 4, 8, 4, 6, 6, 8, 8 };
assert(SchedulingSolutionDP(serverCenter, tasks, 0) == true);
}
{
std::vector<int> serverCenter = { 1, 3 };
std::vector<int> tasks = { 4 };
assert(SchedulingSolutionDP(serverCenter, tasks, 0) == false);
}
{
std::vector<int> serverCenter = { 7, 6 };
std::vector<int> tasks = { 5, 3, 3, 2 };
assert(SchedulingSolutionDP(serverCenter, tasks, 0) == true);
}
{
std::vector<int> serverCenter = { 1, 3, 1, 2, 3, 4 };
std::vector<int> tasks = { 4, 3, 1, 2, 3, 1 };
assert(SchedulingSolutionDP(serverCenter, tasks, 0) == true);
}
{
std::vector<int> serverCenter = { 2, 5, 10, 4, 13, 19, 23, 11, 8, 17 };
std::vector<int> tasks = { 30, 2, 1 };
assert(SchedulingSolutionDP(serverCenter, tasks, 0) == false);
}
{
std::vector<int> serverCenter = { 8, 6, 2 };
std::vector<int> tasks = { 5, 4, 3, 2, 1 };
assert(SchedulingSolutionDP(serverCenter, tasks, 0) == true);
}
{
std::vector<int> serverCenter = { 8, 6, 2 };
std::vector<int> tasks = { 5, 4, 4, 2, 1 };
assert(SchedulingSolutionDP(serverCenter, tasks, 0) == true);
}
}
// ********************************************************************************
No comments:
Post a Comment