Write perfect code to generate all possible permutations of a string w/o repetitions and only using constant memory.

Question

Sigiloso · Accepted Answer

You need to store and update a status vector to decide which permutation to generate next.

Sigiloso · Answer

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

Allen · Answer

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] = 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;
        }

    }

Coder · Answer

Can somebody explain the logic of the code by Alien ?

NoOne · Answer

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);

    }
}

Sanchay Subhedar · Answer

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]]

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas