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);
    }

}