CodeKaur
BAN USER- 11of 11 votes
AnswersThere 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?
- CodeKaur in United States
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.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
Queue or stack will work as well. I solved it maintaining two list/Array of each color and also pointer to each element in the list.
Solution is still 2 * O(n).
Step 1: Scan through the list until head == current (circular linked list) and create a list/Array of each color nodes.
Step2: iterate through the pattern "rgyb" until all the elements are used and start populating final list
Step 3: return head of new list
Here is the code in C#:
public class Node {
public char color;
public Node next;
};
enum colors {
r = 0,
g,
y,
b
};
public static Node RearrangeList(Node head, string pattern ) {
Node[] colorArray = new Node[4];
Node[] pointerToCurrent = new Node[4];
int elementCount = 0;
for(int i =0;i<4;i++) {
colorArray[i] = null;
pointerToCurrent[i] = null;
}
Node current = head;
bool firstExecution = true;
while(firstExecution || !Object.Equals(current, head)){
firstExecution = false;
int index = getIndex(current.color);
if(colorArray[index] == null){
colorArray[index] = current;
pointerToCurrent[index] = current;
} else {
pointerToCurrent[index].next = current;
pointerToCurrent[index] = current;
}
current = current.next;
pointerToCurrent[index].next = null;
elementCount++;
}
Node newHead = null;
current = null;
while(elementCount > 0) {
foreach (char c in pattern)
{
int index = getIndex(c);
if(newHead == null) {
newHead = current = colorArray[index];
}
else {
current.next = colorArray[index];
current = current.next;
}
colorArray[index] = colorArray[index].next;
current.next = null;
}
elementCount -= pattern.Length;
}
return newHead;
}
could you please explain your algorithm than just writing lines of code.
- CodeKaur August 05, 2014