## Google Interview Question: Find a Pair Set Where Sum…

Here is another google interview question (taken from here)

They give you a list of numbers such as {4, 1, 5, 2, 3, -1, 6,} and a threshold lets say 4

and ask for distinct pair sets from the list, where sum of the numbers in each pair less or equal to the threshold.

in this case answer should be;(4, -1), (1, -1), (1, 1), (1, 2), (1, 3), (5, -1), (2, -1), (2, 1), (2, 2), (3, -1), (3, 1), (-1, -1), (-1, 1), (-1, 2), (-1, 3), (-1, 4), (-1, 5)

well my solution is not O(n) as I use a sorted set. First put all the numbers and then get the range up to the difference between a number and the threshold.

In the worst case my solution is O(n^2) and on average O(n.logn)

You can run it from here

here is the code:

/** * User: uerturk */ import java.util.*; /** * Input - array of integers size N, integer Threshold. * Output - the pairs (x, y) of distinct elements with condition x + y <= Threshold. * Is that possible to implement is with O(n) ? */ class FindPairsUnderThreshold { public List<Map.Entry<Integer, Set<Integer>>> solve(Integer[] integers, Integer threshold) { // the complexity > O(n), sorted list is the key in this solution SortedSet<Integer> sortedSet = new TreeSet<Integer>(); // first put values into the sorted set for (Integer number : integers) { sortedSet.add(number); } // then get the range from the head (smallest value) to the maximum value that satisfies the condition List<Map.Entry<Integer, Set<Integer>>> result = new ArrayList<Map.Entry<Integer, Set<Integer>>>(); for (Integer number : integers) { // headSet is not inclusive, +1 is to make it include the exact sum int diff = threshold - number + 1; Set<Integer> integerIntegerSortedMap = sortedSet.headSet(diff); Map.Entry<Integer, Set<Integer>> integerSetPair = new AbstractMap.SimpleEntry<Integer, Set<Integer>>(number, integerIntegerSortedMap); result.add(integerSetPair); } return result; } public static void main(String[] args) { Integer[] integers = {4, 1, 5, 2, 3, -1, 6,}; Integer threshold = 4; List<Map.Entry<Integer, Set<Integer>>> solution = new FindPairsUnderThreshold().solve(integers, threshold); for (Map.Entry<Integer, Set<Integer>> entry : solution) { Integer first = entry.getKey(); for (Integer second : entry.getValue()) { System.out.print("(" + first + ", " + second + "), "); } } System.out.println(solution); } }