Accenture Interview Question for Interns


Country: India
Interview Type: Phone Interview




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

1. store the size of the input array (i.e Len).
2. generate the bit sequence from (000...Len times) to (1111.... Len times)
3. Use above bit sequence to select the subset of the input set and then send the subset to the separate permute function.
Example :
input : {a, b, c}
abc
000 - 0 (Ignore)
001 - 1 (send subset {c} to permute function)
010 - 2 (send subset {b} to permute function)
011 - 3 (send subset {b,c} to permute function)
100 - 4 (send subset {a} to permute function)
101 - 5 (send subset {a,c} to permute function)
110 - 6 (send subset {a,b} to permute function)
111 - 7 (send subset {a,b,c} to permute function)

Please let me know if good solution is present.

- Pavan kumar Thati October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

How would this include "ca"?

- jvermette October 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

permutation of set {c,a} is {(ac),(ca)}.

- Pavan kumar Thati October 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

/* for Yogi.rulzz */
#include <stdio.h>
#include <stdlib.h>

typedef enum {false, true} bool;

char input[]={'a','b','c','z'};
#define N sizeof(input)/sizeof(*input)  //size of input array & num. decisions to make

void function()
{
	static int decisions = 0;  //number of decisions (either fill a letter, or blank decision)
	static bool used[N];	      //track characters we've used
	static char result[N+1];  //result array that will be printed after N decisions
    	static int respos = 0;      //position of result[] each invocation has an option to fill
    
	int i; 
	
	if(decisions == N)  { 	//we've made all N decisions in creating result 
        	result[respos]='\0';
        	if(respos !=0 ) printf("%s\n", result);  //print non-empty results
	        return;
    	}

	//if there is nothing in result array, we can make an empty decision 
	if( respos == 0 ) decisions++, function(), decisions--;
		
	//try filling result[] with characters from input[]
    	for(i=0; i < N; i++)   	{
        	if( used[i] ) continue;  //if i-th character already used, skip it

        	/* fill result[] with i-th char and recurse */	
		used[i] = true;					//mark i-th character as used
        	decisions++;					//we've made another decision
        	result[respos++]=input[i];			//place i-th character of input[] 
        	function(), decisions--, respos--;  	//recurse; unwind variables
        	used[i] = false;					//mark i-th character as unused
    	}
}	

int main (void)
{
	function(); 
	return 0;
}

Design decisions like calling the function "function" or using static variables (without passing variables recursively) were made for pedagogical and/or to limit sizes of stack frames.

In real code you'd want to:
1) For variables that don't unwind fully (e.g., used array), you need a wrapper that resets them before each call to the function.
2) You would decide against static variables if you are going to multi-thread into the function.
3) You would call "function" something else (but I find when talking about recursion, and this is only true for a recursive function, people sometimes function better looking at a bland name like "function" ).
4) For deep recursive use, you would might need to change the recursive function (hardware stack) to a software stack based solution to prevent stack overflow.

Please feel free to let me know of bugs in replies or here collabedit.com/b386g

Thank you Yogi, as this was fun and new for me.

Follow-up question to people:
=========================
If Input has a size of N.
How many output strings will there be?
{Counting formula + reasoning for it}

- S O U N D W A V E October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wow, above had perfect alignment when I pasted it, but it looks like garbage after I clicked Submit.

ideone.com/9jo6Kw , collabedit.com/b386g

- S O U N D W A V E October 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

or collabedit.com/b386g/history

- S O U N D W A V E October 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.util.Scanner;

public class CompletePermutationTest{
   public static void main(String [] args){
      Scanner scn=new Scanner(System.in);
	  
	  System.out.print("please enter your 4 alphabets\t");
	  char [] c1=new char[4];
	  int count1,count2,count3,count4;
	  count1=count2=count3=count4=0;
	  
	  for(int i=0;i<c1.length;i++)
	    c1[i]=scn.next().trim().charAt(0);
		
	System.out.println("here your alphabets that you enter\n");
	for(int i=0;i<c1.length;i++)
	  System.out.print(c1[i]+"\t");
	  
	  System.out.println("\n");
	  
	  for(int i=0;i<c1.length;i++)
	     for(int j=0;j<c1.length;j++)
		    for(int k=0;k<c1.length;k++)
			   for(int l=0;l<c1.length;l++)	
			     if(i==j&&j==k&&k==l){
 				    System.out.print(c1[l]+"\t");
					count1++;
					}
				else if(i==j&&j==k){
				    if(k!=l){
					  System.out.print(""+c1[k]+c1[l]+"\t");
					  count2++;
					  }
					  }
				else if(i==j){
				  if(j!=k&&k!=l&&j!=l){
				    System.out.print(""+c1[j]+c1[k]+c1[l]+"\t");
				      count3++;
					  }
				}
				else if(i!=j&&i!=k&&i!=l&&j!=k&&j!=l&&k!=l){
				  System.out.print(""+c1[i]+c1[j]+c1[k]+c1[l]+"\t");
				  count4++;
				  }	
				
				  
		System.out.println("\ntotal no of 1 string is\t"+count1+"\ntotal no of 2 String is\t"+count2);
		System.out.println("total no of 3 String is\t"+count3+"\ntotal no of 4 String is\t"+count4);
		System.out.println("total no of permutation is\t"+(count1+count2+count3+count4));
}
}

