Microsoft Interview Question for Software Engineer / Developers






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

Check this algo and reply back if you face any issues.

public class AlgoPetrolDistance{
public static void main(String[] args){
Random random = new Random();
List myPetrolPumpsList = new ArrayList<PetrolPump>();
for(int i = 0; i < 6; i++){
myPetrolPumpsList.add(new PetrolPump(random.nextInt(20), random.nextInt(20)));
}
System.out.println("list " + myPetrolPumpsList);

//For finding out first possible route to all destinations in circle with given conditions
int startPoint = solution_1(myPetrolPumpsList);
if(startPoint == -1){
System.out.println("There is no possible startPoint to visit all Petrol pumps/destinations");
}else{
System.out.println("startPoint to reach all nodes is " + (startPoint + 1));
}

//For findint out whether its possible to reach all points starting from each node
for(int i = 0; i < 6; i++){
int result = possibleStartPointsToCoverDistance(myPetrolPumpsList, i);
if(result ==-1){
System.out.println("There is no possible route from " + i);
}else{
System.out.println(" There is possiblity to cover all Points if user starts from " + i);
}
}
}

static int solution_1(List<PetrolPump> myPetrolPumpsList){
int start = 0;
int petrolsum = 0;
int distancesum = 0;
int index = 0;
int nodesVisited = 0;
int totalNodesVisited = 0;
int size = myPetrolPumpsList.size();
//max no of iterations are limited to 2n if all nodes are visited before 2*n iterations then it will break.
while(nodesVisited != size && totalNodesVisited != 2 * size)
{
petrolsum += myPetrolPumpsList.get(index).mMaxPetrolLimit;
distancesum += myPetrolPumpsList.get(index).mDistanceToNextPump;
totalNodesVisited++;
nodesVisited++;
//Total of petrol is not enough to cover the distance then start from next node
if(petrolsum < distancesum)
{
petrolsum = 0;
nodesVisited = 0;
distancesum = 0;
start = index + 1;
}
System.out.println(" Nodes visited " + nodesVisited);
index = (index + 1) % size;
}
//To return if all nodes are not reachable
if(nodesVisited != size){
return -1;
}

// Return starting point
return start;
}

static int possibleStartPointsToCoverDistance(List<PetrolPump> myPetrolPumpsList, int startNode){
int petrolsum = 0;
int distancesum = 0;
int index = startNode;
int nodesVisited = 0;
int totalNodesVisited = 0;
int size = myPetrolPumpsList.size();
//max no of iterations are limited to 2n if all nodes are visited before 2*n iterations then it will break.
while(nodesVisited != size && totalNodesVisited != size)
{
petrolsum += myPetrolPumpsList.get(index).mMaxPetrolLimit;
distancesum += myPetrolPumpsList.get(index).mDistanceToNextPump;
totalNodesVisited++;
nodesVisited++;
//Total of petrol is not enough to cover the distance to next point then return -1 to indicates its not possible
if(petrolsum < distancesum)
{
return -1;
}
index = (index + 1) % size;
}
//To return if all nodes are not reachable
if(nodesVisited != size){
return -1;
}
// Return starting point
return startNode;
}
}


POJO to keep information about each petrol pump(amount of petrol can be filled at this pump and distance to next pump)
public class PetrolPump{
int mMaxPetrolLimit;

int mDistanceToNextPump;

/**
* @param maxPetrolLimit
* @param distanceToNextPump
*/
public PetrolPump(int maxPetrolLimit, int distanceToNextPump){
super();
mMaxPetrolLimit = maxPetrolLimit;
mDistanceToNextPump = distanceToNextPump;
}

/**
* @return the maxPetrolLimit
*/
public int getMaxPetrolLimit(){
return mMaxPetrolLimit;
}

/**
* @param maxPetrolLimit the maxPetrolLimit to set
*/
public void setMaxPetrolLimit(final int maxPetrolLimit){
mMaxPetrolLimit = maxPetrolLimit;
}

/**
* @return the distanceToNextPump
*/
public int getDistanceToNextPump(){
return mDistanceToNextPump;
}

/**
* @param distanceToNextPump the distanceToNextPump to set
*/
public void setDistanceToNextPump(final int distanceToNextPump){
mDistanceToNextPump = distanceToNextPump;
}

/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
@Override
public String toString(){
return "[" + mMaxPetrolLimit + " " + mDistanceToNextPump + "]";
}
}

- marutikutre June 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1 Assume that the gas tank in our mode of transport has unlimited capacity.
2 Initially, the gas tank in our mode of transport is empty.
3 start from the city where (d_i - P_i) is maximum
4 Fill gas at every station

