Accenture Interview Question
InternsCountry: India
Interview Type: Phone Interview
/* 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}
Wow, above had perfect alignment when I pasted it, but it looks like garbage after I clicked Submit.
ideone.com/9jo6Kw , collabedit.com/b386g
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));
}
}
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);
}
}
}
}
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++;
}
}}}
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);
}
}
}
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]
1. store the size of the input array (i.e Len).
- Pavan kumar Thati October 21, 20132. 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.