Microsoft Interview Question for Software Engineer / Developers






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

Explaining XYZ idea in more details.
Known fact
If Summation(d(i) - p(i)) < 0 there is not solution.

Start at any node think of it as origin. Starting going forward and maintain E(d(i) - p(i)) if at any point this is negative. It means the rest of the circle must be positive.

Loop
So if at k we are negative start at k+1 and maintain E(d(i) - p(i)) starting from k+1 as 0.

Two possiblites we cross the origin and there is a negative sum. In this case no solution.
We complete a loop. That means a solution starting at that k+1.

- WellSaid July 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Question is unclear.
it says petrol stations going in a circle, and asks where to start to complete the loop.
Why not just start at any station, they are in a circle anyways. maybe some info is missing

- LastTroll February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Taking mileage as 1 KM/Liter, suppose p(0) is 2 Liters and d(0) is 3 KM, then we can't make it from s(0) to s(1).
An O(n) approach is to start from s(0), go on till available petrol Sum(p(i)-d(i)), becomes negative, then move backwards s(n-1), s(n-2), ... till it becomes +ve again, go on doing like this, till you arrive at same node from both sides... let me know if this is still not clear. Sorry, the question is easy to explain in picture - the way it was put in front of me, think of it in terms of circular list, will be easier to comprehend.

- Anil February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Test{

	public static boolean isPossible(int[] pet,int[] dis,int start , int end, int excess){
		int n = pet.length-1;
		if(end<start)end=n+end;
		for(int i=start;i<=end;i++){
			if(pet[i%n]+excess<dis[i])return false;
			excess+=pet[i%n]-dis[i];
		}
		return true;
		
	}
	public static int getStation(int[] pet, int[] dis){
		for(int i=0;i<dis.length;i++){
			int end=dis.length-1;	
			if(i!=0)end = i-1;
			if(isPossible[pet,dis,i,end,0]){
				return i;
			}
		}
		return -1;
		
	}
	public static void main(String args[]){
		int[] dis= new int[]{3,5,7,1,9,11,23,4};
		int[] pet=  new int[]{1,5,6,7,53,23,11,0};
		System.out.println(getStation(pet,dis));
	 }
}

- Anonymous February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ignore the above code:

public class Test{

        public static boolean isPossible(int[] pet,int[] dis,int start , int end, int excess){
                int n = pet.length;
                if(end<start)end=n+end;
                for(int i=start;i<=end;i++){
                        if(pet[i%n]+excess<dis[i%n])return false;
                        excess+=pet[i%n]-dis[i%n];
                }
                return true;

        }
        public static int getStation(int[] pet, int[] dis){
                for(int i=0;i<dis.length;i++){
                        int end=dis.length-1;
                        if(i!=0)end = i-1;
                        if(isPossible(pet,dis,i,end,0)){
                                return i;
                        }
                }
                return -1;

        }
        public static void main(String args[]){
                int[] dis= new int[]{3,5,7,1,9,11,23,4};
                int[] pet=  new int[]{1,5,6,7,53,23,11,0};
                System.out.println(getStation(pet,dis));
         }
}
~

- Anonymous February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I believe your code will work in O(n squared) time. A more efficient version will try starting at one station, adding up the difference between the petrol and distance one by one, until either the running sum is negative or the starting node is reached. If the running sum is negative at some point, increment the starting point by 1, removing the difference for the removed node from the running some. Do this until the running sum is positive again, and restart adding nodes. If your beginning node becomes the first node without finding a viable path, return false.

This should work in O(n).

- Baris February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous; it is O(nsquared)
And,
Create an account so you can edit ur code. right now posting ur code again and again makes it look like spam

- Anonymous February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar to Finding a connected component in a graph using DFS or BFS.

- Anonymous February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can u please clear the question

- Anonymous February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this is a Dynammic programming problem

- crackit February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this can be solved in 0(n) try to find by urself otherwise tmrw i will tell u guys.............do some brain strom.

