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

3 Answers 3

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\$
6
  • \$\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\$ Commented Oct 18, 2018 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
    Commented Oct 18, 2018 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
    Commented Oct 18, 2018 at 17:13
  • \$\begingroup\$ Thanks @AJNeufeld - that's a good explanation (perhaps worth copying into the answer, at least in part). \$\endgroup\$ Commented Oct 18, 2018 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
    Commented Oct 18, 2018 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\$
3
  • 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
    Commented Oct 17, 2018 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
    Commented Oct 17, 2018 at 5:39
  • \$\begingroup\$ codereview.stackexchange.com/questions/205939/… \$\endgroup\$ Commented Oct 20, 2018 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\$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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