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?