## Bloomberg LP Interview Question for Software Engineer / Developers

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];
{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...");

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).

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.

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)

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.

Comment hidden because of low score. Click to expand.
0

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

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

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

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.

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.

Comment hidden because of low score. Click to expand.
0

@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)

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...

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!

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

yes, bejafella's got it

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???

Comment hidden because of low score. Click to expand.
0

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

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

What if the gas tank is limited in capacity ?

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

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).

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.

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

class GasStation {

public static int canCompleteCircuit(int[] gas, int[] cost) {
if(gas == null || cost == null) return -1;

int total = 0;
int upToNow = 0;
int startPos = 0;
for(int i=0; i<gas.length; i++) {
int delta = gas[i] - cost[i];
if(upToNow >= 0) upToNow += delta;
else {
upToNow = delta;
startPos = i;
}
total += delta;
}

}

public static void main(String[] args) {
int[] gas = {3,5,7};
int[] cost = {8,4,3};
System.out.println(canCompleteCircuit(gas, cost));
}
}

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.

### 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.