|
Given a cycle of n nodes. Each node has a money Bi .......
Microsoft Interview Questions and Answers
(Continued from previous question...)
130. Given a cycle of n nodes. Each node has a money Bi .......
Question:
Given a cycle of n nodes. Each node has a money Bi and each edge of the cycle has a cost Ci.Now when i am at a node, i acquire the money at the node and if i have to move to the next node in the cycle , i have to pay a cost corresponding to that edge. Now the cycle is unidirectional and we define a trip as starting from a node and coming back to it. Answer the following questions:
1. Give a necessary and sufficient condition for a trip to exist.
2. Given 1, give an algorithm to find the start node.
maybe an answer:
Given the example p1(c1)->p2(c2)->p3(c3)->...->pn(cn). Say we pick a random node i that pi>ci, start from there keep going and updating the sum until it becomes negative. Then we start from the next node j with initial sum pj-cj, keep doing that, if we manage to get back to pi, then j would be the right starting node. Otherwise do the same thing until we manage to get back to i, the last restart point we pick is the starting point. The reason is because when we find a interval i to j with sum (pi-ci)+...+(pj-cj) = -A, the remaining sum must be larger or equal to A. And the sum from the last restart point to i must be larger than A+B+C+..., which are those negative sum we've got during the process. (Because of the necessary condition)
maybe an answer2:
public class PetrolBunksInaCircle
{
private int[] money;
private int[] cost;
public PetrolBunksInaCircle(int[] moneyAtNode, int[] costPerEdge)
{
money = moneyAtNode;
cost = costPerEdge;
}
public int GetStartNodeForSuccessfullTrip()
{
int moneySoFar;
int startNode;
int currentNode;
int iterationCount;
iterationCount = 1; //this is used to break an infinite loop
startNode = 0;
currentNode = 1;
moneySoFar = money[0] - cost[0];
while (currentNode != startNode && iterationCount == 1)
{
if (moneySoFar < 0)
{
//need to reset
moneySoFar = money[currentNode] - cost[currentNode];
startNode = currentNode;
if(startNode == 0)
{
iterationCount++;
}
currentNode = (currentNode + 1) % cost.Length;
}
else
{
moneySoFar = moneySoFar + (money[currentNode] - cost[currentNode]);
currentNode = (currentNode + 1) % cost.Length;
}
}
if(iterationCount > 1)
{
return -1;
}
return startNode;
}
(Continued on next question...)
Other Interview Questions
| 