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

- uuuouou April 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- akashgupta.edu April 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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]

- uuuouou April 12, 2014 | Flag
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.

- Anonymous April 12, 2014 | Flag Reply
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..

- coderX April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- chaitu308 April 13, 2014 | Flag
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[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;
	}
}

- iroodaz April 13, 2014 | Flag Reply
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)}

- Think simple April 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- iroodaz April 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- cleverwebber April 15, 2014 | Flag Reply
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
	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.

- Rohan Sen April 26, 2014 | Flag Reply
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;

- Anon July 18, 2014 | Flag Reply
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 )
{
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;

}

- pablocael September 02, 2014 | Flag Reply
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 )
    {
        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;
        
}

- Anonymous September 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"

- Anonymous December 30, 2014 | Flag Reply
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_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

- Kunal December 17, 2017 | Flag Reply
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.

- Anonymous April 12, 2014 | Flag Reply
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
Task capacity needs: 4

- uuuouou April 12, 2014 | Flag


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