## Linkedin Interview Question

Software Engineer / Developerspublic static void findNumber(int [] arr, int sumvalue) {

Map hash = new HashMap<Integer, Integer>();

for(int i=0; i< arr.length; i++) {

if(hash.get(arr[i]) == null) {

int x = sumvalue - arr[i];

hash.put(arr[i], x);

if(hash.get(x) != null) {

System.out.println("The two numbers - " + arr[i] + " and " + x);

}

}

}

}

// Sort the array first ..

int arr[] = {-2,0,1,2,3,6,10,19,21,23,43};

int start=0, end = arr.length-1;

int x= 0;

while (start<end) {

if(arr[start]+arr[end]<x)

start++;

else if(arr[start]+arr[end]>x)

end--;

else if(arr[start]+arr[end]==x){

System.out.println("pair " + arr[start] + " " + arr[end]);

break;

}

}

// nlogn solution

METHOD 1 (Use Sorting)

Algorithm:

hasArrayTwoCandidates (A[], ar_size, sum)

1) Sort the array in non-decreasing order.

2) Initialize two index variables to find the candidate

elements in the sorted array.

(a) Initialize first to the leftmost index: l = 0

(b) Initialize second the rightmost index: r = ar_size-1

3) Loop while l < r.

(a) If (A[l] + A[r] == sum) then return 1

(b) Else if( A[l] + A[r] < sum ) then l++

(c) Else r--

4) No candidates in whole array - return 0

METHOD 2 (Use Hash Map)

This method works in O(n) time if range of numbers is known.

Let sum be the given sum and A[] be the array in which we need to find pair.

1) Initialize Binary Hash Map M[] = {0, 0, …}

2) Do following for each element A[i] in A[]

(a) If M[x - A[i]] is set then print the pair (A[i], x – A[i])

(b) Set M[A[i]]

```
/*
* find all pairs of numbers that sum up to k
* 2341,5 -> {(2,3), (4,1)}
* 2222,4 -> {(2, 2), (2, 2), (2, 2), (2, 2), (2, 2), (2, 2)}
* 2, 4 -> {}
*/
void find_sum_pairs(int* vec, int n, int k)
{
qsort(vec, n, sizeof(int)); //O(nlog(n))
int left, right;
left = 0;
right = n - 1;
while(left < right)
{
if (vec[left] + vec[right] == k)
{
printf("(%d, %d)\n", left, right);
for (int r = right - 1; r > left; r--)
{
if (vec[r] == vec[right])
{
printf("(%d, %d)\n", left, r);
}
}
left++;
}
else if (vec[left] + vec[right] < k)
{
left++;
}
else
{
right--;
}
}
}
```

METHOD 1 (Use Sorting)

- vikram patil August 11, 2011Algorithm:

hasArrayTwoCandidates (A[], ar_size, sum)

1) Sort the array in non-decreasing order.

2) Initialize two index variables to find the candidate

elements in the sorted array.

(a) Initialize first to the leftmost index: l = 0

(b) Initialize second the rightmost index: r = ar_size-1

3) Loop while l < r.

(a) If (A[l] + A[r] == sum) then return 1

(b) Else if( A[l] + A[r] < sum ) then l++

(c) Else r--

4) No candidates in whole array - return 0

METHOD 2 (Use Hash Map)

This method works in O(n) time if range of numbers is known.

Let sum be the given sum and A[] be the array in which we need to find pair.

1) Initialize Binary Hash Map M[] = {0, 0, …}

2) Do following for each element A[i] in A[]

(a) If M[x - A[i]] is set then print the pair (A[i], x – A[i])

(b) Set M[A[i]]