## Interview Question for Quality Assurance Engineers

Country: India
Interview Type: In-Person

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

The question is similar to find pairs that sum up to a given number. This problem can be solved in O(n) as:

``````#include <stdio.h>
#include <conio.h>

void findPairs(int arr[],int n,int sum)
{
int temp,bin={0},i;
for(i=0;i<n;i++)
{
temp=sum-arr[i];
if(temp>=0&&bin[temp]==1)
{
printf(" %d %d ",temp,arr[i]);
}
bin[arr[i]]=1;
}
}
int main()
{
int arr[]={0,1,2,3,5,6,9};
int n=sizeof(arr)/sizeof(arr);
findPairs(arr,n,9);
}``````

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

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

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

+1
I like that you only outlined the algo/idea.

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

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.

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

that's n*lgn

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

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 )
otherwise
if(a[p1] +a[p2]> 9)
p2--;
elseif(a[p1] +a[p2]<9)
p1++;
time complexity= O(n)

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

Hi, In ur 3rd technique, is the per-requisite that array should be sorted ? If yes, the complexity should be considered as well. Correct me if wrong.

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

1. add all numbers to hash table
2. for each no in array search for hash(9-a[i])

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

Combinations of two, or more?

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

Its more then 2 ..you need to generate all the combinations which produces the desired sum

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

``````#!/usr/bin/python

def main(self):
a = range(10)
b = []

for i in range(9):
b.append([a[i], a[9-i]])

print '{0}'.format(b)

if __name__ == '__main__':
main()``````

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

``````while( count!=7)
{
for(i=0;i<7;i++)
{

sum=A1[count];
sum=sum+A1[i+1];

if(sum==9)
{
cout<<"{"<<A1[count]<<","<<A1[i+1]<<"}"<<endl;

}
}
count++;
}``````

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

#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)

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

``````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``````

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

Dont know why it was copied twice, the my solution takes O(n) by using a hashtable

``````def printCombination(numList, summ):
numDict = {}
for num in numList:
partner = summ - num
if partner in numDict:
print "(%i, %i)" %(num, partner)
else:
numDict[num] = True``````

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

``````#include<stdio.h>
#include<conio.h>
main()
{
int i,j,found;
int a[]={0,1,2,3,5,6,7,8,9};
for(i=0;i<8;i++)
{
found=0;
for(j=i+1;j<9 && found==0;j++)
{
if(a[i]+a[j]==9)
{
printf("{%d,%d} ",a[i],a[j]);
found=1;
}
}
}
getch();
}``````

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

``````public static void SumTwoElement(int[] array)
{
array = MergeSort(array);
for (int i = 0, j=array.Length-1; i < array.Length&& j>0; i++,j--)
{
if (array[i] + array[j] == 9)
{
Console.WriteLine("{0},{1}",array[i],array[j]);
}

}
}``````

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.