VMWare Inc Interview Question
Member Technical StaffsCountry: United States
Interview Type: Written Test
no of Server = s
no of Task = t
Logic
1. Sort the server - O(s*logs)
2. Sort the Task - O(t*logt)
3. For i = t to 1
Bool task_scheduled = false
For j = 1 to s
if( T[ i ] < S[ j ] )
S[ j ] = S[ j ] - T[i]
task_scheduled = true
End For
if( !task_scheduled)
return false
End for
- O(s*t)
Worst case complexity - max of three
Will think of better solution and post
I'm sorry but I don't think the greed algorithm works well. Let's take the following case as an example:
server capacity[] = {4, 5}
task need[] = {2, 2, 2, 3}
Then according to your algorithm, the process will be:
(1)task[3] assign to server[0]
(2)task[2] assign to server[1]
(3)task[1] assign to server[1]
(4)task[0] can not be assigned, return false
while actually we can schdule them like this:
task[0] and task[1] => server[0]
task[2] and task[3] => server[1]
As the number of servers and the number of tasks is not so big, we can use backtracking to solve it, and use memoization technique (dynamic programming) to keep track of previously visited configurations and to have a better running time by pruning duplicate sub-trees.
Here is my implementation in C++:
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#define mp make_pair
using namespace std;
int tmp1[10], tmp2[10];
struct srtArray{
int n;
int *ary;
srtArray(int N)
{
n = N;
ary = new int[n];
}
void srt()
{
sort(ary, ary + n);
}
bool operator < (const srtArray& that)const
{
int i;
for (i = 0; i < n && that.ary[i] == ary[i]; i++);
if (i == n)
return false;
return ary[i] < that.ary[i];
}
};
set < pair<int, srtArray> > seen;
int remCap[10];
int totalTaskCount,serverCount;
int tasksCapacity[10];
vector < pair<int, int> > answer;
bool solve(int curtask)
{
if (curtask == totalTaskCount)
return true;
srtArray *curarray = new srtArray(serverCount);
for (int i = 0; i < serverCount; i++)
curarray->ary[i] = remCap[i];
curarray->srt();
if (seen.find(mp(curtask,*curarray)) != seen.end())
return false;
for (int i = 0; i < serverCount; i++)
{
if (remCap[i] >= tasksCapacity[curtask])
{
remCap[i] -= tasksCapacity[curtask];
if (solve(curtask + 1))
{
answer.push_back(mp(curtask + 1, i + 1));
return true;
}
remCap[i] += tasksCapacity[curtask];
}
}
seen.insert(mp(curtask, *curarray));
return false;
}
bool startSolving(int sCount,int *sCap,int tCount,int *tCap)
{
totalTaskCount = tCount;
for (int i = 0; i < tCount; i++)
tasksCapacity[i] = tCap[i];
serverCount = sCount;
for (int i = 0; i < sCount; i++)
remCap[i] = sCap[i];
return solve(0);
}
int main()
{
int n, t;
int *sCap = new int[10];
int *tCap = new int[10];
while (cin >> n >> t)
{
seen.clear();
answer.clear();
for (int i = 0; i < n; i++)
cin >> sCap[i];
for (int i = 0; i < t; i++)
cin >> tCap[i];
if (startSolving(n, sCap, t, tCap))
{
cout << "Possible!\n";
for (int i = 0; i < answer.size(); i++)
cout << answer[i].first << " -> " << answer[i].second << endl;
}
else
cout << "Impossible\n";
cout << endl;
}
}
There is no optimization required here and hence no need for dynamic programming or greedy algorithms. All we need to return is true or false.
1. Put the servers in a min heap, put the tasks in a min heap.
2. extract the top of both heaps and try to set the task on that server capacity.
2a. If able, reduce the tasks capacity from the server capacity and insert reduced server capacity back to the heap.
2b. If can't insert back the task to its heap.
3. continue so long as server heap is not empty.
run time: max{Tlog(S),Slog(S),Tlog(T)}
Hey buddy. Unfortunately, this algorithm won't work. Consider this testcase:
Servers: 7 9
Tasks: 3 3 3 7
This solution will first assign the first two tasks to the first server and the third task to the second server. After that, we won't have enough server capacity for the fourth task; therefore, it will return false. However, if we assign the first three tasks to the second server, and the last task to the first server, we have a valid assignment.
bool CanAllocate(
vector<int> &Servers,
vector<int> &Tasks,
const size_t TaskIdx,
const size_t ServIdx)
{
if(ServIdx == Servers.size() && TaskIdx == Tasks.size())
{
return (true);
}
if(ServIdx == Servers.size() || TaskIdx == Tasks.size())
{
return (false);
}
for(size_t i = TaskIdx; i < Tasks.size(); ++i)
{
swap(Tasks[TaskIdx],Tasks[i]);
if(Servers[ServIdx] >= Tasks[TaskIdx])
{
Servers[ServIdx] -= Tasks[TaskIdx];
if(CanAllocate(Servers,Tasks,TaskIdx + 1,ServIdx))
{
return (true);
}
else if(CanAllocate(Servers,Tasks,TaskIdx + 1,ServIdx + 1))
{
return (true);
}
Servers[ServIdx] += Tasks[TaskIdx];
}
swap(Tasks[TaskIdx],Tasks[i]);
}
return (false);
}
Just the idea without any optimization. Creating max heaps for both sets makes it more efficient.
till task_set is empty
do
max_task=get_max_task(task_set); delete(task_set, max_task);
index_in_server_set = get_max_server_slot(server_set)
if (max_task <= server_set[index_in_server_set]) {
server_set[index_in_server_set] -= max_task;
} else {
return false; /* failed since max available server slot is less than max task size */
}
}
Notice that max slot means max available server space so a server may have max slot even after accommodating multiple tasks if other servers are far less capacious.
It looks like the interviewer is not interested in actual allocation. Actual allocation is NP-complete problem, but checking whether solution exists in not NP. So, we can check for some corner conditions and then check if the all the tasks can be allocated on the servers. The actual steps. should be:
(i) Sort the servers in descending order based on their memory. Call this List S.
(ii) sort the tasks in descending order based on the required memory. Call this list T.
(iii) check for following conditions:
(a) If T(last_elem) < S(0) or T(0) > S(0) return false;
(b) if len(T) > 64 return false;
(c) if (Sum_of_all_elements of T > Sum_of_all_elements of S) return false;
(d) return true;
A little bit more clear code for C++:
Its a branch and bound solution. Its is like a backtracking but bounding inadmissible solutions:
bool hasAvailableServer( std::vector<int>& serversState )
{
for( int i = 0 ; i < serversState.size(); ++i )
{
if( serversState[i] != 0 )
return true;
}
return false;
}
bool hasAvailableTask( std::vector<int>& taskState )
{
return !taskState.empty();
}
struct State
{
std::vector<int> tasks;
std::vector<int> servers;
bool canContinue()
{
if( servers.empty() )
return false;
int maxSlot = servers[0];
int sumServerCap = servers[0];
for( int i = 1; i < servers.size(); ++i )
{
if( maxSlot < servers[i] )
maxSlot = servers[i];
sumServerCap += servers[i];
}
int maxTask = tasks[0];
int sumTasksSize = tasks[0];
for( int i = 1; i < tasks.size(); ++i )
{
if( maxTask < tasks[i] )
maxTask = tasks[i];
sumTasksSize += tasks[i];
}
if( sumTasksSize > sumServerCap || maxTask > maxSlot )
return false;
return true;
}
bool hasFinished()
{
return !hasAvailableTask( tasks );
}
void print()
{
std::cout << "remaining tasks : ";
for( int i = 0; i < tasks.size(); ++i )
{
std::cout << tasks[i] << " ";
}
std::cout << "| remaining servers : ";
for( int i = 0; i < servers.size(); ++i )
{
std::cout << servers[i] << " ";
}
std::cout << std::endl;
}
};
bool seekTaskFit( State& state )
{
if( state.hasFinished() )
return true;
if( !state.canContinue() )
return false;
state.print();
int task = 0;
int server = 0;
while( true )
{
if( server == state.servers.size() )
break;
while( task < state.tasks.size() && state.tasks[task] > state.servers[server] )
{
task++;
}
if( task < state.tasks.size() )
{
// found a fit
int taskSize = state.tasks[task];
state.servers[server] -= taskSize;
state.tasks.erase( state.tasks.begin() + task );
if( seekTaskFit( state ) )
return true;
// backtrack
state.tasks.insert( state.tasks.begin() + task, taskSize );
state.servers[server] += taskSize;
task++;
}
else
{
task = 0;
server++;
}
}
return false;
}
A little bit more clear code for C++:
Its a branch and bound solution. Its is like a backtracking but bounding inadmissible solutions:
bool hasAvailableServer( std::vector<int>& serversState )
{
for( int i = 0 ; i < serversState.size(); ++i )
{
if( serversState[i] != 0 )
return true;
}
return false;
}
bool hasAvailableTask( std::vector<int>& taskState )
{
return !taskState.empty();
}
struct State
{
std::vector<int> tasks;
std::vector<int> servers;
bool canContinue()
{
if( servers.empty() )
return false;
int maxSlot = servers[0];
int sumServerCap = servers[0];
for( int i = 1; i < servers.size(); ++i )
{
if( maxSlot < servers[i] )
maxSlot = servers[i];
sumServerCap += servers[i];
}
int maxTask = tasks[0];
int sumTasksSize = tasks[0];
for( int i = 1; i < tasks.size(); ++i )
{
if( maxTask < tasks[i] )
maxTask = tasks[i];
sumTasksSize += tasks[i];
}
if( sumTasksSize > sumServerCap || maxTask > maxSlot )
return false;
return true;
}
bool hasFinished()
{
return !hasAvailableTask( tasks );
}
void print()
{
std::cout << "remaining tasks : ";
for( int i = 0; i < tasks.size(); ++i )
{
std::cout << tasks[i] << " ";
}
std::cout << "| remaining servers : ";
for( int i = 0; i < servers.size(); ++i )
{
std::cout << servers[i] << " ";
}
std::cout << std::endl;
}
};
bool seekTaskFit( State& state )
{
if( state.hasFinished() )
return true;
if( !state.canContinue() )
return false;
state.print();
int task = 0;
int server = 0;
while( true )
{
if( server == state.servers.size() )
break;
while( task < state.tasks.size() && state.tasks[task] > state.servers[server] )
{
task++;
}
if( task < state.tasks.size() )
{
// found a fit
int taskSize = state.tasks[task];
state.servers[server] -= taskSize;
state.tasks.erase( state.tasks.begin() + task );
if( seekTaskFit( state ) )
return true;
// backtrack
state.tasks.insert( state.tasks.begin() + task, taskSize );
state.servers[server] += taskSize;
task++;
}
else
{
task = 0;
server++;
}
}
return false;
}
task.sort()
server.sort()
k = len(task)-1
n = server[len(server)-1]
for i in range(len(server)-1,-1,-1):
print i, "i"
while (k>=0 and n >= task[k]):
n = n - task[k]
task.remove(task[k])
k = k - 1
print k, n, task
for item in task:
if item == n:
task.remove(item)
k = k - 1
print "k", k, item, task
if k>=0:
n = task[k]
print k,n,task
if k <= -1:
print "true"
else:
print "false"
The sum of tasks and server capacity would work with one condition.
Sum_tasks=sum (task)
Sum_capacity=sum(capacity)
Max_server_cap_val=maximum value from all servers
Max_tasks_val = maximum value from all tasks
If sum_tasks<=sum_capacity && max_tasks_val <= max_server_ val
Return true
Else return false
There are at most 8 tasks and 8 servers, so the count of assignment is at most 8^8 = 2^24, which is not a very large size. Depth First Search could just work well.
- uuuouou April 12, 2014