Java Interview Task: Complete the Java method for a sorted array

Question

Possible Duplicate:
Find a pair of elements from an array whose sum equals a given number

I was recently presented with the following Java interview question.

The target is to complete the method task with only a single pass over the input array.

I claimed it is not possible to complete this task on a single pass over the array but I was met with the usual silence, pause and then the interviewer proclaimed the interview was at an end without giving me the answer.

public class SortedArrayOps {  
    public SortedArrayOps() {  

    }  

//    Print at the system out the first two ints found in the sorted array: sortedInts[] whose sum is equal to Sum in a single pass over the array sortedInts[] with no 0 value allowed.  
//  i.e. sortedInts[i] + sortedInts[?] = Sum where ? is the target index to be found to complete the task.  
static void PrintIntSumValues(int Sum, int sortedInts[]) {  
//        need to test to see if the Sum value is contained in the array sortedInts. And, if not do nothing.  
    for(int i=0; i<sortedInts.length; i++) {  
//            ... do some work: algebra and logic ...  
//            System.out.println sortedInts[i]+sortedInts[?] sums to Sum.  
    }  
}  

public static void main(String[] args) {  
    final int[] sortedArray = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
    PrintIntSumValues(48, sortedArray);  
}

}

So... what is the expected answer for the input "48"? 1 and 47? — SingleShot, Jul 31 '12 at 02:20
hint: even if you cant do it in a single pass, the art of the interview is to show your thought process - so start with a hmm, how would i do it in two passes? talk about it, try to get hints if necessary. — akf, Jul 31 '12 at 02:26
if there are no memory limits, then it is trivial. Also if it is guaranteed that every element between 1...n exists, then it is trivial. — Markus Mikkolainen, Jul 31 '12 at 02:31
also they dont define "first" i think it would be 23+25? if we know that the array is continuous and last elemetn of array is greater than Sum/2, then we know that the answer is (Sum/2)+-1. But that is a very simplified case. — Markus Mikkolainen, Jul 31 '12 at 02:34
You have to do a moving binary search. It can be done with no additional data structures. I will post the answer in a few minutes (once it works :) ). — Michael Graczyk, Jul 31 '12 at 03:06
There is a linear solution [here](https://stackoverflow.com/questions/43441616/have-on2-algorithm-for-two-sum-convert-to-on-linear-solution) without hashing. — user202729, May 12 '18 at 04:42

score 1 · Answer 1 · answered Jul 31 '12 at 03:50

I am not sure which values in the array you are looking for (what does "first two" ints mean? Minimum sum of their indices? One is smallest? Any two that happen to pop out first?), but this solution is O(n), takes one pass, uses no additional data structures, and only uses one extra int. It does not always find the two indices closest together, nor does it always find the "first", whatever that might mean. I believe that it will always find the two whose sum is smallest (until you guys find a counter example).

Let me know if you guys find any bugs with it:

class Test {

    public static void main(String[] args) {  
        int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        PrintIntSumValues(6, sortedArray);

        sortedArray = new int[] {1, 2,3, 12, 23423};
        PrintIntSumValues(15, sortedArray);


        sortedArray = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        PrintIntSumValues(100, sortedArray);

        sortedArray = new int[] {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
        PrintIntSumValues(48, sortedArray);  
    }

    //    Print at the system out the first two ints found in the sorted array: sortedInts[] whose sum is equal to Sum in a single pass over the array sortedInts[] with no 0 value allowed.  
    //  i.e. sortedInts[i] + sortedInts[?] = Sum where ? is the target index to be found to complete the task.  
    static void PrintIntSumValues(int Sum, int sortedInts[]) {  
        // need to test to see if the Sum value is contained in the array sortedInts. And, if not do nothing.  
        int offset = sortedInts.length-1;

        for(int i=0; i<sortedInts.length; i++) {  
            //            ... do some work: algebra and logic ...   
            if ((sortedInts[i] + sortedInts[offset]) == Sum){
                System.out.println("sortedInts[" + i + "]+sortedInts[" + offset + "] sums to " + Sum + ".");
                return;
            } else {
                int remaining = Sum - sortedInts[i];
                if (remaining < sortedInts[i] ){
                    // We need something before i
                    if (remaining < sortedInts[offset]) {
                        // Even before offset
                        offset = 0 + (offset - 0)/2;
                    } else {
                        // Between offset and i
                        offset = offset + (i - offset)/2;
                    }
                } else {
                    // We need something after i
                    if (remaining < sortedInts[offset]) {
                        // But before offset
                        offset = i + (offset - i)/2;
                    } else {
                        // Even after offset
                        offset = offset + (sortedInts.length - offset)/2;
                    }
                }
            }
        }  
        System.out.println("There was no sum :(");

    }  
}

You can view the output here.

Though not explicitly stated, I believe that the two integers of the sum must be unique. Your first example outputted `[2]+[2] =6`, which is true, but the desired solution would be `[1]+[3] = 6` because [2] & [2] are obviously not unique integers. — recursion.ninja, Aug 14 '12 at 21:42
@awashburn That's probably true. I ignored that problem because ensuring uniqueness of the indices here adds a lot of complication to the algorithm. For the purpose of an interview, I think attempts at "clever" *O(n)* solutions like this are better than more accurate *O(n^2)* solutions (or *O(n^3)*). Of course if this were production code I would gladly take working *O(n^3)* over incorrect *O(n)*. — Michael Graczyk, Aug 14 '12 at 21:49
understandable point, This is just an example after all. I like you approach to the problem (better then mine) and am happy to have learned this new technique. I wasn't a fan of the `HashMap` solution; being dependent on imports and creating a new data structure wasn't an intellectually satisfying answer. This however is most intellectually satisfying! — recursion.ninja, Aug 14 '12 at 22:02

score 0 · Answer 2 · answered Jul 31 '12 at 02:31

import java.util.HashMap;

            public class SortedArrayOps {

                public SortedArrayOps() {
                }

            //    Print at the system out the first two ints found in the sorted array: sortedInts[] whose sum is equal to Sum in a single pass over the array sortedInts[] with no 0 value allowed.
            //  i.e. sortedInts[i] + sortedInts[?] = Sum where ? is the target index to be found to complete the task.
            static void PrintIntSumValues(int Sum, int sortedInts[]) {
                HashMap<Integer, Boolean> pool= new HashMap<Integer, Boolean> ();
                for(int i=0; i<sortedInts.length; i++) {
                    int current = sortedInts[i];
                    int target = Sum - current;
                    if (pool.containsKey(target)) {
                        System.out.println(String.format("%d and %d sum to %d", current, target, Sum));
                        break;
                    }
                    else {
                        pool.put(current, Boolean.TRUE);
                    }
                }
            }

            public static void main(String[] args) {
                final int[] sortedArray = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
                PrintIntSumValues(48, sortedArray);
            }
            }

score 0 · Answer 3 · answered Jul 31 '12 at 02:49

Here is a complete solution using a HashMap:

import java.util.HashMap;

public class Test
{
    public static void main(String[] args)
    {
        final int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int sum = 6;

        printSum(sum, sortedArray);
    }

    private static void printSum(int sum, int[] sortedArray)
    {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (int index = 0; index < sortedArray.length; index++)
        {
            int currentNumber = sortedArray[index];
            int remainder = sum - currentNumber;

            if (map.containsKey(remainder))
            {
                System.out.println(String.format("%d + %d = %d", currentNumber, remainder, sum));

                break;
            }
            else
            {
                map.put(currentNumber, index);
            }
        }
    }
}

score 0 · Answer 4 · answered Jul 31 '12 at 10:59

This should work. You have two pointers, and make only a single pass through the data.

j = sortedInts.length - 1;
for(int i=0; i<sortedInts.length && j>=i; i++) {  
    sx = sortedInts[i];
    while (sx + sortedInts[j] > Sum)
        j++;
    if (sx + sortedInts[j] == Sum)
        ...
}

didxga · Answer 5 · 2012-07-31T04:35:12.470

Because the array of values is specific, the solution can be simplified as this,

public class SortedArrayOps {
public SortedArrayOps() {

}

// Print at the system out the first two ints found in the sorted array:
// sortedInts[] whose sum is equal to Sum in a single pass over the array
// sortedInts[] with no 0 value allowed.
// i.e. sortedInts[i] + sortedInts[?] = Sum where ? is the target index to
// be found to complete the task.
static void PrintIntSumValues(int Sum, int sortedInts[]) {
    // need to test to see if the Sum value is contained in the array
    // sortedInts. And, if not do nothing.
    for (int i = 0; i < sortedInts.length; i++) {
        // ... do some work: algebra and logic ...
        // System.out.println sortedInts[i]+sortedInts[?] sums to Sum.
        int remainder = Sum - sortedInts[i];
        if( remainder <= sortedInts.length && remainder>0 && remainder!=sortedInts[i]) {
            System.out.print(String.format("%d + %d = %d", sortedInts[i], sortedInts[remainder-1], Sum));
            break;
        }
    }
}

public static void main(String[] args) {
    final int[] sortedArray = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
            14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
            30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
            46, 47, 48, 49, 50 };
    PrintIntSumValues(48, sortedArray);
}

}

I do not think it is okay to assume that the array will always be that same array. — Michael Graczyk, Jul 31 '12 at 05:06
the code which given by the interviewer hard coded it as such, if it is variable, why not declared as array variable, instead of a specific array. — didxga, Jul 31 '12 at 05:10
Assuming the sortedArray is always this one, you can simply pre-compute the sum (51*25) = 1275, and return (val > 0 && val <= 1275). Perhaps the interviewer just wanted to test ones ability to do summations. — Xantix, Aug 07 '12 at 08:55

Java Interview Task: Complete the Java method for a sorted array

5 Answers5