## Microsoft Interview Question for SDE-2s

Team: Cloud & Enterprise team
Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array.
One variable points to the first element.
Another variable points to the last element.
Add the numbers in those indexes and move them as needed.

A few other testcase
Smallest and the biggest number should not add more than Integer.Max.
Array length must not be more than Integer.Max
Method parameters must not allow long.

Comment hidden because of low score. Click to expand.
0

I implemented the sort technique in C. I dont think we need to return true or false. The question says, find all pairs which add to the number given. Hence must print out the pairs:

``````void find_pairs( int a[],int size) {
sort(a);
int first,last,i,j;
first = a;
last = a[size-1];
i=0;
j=size-1;
while(j>i) {
if(first+last == num) {
printf("%d,%d\n",first,last);
first=a[++i];
last=a[--j];
}
if(first>num) first= a[++i];
if(last>num) last =a[--j];
}
}``````

I am not very good at calculating complexity. But this is an O(n) algorithm I guess?

Comment hidden because of low score. Click to expand.
0

Another O(n) approach in C:

``````void find_pairs(int a[], int size) {
static int arr,i;
for(i=0;i<size;i++)
arr[a[i]]=1;
for(i=0;i<size;i++) {
if((num >= a[i]) {
if(arr[num-a[i]]==1) {
arr[a[i]]=0;
printf("%d,%d\n",a[i],num-a[i]);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

The complexity of your program is not O(n) , it depends on sorting algorithm.

Comment hidden because of low score. Click to expand.
0

The complexity of your program is not O(n) , it depends on sorting algorithm.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this can be considered as well: all values in array should not be greater than the given number

Comment hidden because of low score. Click to expand.
0
of 0 vote

Maintain HashSet or HashMap of numbers found.
For each number n
- Search for sum-n in hash. If it exists, then n + sum-n is a pair that sums to sum.
- Place n into hash.
O(n)

For one thing, the question says to find all pairs that sum to a given number. This means testing return of true or false isn't quite valid. You would want to test for different sets of results.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think having negative numbers is valid. -4+ -1 = -5. Nothing wrong in this.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int[] getSums(int[] a, int n)
{
Array.Sort<int>(a);
Array.Reverse(a);
int sum = 0;
int[] result = new int[a.Length];

int k = 0;
for (int i = 0; i < a.Length; i++)
{
if (a[i] + sum <= n)
{
sum += a[i];
result[k++] = a[i];
}
}

if (sum == n)
{
Array.Resize(ref result, k);
return result;
}

return new int;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Some more test cases are as follows:
1) If the given number is zero, then the integer array must have at least one negative number and one positive number having the same absolute value. Otherwise the we don't have valid pairs. for e.g. {1,-1} or {-2,2} etc.

2) If the given number is negative then at least one negative number exist in the integer array. Otherwise the we don't have valid pairs.

3) If the given number is positive, then at least one positive number exists in the integer array. Otherwise the we don't have valid pairs.

4) If the number is even, then the resultant pair must be combination of even numbers only or odd numbers only. The resultant pair cannot have one even and one odd because sum of even and odd cannot be even. So the valid pairs can be {even, even} or {odd, odd}.

5) Similarly, if the given number is odd, the valid pair should be combination of one even number and one odd number. for e.g. {even, odd} or {odd, even}.

Hope this helps.
Thanks,

Comment hidden because of low score. Click to expand.
0
of 0 vote

Some more test cases are as follows:

1) If the given number is zero, then the integer array must have at least one negative number and one positive number having the same absolute value.
Otherwise we don't have valid pairs.

2) If the given number is negative, then the integer array must have at least one negative number. Otherwise we don't have valid pairs.

3) If the given number is positive, then the integer array must have at least one positive number. Otherwise we don't have valid pairs.

4) If the number is even, then the resultant pair must be combination of even numbers only or odd numbers only. The resultant pair cannot have one even and one odd because sum of even and odd cannot be even. So the valid pairs can be {even, even} or {odd, odd}.

5) Similarly, if the number is odd, then the resultant pair must be combination of even number and odd number only. So the valid pairs can be {even, odd} or {odd, even}.