- nasa February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this can be solved in 0(n) try to find by urself otherwise tmrw i will tell u guys.............do some brain strom.

- nasa February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can use greedy method here.
1) calculate p-d at each station.
2) pick the hightest p-d and travel clockwise/anti-clockwise.
3) one of them has to work.

any contradictory proofs for this approach?

- Anony February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

hmm how about this example:

1--(1)--2--(1)--3--(1)--4--(2)--5--(2)--6--(2)--7--(2)--1
Number is bracket is the distance between nodes.
And you have P(4) = 7 and P(3)=3, others has 0 petro.

According to your greedy algorithm (correct me if I'm wront), you will choose to start at node 4 since 7/2 is bigger than 3/1?

- Anonymous February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Start at any petrol station and keep moving by using advancing Pi-Di petrol to next station. If you end up getting stuck in between stations k and k+1, start over from the k+1 station.
It works in O(n)..You think about it, why it works :)

- XYZ February 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

in your example.. there is no solution because for a solution to exist, sigma pi > sigma di.

- Anony February 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But, lets p3 =4. then sigma di = sigma pi =11.
travel anti-clockwise u have the solution. but i think i figured the contradictory proof.

pi = {5,5,5,0,10,0,5,5,5}
di = {1,1,1,9,1,9,1,1,1}

- Anony February 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Right, sorry I mad a typo. P(3) should be 4 instead of 3.

- Anonymous February 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

XYZ awesome solution

- WellSaid July 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use backtracking to solve the problem, start at any position and incrementally keep going, if we get a negative value then come backward and choose the next station.

- hue February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Backtracking solution works. I've coded it and verified with all different scenarios.

- Anony February 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe this should be solved by dynamic programming. Let c[i,j] denote the excess fuel when going from i to j. Then the recursion should be c[i,j] = max((c[i,j-1] + p(j)-d(j)),(c[i-1,j] + p(i)-d(i))) for possible i,j

- Anonymous February 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That would be O(N^2).

The O(N) algorithm is simply to keep track of the difference b/w two quantities (also keep the running sum )and as soon as you encounter that the above condition is violated i.e running sum becomes -ve , start over from the next node(i.e after the node at which sum becomes -ve).

Also the question asked prior to this one was:

Give a necessary condition for the trip to exist.

Thanks!!!

- Guess Who?? February 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above algo. looks right.

The necessary condition should be \sum p_i >= \sum d_i.

- Anonymous March 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can this be solved same
1. keep an array of l(i) = d(i)-p(i)
2. keep a copy of the array l at the end of l
3. From the first index find the max subarray of size n.(running sum positive)
Order will be O(n)

- anno February 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

p(i)-d(i)

- anno February 26, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

good job

- XYZ July 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First of all, I don't think the s(i) is useful here. All we need is the capacity of each station, and the distance to the next one. Below is an O(n) solution. Start at station 0, with zero fuel. Add current station's capacity to the fuel, then subtract current station's distance from the fuel. If the fuel is negative, we need to keep advancing the starting station till we have non-negative fuel again. Otherwise we just move on to the next station and do the same capacity/distance accounting. We quit when we have either completed a loop or no valid starting station exists.

These accounting can be tricky. Since I haven't tested my code, it might not work but the general idea should work.

static int start(int[] cap, int[] dist) {
  int N = cap.length;
  int start=0;
  int curr=0;
  while(start>=N) {
    int fuel=0;
    while(true) {
      fuel+=cap[curr];
      fuel-=dist[curr];
      if(fuel<0)
        break;
      curr = (curr+1) % N;
      if(curr==start)
        return start;
    }

    while(fuel<0) {
      fuel-=cap[start];
      fuel+=dist[start];
      start++;
      if(start>=N)
        break;
    }
  }
  return -1;
}

- Sunny January 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar to Kadane's maximum subarray problem, the difference is we rotate the circle twice to cover starting from every node.

- IntwPrep.MS December 30, 2013 | Flag Reply


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