- gautam October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

class PermutationCombinationAI
    {
        public static void Do()
        {
            List<char> input = new List<char>() { 'a','b','c' };
            List<List<char>> container = new List<List<char>>();
            SimplePowerSet(input, container);

            foreach (List<char> set in container)
            {
                Utils.PrintGList<char>(set);
            }
        }

        private static void SimplePowerSet(List<char> input, List<List<char>> container)
        {
            List<char> temp = new List<char>();
            temp.AddRange(input);

            container.Add(temp);

            if (temp.Count > 1)
            {
                List<char> temp2 = new List<char>();
                for (int i = 0; i < temp.Count; i++)
                {
                    temp2 = new List<char>();
                    temp2.AddRange(temp);
                    temp2.RemoveAt(i);
                    SimplePowerSet(temp2, container);
                }
            }
        } 
    }

- allanchanly October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Wow, above had perfect alignment when I pasted it, but it looks like garbage after I clicked Submit.

ideone.com/9jo6Kw , collabedit.com/b386g

- S O U N D W A V E October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Arr{

static String[] set=new String[100];

static int size=0;
static int index=0;
public static void main(String a[])
{
String arr[]={"a","b","c","d"};

Arr array=new Arr();

for(int i=0;i<arr.length;i++)
{
set[i]=arr[i];
size++;
}

for(int j=0;j<size;j++)
{
array.output(set[j],arr);
}

for(int j=0;j<size;j++)
System.out.println(set[j]+"");


}

public void output(String s,String[] arr)
{
for(int i=0;i<arr.length;i++)
{
if(s.contains(arr[i]))
continue;
else
{
set[size]=s+arr[i];
size++;
}

}}}

- abhishekgrover October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;


public class CombinationGenerator {
    public static Comparator<String> stringComparator
            = new Comparator<String>() {

        @Override
        public int compare(String s, String s2) {
            if(s.length() > s2.length()) {
                return 1;
            } else if (s.length() == s2.length()) {
                return s.compareTo(s2);
            } else {
                return -1;
            }
        }
    };
    public String [] combine(String [] basic) {
        Set<String> combinations
                = new TreeSet<String>(stringComparator);
        for (int i = 0; i < basic.length; i++){
            for (int j = 0; j < basic.length; j++){
                String letter = basic[j];
                if (!combinations.contains(letter)) {
                    combinations.add(letter);
                } else {
                    combinations.addAll(combineWith(letter,
                            combinations));
                }
            }
        }
        return combinations.toArray(new String[0]);
    }
    public List<String> combineWith(String letter,
                                    Set<String> combinations) {
        List<String> buffer = new ArrayList<String>();
        for (String element : combinations){
             if(!element.contains(letter)) {
                 for (int i = 0; i <= element.toCharArray().length; i++) {
                     StringBuilder elementBuilder
                             = new StringBuilder(element);
                     elementBuilder.insert(i, letter);
                     buffer.add(elementBuilder.toString());
                 }
             }
        }
        return buffer;
    }
    public static void main(String [] args){
        for(String element: new CombinationGenerator()
                .combine(new String[]{"a", "b", "c"})) {
            System.out.println(element);
        }
    }
}