- narada July 15, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You do not know how much petrol is there in each tank to compute your formula....

Start from any arbitrary node and go in one direction. say left... then keep going by refueling the tank at each gas bunk.. If your car runs out of gas... then start from the next gas station but store the gas station in a global queue or sthg too...keep doing this unless you either come back to the original station in which case you found the solution or u run out of gas after the gas station which is already present in the global queue. If that happens, then start your solution in the other direction. and i think all this should be done using recursion and backtracking...

- Adi August 21, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

(1)make a circlular linked list
(2)pick from any random node and start traversing
(3)if u not got thro till end, go one step back and then try

O(n^2)

- mail2vcp@gmail.com October 01, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we need to traverse list d1.....dn and find out the sequence with smaller di's in starting and larger di's at the end.
This list d1..... dn can be very random, it may not be possible to find series like this, then start with station with smallest di.

- Anonymous October 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dynamic programming?

- Anonymous October 13, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution 1:
1) First, we have to start from a station where p_i >= d_i. Find all such i's, put them in a list L.
2) For each station i in L, check if a series of conditions are satisfied: (p_i-d_i) + p_i+1 >= d_i+1, (p_i-d_i)+(p_i+1 - d_i+1) + p_i+2 >= d_i+2, ..., until it circles back to i. The first i satisfies these conditions is the station we are looking for.
3) the running time is about O(n^2)

Solution 2:
1) Find the station i with the largest gap between the fuel and distance, i.e., (p_i - d_i) is the minimum.
2) go through the circle on the reverse direction, i.e., i -> i-1 -> i-2, ..., sum up all (p_i - d_i) along the road, until the sum becomes positive, let's the sum is S >= 0. Suppose the path length is L.
3) now the above path can be viewed as a new station i', with (p_i' - d_i') = S. The problem is reduced to a smaller problem with n - L + 1 nodes
4) The running time is roughly O(nlogn)

- summer March 03, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I did not get your 2nd solution. Your first solution also looks complicated. There is a simpler O(n^2) solution:

1. Find difference between petrol and distance (i.e. p_i - d_i) of all stations
2. For each positive number as starting bunk, sum the differences of n stations.
2.a. If at any point the sum becomes less than zero, start over with the next positive number
2.b. If the sum becomes zero when the last difference is added, we got the starting stations

Step 2 has complexity O(n^2)

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

hey...can be done n O(n) time..using circular link list
1.find the diff betwn p and d for each bunk...O(n)
2.start from any bunk..curr=start->next...sum=start->diff
if(sum<0)then start=curr;curr=curr->next;sum=start->diff;
else sum+=curr->diff...curr=curr->next;
3.cout<<start->d<<start->p..

- sg December 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Either express the idea using pseudo code or write valid code. What you wrote is junk.

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

Can be done in O(n).
1)construct 2n size array which hold the bunks start from anywhere twice, for example, bi,b(i+1).....b(i+n-1);bi,b(i+1).....b(i+n-1)
2)Now construct another 2n size array R to hold R[k]=R[k-1]+petrolatbunk[k]-distance[k-1,k]
3)Finally, you will find R[i]=R[i+n], then that is it.

- Anonymous May 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

http: // dingding2009. wordpress. com/ 2009 / 08/ 20/ daily-problem-solving-sessions/

- gaurav July 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#define MAX 10

using namespace std;

void optimize(int n, int p[], int d[]){
int start=0, end, sumdis=0, sumpetrol=0;
int clockstart=0;
bool firstTry=true;
int travel=start;

while(clockstart!=start || firstTry==true){


//cout<<travel<<" ";
sumdis+=d[travel];
sumpetrol+=p[travel];

//to check if there is sufficient petrol to travel further
if(sumpetrol<sumdis){

if(firstTry==true)firstTry=false;

if(travel < n-1)
start=travel+1;
else
start=0;

travel=start;sumdis=0;sumpetrol=0;//clockstart=start;firstTry=true;
cout<<endl;

continue;
}

// to implement circular nature in array
if(travel < n-1)
travel=travel+1;
else
travel=0;


if(travel==start){
cout<<"Success";
cout<<"\n"<<"Start->"<<start+1<<" End-->"<<travel;
return;
}
}
cout<<"\n"<<"failure";
}

