Simple Proof to the Container with Most Water Problem | Hacker News Reader

Simple Proof to the Container with Most Water Problem

leimao.github.io

56 pointskeyboardman24 comments

That dude’s bio is... brutal.

“I was a Ph.D. candidate in the Department of Biochemistry at Duke University, working on DNA repair mechanisms. There, after spending almost four years, I systematically proved that most of the projects, theories and guidance from the advisor, which I was forced to do and obey, were wrong. To me, a sound Ph.D. degree or research position job title does not tell anything about the person’s capability of solving a problem and whether the person is a true scientist or not. I have already proved that I am better than most of the people there. In 2016, I decided to leave Duke University, with my own glory, without a Ph.D. degree.”

https://leimao.github.io/cv/

Good lord, that takes grit to say the least. I would love to hear some war stories from this time, unfortunately there are no anecdotes or any of his dis-proofs on his blog (at least that I could find).

I lucky-guessed and found the author on HN[1], but there are no @mentions here to ask them for some anecdotes.

1: https://news.ycombinator.com/user?id=leimao

What he's describing is perfectly plausible. If you don't have a strong enough relationship with your department chair and committee to push back or are dependent on your advisor for funding the eject button is best.

Not sure if laying final judgment down in your cv really helps anyone. I don't know what goal it achieves. Write that letter to the department head in question and set the story straight. He's not reading your CV.

CV is also known as curriculum vitae, which (very) roughly translates to biography (as "events of life"). Following that and not a learned format I'd argue that all events that influenced one's professional career are welcome to be mentioned

Definitely not. You're degrees, publications, and jobs but not personal anecdotes. Except for goals and research or teaching philosophy.

The official leetcode endorsed proof is quite simple: https://leetcode.com/problems/container-with-most-water/disc...

It just doesn't bother with the counting argument that OP makes.

Also, the largest cross section of a cube is a rectangle of size √2, not a hexagon (3/4 √3). The largest regular polygon cross section is a hexagon.

http://mathworld.wolfram.com/Cube.html

I am not a mathematician, but the problem seems easier to intuit. Like a lot of math problems, a formal proof is annoying but I definitely think a regular joe can convince himself why this works.

Start at i,j with heights h_i < h_j. Then we know that if i is involved in the solution, it must be paired with j.

We know this because if it's paired with any other point, the other point is either: a. shorter than h_i, which means it's shorter than h_j. And since it's also closer to i than j is, the area is smaller. b. equal or taller than h_i. But this will never make a larger area since the height will be limited by h_i, but the distance smaller than the distance from i to j.

So we can stop considering i as part of the solution space.

Of course that doesnt make it a good interview question. It relies on a brilliant stroke of insight, rather than relying on established data structures or algorithms.

I think it's much more clear if you start by trying to apply the constraint to the brute force algorithm.

The water container area is the distance the two sides are apart (width), by the height of the shorter side [therefore, the longer side acts to mimic it].

Doing brute force on array $[n_1 n_2 ... n_k]$;

You'd naturally start at $n_1$ and calculate volume $V(n_1, n_k)$ and work your way inwards calculating each volume. However, if at any point $n_1$ is the shorter side, then the secondary side $n_j$ now mimics $n_1$ in height; and therefore, any new side closer to $n_1$ cannot increase the height of the container (but would decrease the width, and therefore area).

Then you'd continue the same with $n_2$, breaking iteration when $n_2$ becomes the shorter side or if $n_2$ cannot develop a greater area than $n_1$ did (either n_1 > n_2 or oldArea > n_2 * width).

etc.

As a sometime mathematician, I'd say that's a perfectly complete and formal proof.

Nitpick about the leetcode description of the problem:

https://leetcode.com/problems/container-with-most-water/desc...

The way it’s written, the walls are uniformly spaced — located at their corresponding integers in the height array.

But the picture shows them as non-uniformly spaced: the wall to the right of the first red has a bigger separation than all the others.

Why is the container not the one contained between the lines of height 8, instead of the line 7 height?

Either "walls" are porous or they aren't.

Because they're only at a distance of 5 from each other.

7x7 > 8x5.

I actually looked through a few LeetCode problems a couple months back and had a brief panic that I found tricky/nonintuitive to formally prove from first principles problems that were apparently "easy" or "trivial" to just intuit (as LeetCode commenters tend to characterize, anyway). I was never satisfied with people's "oh, just do xyz and it makes sense" - I just assumed I was dumb... Still not sure what to make of this - I'm not the only one, I guess... ?

If you've ever checked out "Cracking the Coding Interview", you'll see there are many "algorithmic tricks" people can use to quickly improve performance while performing operations. An example from this problem, the author uses "a two pointer approach" to inch the head and tail pointers closer to one another, to cover all pertinent combinations and reduce run time. There are all kinds of little idioms, and many people that would take the time to comment on LeetCode forums are likely well versed in them.

Is this the kind of thing they are asking in interviews these days? I guess it is nice that this author can prove the correctness of their solution, but what's up with that code? Why is what would otherwise be a perfectly good free function instead a member function of a class with no other functions? Why instead of the usual C++ style of a function taking start and end iterators as arguments does this function take a mutable ref to vector<int>? Are these "leetcode" idioms? Does this site just exist to poison the minds of young developers?

Yes, the code style is dictated by leetcode. It feels a bit "Java" to use a class instead of free function, but seems pretty irrelevant in the grand scheme of things.

The starting point for this problem is provided as:

    class Solution {
    public:
        int maxArea(vector<int>& height) {
        
        }
    };

I saw this problem in an interview about a decade ago, at one of the larger tech companies. Google or something. Supposedly Google doesn't do "algorithmic" interviews like this anymore.

> Supposedly Google doesn't do "algorithmic" interviews like this anymore.

That's not true. In fact if anything that's all they do now.

> That's not true. In fact if anything that's all they do now.

That's not true. It is however, still a majority of what they do.

Oh they do. Some ppl have had this exact question in recent times per leetcode tags

It's an algorithm problem, not a C++ problem. Also, iterators prevent random access. You can always get iterators from a vector if you need them. And mutability is provided for convenience and because const doesn't matter in this situation.

Perhaps your not aware of C++ random_access iterators? You can indeed do random access with iterators and this functionality is integral to many standard library algorithms.

http://www.cplusplus.com/reference/iterator/RandomAccessIter...

See that’s the kind of information I want to surface in an interview: candidate thinks C++ doesn’t have random-access iteration. No hire.

Reply on news.ycombinator.com