Deepest pit of an array

Question

Following is based on a problem description from a Codility test, as a task in an interview.

---

DeepestPit - problem description

A non-empty zero-indexed array B consisting of M integers is given. A pit in this array is any triplet of integers (X, Y, Z) such that:

• 0 ≤ X < Y < Z < M
• sequence [B[X], B[X+1], ..., B[Y]] is strictly decreasing, i.e. B[X] > B[X+1] > ... > B[Y]
• sequence B[Y], B[Y+1], ..., B[Z] is strictly increasing, i.e. B[Y] < B[Y+1] < ... < B[Z]

The depth of a pit (X, Y, Z) is the number min{B[X] − B[Y], B[Z] − B[Y]}.

For example, consider array B consisting of 10 elements such that:

B[0] = 0
B[1] = 2
B[2] = 7
B[3] = -4
B[4] = 0
B[5] = 4
B[6] = 0
B[7] = -6
B[8] = 4
B[9] = 6

Triplet (2, 3, 4) is one of pits in this array, because sequence [B[2], B[3]] is strictly decreasing (7 > −4) and sequence [B[3], B[4]] is strictly increasing (−4 < 0). Its depth is min{B[2] − B[3], B[4] − B[3]} = 4. Triplet (2, 3, 5) is another pit with depth 8. Triplet (5, 7, 8) is yet another pit with depth 10. There is no pit in this array deeper (i.e. having depth greater) than 10.

Write a function:

function deepest_pit(B)

that, given a non-empty zero-indexed array B consisting of M integers, returns the depth of the deepest pit in array B. The function should return −1 if there are no pits in array B.

For example, for the above array B, the function should return 10, as explained above.

Write an efficient algorithm for the function.

Assume that:

• M is an integer within the range [1..1,000,000];

• each element of array B is an integer within the range [−100,000,000..100,000,000].

(A previous test instead stated the complexity conditions as follows.)

Complexity:

• expected worst-case time complexity is O(M);
• expected worst-case space complexity is O(M), beyond input storage (not counting the storage required for input arguments).

---

My solution, as follows, gets a task score of 100% (100% for correctness and 100% for performance).

function deepest_pit(B) {
    // write your code in JavaScript (Node.js 8.9.4)

    var M = B.length,
        depth = -1;

    if (M < 3) {
        return depth;
    }

    var X, Y, Z;
    var i = 0, j, k;

    while (i < M - 2) {
        X = B[i];
        // console.log("i = ", i, "X = ", X)
        j = i + 1;
        while (B[j] < B[j - 1] && j < M - 1) {
            j++;
        }
        if (j === i + 1) {
            i++;
            continue;
        }
        j = j - 1;
        Y = B[j];
        // console.log("i = ", i, "Y = ", Y)
        k = j + 1;
        while (B[k] > B[k - 1] && k < M) {
            k++;
        }
        if (k === j + 1) {
            i++;
            continue;
        }
        k = k - 1;
        Z = B[k];
        depth = Math.max(depth, Math.min(p - Y, Z - Y));
        // console.log("depth is", depth)
        i++;
    }

    return depth;
}

JSFiddle with the above code, plus tests.

Answer 1

Overall, reading this code, my reaction is "huh?". It looks like a bunch of gibberish at first (and second) glance. There are no english words. I would not want to maintain this code after you left my company.

Correctness

Your answer is correct! That's a good start.

Explain the problem

You've given an explanation of the problem in your post. It's also not super easy to understand, but at minimum add it at the top of your code. See if you can make it much shorter and put it in your own words. Here is my go:

An array can be viewed as a series of height measurements of a piece of land, as seen from the side. Seen this way, define a pit as an area that continuously slopes down from two "top" endpoints on either side, to a "bottommost" point somewhere in between. The depth of the pit is the vertical distance between the lowest height (the bottom) and the highest height on both sides (the lower top endpoint). deepest_pit considers all pits and returns the depth of the deepest pit.

Example

Give a short example input and output, with a short english explanation of why that output is correct. Put it in the problem explanation.

A diagram of the array as a line graph would be very helpful here.

Variable names

Your variable names are M, X, Y, Z, i, j, k, and depth. I realize some of these were provided by the problem, but this is unreadable. Name then so it's clear what data is in each variable and what it means.

Comments

Algorithms need comments, more than most code.

There is no explanation of what the parts of the algorithm do. Add comments for the different sections. Add comments explaining why you are doing things. Have a comment associated with each continue statement.

Tests

You have some tests, that's good.

Answer 2

function deepest_pit(B) {

The JavaScript style guide here indicates that camelCase is recommended for functions. JavaScript is not that Java like really, but it has got that in common.

---

// write your code in JavaScript (Node.js 8.9.4)

That's not needed anymore in the code.

---

var M = B.length,
    depth = -1;

I'd strongly recommend to put variable declarations on separate lines, so:

var M = B.length;
var depth = -1;

Furthermore, I'd try and avoid "magic values" such as -1 (try and use a separate boolean to indicate state, for instance). And if I use them I prefer to make them a constant, e.g. NO_DEPTH_RECORDED = -1. This could declaration would also be helpful for the user of the function.

---

var X, Y, Z;
var i = 0, j, k;

This kind of variable declaration on top of the function is required for C-style code, but not for higher languages such as JavaScript. Just define the variables where they are required. This makes it easier to humans as variables have a better defined scope. It also helps when refactoring the code, e.g. for method extraction.

---

// console.log("i = ", i, "X = ", X)

This is not a good idea, never leave commented out code in your application. If you have to do this, prefix it with a "DEBUG: " tag so the lines that need to be removed before release can be found more easily.

Generic remarks

Although X, Y, Z and M have been defined in the challenge, I would still use lowercase due to the code conventions, and possibly reference the challenge so that people can understand the variable names.

---

while (i < M - 2) {

A for loop seems more reasonable here, i starts with zero, and M is known in advance. Both continue statements are prefixed with i++ and so is the end of the while loop.

---

As you seem to increase i every step I wonder if this is the most efficient algorithm. Once you've found a pit, it will continue 1 place and find the same pit all over - at least I think that is what happens.

---

As indicated by the other answer the main issue is that the code doesn't explain the algorithm used, and thus is it very hard to maintain or grasp. Additionally it is also difficult to find any performance related issues with the algorithm used. That kind of thing needs to be documented either inline or in the documentation of the class / functions.