Interview Question
Quality Assurance EngineersCountry: India
Interview Type: In-Person
it is a typical question
1. sort the array in ascending order
2. set two pointer i,j:
i point at the first element(also smallest) of the array
j point at the last element(also largest) of the array
3. now move the i to the end of the array and move the j to the begin of the array according to the result r=array[i]+array[j]:
if r>target: set j--
if r<target: set i++
if r == target: you got one pair, if any number can only in one pair you should do both j-- and i++ otherwise its up to you choice
I always disagree with solutions coming out of naive iterations !!!
This can be solved by using Binary Search.
Perform a binary search for SUM - arr[i] in array.
This problem can be solved in three ways:
1)fix one element and find other element such that a[i] + a[j] =9 using linear search;
for(i=1;i<n;i++)
{ for (j= i;j<n; j++)
if(a[i] + a[j]==9)
return(i,j);
}
time complexity= O(n2)
2) fix first element and find other by binary search
for(i=1;i<n;i++)
{ use binary search here.
}
time complexity= O(nlogn)
3)
use greedy technique
take two pointers p1,p2 put them at rear ends.
then
if(a[p1] + a[p2] =9 )
return element at address;
otherwise
if(a[p1] +a[p2]> 9)
p2--;
elseif(a[p1] +a[p2]<9)
p1++;
time complexity= O(n)
#include<iostream>
#define MAX 7
int main(int argc,char **argv)
{
int arr[MAX]={0,4,2,3,5,6,9};
int com_num;
int end_index=MAX-1;
int index,sum=0;
std::cout<<"Enter commbination number"<<std::endl;
std::cin>>com_num;
for(index=0; index<MAX-1;)
{
sum=arr[index]+arr[end_index];
if(sum==com_num)
{
std::cout<<"{"<<arr[index]<<","<<arr[end_index]<<"}"<<"\t";
}
end_index--;
if(end_index==index)
{
index++;
end_index=MAX-1;
}
}
}complexity o(n)
def printCombination(numList, summ):
numDict = {}
for num in numList:
partner = summ - num
if partner in numDict:
print "(%i, %i)" %(num, partner)
else:
numDict[num] = Truedef printCombination(numList, summ):
numDict = {}
for num in numList:
partner = summ - num
if partner in numDict:
print "(%i, %i)" %(num, partner)
else:
numDict[num] = True
The question is similar to find pairs that sum up to a given number. This problem can be solved in O(n) as:
- vgeek September 22, 2013