8
\$\begingroup\$

An interview question I received:

You are given two unsorted lists of positive doubles

  • x contains the results from experiment 1
  • y which contains the results from experiment 2.

All results from the second experiment y are improvements over x by i percent, where i is an integer. That is to say that given a result from x, the corresponding result from y will be an i percent improvement.

However, the lists are not parallel; that is to say x[0] does not necessarily correspond to y[0]. Find the value of i.

Note: must be written in Java 7

Some examples

Inputs:

y = [1.0]
x = [1.0]

Output:

0

Inputs:

y = [2.2999999999999998, 15.0, 102.40000000000001, 3486.8000000000002]
x = [23.0, 150.0, 1024.0, 34868.0]

Output:

90

Inputs:

y = [23, 11.1, 50.4]
x = [22.2, 46, 100.8]

Output:

50

Note in the last case where 46 -> 23 and 22.2 -> 11.1 but the index of 46 is not the index of 23, etc.

My Solution

import java.util.Arrays;

//Time complexity: O(n)
//Space complexity: O(1)
public class Solution{   
    public static int solution(double[] secondRun, double[] firstRun) {

        Double firstRunMax = findMax(firstRun),
               secondRunMax = findMax(secondRun);

        return (int)((1.0-secondRunMax/firstRunMax)*100);
    }

    private static double findMax(double[] array){
        double max = -Double.MAX_VALUE;

        for(double d : array){
            if(d > max){
                max = d;
            }
        }

        return max;
    }
}

Strengths: Very simple, as efficient as possible (I think?), ignores most of the data

Weakness: the return line is a little convoluted. Perhaps there is a better way to simplify it also. Also I thought I would be able to find a simple Arrays.Max method or something in Java, but I didnt see any during a quick glance.

\$\endgroup\$
  • \$\begingroup\$ Just a quick note: use Collections.max(array) to get the max - you don't need the findMax function. \$\endgroup\$ – Ryan Jan 9 '15 at 4:04
  • \$\begingroup\$ I think the answers should be: 0, 900, 100 (instead of 0, 90, 50). \$\endgroup\$ – JS1 Jan 9 '15 at 4:10
  • \$\begingroup\$ @Ryan There is a Collections.max, but it only takes collections (arrays are not collections in Java) \$\endgroup\$ – David says Reinstate Monica Jan 9 '15 at 4:22
  • \$\begingroup\$ @DavidGrinberg just use Arrays.asList in the argument then. \$\endgroup\$ – Ryan Jan 9 '15 at 4:22
  • 1
    \$\begingroup\$ @Ryan That would be hugely inefficient. Why would I want to convert the array to list just so I can find the max? \$\endgroup\$ – David says Reinstate Monica Jan 9 '15 at 4:23
4
\$\begingroup\$

You are auto-boxing the results of your function call, only to un-box them later. If everything else is using double (a primitive), there is no reason to declare the local variables in solution() as Double (an object). This doesn't effect the big-O of your solution, but it is extra operations for the JVM to execute.


Give your class and public method better names. If you actually needed this in production code, there would be no way to know what this code did. The names tell you nothing and there is no documentation.


There is a max(), but it works on Collections, not arrays. However, writing your own max method is not that hard, so it is up to you if you want to replace it.


Note: Until seeing you question, I didn't know that Double.MIN_VALUE and Integer.MIN_VALUE do not represent the same concept for the respective type. This isn't your fault, but it is unintuitive. Explination

\$\endgroup\$
  • \$\begingroup\$ Class/function names were mandated, as well as the signature, but otherwise I agree with you. \$\endgroup\$ – David says Reinstate Monica Jan 9 '15 at 4:19
4
\$\begingroup\$

Oh, I like challenges like this. Looking through your solution, though, you make statements that do not quite ring true, you say it 'ignores most of the data', but that's not true, it inspects all the data, scanning both arrays completely.

On the other hand, that is as efficient as it can be (\$O(n)\$), so that's OK. You just need to realize that you scan it all.

