Accenture Interview Question for Software Analysts


Country: India
Interview Type: In-Person




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

We can solve this problem using backtracking, here is the code, basically we try all the possible +- assignments

#include <stdio.h>
#include <stdlib.h>
char symb[10]={0};
int count=0;

void printsym(int k, int A[]){
    for(int i=2; i <= k-1 ; i++)
        printf("%d %c ",A[i-1],symb[i]);
    
    printf("%d ",A[k-1]);    
    printf("\n");     
}



     
void result( int A[], int k, int N, int R){
     int temp = R;
     
    if ( k == N ) {
         count++;
         if ( (R == A[N]) )
         {  printf("R IS %d\n",R); printsym(k,A); return;}    
             
         else 
            { return;}
    }
    else {
         
                     R = R+A[k];
                     symb[k]='+';
                     result(A,k+1,N,R);
                     
                     
                     temp = temp-A[k];
                     symb[k]='-';
                     result(A,k+1,N,temp);
             
              
         
         
    }
     
}

int main(){
      int A[] = {0,1,2,3,4,5,1};  //1-2+3-4+5=3
      int R = A[1]; 
      result(A,2,6,R);
    
    
}

YOu can understand this solution by watching this video
youtube.com/watch?v=14Jb7aycv3c

- coolsolution September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cool

- Biswajit Sinha September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

void printVec(vector<int> sol, vector<char> sign)
{
	for(int i = 0; i <sol.size(); i++)
	{
		cout <<sign[i]<<sol[i];
	}
}
void PrintCombination(vector<int> numbers, vector<int> sol, vector<char> sign, int target1, int pos)
{
	if(target1 == 0 )
	{
		cout << endl << "-------------Solution-------------"<<endl;
		printVec(sol, sign);
		cout << endl << "-------------Solution-------------"<<endl;
		return;
	}
	for(int i = pos; i<numbers.size(); i++)
	{
		int temp1 = target1-numbers[i];
		sol.push_back(numbers[i]);
		sign.push_back('+');
		PrintCombination(numbers, sol, sign, temp1, i+1);

		//sol.pop_back();
		//sol.push_back(numbers[i]);
		sign.pop_back();
		sign.push_back('-');
		temp1 = target1+numbers[i];
		PrintCombination(numbers, sol, sign, temp1, i+1);

		sign.pop_back();
		sol.pop_back();
	}
}
int main()
{
vector<int> numbers;
	vector<int> solu;
	vector<char> sign;
	numbers.push_back(1);
	numbers.push_back(2);
	numbers.push_back(3);
	numbers.push_back(4);
	numbers.push_back(5);
	PrintCombination(numbers, solu, sign, 3, 0);
return 0;
}

- Prashant R Kumar September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include<iostream>
#include<malloc.h>
#include<string.h>

using namespace std;

int flag =0;

void calculation(int *a,char *s,int n)
{
	int i,output=a[0];
	for(i=0; i< n-2 ;i++){
		if(s[i]=='+') {
			output +=a[i+1];
		}
		else output-=a[i+1];
	}
	if(output == a[n-1]){
		flag = 1;
		for(i=0; i<n-2 ;i++){
			cout<<a[i]<<s[i];			
		}
		cout<<a[i]<<" = "<<a[i+1]<<endl;		
		
	}
	
}

void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void prm(int *a , int n, char *s, int begin, int end) 
{
   int j; 
   char was[256];
   bzero(was, 256);
   if (begin == end){
   	  //cout<<s<<endl; 	
     calculation(a,s,n);
   }  
   else
   {
        for (j = begin; j <= end; j++)
       {
		  if (!was[*(s+j)]) {	
          swap((s+begin), (s+j));
          prm(a,n,s, begin+1, end);
          swap((s+begin), (s+j));
          was[*(s+j)] = 1;
          } 
       }
   }
} 
 
void pnc (int *a, int n)
{
	int i;
	char *s=new char[n-2];
	for(i=0;i<n-2;i++) s[i] = '+';
	//cout<<s<<endl;
	calculation(a,s,n);
	for(i=0;i<n-2;i++){
		s[i]= '-';
		//cout<<"s before prm = "<<s<<endl;
		prm(a,n,s,0,n-3);
	}
}

main()
{
	int n;
	cout<<"Enter number of elements\n";
	cin >>n;
	int *a=new int[n];
	cout<<"Enter set\n";
	for(int i=0;i<n;i++) cin>> a[i];
	cout<<"\n";
	pnc(a,n);
	if(flag ==0 ) cout<<"No solution\n";
	
}

- j.a.b. September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Test{
	static int count=0;
	public static void main(String args[]){
		System.out.println("Enter digits");
		Scanner scanner=new Scanner(System.in);
		String numbers[]=scanner.nextLine().split(" ");
		System.out.println("Enter answer which is wanted");
		int ans=scanner.nextInt();
		if(numbers.length==1&&Integer.parseInt(numbers[0])==ans){
			System.out.println("The solution is:"+numbers[0]);
			return;
		}
		generateAllEquations(numbers,ans,numbers[0],1);
		if(count==0)
			System.out.println("No solution");
	}
	private static void generateAllEquations(String[] numbers, int ans,String string, int index) {
		if(index==numbers.length){
			if(checkAns(string,ans))
				System.out.println("The "+(++count)+": solution is:"+string);
			return;
		}
		generateAllEquations(numbers,ans,string+"+"+numbers[index],index+1);
		generateAllEquations(numbers,ans,string+"-"+numbers[index],index+1);

	}

	private static boolean checkAns(String str,int ans){
		String temp="";
		int result=0;
		char prev=' ';
		for(int l=0;l<str.length();l++){
			if(str.charAt(l)=='+'||str.charAt(l)=='-'){
				if(prev=='+')
					result=result+Integer.parseInt(temp);
				else if(prev=='-')
					result=result-Integer.parseInt(temp);
				else
					result=Integer.parseInt(temp);
				prev=str.charAt(l);
				temp="";
			}
			else
				temp+=str.charAt(l);
		}
		if(prev=='+')
			result=result+Integer.parseInt(temp);
		else if(prev=='-')
			result=result-Integer.parseInt(temp);
		if(result==ans)
			return true;
		return false;
	}		
}
The complexity is n2.

- Apex September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity will be 2^(n-1), so it's not a good idea.

- Anonymous September 09, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More