3
\$\begingroup\$

I was presented with an interview question described as follows:

Receiving an int[] A of cities, where each A[i] has an appeal value. We want to plan our trip based on the highest appeal possible, taking in mind that is calculated as follows A[i] + A[j] + (i - j). This means the appeal values of 2 cities summed, plus their distance.

Function signature:

public static int solution(int[] A);

The constraints were the following:

  • N is an integer within [1, 100,000]
  • A[i] is an integer within [-1,000,000,000, 1,000,000,000]

Using the same value is a possible valid solution, so for example, if we have A = {1, 3, -3}; this should return 6 as visiting city A[0] twice gives the max appeal value A[0] + A[0] + (0 - 0) = 6.

So given that, a possible solution is the same value twice, I did not found other solution than:

int highestAppeal = 0;

for (int i = 0; i < A.length; i++) {
    for (int j = 0; j < A.length; j++) {
        int currentAppeal = A[i] + A[j] + (i - j);
        highestAppeal = currentAppeal > highestAppeal ? currentAppeal : highestAppeal;
    }
}

return highestAppeal;

This solution was marked as pretty bad. I realize that a \$O(n^2)\$ solution is far from efficient, but in this case, I did not see how to improve it. Later on, I thought about sorting A values in descending order and, for repeated values, using indexes in ascending order. But I don't see that going forward.

What would be a better and more efficient solution for this?

\$\endgroup\$
  • \$\begingroup\$ Well, I've added the expected function signature, so it is clear that an int is expected as result. \$\endgroup\$ – Power_of_zero Apr 9 at 12:13
  • \$\begingroup\$ Ah, sorry, missed that. \$\endgroup\$ – TorbenPutkonen Apr 9 at 12:16
  • 1
    \$\begingroup\$ I deleted my answer. I've come to the conclusion that this was a trick question with a purpose of finding out if you notice bad requirements and are able to ask clarifications. \$\endgroup\$ – TorbenPutkonen Apr 9 at 12:24
  • \$\begingroup\$ I had lots of things to ask clarification for, but they sent me as an assignment through a site. I had 2 tasks which I had to do in 1 hour. This was one of them. \$\endgroup\$ – Power_of_zero Apr 9 at 12:25
  • \$\begingroup\$ So, had no contact or any way of asking anything. \$\endgroup\$ – Power_of_zero Apr 9 at 12:26
1
\$\begingroup\$

Thinking this more, there are three things affecting the appeal.

  • A[i]
  • A[j]
  • i - j

Since A[i] + A[j] is the same as A[j] + A[i], you don't need to traverse the whole array in the inner loop.

Since the third component increases the appeal only when j < i, you can restrict the inner loop to run from 0 to i.

You also need to take into account the fact that all cities may have negative appeal. Integer.MIN_VALUE is safe initial value, as the lowest valid value (2 * -1000000000 - 100000) is still greater than that.

Using Math.max would have been more readable.

    int highestAppeal = Integer.MIN_VALUE;

    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j <= i; j++) {
            final int currentAppeal = A[i] + A[j] + (i - j);
            highestAppeal = Math.max(highestAppeal, currentAppeal);
        }
    }

    return highestAppeal; 

And you can't overestimate the value of commented code in an interview answer.

\$\endgroup\$
0
\$\begingroup\$

Yesterday, I asked the interviewers themselves for an efficient solution to this problem, and I finally got one:

int maxStart = A[0];
int maxEnd = A[0];

for (int i = 0; i < A.length; i++) {
    if ((A[i] - i) > maxStart) {
        maxStart = A[i] - i;
    }

    if ((A[i] + i) > maxEnd) {
        maxEnd = A[i] + i;
    }
}

return maxEnd + maxStart;

So this is the O(n) solution they gave me, which I found pretty beautiful to be honest.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.