Bloomberg LP Interview Question Software Engineer / Developers

  • bloomberg-lp-interview-questions
    0
    of 0 votes
    19
    Answers

    There are n gas stations positioned along a circular road. Each has a limited supply of gas. You can only drive clockwise around the road. You start with zero gas. Knowing how much gas you need to get from each gas station to the next and how much gas you can get at each station, design an algorithm to find the gas station you need to start at to get all the way around the circle.

    - DPS Prog on May 17, 2009 Report Duplicate | Flag
    Bloomberg LP Software Engineer / Developer Brain Teasers



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

let's say gasMinusDist represents value of gas at a station minus the distance from this station to next station.

take example: 5,-10,4,6,-10,5,5 as 7 values. Since this is circular , so we can write this array as 5,-10, 4,6,-10,5,5,5,-10,4,6,-10,5 so that if we start from last gas station, we can still go through the round

code will look like

int delta=0; int count=0;
for int(i=0;i<2*n-1;i++)
{
delta+=gasMinusDist[i];
if (delta<0)/*not fit to start with this iteration
{delta=0;count=0;continue;}
count++; if (count==n) break;
}
if (count ==n)printf("start round from gas station number %d,i-count+1);
else printf("not possible...");

- nutcracker on February 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is what Cormen has to say about the above problem but i quite well did not understand the solution..

The optimal strategy is the obvious greedy one. Starting will a full tank of gas,
Professor Midas should go to the farthest gas station he can get to within n miles
of Newark. Fill up there. Then go to the farthest gas station he can get to within n
miles of where he Þlled up, and Þll up there, and so on.
Looked at another way, at each gas station, Professor Midas should check whether
he can make it to the next gas station without stopping at this one. If he can, skip
this one. If he cannot, then Þll up. Professor Midas doesn’t need to know how
much gas he has or how far the next station is to implement this approach, since at
each Þllup, he can determine which is the next station at which he’ll need to stop.
This problem has optimal substructure. Suppose there are m possible gas stations.
Consider an optimal solution with s stations and whose Þrst stop is at the kth gas
station. Then the rest of the optimal solution must be an optimal solution to the
subproblem of the remaining m − k stations. Otherwise, if there were a better
solution to the subproblem, i.e., one with fewer than s −1 stops, we could use it to
come up with a solution with fewer than s stops for the full problem, contradicting
our supposition of optimality.
This problem also has the greedy-choice property. Suppose there are k gas stations
beyond the start that are within n miles of the start. The greedy solution chooses
the kth station as its Þrst stop. No station beyond the kth works as a Þrst stop,
since Professor Midas runs out of gas Þrst. If a solution chooses a station j < k as
its Þrst stop, then Professor Midas could choose the kth station instead, having at
least as much gas when he leaves the kth station as if he’d chosen the j th station.
Therefore, he would get at least as far without Þlling up again if he had chosen the
kth station.
If there are m gas stations on the map, Midas needs to inspect each one just once.
The running time is O(m).

- Cookie on May 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

For each station, find (distance that can be traveled with gas available in that station - distance to next station). Create an array of these values and find the maximum positive consecutive substring. You have to start driving at the beginning of this substring.
PS: Remember that the stations are circularly arranged, so should the array. So it is possible for you to start on the "last" station and still go around to all of them.
PPS: Another thing that can be done is to ensure that sum of all distances to be traveled is less than distance that can be traveled with available gas. Otherwise, it makes not difference where you start, you will get stranded.

- karthikvaidy on June 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Basically you have two arrays, gas_needed[n] and gas_at_station[n]. However, I would work with a third array which is the difference gas_needed - gas_at_station. Let's call this array gas_remaining[n](R[n])
Sum(Ri) where m is the nth consecutive station after i. i is the starting station if
i->m
the sum never goes negative.

O(m)

- Bajanfella on June 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) time is easy. Start at each and just simulate it out.


O(n) time is possible, but I won''t spoil it for you.

- LOler on May 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

its not spoiling ... its a platform if u have a better solution u present it here else nope...

- Roshan on December 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check Cormen for this, Its in exercise section of some chapters.....

- CyberPhoenix on May 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Cookie, no, that's not the problem. Therefore that's not the solution :))

I won't give the full solution how to do it in O(n), but I will provide all the hints.
The problem can be cast into a modified version of the very know problem: Maximum Consecutive Subsequence (of length 2*n-1). If during the search (in linear time for Maximum Consecutive Subsequence) you find a positive sum of length n, you found the solution to this problem.

- Marian on May 26, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Bajanfella, Your algorithm is O(m^2) instead of O(m). Basically, you are just simulating with different starting points.

- noname on July 10, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@noname, I think you're right. You'll have to keep changing the starting position (upto a maximum of m times) and trying till you find a sum that never goes negative. So it would be O(m^2)

- deepak on January 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

making use of a part of data str given by BajanFella, Lets take all the three arrays. Now in the arrya gas_remaining[] find the maximum subsequence which can be done in O(m), now starting at the first element of the subsequence solves the problem, thats it, we're done...

- smartAss on July 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bejafella's answer is the correct one...and I must say this quite a popular interview question!

- googler on August 13, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

yes, bejafella's got it

- john on August 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if i have a car with 'zero' gas, how would i start the car in the first place???

- vipul k. on September 21, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That is why you imagine your car placed at a station first, fill the tank and then and start moving.

- Anonymous on January 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What if the gas tank is limited in capacity ?

- S.M on October 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

then change your CAR!

- Anonymous on January 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A linear solution for this problem,
For every station a ( starting point of the trip)
calculate the carry over gas from station a to other stations in the trip , if there is a negative carry over mark this station unsuitable for starting the trip. ( this can be done O(n) for all stations).

- Anonymous on January 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

See my O(N) time and O(1) space implementation at stackoverflow.com/a/13502863/1832586 along with description of how it works.

- ashot madatyan on November 21, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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