So, I agree, it is close to being as efficient as possible. Certainly, it is as scalable as it could be (good time complexity, and \$O(1)\$ space complexity).

Bugs

  1. I don't believe it gets the best results all the time. Specifically, what if the integer is negative, then the one array will have negative values, and the max(...) from that array will be wrong.

  2. your solution suffers from an off-by-one problem in the event that floating-point operaions are slightly less than accurate (which is typical). For example, you may compute the max of one dataset to be 100.0000, and the other to be 33.33334. When you do the division, the result will be 2.999999 which, when you re-calculate the factor, will truncate the wrong way in the int conversion. You need to round, and not truncate.

Summing, not max

I believe the better solution to this problem would be to sum all the values from each array, and then to compute the ratio afterwards.

The math is simple. If you have the two data arrays [a,b,c,d,...] and the corresponding set [A,B,C,D,...] where you know that A is some factor Q times larger, then you have:

[Qa, Qb, Qc, Qd, ...] == [A, B, C, D, ....]

which implies that:

Q[a, b, c, d, ...] == [A, B, C, D, ...]

So, if you sum the values in both sets, you will have:

Q sum(abcd...) == sum(ABCD...)

and

Q = sum(ABCD...) / sum(abcd...)

This makes it all quite simple...

double sumA = 0.0;
double sumB = 0.0;

for (int i = 0; i < firstRun.length; i++) {
    sumA += firstRun[i];
    sumB += secondRun[i];
}

double q = sumB / sumA;

Now, q is a value which may not be easy to translate directly to an integer. For example, because of floating-point inaccuracies, the intended Q factor may be 5, but the computed one is 4.99999999997 or something.

return (int)Math.round(q);

Note that summing the values instead of finding the max, will be approximately equally efficient. In each case, you are going through all elements just once.

Java 8

Notice, in Java 8, this would be a nice problem....:

return (int)(Math.round(Arrays.stream(secondRun).sum() / Arrays.stream(firstRun).sum());
\$\endgroup\$
  • \$\begingroup\$ I forgot to add a couple constraints - all values are positive, and must be Java 7. I'll edit question. \$\endgroup\$ – David says Reinstate Monica Jan 9 '15 at 4:14
  • \$\begingroup\$ Since all values are positive, it would be more efficient to find max than to sum, correct? (though both would still be O(n)). Though I do think your sum idea is pretty cool. \$\endgroup\$ – David says Reinstate Monica Jan 9 '15 at 4:21
  • \$\begingroup\$ I don't believe there would be any significant difference between the sum and max. I have identified some other issues too, edited my answer. \$\endgroup\$ – rolfl Jan 9 '15 at 4:24
  • \$\begingroup\$ Also for Bug 3 I think you have it backwards. The second run will always be smaller than the first run (there is always an improvement). Thus it will not be 10.0/1.0 but 1.0/10.0 -> (1.0 - 1.0/10.0) * 100 = 90 \$\endgroup\$ – David says Reinstate Monica Jan 9 '15 at 4:29
  • 1
    \$\begingroup\$ Adding floating point numbers can be tricky if the values to be added involve very large and very small numbers. So finding the max seems like a more robust solution \$\endgroup\$ – ChrisWue Jan 9 '15 at 7:53
2
\$\begingroup\$

With such a short piece of code, there is not really much to say.

Some notes:

  1. return (int)((1.0-secondRunMax/firstRunMax)*100);

    This is hard to read. Put spaces before and after all the operators, to improve readability:

    return (int) ((1.0 - secondRunMax / firstRunMax) * 100);

  2. public static int solution(double[] secondRun, double[] firstRun)

    To me, it doesn't make sense to put secondRun before firstRun. Reverse their locations:

    public static int solution(double[] firstRun, double[] secondRun)

\$\endgroup\$
  • \$\begingroup\$ I agree with both points, but for point 2 the signature was provided, so not much choice there. \$\endgroup\$ – David says Reinstate Monica Jan 9 '15 at 4:17

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.