- getman.sergei October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<String> getPermutations(char[] source) {
    	
    	// Algorithm:
    	//
    	// to start, create a list of one item for each letter - in this 
    	// case: [a,b,c,d]
    	//
    	//      {a} {b} {c} {d}
    	//
    	// the iterative logic:
    	//   -add permutation list to all permutations
    	//   -discard the first permutation leaving {b} {c} {d} 
    	//   -discard the last item from our source items 
    	//    [a,b,c,d] - leaving [a,b,c] in this case)
    	//   -permutate the source items (here: [a,b,c]) into the remaining 
    	//    lists - in this case: {b},{c},{d}
    	//    'a' into {b},{c},{d}
    	//    'b' into {c},{d}
    	//    'c' into {d}
    	//
    	//     {ab,ba,ac,ca,ad,da}   {bc,cb,db,bd}   {cd,dc}
    	//
    	//   -add orginal permutations lists to 'all permutations' and discard
    	//
    	// repeat iterative logic above:
    	//   -add permutation list to all permutations
    	//   -discard the first permutation leaving: {bc,cb,db,bd}   {cd,dc}
    	//   -discard last item in source items: [a,b,c] becomes [a,b]
    	//   -permutate source items [a,c] into remaining lists: 
    	//     'a' into {bc,cb,db,bd}
    	//     'b' into {cd,dc}
    	//
    	//      {abc,bac,bca,acb..}  {bcd,dbc,cdb,bdc..}
    	//
    	// the last iteration should have one source item and one list to permutate.
    	// here it would be 'a' into {bcd,dbc,cdb,bdc..}
    	
    	List<ArrayList<String>> currentPermutationsLists = 
    			new ArrayList<ArrayList<String>>();
    	List<String> allPermutations = new ArrayList<String>();
    	
    	// populate currentPermutations with initial values
    	// also these initial permutations to 'all permutations'
    	for (char ch : source) {
    		ArrayList<String> permutations = new ArrayList<String>();
    		permutations.add("" + ch);
    		currentPermutationsLists.add(permutations);
    	}
    	
    	while (source.length > 1) {
    		
    		// add the currentPermutations to 'all permutations'
    		for (ArrayList<String> permutations : currentPermutationsLists) 
    			allPermutations.addAll(permutations);
    		
    		// discard the first permutation list
    		currentPermutationsLists.remove(0);
    		
    		// discard the last letter from source
    		source = Arrays.copyOf(source, source.length - 1);    		
    		
    		// now create new permutations
        	List<ArrayList<String>> newPermutationsLists = 
        			new ArrayList<ArrayList<String>>();
    		for (char ch : source) {    			
    			ArrayList<String> newPermutations = new ArrayList<String>();
    			for (ArrayList<String> permutations : 
    				currentPermutationsLists) {
    				newPermutations.addAll(
    						generatePermutations(permutations, ch));
    			}
    			newPermutationsLists.add(newPermutations);    			
    			currentPermutationsLists.remove(0);
    		}
    		currentPermutationsLists = newPermutationsLists;
    		
    		// if this is the last iteration, add the currentPermutations 
    		// to 'all permutations'
    		if (source.length == 1) {
       			allPermutations.addAll(currentPermutationsLists.get(0));
    		}	
    	}
    	
    	return allPermutations;
    }
    
    /**
     * Creates a new set for permutations with 
     * currentPermutations and the added character, newChar
     */
    private static ArrayList<String> generatePermutations(ArrayList<String>
    currentPermutations, char newChar) {
    	ArrayList<String> generatedPermutations = new ArrayList<String>();
    	
    	// no permutations? just use this letter as a start
    	if (currentPermutations.isEmpty()) {
    		generatedPermutations.add("" + newChar);
    		return generatedPermutations;
    	}
    	
    	for (String str : currentPermutations) {
			
    		// insert newChar at each index of str
    		for (int i = 0; i < str.length(); i++) {
   				generatedPermutations.add(insertChar(str, newChar, i));
    		}
    		
    		// add the final permutation (with newChar at the end)
    		generatedPermutations.add(str + newChar);    		
    	}
    	
		return generatedPermutations;    	
    }
    
    private static String insertChar(String str, char ch, int index) {
    	
    	// buffer for new string creation
    	char[] array = new char[str.length() + 1];

    	// 'i' is the index into string 
    	// 'j' is index into the new string
    	for (int i = str.length() - 1, j = array.length - 1; i >= 0; i--) {
    		
    		char nextChar = str.charAt(i);
    		
    		// chars to the left of the insertion index 
    		// move to the corresponding index
    		if (i < index)
    			array[i] = nextChar;
    		
    		// insertion char
    		else if (i == index) {
    			array[j] = nextChar;
    			array[i] = ch;
    			j = i;
    		}
    		
    		// shift to the right
    		else {
	    		array[j] = nextChar;
	    		j = i;
    		}
    	}
    	
    	return new String(array);    
    }

   public static void getPermutationsTest() {
	   char[] chars = {'a', 'b', 'c'};
	   
	   List<String> permutations = StringUtil.getPermutations(chars);
	   System.out.println(permutations);
   }

// output
[a, b, c, ab, ba, ac, ca, bc, cb, abc, bac, bca, acb, cab, cba]

- Michael.J.Keating October 24, 2013 | Flag Reply


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