Google Interview Question: Find the integer pairs in an ... | Glassdoor

Interview Question

Software Engineer Intern Interview

Find the integer pairs in an integer array, so that they

  sum up to a specific number n.
Answer

Interview Answer

7 Answers

1

Sort the array using quick sort. Start from the highest value on top, say x, and binary search the array to see if there exists n-x. If not, remove top element and shrink array by 1 and repeat. If found, there's your solution.

pflau on Oct 6, 2010
3

Complexity O(N):

void findSum(int sum, int[] vec) {
    Set set= new HashSet(vec.length);
    for (int i : set) {
        int j = sum - i;
        if (set.contains(j)) {
            printf("%i + %i = %i \n", i, j, sum);
        }
        set.add(i);
    }

vsp on Oct 7, 2010
0

typo: the "for" loop is for (int i : vec) {

vsp on Oct 7, 2010
0

To elaborate on vsp's solution. I believe they are looking for the matching pairs in the array that sum to n.

Ex:
 5,0 4,1 2,3 6,-1

I'd suggest dumping the vector into a hash O(n). Then walk the vector getting i and check the hash for the j where j = sum - i;. When j is in the hash, then you have an ij pair.

Anonymous on Dec 12, 2010
0

Working Answer ...

import java.util.ArrayList ;
import java.util.HashMap ;

public class findpair {

        public static void main (String [] args) {

                int [] array = new int [] { 1,6,4,2,6,2,3,4,5,1,6,7,8,3,4 } ;
                for ( int ii : array) { System.out.print( ii+" " ); } System.out.println();
                pairPrint( array, 10 ) ;
        }

        private static void pairPrint ( int [] array , int value) {

                HashMap > map = new HashMap > ( array.length ) ;

                int counter = 0;
                for ( int ii : array ) {

                    /// If we find a match we add it and print the pairs
                    if ( map.containsKey(ii) ) { for ( Integer jj : map.get(ii) ) { System.out.println( " Pair at " + counter + " + " + jj ) ; }}

                    // Add it to the map
                    if ( map.containsKey(value-ii) ) { map.get(value-ii).add(counter) ; }
                    else { ArrayList list = new ArrayList(); list.add(counter ); map.put(value-ii , list) ; }
                    counter++ ;
                }

        }

}

bazooka on Jan 13, 2012
0

hashtable provide a O(l) time and O(n) memory algorithm which l is length of array

sakuin on Mar 4, 2013
0

Saw the video on youtube. That example is sorted array.
If we solve the problem using unsorted array. It needs some kind of probabilistic model to evaluate the complexity. So I am not going to try that.
Let's use a general Quicksort to sort it first. Which average O(n log n)
Then we can try to find a pair from the result.

There is an extra piece of information which is the specific number "n". Think of the sorted array like a stair shape block.

Pseudo Algo:
0. input array X
1. look for the number closest to n/2.
2. Cut this array into two arrays (fold it in half). W[] and Q[]
3. Loop(i=0;i++;i

Maxi Wu on Dec 13, 2018

Add Answers or Comments

To comment on this, Sign In or Sign Up.