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.

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

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

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 &gt; map = new HashMap &gt; ( 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