Introduction algorithm is incorrect, also implementation is missing from about elements-of-programming-interviews HOT 8 CLOSED

Hey Mpatel,

Thanks for your reporting. In fact, Problem 3.3 is identical to the stock price 
problem. We did this before because the stock price problem is kind too 
well-known and we wanted to remodel it such that readers who already know the 
stock price problem still pay sometime to uncover the true formulation of this 
problem. Please take a look at the problem part of Problem 3.3, and you will 
notice that we said Problem 3.3 is the another application of the stock price 
problem. The link to the code is at 
https://code.google.com/p/elements-of-programming-interviews/source/browse/trunk
/Robot_battery.cpp.

About the errata, we do have an internal use one which tracks all bugs we found 
but it is not organized very well. From what you got, it should be the most 
up-to-date one so most of that will probably not be useful to you.

Please let us know if you have any problem, and we are glad to help you.

Tsung-Hsien

I see now that the robot battery problem is intended to be the same as the 
stock trading problem. However, the robot battery problem is an 
over-simplification of the stock problem. For stocks, you must buy before 
selling. The robot does not have such a constraint. The stock problem cannot be 
solved in O(n) time.

Consider that for the stocks, the largest delta of low-to-high points occurs in 
the first half of the array, but the lowest point is in the second-half of the 
array (and has a smaller delta to the next high).  

The algorithm needs to figure out which delta to take, the one in the left-half 
or the right-half.

The robot battery algorithm does not remember the value of the left-half (which 
is actually the best).  It thinks the minimum is the one in the right-half, and 
greedily takes that to be the new "min". Bad idea.

Hey Mpatel,

The robot battery problem is the same as the stock price problem. Because a 
high point appearing before a low point does not make effect to the battery 
volume; however, a low point appearing before high point may make effect to the 
battery since we need the use the energy in the batter to conquer the height 
difference. These two scenarios are identical to the stock price problem; we 
don't care about a high price before low price since we won't sell on that, and 
we do care a low price before high price since we might gain more.

Tsung-Hsien,  
Please consider the scenario I listed above, where the left-half of the array 
is better than the right-half (but the right-half has the lowest point). Do you 
still think the robot algorithm works in this scenario?
-Mitesh

Hey Mitesh,

Let's consider a small example A = <3, 10, 1, 5> where the first-half contains 
<3, 10> and the second-half contains <1, 5>. We can see that the first-half 
contains the largest delta, which is 10 - 3 = 7, and the second-half contains 
the lowest point, which is 1.

Now, let's run the algorithm in 
https://code.google.com/p/elements-of-programming-interviews/source/browse/trunk
/Robot_battery.cpp step by step, we focus on the variable values in line 15 and 
16, which are capacity (the answer) and min_height:

1. Process A[0], which is 3: capacity = max(0, 3 - 
numeric_limits<HeightType>::max()) = 0, min_height = 
min(numeric_limits<HeightType>::max(), 3) = 3.
2. Process A[1], which is 10: capacity = max(0, 10 - 3) = 7, min_height = 
min(3, 10) = 3.
3. Process A[2], which is 1: capacity = max(7, 1 - 3) = 7, min_height = min(3, 
1) = 1.
4. Process A[3], which is 5: capacity = max(7, 5 - 1) = 7, min_height = min(1, 
5) = 1.

From the above trace, you probably already noticed the core of this algorithm 
is that every height only needs to care about the minimum which is appeared 
before itself, which we use min_height to keep. By keeping min_height, we 
basically examine all potential pair without explicitly examining all pairs 
(n^2). 

ahh, you have convinced me that the robot algorithm works. My mistake. Thank 
you for your time in working it out.

Hey Mitesh,

Not a problem! Thanks for your report, and we probably will rewrite part of the 
solution to make it more clear.