Finding pair in an array with the OO approach

Question

Description:

I am trying to solve algorithmic problems mixing them with Object oriented design as part of my interview preparation. So, the question is given an array of integers find the pair of index which satisfy the given sum hence, given:

arr = [1, 2, 3, 4, 5] , sum = 6, answer = (2, 4) or (1, 5)

Code:

class Solution {
    static final class Pair {
        public final int i;
        public final int j;

        public Pair() {
            i = -1;
            j = -1;
        }

        public Pair(int i, int j) {
            this.i = i;
            this.j = j;
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            return "(" + i + ", " + j + ")";
        }
    }

    static final class PairSum {
        private Pair p;

        public PairSum(int[] arr, int sum) {
            // validation here
            int n = arr.length;
            boolean found = false;
            for (int i = 0; i < n; i++) {
                if (found == true) break;
                for (int j = i + 1; j < n; j++) {
                    if (arr[i] + arr[j] == sum) {
                        p = new Pair(i, j);
                        found = true;
                    }
                }
            }
            if (p == null) // no pair found
                p = new Pair();
        }

        public Pair get() {
            return p;
        }
    }

    static final class PairSumFast {
        private Pair p;

        public PairSumFast(int[] arr, int sum) {
            // validation here
            Map<Integer, Integer> map = new HashMap<>();

            for (int i = 0; i < arr.length; i++) {
                int diff = sum - arr[i];
                if (map.containsKey(diff)) {
                    p = new Pair(map.get(diff), i);
                    break;
                }
                else
                    map.put(arr[i], i);
            }
            if (p == null) p = new Pair();
        }

        public Pair get() {
            return p;
        }
    }

    public static void main (String[] args) throws java.lang.Exception {
        PairSum p = new PairSum(new int[]{1, 2, 3, 0, 4}, 4);
        System.out.println(p.get()); // (0, 2)

        p = new PairSum(new int[]{1, 2, 3, 0, 4}, 5);
        System.out.println(p.get()); // (0, 4)

        p = new PairSum(new int[]{1, 2, 3, 0, 4}, 10);
        System.out.println(p.get()); // (-1, -1)

        PairSumFast p2 = new PairSumFast(new int[]{1, 2, 3, 0, 4}, 4);
        System.out.println(p2.get()); // (0, 2)

        p2 = new PairSumFast(new int[]{1, 2, 3, 0, 4}, 5);
        System.out.println(p2.get()); // (0, 4)

        p2 = new PairSumFast(new int[]{1, 2, 3, 0, 4}, 10);
        System.out.println(p2.get()); // (-1, -1)
    }
}

Given the time constraint I am not sure if its a good approach but I think it should a good impression. I would like to hear if my code could be improved further?

Answer 1

The biggest problem here IMO is that, from a OOP point of view, it's a bit difficult to represent an algorithm as an object. Objects usually represent "things" which have methods that represent "actions" that happen to those things. Algorithms are usually used in such actions. The object in this case would be the array, but since in Java arrays aren't objects and Java doesn't have the concept of extension methods, it's difficult to represent a stand-alone algorithm in an OOP way.

EDIT: I just realized, your algorithms are returning a pair of indices instead of values from the arrays. That doesn't correspond to the example, and in most cases the pair of values would be more useful than the indices. Also my remarks are based on the assumption that values are returned.

Never-the-less here are some remarks about the OOP side of things:

class Pair

The biggest problem here is the usage of -1 to represent ... what exactly? Keep in mind -1 is a completely "normal" valid integer. A developer who uses that class and who doesn't explicitly check for that -1 will get no error message when using it in calculations and instead his program most likely will run fine, but display wrong results. More importantly your program currently displays "(-1, -1)" when there is no solution, but it looks like a possible solution. What if the array contains two -1s and you ask for a sum of -2? How do you distinguish between a correct result and no result.

If you actually should need such an "empty" value of Pair you should use Integers and null. However in your case there is no need for such an empty result. Just drop the default constructor. Instead just have your algorithm return null or - if you don't like using null - use Java 8's Optional.

Pair is a perfect case for an immutable object. There is no reason to change one of the values in the pair after creation. Make the fields private and create getters for them.

---

PairSum/PairSumFast

Since both classes do the same thing, it would be worth considering have them implement a common interface. For such a small example it may be over-engineered, but it would display some insight into OOP.

Another thing that would show a bit more OOP would be to use the Collection interface instead of an array to provide the input. In Java it is rare to actually use an array as a "top level" data structure, since they are not objects are inflexble and don't fit in with Java's collection infrastructure. Arrays are usually used as a low level data storage structure and hidden in the implementation details of classes.