Microsoft Interview Question
SDE-2sTeam: Cloud & Enterprise team
Country: India
Interview Type: Phone Interview
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[0];
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?
Another O(n) approach in C:
void find_pairs(int a[], int size) {
static int arr[100],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]);
}
}
}
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.
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[0];
}
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,
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,
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.
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]);
}
}
}
}
#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;
}
Questions to ask:
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)
map.Add(i, 1);
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)
Sort the array.
- s100banerjee May 15, 2015One 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.