Palantir Technologies

www.palantir.com
Engaged Employer

## Interview Question

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:

10

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
1

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

Anonymous on Jan 12, 2010
7

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.

This post has been removed.

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
3

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

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
0

Ok first determine the payload capacity of a truck. How many trucks required for payload. Assign one or mire truck to carry the fuel of other trucks which wont be delivering

Anonymous on May 4, 2015