FlexTrade Interview Question Software Engineer / Developers
Well after the interview i came to this solution . first i got the summation of all elements in array and then divide the sum by 2 . now look into array for elements who can sum upto this sum .
Yes its O(n+ n2) = O(n2) solution . I dont know better than this .
void 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 [] = { .... };
int sum = ArraySummation(a,size);
sum = sum / 2;
FindSumElem(a,size,sum);
}
Assumption: two half doesn't mean two equal sized half array....
This solution in worst case runs in O(n). Important idea is to use constraint (0 to 5)
bool HalfArraySum(int a[], int size){
int i=0;
int n =size-1;
int sum1 = a[i];
int sum2 = a[n];
while( (n-i)!=1){
int max_val =(n-i-1)*5 ;
if(sum1 == sum2 ){
++i;
sum1 +=a[i];
if( (n-i)!=1){
--n;
sum2 +=a[n];
}
continue;
} else if(((sum1 - sum2) > max_val) || ((sum2 - sum1) > max_val) ){
return false ;
}
else if (sum1 > sum2 ){
--n;
sum2 +=a[n];
continue;
}else {
++i;
sum1 +=a[i];
continue;
}
}
if( sum1 == sum2)
return true;
return false;
}
int main(){
int a [] = { .... };
bool sumHalf = HalfArraySum(a,size);
}
its not working for this
int a[] = {1,2,4,5};
cout << HalfArraySum(a,4);
expected was to return 1 as u can have 1,5 and 2,4
By reading above posts, I think there are two assumptions depending on that you will get the answer:
a) "array can be divided into 2 half such a that sum of the two half would be equal": Does it mean two equal half or non equal half..Also if its gonna be equal half then sum should be half of total sum( what if size of array is odd , I think we can neglect this)..
b) reordering of array elements is allowed...
There is only two ways to interpret the problem:
1) They want array to literally cut at some index to get two halves:
a find sum/2 = n
b scan again array and see whether you can cut neatly at some index to get sum/2
2) They want to form two sub arrays whose union will get original array:
This is NP-Complete. Couldn't believe asking NP-Complete solution on the phone interview. See here: en.wikipedia.org/wiki/Partition_problem. Either in-experience interviewer doing what he/she does not know or just mean. Ask him/her to give the solution. By the way, sachinsaner, do you get offer or what is your impression about the company, interviewer?
well the ans is quite simple...no need of such hi-fi logic...
sum the elements in the array.if the sum is even,then check the no. of elements in the array...if that too turn out to be even..=>array can be divided to two equal halves with sum of two halves equal....
#include<iostream>
#include<cstdlib>)
#include<algorithm>
#include<vector>
using namespace std;
int sum(vector<int> v){
int s=0;
for(int i=0;i<v.size();i++)
s=s+v[i];
//cout<<s;
return s;
}
int main(){
int n;
cin>>n;
cout<<endl;
int arr[n];
vector<int> v1;
vector<int> v2;
for(int i=0;i<n;i++){
cin>>arr[i];
}
sort(arr,arr+n);
cout<<"SORTED ARRAY\n";
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
for(int i=n-1;i>=0;i--){
if(sum(v1)<sum(v2)){
v1.push_back(arr[i]);
}
else
v2.push_back(arr[i]);
}
if(sum(v1)==sum(v2)){
cout<<"FIRST PARTITION\n";
for(int i=0;i<v1.size();i++)
cout<<v1[i]<<" ";
cout<<endl;
cout<<"\nSECOND PARTITION\n";
for(int i=0;i<v2.size();i++)
cout<<v2[i]<<" ";
}
else{
cout<<"PARTITION NOT POSSIBLE";
}
system("pause");
return 0;
}
#include<iostream>
#include<cstdlib>)
#include<algorithm>
#include<vector>
using namespace std;
vector<int> v7;
int found = 0;
int getmore(int i, int needed, vector<int> v)
{
int j;
if ( v[0] > needed)
{
return 2;
}
if (v[i-1] == needed)
{
v7.push_back(v[i-1]);
found = 1;
return 1;
}
if (i==1)
{
return 2;
}
for (j=i-1; j>0; j--)
{
if ( found == 1 )
{
v7.push_back(v[j+1]);
return 1;
}
else
{
int a = getmore( j, needed - v[j],v);
if ( a == 1)
{
v7.push_back(v[j]);
return 1;
}
else if ( a == 2)
{
getmore( j, needed ,v) ;
return 2;
}
}
}
}
int main(){
int n;
int s1 = 0;//sum
int halfsum;
int need1;
cin>>n;
cin >> halfsum;
cout<<endl;
int arr[n];
int ans = 0;
vector<int> v5;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n);
cout<<"SORTED ARRAY\n";
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
s1+=arr[i];
v5.push_back(arr[i]);
}
int i= n;
need1= halfsum;
getmore(i,need1,v5);
cout << v7.size() << endl;
cout << "answer" << endl;
for(int i=0;i<v7.size();i++)
{
ans += v7[i];
cout<< " " << v7[i]<<" ";
}
cout << " halfsum = " << halfsum << " answer sum = " << ans;
return 0;
}
Anybody knows any algorithm which is not polynomial complexity?
- Anonymous March 29, 2010Otherwise, its trivial with a recursive soln starting with the first number and keep on adding numbers (at the same time maintaing the rest of the sum) such that the sums are equal.