Palantir Technologies

  www.palantir.com
  www.palantir.com

Interview Question

Business Development Engineer Interview Palo Alto, CA

Given a fleet of 50 trucks, each with a full fuel tank and

  a range of 100 miles, how far can you deliver a payload? You can transfer the payload from truck to truck, and you can transfer fuel from truck to truck. Extend your answer for n trucks.
Tags:
Answer

Interview Answer

22 Answers

8

So 50 trucks is solvable but annoying. The answer depends on payload size, also if the truck needs to return. If we assume no return and 1 truck can carry the payload. Make the number of trucks 64 for even powers of 2. The trucks all take off together and every 50 miles they all have half full tanks. Half of the trucks are sacrificed to refill the other half. Number of trucks goes from 64 -> 32 -> 16 -> 8 ->4 ->2 -> 1. So 6 splits * 50 miles = 300 + last truck has 100 miles. 400 for 64 trucks. 50 can be solved with annoying fractions. General answer is 50 * log(base2) of n + 100. :-)

Anonymous on Jan 12, 2010
0

Yes, your assumptions are correct, and so is your solution.

Anonymous on Jan 12, 2010
4

The answer is 450 miles. it is the sum for n=1 to 50 of [ 100 / (50-n) ]
After 2 miles you would transfer all of the fuel from one truck, and could fill all 49 of the other trucks. (100mile range / 50 trucks = 2 miles before the first truck could be emptied of all fuel and is not needed to carry any fuel) at that point you only have 49 trucks, so 100/49 is the distance before you park the second truck. After parking 49 trucks you would have one full truck of fuel that would finish the last 100 miles.
General solution for X trucks with Y range is Sum for n=1toX of [Y / (x-n)]

DareN on Jan 16, 2010
3

My equation was off by one, need to sum for n=0to49, not 50. (since 100/(50-50) is infinite obviously it was in error.)

DareN on Jan 16, 2010
0

The answer is quite simple. You can deliver the payload an infinite distance. Since you have 50 trucks at your disposal you can run one truck with the payload until its near empty then transfer the payload to a full truck. The near empty truck can re-fuel and then drive towards the destination re-fueling as needed. Once the truck with the payload is near empty it can transfer the load to a truck that has recently been refueled.

Ed on Jan 18, 2010
0

The answer is quite simple. You can deliver the payload an infinite distance. Since you have 50 trucks at your disposal you can run one truck with the payload until its near empty then transfer the payload to a full truck. The near empty truck can re-fuel and then drive towards the destination re-fueling as needed. Once the truck with the payload is near empty it can transfer the load to a truck that has recently been refueled.

Ed on Jan 18, 2010
0

Ua… Everyone needs to try again...

Two trucks go 33 1/3 miles out and the second truck gives ½ of its remaining 2/3 of a tank to the other truck who parks and waits for the other truck to go back. It has enough fuel to return and comes back out with another truck who does the same thing but now we have two trucks 33 miles out and both with 2/3 of a tank or 66 2/3 miles of fuel remaining. With this method of inch worming and returning to refuel you can achieve a spacing of 33 1/3 miles between each truck and continue to refuel the entire chain. Only then once the entire refueling chain is stretched out to the range of 1666.66 miles you can have a truck be totally fueled 100% and then go either 50 more miles and still be theoretically able to return back to home base or 100 miles to sacrifice the truck for a delivery giving you a maximum range of (n + 1) * (1/3 of range) yielding a potential range of 1766 2/3 miles. You use a lot more fuel getting out to where you want to go but your range is increased well above the 400 miles range and the trucks aren’t lost.

JP on Jan 18, 2010
0

It is 1800 not 1766... I did the same 0 to 50 vs 1 to 50 miscalcuation. 100 + 51*100/3 = 1800

JP on Jan 18, 2010

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.

0

And if you want to be creative - 25 of those trucks can toe fully-fueled 25 trucks.

Wanna try again?

Jixavius on Jan 18, 2010
6

This is a straightforward programming problem. Clever solutions such as allowing the other trucks to refuel and allowing other trucks to tow extra trucks full of fuel rarely impress the interviewer.

The simplest solution involves recursion, or induction.
Imagine a function f(n) where f(n) is the distance n trucks can carry the load, the problem defines f(1)=100, and we're asked to solve for f(50), so our job is to solve for f(n) in terms of f(n-1), f(1) and n.

It's safe to assume each truck, including the fully loaded truck will travel the same distance and that fuel is used uniformly over the distance. So with n trucks, the trucks should travel just far enough that n-1 trucks have room in their tanks for the nth truck's fuel, then transfer an solve for n-1.

This equation is f(n) = f(1)/(n) + f(n-1)
(All perl vs python vs ruby/etc wars aside)
Plugging this into a simple scripting language such as perl is an easy way to solve this:

sub f{
  my $n = shift;
  return 100 if($n == 1);
  return f(1)/($n) + f($n-1);
}

print "50: " . f(50) . "\n";'

On the command line, this gives a quick answer:

> perl -e 'sub f{ my $n = shift; return 100 if($n==1); return f(1)/($n) + f($n-1);} print "50: " . f(50) . "\n";'

50: 449.920533832942

Approximately 449.92 miles with 50 trucks.

The recursive subroutine above will suffice as a general solution in terms of n.

Joe on Jan 18, 2010
2

Not a programmer but this is how I solved it. You obiously want to shed a truck as soon as the other trucks have room for the fuel from one truck. Since trucks have a range of 100 miles when all trucks have a tolal of 100 miles you can refill all truck s from one truck's remaing fuel. 100 miles divided by 50 trucks is 2 so two miles is the first refueling point at which time you will lose one truck. So I set up a Excel worksheet. Column A number of trucks beginning with 50 down to 1. Column B has formula 100/A1. Sum column B is 449.9205. Same as other s have come up with.

