1
\$\begingroup\$

On interview I was asked to write method with following contract:

boolean checkList(List<Long> list, long sum){...}

for example it has to return true for arguments:
({1,2,3,4,5,6}, 9) because 4+5 = 9

and it have to return false for arguments:

({0,10,30}, 11) because there are no combination of 2 elements with sum 11

I suggested code like this:

boolean checkList(List<Long> list, long expectedSum) {
    if (list.size() < 2) {
        return false;
    }
    for (int i = 0; i < list.size() - 1; i++) {
        for (int k = i; k < list.size(); k++) {
            if ((list.get(i) + list.get(k)) == expectedSum) {
                return true;
            }
        }
    }
    return false;
}

But interviewer asked me to improve the solution. How?

\$\endgroup\$
4
\$\begingroup\$

As 200_success mentions, your solution is \$O(n^2)\$, due to the double for loop.

You actually have an error in your inner loop. You start the inner loop with for (int k = i; ..., but it should be for (int k = i + 1; .... This means you could return true for an even expected sum when half of that value appears once in the list.

If you correct the above error, the test for list.size() < 2 is unnecessary. The outer loop will run at most once (size=1) and the inner loop will not run at all, therefore the return false; at the end of the function will be executed.


An \$O(n)\$ solution is:

  • start with an empty set
  • for each value x in the list:
    • if set contains expectedSum - x, return true
    • add x to the set.
  • returnfalse

It is important to check for containment before adding the value, or ({1,2,3,4}, 8) would return true, despite not containing a pair of 4’s.

Set<Long> set = new HashSet<>(list.size()*2);
for(long x: list) {
    if (set.contains(expectedSum - x)) {
        return true;
    }
    set.add(x);
}
return false;

The list does not need to be sorted.

The capacity of the HashSet is initialized to double the size of the list, to avoid re-sizings, which would slow the algorithm down.

From the comments: "Why double?" The default load factor for a HashSet is 0.75. If the number of elements in the set exceeds load_factor * capacity, the capacity is increased and the contents rehashed for the new size. If the capacity was set to the size of the list, it would still end up expanding the capacity and rehashing after adding the first 75% of the entries in the list. You need an initial capacity at least 33% larger than the final size to avoid the expansion: list.size()*4/3 + 1 might be sufficient, but is perhaps cutting things a little too fine. Double seemed a reasonable amount.

\$\endgroup\$
  • \$\begingroup\$ Can you explain why you need double the capacity of the list, rather than simply the same capacity? set.size() <= list.size() at the end of the loop. \$\endgroup\$ – Toby Speight Oct 18 '18 at 8:49
  • \$\begingroup\$ Also doesn't really understand why size is doubled. Moreover this could be perceived by interviewer as a premature optimisation, because set resizing asymptotically runs in constant time. \$\endgroup\$ – eleven Oct 18 '18 at 16:35
  • \$\begingroup\$ @TobySpeight The default load factor for a HashSet is 0.75. If the number of elements in the set exceeds load_factor * capacity, the capacity is increased and the contents rehashed for the new size. If the capacity was set to the size of the list, it would end up expanding the capacity and rehashing after adding the first 75% of the entries in the list. You need an initial capacity at least 33% larger than the final size to avoid the expansion: new HashSet(list.size()*4/3+1) would be sufficient, but cutting things a little too fine. Double seemed a reasonable size. \$\endgroup\$ – AJNeufeld Oct 18 '18 at 17:13
  • \$\begingroup\$ Thanks @AJNeufeld - that's a good explanation (perhaps worth copying into the answer, at least in part). \$\endgroup\$ – Toby Speight Oct 18 '18 at 17:14
  • \$\begingroup\$ @eleven With exactly one pair of numbers that sum to the expected total, assuming they are distributed randomly, the expected value of the index of the second number in the pair would be 67% of the way through the list. While we might get lucky and find the pair early in the list, on average, the capacity of the HashSet will be expanded to at least (2/3)*(4/3) = 8/9 of the size of the list. If the pair isn't found, the HashSet has to be expanded to at least 4/3 of the size of the list. Is it premature optimization, or just allocating the required resources for solving the problem? \$\endgroup\$ – AJNeufeld Oct 18 '18 at 17:27
3
\$\begingroup\$

There are many ways to solve this puzzle. Your approach seems to fine. It is simple and it is easy to understand. But you can replace your inner loop by a method of List:

public static boolean checkList_contains(List<Integer> list, int sum) {
    if (list.size() < 2) {
        return false;
    }
    for (int i = 0; i < list.size() - 1; i++) {
        if (list.contains(sum - list.get(i)))
            return true;
    }
    return false;
}

This tries to find the missing value by calling contains.

Then you can use modern streams instead of for loops:

public static boolean checkList_streams(List<Integer> list, int sum) {
    return list.stream()
            .map(x -> sum - x)
            .filter(list::contains)
            .findAny()
            .isPresent();
}

But here it should be allowed to use the same element twice.

Theses both solutions are very inefficient. Both have a running time in O(n²).

If you expect a sorted list you can use two indices which moves from left and right until you find a matching pair (which is what @200_success has written):

public static boolean checkList_sorted_list(List<Integer> list, int sum) {
    int lowerIndex = 0;
    int upperIndex = list.size() - 1;
    while (lowerIndex < upperIndex) {
        int testSum = list.get(lowerIndex) + list.get(upperIndex);
        if (testSum > sum) upperIndex --;
        else if (testSum < sum) lowerIndex ++;
        else return true;
    }
    return false;
}

This is in O(n).

\$\endgroup\$
  • 1
    \$\begingroup\$ Your stream solution is interesting, but list::contains is searching from the start of the list, doubling the amount of work performed over the OP’s solution. You could stream over the list indices and .filter(list.subList(i+1, n).contains(sum - list.get(i))) ... then findAny and ifPresent. \$\endgroup\$ – AJNeufeld Oct 17 '18 at 5:28
  • 1
    \$\begingroup\$ Actually, use .anyMatch(list.subList(i+1, n).contains(sum - list.get(i))) and skip the filter/findAny/ifPresent \$\endgroup\$ – AJNeufeld Oct 17 '18 at 5:39
  • \$\begingroup\$ codereview.stackexchange.com/questions/205939/… \$\endgroup\$ – gstackoverflow Oct 20 '18 at 11:32
2
\$\begingroup\$

Your solution is inefficient: for a list of length n, the worst-case running time is O(n2), because you may need to test every possible pair of numbers.

A better algorithm would be to sort the list first. (Maybe it's already sorted? You didn't specify, but your examples suggest that that might be the case.) Then, you would only need to try pairs where the left index only increases (if the pair sum is too small) and the right index only decreases (if the pair sum is too large). The running time for that would be O(n log n) for the sorting step, plus O(n) for the search.

\$\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.