Cisco Systems Interview Question
Software Engineer / Developersvoid FindSumElem(int a[] , int size , int num){
vector<int> v;
for(int i = 0 ; i < size ; i++){
int index = i;
int sum = 0;
int j = i;
for(; j < size ; j++){
sum =sum + a[j];
v.push_back(a[j]);
if(sum == num){
cout << "Num found "<<num<< " " << sum << endl;
for(vector<int>::iterator it = v.begin() ; it != v.end() ; it++)
cout <<*it<<endl;
return;
}
if(sum > num ){
//make j point to next element
//EX. if a [] = {-1 , 0 ,3 } if previous j was at index 0 i.e. a[j] == -1
//now make it point to index 1 i.e a[j] == 0
//Basically i am skipping the element pointed by J as it is not part of solution
j = ++index;
//Flush the vector and start again
v.clear();
v.push_back(a[i]);
sum = a[i];
}
}
}
cout << "No such elements"<<endl;
}
int main( )
{
int a[] = {-1,0,3,4,5,6};
FindSumElem(a,6,9
);
return 0;
}
Guys your comments are welcome also try it with diff i/p and let me know of any bugs
P.S. please use Reply to Comment so i will come to know if anybody has replied
Yup it should work , basically above code is brute force algo for given problem . Its a NP complete problem and above code runs in exponential time . Look for subset sum problem on wiki
en.wikipedia.org/wiki/Subset_sum_problem
Recursive version - (Not iterative, recursion means same function is called by itself on itself for itself)
bool sum(int *a, int start, int end, int val){
if(start>end)return false;
for(int i=start;i<=end;++i){
if(a[i]<val){
if(sum(a,i+1,end,val-a[i])){
return true;
}
}
else if(a[i]==val){
return true;
}
}
return false;
}
void SubSetSum(int arr[], int start, int end, int PartialSum, int targetSum, vector<int> v){
if (start >=end){
if (partialSum == targetSum){
for (int i=0; i < v.size();i++){
cout << " " << v[i];
}
cout << endl;
return;
}
}
SubSetSum(arr, start+1, end, PartialSum + arr[start], targetSum, set.push_back(arr[i]);
set.pop_back(arr[i]);
SubSetSum(arr, start+1, end, PartialSum, targetSum, set);
}
Search for a pair which sums to S
Let A be a sorted array of integers ans S a target integer
Problem: Design an efficient algorithm for determining if there exist a pair of indices i,j (not necessarily distinct) such that A[i] + A[j] = S
SOL:
store the values from the array in a hashtable, then for each new value, check to see if its complement has already been seen and if so, what is the index.
This solution will work only for positive numbers and time complexity is: n*sum
public void knapsack()
{
int[] a = { 0, 1, 2, 3, 4, 5, 6 };
// the value we are looking for
int sum = 10;
Boolean[,] k = new Boolean[a.Length, sum + 1];
k[0, 0] = true;
for (int s = 1; s <= sum; s++)
{
k[0, s] = false;
}
for (int iIndex = 1; iIndex < a.Length; iIndex++)
{
for (int s = 0; s <= sum; s++)
{
if (a[iIndex] <= s)
{
k[iIndex, s] = k[iIndex - 1, s] || k[iIndex - 1, s - a[iIndex]];
}
else
{
k[iIndex, s] = k[iIndex - 1, s];
}
}
}
// to display solution
DisplayKnapsack(a, k, sum);
}
private void DisplayKnapsack(int[] input, bool[,] output, int knapSackSize)
{
int m= input.Length - 1;
int n = knapSackSize;
if (!output[input.Length -1 , knapSackSize])
{
Console.WriteLine("Knapsack cant be completely filled with given collection of weights. Next best solution is ");
while(!output[m,n])
{
n--;
}
Console.WriteLine(n.ToString() + " and weights selected are : ");
}
else
{
Console.WriteLine("Knapsack can be completely filled with given collection of weights and the weights participated in the soultion are : ");
}
while(n> 0)
{
// this is to check if the smaller subset can also lead to the size of knapsack and giving priority to that
if(output[m - 1,n] == true)
{
m--;
}
else
{
Console.WriteLine(input[m]);
n -= input[m];
m--;
}
}
}
its a dynamic programming problem
- Anonymous March 26, 2010