For the last two weeks, I’ve had a bunch of interviews and code challenge tasks I was taking which took up a lot of my time. Add that to #DadLife and the result is two weeks with no content. The pressure is off for the moment so I’m picking it up again. So for today:
We are given an N length array with numbers ranging between a few negative million to a few positive million. If there exists at least one 3-tuple (P, Q, R) combination of values that satisfy the conditions below, return 1 otherwise return 0.
- The values A, B, C represent indices of A
- 0 <= P < Q < R < N
- A[P] + A[Q] > A[R]
- A[P] + A[R] > A[Q]
- A[R] + A[Q] > A[P]
The brute force approach worked ok, but as usual didn’t make the performance tests.
Here we have to check a few conditions.
- First and easiest, A[P] should always be less than the sum of A[Q] and A[R].
a < b + c
- Second A[P] should be greater than A[Q] – A[R] and A[P] should be greater than A[R] – A[Q], we get these from solving the equations we get in the conditions and can combine the two into one check
a > Math.abs(b - c)
And thus our first attempt looks like:
We are obviously looping too much. So I decided to optimise this by first introducing a sort. This should then hopefully reduce it down to one loop. Here is where I made a terrible mistake that messed me up for the better part of 2 hours.
Do you see that condition that checks if our three numbers match our conditions? Yeah, when switching to a sorted approach I was using I as my iterating variable and accidentally inserted 1 instead of i on one of my conditions. So instead of this:
I had this:
If you can’t see the difference, welcome to the club. So it passed a few local tests by happy accident but wouldn’t pass the larger tests. I spent a lot of time trying to figure out what was wrong until I was pulling my locks out. Then after a little break, I came back and saw it.
Correcting the typo fixed the issue and the code passed everything.
Typos are evil.