CareerCup

1 - Assume same number of processes and servers
2 - Yes
3 - No

The only goal is to match process to a server. You don't need to worry about optimizing the match or other complicated scenarios.

I think this is CPU scheduling related problem. What CPU does to assign memory to different processes is it follows Best Fit or First Fit type of techniques.
It could also be treated as that version of knapsack problem which is solvable by dynamic programming approach..

Think of the complete bipartite graph (Process,Server), with two edges between any (i,j), one of the edges being marked by max memory of the process and the other max hard disc. Then maximize network flow.

en.wikipedia.org/wiki/Maximum_flow_problem#Multi-source_multi-sink_maximum_flow_problem

machines [300,24] [200, 15] [250, 50] [100, 45]

processes [50,50] [75, 24] [275, 20] [190, 10]

sort the machınes and processes according to their disk space need and availability

machines sorted -> [100, 45] [200, 15] [250, 50] [300,24]
processe sorted -> [50,40] [75, 24] [190, 10] [275, 20]

run over the process list and check from the beginning if any machine is suitable for taht process. This is a first match algo I think.


[50,40] [100,45]
[75,24] [250,50]
[190,10] [200,15]
[275,20] [300,24]

is hard disk space is enough and memory is not enough check the next and continue like that.
There must be a field for machine class that is about the availibility of the machine and
while traversing the machine list we need to check that.

Complexity is O(mn + mlogm + nlogn) where m is the number ofprocesses and n is the number of machines

seems like a classic constraint satisfaction problem (e.g., n-queens). Perhaps it suffices to simply assign processes to machines greedily: go through the list in any order, assign to the first machine that satisfies the requirements, and then backtrack if no feasible machine can be found.

It is a bipartite graph maximum matching problem:

mcs.csueastbay.edu/~simon/handouts/4245/hall.html

it is a bipartite maximum matching prob

Like other people said: bipartite matching. In one bipartition you put processes; in the other you put servers. Make an edge from a process P to a server S if S can accommodate P. Now you need to find a perfect matching from processes to servers within this bipartite graph, for which any number of at-most O(N^3) solutions are possible.

how about about applying the banker's algorithm for resource allocation to each process...
if anyone finds any problem to this approach then just post it here....

Agree with Bullocks (and others) on the maximum bipartite matching. The solution is not a path but rather a collection of edges between servers and processes.

Originally, there's an edge between a server and a process if a server can run that process. After the maximum bipartite matching is solved, there is at most one edge from each server and at most one edge to each process. If the number of edges is n, i.e. each server has exactly one edge and each process has exactly one edge, than the maximum matching is perfect and we can run all processes simultaneously. If the maximum matching is not perfect (i.e. we have e < n edges), there are (n-e) processes that cannot be run no matter how we arrange the servers and the processes.

The algorithm to find the maximum bipartite matching is to turn the bipartite graph into a flow network by adding a source and a sink and assigning a capacity of 1 to each edge. Then you can use Ford-Fulkerson method to find the maximum flow.

saumils1987, banker's algorithm seems to be for a completely different context and I don't quite see how it could be modified to work for this case. The main difference that I see is that in banker's algorithm, processes take only what they need, whereas here they take the whole machine (whether they need it or not). Also, in banker's algorithm, there's no need to run everything at the same time but that's what we are trying to do here. I'd be interested to know the details of what you had in mind ...

hey what about this way:

for each process identify how many machines it can be alocated to.

so we have a list:
[(p1,5), (p2,3), (p3,1)]

then sort the list in number machines allowed
[(p3,1), (p2,3), (p1,5)]

Now allot the machine to process which can only be alloted to 1 and update the list etc etc

if min num of machines for a process is >1, then allocate any of them.. not sure if it would work but just an idea.. what do you guys think?

I think a dynamic programming approach might work here. Sort the processes and the machines on hard disk capacity. It looks like one might be able to reduce this to the longest common sequence problem - we have to find the longest sequence of processes that can be assigned to machines here.

I am reading all post and if i wrong , we just need to find the server which is best fit for a given process. I am doing as follow

array with pair<memory, hardisk>
array2 index of server
sort on hardisk then stable sort on memory
iterate each process and do binary search return which matches best(not necessary exact match) on array
swap  that with last 
array2 [i] = n;
reduce n (initial length of array) by 1

I don't think we can use Bipartite here, or we need to modify it, which i could not figure out..
In bipartite, we can divide the flow among several paths. suppose a node emits 4 unit flow, it can be divided in 2 + 2 units in different paths. but here we cannot do this...
correct me if i am wrong??

Maybe the interviewer wanted to schedule process as many as possible. If not a optimal question, sort the machines by memory and then by disk, like in sql sort by memory, disk.
For each process, find the lower bound and upper bound by memory, and then we get a range of machine order by disk. Then get the lower bound by binary search. Assign this process to the machine found.

Time complexity is O(nlog(n)). 1 sort is O(nlogn), n binary search is nlogn.

is it a newwork stream problem...too complex to write code...

Haven't explored advance graph. but this can be done in n^2 in a greedy way
We can basically store the list of indexes of machine for each process that is eligible for each process and store it in min priority queue based on size of list of eligible mc. we take each element starting with minimum mc available for process and keep assigning, we'd need a used boolean array for that too. This is more accurate than sorting and assigning from left side as mentioned by other people.

Haven't explored advance graph. but this can be done in n^2 in a greedy way
We can basically store the list of indexes of machine for each process that is eligible for each process and store it in min priority queue based on size of list of eligible mc. we take each element starting with minimum mc available for process and keep assigning, we'd need a used boolean array for that too. This is more accurate than sorting and assigning from left side as mentioned by other people.

We can ask different questions to the interviewer like:
1 - Can there be less number of processes?
2 - Can a process use a machine with the memory more then it needs and this question can also be asked for memory. For Ex-> there is machine with 200 mb disk space and 32 mb memory. Will the process that needs 100 mb space use the machine or check another machine.?
3 - Is there a priority for the choice of disk space and memory?

Can you explain the details you talked if there is any.