4.1 of 5
www.google.com Mountain View, CA 5000+ Employees

"Write perfect code to generate all possible permutations of a string w/o repetitions and only using constant memory."
 Tags: code ,   See less 8

Part of a SWE Interview Review - one of 2,373 Google Interview Reviews

1
of 1
vote
You need to store and update a status vector to decide which permutation to generate next.
- Interview Candidate on Nov 20, 2011 Flag Response
0
of 0
class Permutation
{
int *orig;
int *curr;
int n;
int *perm;
int *temp;

public:
Permutation(int *o, int s)
{
n = s;
orig = new int[n];
memcpy(orig, o, n * sizeof(int));
curr = new int[n];
memcpy(curr, o, n * sizeof(int));
perm = new int [n];
memset(perm, 0, sizeof(int) * n);
temp = new int[n];
memset(temp, 0, sizeof(int) *n);
}

int *GetCurr()
{
return curr;
}

bool GenNext()
{
int i;

for (i = n-1; i >= 0; --i)
{
if (perm[i] != n - i)
{
++perm[i];
break;
}
}

if (i < 0)
{
return false;
}

for (int i = 0; i < n; ++i)
{
int r = -1;
for (j = 0; j < n &&; ++j)
{
if (temp[j] == 0)
{
++r;
if (r == perm[i])
{
curr[i] = orig[j];
temp[j] = 1;
break;
}
}
}
}

memset(temp, 0, sizeof(int) *n);

}
}
- NoOne on Dec 1, 2011 Flag Response
0
of 1
vote
It can also be done this way:
assuming string is ACEF.
A simple function to generate a unique digit for each character of the string. Assuming each character is unique in the string. Can also use Ascii. It will be of the order O(n).
say ACEF translates to 1234

Get the smallest number and the largest number
1234 and 4321.Can be done in liner amount of time if sorting algorithms like counting algo is used.

keep generating numbers between1234 and 4321 in which all the digits fall. Will involve incrementing numbers, mod (to find digits of the number) and binary search therefore running time of constant [to increment] + O(n)[to find digits] + O(nlogn) [to search it in the intial set of digits [1,2,3,4]]
- Sanchay Subhedar on Dec 1, 2011 Flag Response
0
of 0
Memory: Original as char array, used as fixed size boolean array

void PermPrint(char[] originals, boolean[] used, int processIndex, String previousString)
{
if(processIndex==originals.length)//done
{
System.out.println(previousString);
return;
}
else
{
for(int i=0; i<originals.length;i++)
{
if(!used[i])
{
used[i] = true;//firstly choose this unused char
PermPrint(originals, used, processIndex+1, previousString+originals[i]);
used[i] = false;//without choosing the char
}
}
}
}
- Anonymous on Dec 7, 2011 Flag Response
1
of 1
vote
1. Sort the array in lex order.

2. call the following function

public static void generatePermutation(String str /*sorted string*/) {
char[] A = str.toCharArray();
System.out.println(str);

if (A.length == 0) {
return;
}

/*Find the largest k, s.t. A[k] < A[k+1]*/
while (true) {
int i = A.length - 2, j = A.length - 1;
while (i >= 0 && A[i] >= A[i + 1]) {
i--;
}

if (i >= 0) {
while (A[i] >= A[j]) {
j--;
}
char tmp1 = A[i];
A[i] = A[j];
A[j] = tmp1;

/*reverse string from i+1 to A.length-1*/
for (int k = i + 1, l = A.length - 1; k < l; k++, l--) {
char tmp2 = A[k];
A[k] = A[l];
A[l] = tmp2;

}
System.out.println(A);
} else
break;
}

}
- Allen on Dec 7, 2011 Flag Response
0
of 0