Hope this helps.

Thanks,

Comment hidden because of low score. Click to expand.
0
of 0 vote

hmm, your test cases dont sound like test cases. They sound more like requirements for the function.

Think of testcases as inputs to the program.

1. give input > number
2. give negative input
3. give all numbers are the same < number
etc etc.
4. give all numbers > 0 in array, number = 0
etc etc

think of all possible variations of inputs that may exists and come up with a reasonable sampling of those.

that makes a good test case.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is an O(m+n) solution with lots of places where u can check for various boundary conditions and other test inputs. Build it on that. You have actually sort of specified test cases like requirements!!

``````import java.util.*;
class pairs
{
public static void main(String args[])
{
int[] arr = new int[]{5,2,8,6,9,1,4,3};
int sum = 9;
Hashtable vals = new Hashtable();

for(int i=0; i<arr.length;i++)
vals.put(arr[i],arr[i]);

for(int i=0; i<arr.length;i++)
{
if(vals.contains(sum-arr[i]))
{

System.out.println(arr[i]+" "+(sum-arr[i]));
vals.remove(arr[i]);
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0

sorry may not be O(m+n)..can be O(n+n) => O(2n) => O(n)?? i guess!! :/

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <vector>
using namespace std;

void findAllPairs(int a[],
int n,
int num,
std::vector<std::pair<int,int> >& pairs);
int partition(int a[], int start, int end, int pivot);
void quicksort(int a[], int n);
void qsort(int a[], int start, int end);

void printArr(int a[], int n)
{
cout<<endl;
for(int i=0;i<n;++i)
{
cout<<a[i]<<",";
}
cout<<endl;
}

int main()
{
std::vector<std::pair<int,int> > pairs;
int a[] = {3,5,9,10,2,1,-2,-3};
int n = 6;
findAllPairs(a,sizeof(a)/sizeof(int), n, pairs);
for(int i=0;i<pairs.size();++i)
{
cout<<"pair["<<i<<"] = "<<pairs.at(i).first<<","<<pairs.at(i).second<<endl;
}
return 0;
}

void findAllPairs(int a[], int n, int num, std::vector<std::pair<int,int> >& pairs)
{
if (n <= 1)
{
return; //no pair.
}
cout<<"Array before sorting."<<endl;
printArr(a,n);
quicksort(a,n);
cout<<"Array after sorting."<<endl;
printArr(a,n);
int start = 0;
int end = n-1;
while(start < end)
{
if (a[start] + a[end] == num)
{
pairs.push_back(std::make_pair(a[start], a[end]));
++start;
--end;

}
else if (a[start] + a[end] < num)
{
++start;
}
else
{
--end;
}
}
}

void quicksort(int a[], int n)
{
if (n <= 0)
return;
int start = 0;
int end = n-1;
qsort(a, start, end);
}

void qsort(int a[], int start, int end)
{
if (start < end)
{
int pivot = start;
int j = partition(a, start, end, pivot);
int temp = a[pivot];
a[pivot] = a[j];
a[j] = temp;
qsort(a, start, j-1);
qsort(a, j+1, end);
}
}

int partition(int a[], int start, int end, int pivot)
{
while(start < end)
{
while(a[start] <= a[pivot] && start < end)
++start;
while(a[end] > a[pivot])
--end;
if (start < end)
{
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
}
return end;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Does an array contains duplicate?
Does an array contain negative?
Can we afford O(n) auxiliary space to boost performance?

Approaches:

Use hashtable - Time O(n) and Space O(n)

``````static void PrintSumNPairs(int[] input, int sum)
{
Dictionary<int, int> map = new Dictionary<int, int>();
foreach (int i in input)

foreach (int j in input)
{
if (j != sum -j && map.ContainsKey(sum - j))
{
Console.WriteLine("Pair found - " + j + ", " + (sum - j));
map.Remove(j);
map.Remove(sum - j);
}
}
}``````

Approach 2:

Sort O(nlogn)
Traverse from front and back in - O(n2)

total time O(n2) space O(1)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.