Giter Club home page Giter Club logo

Comments (8)

GoogleCodeExporter avatar GoogleCodeExporter commented on July 26, 2024
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

Original comment by [email protected] on 5 Apr 2013 at 6:16

from elements-of-programming-interviews.

GoogleCodeExporter avatar GoogleCodeExporter commented on July 26, 2024
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.

Original comment by [email protected] on 5 Apr 2013 at 7:24

from elements-of-programming-interviews.

GoogleCodeExporter avatar GoogleCodeExporter commented on July 26, 2024
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.

Original comment by [email protected] on 5 Apr 2013 at 7:31

from elements-of-programming-interviews.

GoogleCodeExporter avatar GoogleCodeExporter commented on July 26, 2024
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.

Original comment by [email protected] on 5 Apr 2013 at 7:38

from elements-of-programming-interviews.

GoogleCodeExporter avatar GoogleCodeExporter commented on July 26, 2024
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

Original comment by [email protected] on 5 Apr 2013 at 7:42

from elements-of-programming-interviews.

GoogleCodeExporter avatar GoogleCodeExporter commented on July 26, 2024
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). 

Original comment by [email protected] on 5 Apr 2013 at 7:59

from elements-of-programming-interviews.

GoogleCodeExporter avatar GoogleCodeExporter commented on July 26, 2024
ahh, you have convinced me that the robot algorithm works. My mistake. Thank 
you for your time in working it out.

Original comment by [email protected] on 5 Apr 2013 at 8:22

from elements-of-programming-interviews.

GoogleCodeExporter avatar GoogleCodeExporter commented on July 26, 2024
Hey Mitesh,

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

Original comment by [email protected] on 5 Apr 2013 at 4:42

  • Changed state: Fixed

from elements-of-programming-interviews.

Related Issues (17)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.