Dan on Jan 19, 2010
0

This would depend on the fuel efficiency of the trucks. You could almost certainly get much farther by having the first truck tow all 50 others, once it runs out of fuel take it out of the train and continue on. One truck pulling others will still get better fuel efficiency than all trucks by themselves. ie you get 10mpg from a truck by itself, and 7 with it pulling the others, vs all using 10mpg at once.

MH on Jan 19, 2010
0

50 trucks with a 100 mile range. The question does not state that all the trucks have to be in the same place to start. It's pretty easy. All the trucks are 100 miles apart. Therefore you can transfer the payload up to 5000 miles.

Carl on Jan 19, 2010
1

I hate these problems. The interviewer is normally probing for a specific answer, and unwilling to understand that the question is fundamentally flawed, and whit they are looking for is being asked in obtuse way, often for the a wrong answer.

Much of hte answer depends on what is or is not available in this crazy mad max world. Is there no more fuel in the world? Can the trucks refuel at the main depot? Is it okay to leave trucks parked on the side of the road? Sometimes the interviewers are asking about how you validate assumptions or deal with your own invalid assumptions of the world... normally not.

Of course the normal answer would be 50 or 45 miles range. Shifting loads and siphoning fuel is a pita.

The next answer would be get a CFN card and trusted drivers, then range is more limited by periodic maintenance i.e. oil changes.

Failing that, as was done during the 1970s oil crunch, get some 50 gallon drums and tie them up to the back of the headache bar. Each gallon of diesel weighs about 8 lbs, and can get you about 4 miles down the road. The united states is about 3000 miles wide. That takes about 6000 lbs of fuel. To get back another 6000. It's not very efficient, but you won't get stuck on the side of the road. due to fuel reasons.

But if you want a wanky CS answer. ( similar to JP's answer, but carrying it to stupidity).

With trucks returning to an infinitely fueled depot: ( my favorite extra world pieces).
By driving two trucks too 50 minus a smidgen miles. Park a truck with a driver in it, and it will have a smidgen of fuel in it. The other truck will keep making trips from 0 to 50 minus a little and transfer it's excess fuel to the parked truck. Eventually there is a fully fueled truck 50 (minus a little) miles from the depot. This chain can be extended one link at a time like some horrible towers of Hanoi problem. Finally you end up with a line of n-1 fully fueled trucks. This line alone stretches 2450 miles (minus 49 smidgens). The last truck in the line could round trip out to 2500. ( n * range/2)

After you have a row of fully fueled rucks 2450 miles long, there might be something funky you could do with it to extend the range. Truck 1 would have 1/2 a tank at the next truck, 25 miles into the second leg it could park and the second truck would then have a full tank at 75 miles from base, but not be able to return. Scale this up across the entire line of trucks. ... one short throw away perl script later... looks like that'll get you about another ~100 miles. so almost 2600 miles with parked empty trucks. Maybe a nonlinear spacing would be beter, not sure.. don't care really.

The fundamental answer is that most CS wanking stuff is often irrelevant in the real world. Money money money, cost cost cost. 50 trucks is somewhere in the piles of money range, quit wasting fuel.

gulfie on Jan 19, 2010
1

very simple to understand solution

public class test
{
    public static void main(String [] args)
    {
        int num=50;
        double result=0;
        for(double i=num;i>0;i--)
        {
            result=result+100/i;
        }
        System.out.println(result);
    }
}

Anonymous on Mar 18, 2010
3

Wow,
Daren up top is definitely correct. I propose it's a little simpler than that.
It is just the summation of n=1 to n=50
for
100/n

Call the last truck the first truck, n=1. being full, it can go 100 miles.
when there are 2 trucks left, 50 miles
repeated down to the starting fleet of 50 trucks going 2 miles.

pretty sure using x-n doesn't bring the world down on itself, but it's unnecessary and makes that 49 to 0 error much easier to fall for.

Ca K on May 5, 2010
0

@Daren Yes I reached the same equation as well. Sum for n=0 to 49 of [ 100 / (50-n) ]
A quick spreadsheet run shows the result as 449.92 miles. It's a horrible and pointless thing to ask this question in an interview without the help of a calculator or spreadsheet.

Engin on Jul 8, 2011
0

I guess my brain also oversimplified the problem. Since it was never stated that all 50 trucks needed to start from the same location I spaced them 100 miles apart towards the destination. If fuel is easier to transfer at each 100 mile point transfer fuel; else transfer payload for a maximum payload delivery distance of 500 miles,

OR

Number_of_Trucks * Range = Maximum_Payload_Delivery_Distance

MarkFJ on Nov 28, 2011
2

I'm a software engineer, but would have answered this completely differently.
You have 50 trucks with a value of say $70,000 each, and 50 full fuel tanks.
Sell 49 trucks, drive the 50th to the local fedex and and tell them where to deliver the payload . With the money remaining buy a villa in the South of France and retire.

Angus on Jun 21, 2012
0

ques is how far u can deliver the payload that totally depends on the ranging limit of fleet of trucks that is 100 miles . it means they cannot move before 100 miles even if we transfer the fuel one after the another it has no sense here , let suppose one truck travels 100 miles (max) , we are not considering that it get emptied before reaching 100 miles after that next truck travels , so the total of distance that could be travelled is 100*50 miles = 5000 miles (this is the max distance the payload can be taken ) while the least could be 100 miles .

PALAK SINHA on Sep 27, 2014

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up