Comments (8)
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.
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.
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.
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.
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.
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.
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.
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)
- Broken Link for New Source Code HOT 5
- solution 3.6 error HOT 2
- solution 3.7 error HOT 3
- solution 4.1 error HOT 3
- problem 3.7 bugs/suggestions... HOT 3
- problem 3.4 the recurrence equation HOT 1
- Patch for /trunk/Subseq_cover.cpp HOT 1
- Patch for /trunk/Rebuild_BST_postorder.cpp HOT 2
- Patch for /trunk/Sudoku_solve.cpp HOT 2
- Problem 8.10 resize problem HOT 1
- 10.2 Indirect Sort Output Error HOT 1
- Patch for /trunk/Remove_kth_last_list_template.cpp HOT 3
- stringToInt in problem 5.6 accepts invalid input "-" HOT 1
- Solution is incorrect for problem 15.22 Scheduling Tutors HOT 2
- Version 1.3.0, Problem 6.4 (1.) Description is there in the book, but algorithm is missing HOT 1
- Broken links HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
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.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from elements-of-programming-interviews.