int main(){

int n, p[MAX],d[MAX];
cout<<"Input NO. of Petrol Pumps-->";
cin>>n;

cout<<endl<<"Enter Petrol -->";
for(int i=0;i<n;i++)
cin>>p[i];

cout<<endl<<"Enter Distance -->";
for(int i=0;i<n;i++)
cin>>d[i];

optimize(n,p,d);

system("PAUSE");
return 0;
}

- coderrr October 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The above solution runs it O(n) time. It is simply based on idea that if there is path from a->b->c->d then there is no way there can exist path from b->c->d or c->d i.e. after everytime we start from the next node of previous failure.

- coderrr October 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

list<int> findStartPoints(int* petrols , int* distances, int noOfPumps)
{
	print("petrols are : \t", petrols, noOfPumps);
	print("distances are : \t",distances,noOfPumps);

	list<int> validStartPoints;
	// find the complete paths validity 
	// i.e. before reaching any station j the sum of petrols till that point should be more than or equal to the distance covered till that
	// let x be the start point p[x] + p[x+1] ... + p[j-1] >= d[x] + d[x+1] + ..... d[j-1] 
	// where  x < j <= (x-1) such that if x > noOfPumps then x resets to 1

	for( int pumpId = 0 ; pumpId < noOfPumps ; pumpId++ )
	{
		cout << "checking for start point : " << pumpId << endl;
		int pv = 0 ;
		int distance = 0;
		int i;
		cout << "The last pump would be : " << (pumpId + noOfPumps - 1) % noOfPumps << endl ;
		for( i = pumpId ; i != (pumpId + noOfPumps - 1) % noOfPumps ; i = (i + 1) % noOfPumps )
		{
			pv += petrols[i];
			distance += distances[i];
			cout << "from " << i << " to " <<  (i + 1) % noOfPumps << " petrol = " << pv << " and distance = " << distance << endl;
			if( pv < distance )
				break;
		}

		if( i == ( (pumpId + noOfPumps - 1) % noOfPumps ) )
		{
			cout << "So this is a valid start point.\n" ;
			validStartPoints.push_back(pumpId);
		}	
		else
			cout << "This is not a valid start point \n";
	}

	return validStartPoints;
}

- nitiraj.rathore December 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi
Actual answer for this question is no need to do the calculation,
the condition is it is a circular linked list,
Do the following steps.
1. Group the nodes while huge fuel available, medium fuel available, less fuel is available, and finally no fuel is available,
I think hardly it will take 4 to 5 groups.

2. start from heavy fuel available nodes, and traverse towards the next medium or less fuel valuable states,
3. suppose medium fuel group is behind heavy fuel group start from medium fuel nodes,
4. suppose less fuel is behind the heavy fuel and medium fuel is ahead of the heavy fuel do the mind calculation is the fuel in less fuel group sufficient to travel and reach the heavy fuel grip, if not start from the heavy fuel group.
5. like this you have to decide and finally travel to no fuel group or very less fuel group. this is the logic behind this puzzle.

- chandrashekhar JP February 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Further use the below logic
1.
struct node {

struct node *next;
int liter_petrol;
int distance;
};

find the node()
{
int petrolarray[numberofnodes];
int distancearray[numberofnodes];
struct node * traverse = node1_ptr;
int i = 0;
while ( traverse->next != node1_ptr) {

petrolarray[i] = liter_petrol;
distancearray[i] = distance;
i++;
}

for ( i = 0; i < numberofnodes; i++) {

printf ("node = %d\t volumeofpetrol = %d\t distance = %d\n",
i, petrolarray[i], distancearray[i] );

}

printf ("Now decide where to start based on the output\n");
}

- chandrashekhar JP, jcpura, cnhalli, tumkur,karnataka,india February 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Further use the below logic
1.
struct node {

struct node *next;
int liter_petrol;
int distance;
};

find the node()
{
int petrolarray[numberofnodes];
int distancearray[numberofnodes];
struct node * traverse = node1_ptr;
int i = 0;
while ( traverse->next != node1_ptr) {

petrolarray[i] =traverse-> liter_petrol;
distancearray[i] =traverse-> distance;
traverse = traverse->next;
i++;
}

for ( i = 0; i < numberofnodes; i++) {

printf ("node = %d\t volumeofpetrol = %d\t distance = %d\n",
i, petrolarray[i], distancearray[i] );

}

printf ("Now decide where to start based on the output\n");
}

- Chandrashekhar JP February 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1 : At each petrol pump , do the calculation (petrol - distance). This number will be either +ve, -ve or zero.

Step 2: Now find the sequence whose sum is maximum. Can be done in O(n)

Step 3: The start point of this longest sum sequence will be the point from which we should start.

- Aditya B May 14, 2014 | 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