## VMWare Inc Interview Question for Member Technical Staffs

Country: United States
Interview Type: Written Test

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

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.

``````private boolean schedule(int i, int[] need, int[] capacity)
{
if(i >= need.length) return true;

for(int k = 0; k < capacity.length; ++k){
if(capacity[k] >= need[i]){
capacity[k] -= need[i];
if(schedule(i + 1, need, capacity)) return true;
capacity[k] += need[i];
}
}
return false;
}
public boolean schedule(int[] need, int[] capacity)
{
//check if total capacity is enough
//check all can be scheduled
return sumOfArray(capacity) >= sumOfArray(need) && schedule(0, need, capacity);
}``````

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

no of Server = s
Logic
1. Sort the server - O(s*logs)
2. Sort the Task - O(t*logt)
3. For i = t to 1
For j = 1 to s
if( T[ i ] < S[ j ] )
S[ j ] = S[ j ] - T[i]
End For
return false
End for

- O(s*t)

Worst case complexity - max of three

Will think of better solution and post

Comment hidden because of low score. Click to expand.
0

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:
(4)task can not be assigned, return false
while actually we can schdule them like this:

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

this is actually the multiple knapsack problem as I see it. It is quite hard to solve this with an exact algorithm as it is NP Hard.

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

Hey friend .. can you please tell me this was for which position..

Comment hidden because of low score. Click to expand.
0

This is for Member Technical Staff position. I do not remember the exact team name but it was for vCloud Director team I guess. This test is for people who are invited for April 21st/22nd hiring event.

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

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, tmp2;

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;
vector < pair<int, int> > answer;

{
return true;

srtArray *curarray = new srtArray(serverCount);
for (int i = 0; i < serverCount; i++)
curarray->ary[i] = remCap[i];
curarray->srt();
return false;

for (int i = 0; i < serverCount; i++)
{
{
{
return true;
}
}
}
return false;
}

bool startSolving(int sCount,int *sCap,int tCount,int *tCap)
{
for (int i = 0; i < tCount; 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;
int *tCap = new int;

while (cin >> n >> t)
{
seen.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++)
}
else
cout << "Impossible\n";
cout << endl;
}
}``````

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

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

Comment hidden because of low score. Click to expand.
0

Hey buddy. Unfortunately, this algorithm won't work. Consider this testcase:
Servers: 7 9

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.

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

``````bool CanAllocate(
vector<int> &Servers,
const size_t ServIdx)
{
{
return (true);
}

{
return (false);
}

{

{

{
return (true);
}
{
return (true);
}

}

}

return (false);
}``````

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

Just the idea without any optimization. Creating max heaps for both sets makes it more efficient.

``````till task_set is empty
do
index_in_server_set = get_max_server_slot(server_set)
} 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.

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

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

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

A little bit more clear code for C++:

Its a branch and bound solution. Its is like a backtracking but bounding inadmissible solutions:

{
for( int i = 0 ; i < serversState.size(); ++i )
{
return true;
}
return false;
}

{

}

struct State
{
std::vector<int> servers;

bool canContinue()
{
if( servers.empty() )
return false;

int maxSlot = servers;
int sumServerCap = servers;
for( int i = 1; i < servers.size(); ++i )
{
if( maxSlot < servers[i] )
maxSlot = servers[i];

sumServerCap += servers[i];
}

for( int i = 1; i < tasks.size(); ++i )
{

}

return false;

return true;
}

bool hasFinished()
{
}

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

};

{

if( state.hasFinished() )
return true;

if( !state.canContinue() )
return false;

state.print();

int server = 0;
while( true )
{
if( server == state.servers.size() )
break;

{
}

{
// found a fit

return true;

// backtrack
}
else
{
server++;
}

}

return false;

}

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

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 )
{
return true;
}
return false;
}

{

}

struct State
{
std::vector<int> servers;

bool canContinue()
{
if( servers.empty() )
return false;

int maxSlot = servers;
int sumServerCap = servers;
for( int i = 1; i < servers.size(); ++i )
{
if( maxSlot < servers[i] )
maxSlot = servers[i];

sumServerCap += servers[i];
}

for( int i = 1; i < tasks.size(); ++i )
{

}

return false;

return true;
}

bool hasFinished()
{
}

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

};

{

if( state.hasFinished() )
return true;

if( !state.canContinue() )
return false;

state.print();

int server = 0;
while( true )
{
if( server == state.servers.size() )
break;

{
}

{
// found a fit

return true;

// backtrack
}
else
{
server++;
}

}

return false;

}``````

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

``````task.sort()
server.sort()

n = server[len(server)-1]
for i in range(len(server)-1,-1,-1):
print i, "i"
while (k>=0 and n >= task[k]):
k = k - 1
if item == n:
k = k - 1
if k>=0:

if k <= -1:
print "true"
else:
print "false"``````

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

The sum of tasks and server capacity would work with one condition.
Sum_capacity=sum(capacity)
Max_server_cap_val=maximum value from all servers

Return true
Else return false

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

Since we just need to return true or false, all you need to do total server capacity and task capacity. if task capacity <= server capacity then return true or false.

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

I suppose here one task's need can not split among several servers, so the following case should return false:
Server capacity limits: 1, 3

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.

### 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.