Google Interview Question


Country: United States
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
5
of 7 vote

The normal recursive call works with a little tweaking, without having to sort the huge list of permutations.

You need to reverse the sub-permutation that was generated.

Working C# code.

using System;
using System.Collections.Generic;
   
namespace CareerCup
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> google = new List<string>();
            google.Add("12");
            google.Add("4");
            google.Add("66");
            google.Add("8");
            google.Add("9");
   
            google.Sort();
            google.Reverse();
   
            printAllPermutationsLex(google, 0);
        }
  
  
        static void printAllPermutationsLex(List <String> perm, int start)
        {
            if (start == perm.Count)
            {
                for (int i = 0; i < perm.Count; i++)
                {
                    Console.Write(perm[i]);
                }
                Console.WriteLine();
                return;
            }
  
            for (int j = start; j < perm.Count; j++)
            {
                string tmp = perm[start];
                perm[start] = perm[j];
                perm[j] = tmp;
   
                printAllPermutationsLex(perm, start + 1);
                if (j < perm.Count-1)
                {
                    perm.Reverse(start + 1, perm.Count - start - 1);
                }
            }
        }
    }
}

Here is the output (snipped)

9866412
9866124
...
8966412
8966124
...
6698412
6698124
...
4986612
4981266
...
1298664
1298466
...
1246698
1246689

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

Forgot to mention. This is eerily similar to the implementation of std::next_permutation (reverse and swap).

- Anonymous September 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

not quite. consider the input array

[ 40 4]

despite having

4 < 40

, the correct permutation order should be

4 40 --> 440
40 4 --> 404

so the numbers should not be sorted based on their magnitude but rather on their highest digits, basically as if we were comparing them as strings.
once you get the properly ordered list, you generate the permutations of sorted array indices in lexicographic order then convert back to get the number behind it. Example:

input:

[4 40 9]

sort ->

[9 4 40]

permutations of indices in lexicographic order --> conversions

[ 0 1 2 ] --> 9440
[ 0 2 1 ] --> 9404
[ 1 0 2 ] --> 4940
[ 1 2 0 ] --> 4409
[ 2 0 1 ] --> 4094
[ 2 1 0 ] --> 4049

- oos September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

my mistake, should have read the code more carefully, ut's correct because it's entering the elements as strings.
sorry for the fuss!

- oos September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@cos: More relevant: you should have checked the output...

- Anonymous September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yeah that too :]

- oos September 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Still does not consider all cases. Try the set of integer {100, 1, 11}, based on the algorithm presented
(1) first sort the items as if they were string, result {1, 100, 11}, reverse {11, 100, 1}.
(2) permute, and the result is

11001
111100
100111
100111
111100
110011

- JediKnight44 September 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, missing one 1 in the result, the correct result is
111001
111100
100111
100111
111100
110011

- JediKnight44 September 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@JediKNight: The output generated by the above code is

111001
111100
100111
100111
111100
110011

What are you expecting the result to be?

- Anonymous September 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, this algorithm seems incomplete.

- Anonymous September 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess it is still missing some cases
Consider the following input{6,68,9}
The code output is 9686, 9668, 6896, (6869,6968), 6689. Which is not right in parenthesis part.

- Anonymous November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

firstly sort the the given array in non decreasing order(by checking first letter(MSL(most significant letter)) only,if first letter matches then only look for second letter and go on) then a usual simple permutation function will work
like permute(n->1)=for(i=n->0){a[i]+permute(n-1->1)} in respective order.

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

u didn't mention about the case when though the first MSL is same but one number is having second MSL while other do not have ......
for eg comparing 4 and 40

- chescho September 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

u didn't mention about the case when though the first MSL is same but one number is having second MSL while other do not have ......
for eg comparing 4 and 40

- chescho September 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

val xs = List(12,4,66,8,9)
xs.permutations // permutate
  .map(_.foldLeft("")(_ + _.toString)) // concatenate as strings
  .map(_.toInt) // back to int
  .toList.sortBy(-_) // sort desc
  .foreach(println _) // print one per line

9866412
9866124
9846612
9841266
9812664
9812466
...
1246689

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

Sorting a huge list is not good. The memory usage is too high.

- Anonymous September 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if numbers are repeated then you can remove rpetitions as you will get permutations in sorted order you just need to traverse this list once and remove all repetitions if there will be repetiotions they will be consecutive.

- dev September 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@rockingnidhijain61:- Do you have questions from your interview?

- Andy2000 September 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming the array is unique(if not, extend the TreeSet to support dups):

Need two TreeSets to avoid ConcurrentModificationException in Java:

public void permutate(String head, final SortedSet<Integer> subset) {
        if (subset.size() == 1) {
            String newPerm = head + subset.first();
            perms.add(newPerm);

            return;
        }

        final TreeSet<Integer> headSortedDigits = new TreeSet<Integer>(subset);
        final TreeSet<Integer> remainingSortedDigits = new TreeSet<Integer>(headSortedDigits);

        final Iterator<Integer> descIter = headSortedDigits.descendingIterator();

        while (descIter.hasNext()) {
            final Integer headInt = descIter.next();

            remainingSortedDigits.remove(headInt);

            permutate(head + headInt, remainingSortedDigits);

            remainingSortedDigits.add(headInt);
        }
    }

How to call the method:
Permutations obj = new Permutations();
final SortedSet<Integer> sortedSet = new TreeSet<Integer>();

 int[] array = <an integer array>;

        for (int i = 0; i < array.length; i++) {
            sortedSet.add(array[i]);
        }

        obj.permutate("", sortedSet);
        obj.print();

Running time:
O(logn*n!)

- Jack September 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assume no "0", and all the numbers are unique.(we'll resolve this later)

sort the numbers in the original array by this rule: if (ab<ba), then a<b

For this example, we get {16,4,75,8,9}

Then DFS. For the "expand" step, a node will pick every entry that is not picked by itself (increasing order) to generate a new node as a child. A node output itself if it has picked all the entries.



If there are duplicates, at the "expand" step, we only pick one of the duplicates entries to generate a child.

If there is a "0" entry, avoid putting it at the first level of the DFS tree.

- Liberacorpus September 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a basic C program without using any supplementary DS (except array obviously).
Time complexity: Horrible
Space complexity: No extra space . Just constant which is a few vars. here and there.

Assumption:
1. All the numbers in array are unique.
2. Numbers in array are given in Non-increasing order with respect to their Most Significant Digit.
If not then we can sort the array in O(NlogN) time. This will not affect my algo as Time complexity is Horrible anyway.

Advantages:
Only two:
1. Not using any extra DS.
2. Only using O(1) extra space.

///////////
//RECURSIVE APPROACH:


//Helper function
static void shiftLeftOrRight(int arr[], int start, int end, int len, int left)
{
    int startElem, from;
    if(left)
    {
        startElem = arr[start];
        from = start+1;
        if((start < 0) || (end>=len))
            return;
        for(; from <=end; from++)
            arr[from-1] = arr[from];

        arr[end] = startElem;
    }
    else
    {
        startElem = arr[end];
        from = end;
        if((start < 0) || (end>=len))
            return;
        for(; from > start; from--)
            arr[from] = arr[from-1];

        arr[start] = startElem;
    }
    return;
}

//Main function.
static void PermuteInNonIncOrder(int arr[], int len, int start, int end)
{
    int i=0;
    if(start>=end)
    {
        Print(arr, len);
        return;
    }
    for(i=start; i<=end; i++)
    {
        shiftLeftOrRight(arr, start, i, len, 0);
        PermuteInNonIncOrder(arr, len, start+1, end);
        shiftLeftOrRight(arr, start, i, len, 1);
    }
    return;
}
//////////////////

Explanation:
=============
Instead of swapping the 2 elements before and after the permutation, I have done
Right and left rotation before and after respectively. This is because of foll. reason as described by following example:

For ex.
Array in sorted order is :
9 8 66 4 12

when for example 66 is swaped with 12 for the next permutation, the resulting array: 9 8 12 4 66 is not in non-inc order
To make it in that order 66 is shifted to rightmost as 4 and 12 are brought before it in order. so that the resulting array
becomes: 9 8 4 12 66 . This will give the next permutation and swapping 12 and 66 with give the next to next permutation.
Hope its clear.
///////////////////////////////////////////////////////////////////////////////////////////////

- pavi.8081 September 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A better solution with full working code and output has already been posted.

- Anonymous September 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for the info. But for better or worse, I dont know, I just tried to give a solution without using any extra packaged DS library and without using any extra space.

- pavi.8081 September 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous : Could you please explain which of the above solution is better and how? Also, what is the time and space complexity of it.

- Anonymous September 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonynous: The total number of swaps is worse for this one, by a constant factor I believe, which matters because we are multiplying n factorial.

Since space etc is similar, I deem this one worse.

- Anonymous September 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

tag

- jiangok2006 September 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

tag

- jiangok2006 September 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java version

public void printPermutations (int[] num) {
	 String[] numString = new String[num.length];
	 for (int i = 0; i < num.length; i++) {
		 numString[i] = Integer.toString(num[i]);
	 }
	 Arrays.sort(numString);
	 reverseArray(numString);
	 printArray (getPerm (numString, 0));
	}

	private void printArray(ArrayList<String[]> perm) {
		for (String[] set: perm) {
			for (int j = 0; j < set.length; j++) {
				System.out.print(set[j]);
			}
			System.out.println();
		}
		
	}

	private ArrayList<String[]> getPerm (String[] num, int start) {
		ArrayList<String[]> permutations = new ArrayList<String[]>();	
		if (start == num.length - 1) {
			permutations.add(new String[]{num[start]});
		} else {
			String current = num[start];
			ArrayList<String[]> results = getPerm (num, start + 1);
			for (String[] set: results) {
				permutations.add(insertElement(set, 0, current));
			}
			for (String[] set: results) {
				for (int i = 1; i <= set.length; i++) {
					String[] newPerm = insertElement (set, i, current);
					permutations.add(newPerm);
				}
			}
		}
		return permutations;
	}
	
	private String[] insertElement(String[] set, int pos, String value) {
		String[] newResult = new String[set.length + 1];
		int i = 0;
		int index = 0;
		for (; i < pos; i++) {
			newResult[index ++] = set[i];
		}
		newResult[index ++] = value;
		for (; i < set.length; i++) {
			newResult[index ++] = set[i];
		}
		return newResult;
	}

	private void reverseArray (String[] array) {
		int i = 0;
		int j = array.length - 1;
		while (i < j) {
			String tmp = array[i];
			array[i] = array[j];
			array[j] = tmp;
			i ++;
			j --;
		}
	}

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

I think this function has problem.


String[] numString = new String[num.length];
for (int i = 0; i < num.length; i++) {
numString[i] = Integer.toString(num[i]);
}
Arrays.sort(numString);
reverseArray(numString);

If the input is [6, 60]. It will sort [60, 6]. But seems like we expect [6, 60] because 660 > 606.

- Anonymous November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swap (int c[],int a, int b)
{

int temp=c[a];
c[a]=c[b];
c[b]=temp;
}

void print(int A[],int n){


for (int var =n-1 ; var >=0 ; --var) {
cout<<A[var]<<" ";
}
cout<<"\n";
}


int permute(int a[],int i,int n){



int j;
if (i == 0)
print(a,n);
else
{
for (j = i; j>=0; j--)
{
swap(a,i ,j); //
permute(a, i-1, n);
swap(a,i,j); //backtrack
}
}



}

- name September 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Following is the BACKTRAKING Algorithm for printing all the permutation of 
Given string in decreasing order.
Time Complexity: O(N^2)
Input is taken as pointer to character arrays. Which is then sorted via :
QuickSortdecreasingOrder(): which sorts the strings in reverse order. That is "9" will come before "89"
*/
#include<stdio.h>
#include<stdlib.h>

#define MAX 100
#define TRUE  1
#define FALSE 0

static int isASolution(k, n)
{
	return (k == n-1);
}

static void printPermutation(int a[], int n)
{
	int i=0;
	for(i=0; i<n; i++)
		printf("%s", numbers[a[i]]);
	printf("\n");

	return;
}
static void candidatesForNextPlace(int a[], int k, int n, int c[], int *ncandidates)
{
	int i, is_in_perm[MAX];

	for(i=0; i<n; i++)
		is_in_perm[i] = FALSE;
	for(i=0; i<k; i++)
		is_in_perm[a[i]] = TRUE;

	*ncandidates = 0;
	for(i=0; i<n; i++)
	{
		if(is_in_perm[i] == FALSE)
		{
			c[*ncandidates] = i;
			(*ncandidates)++;
		}
	}
	return;
}

//Elegant Backtrack method
//Time Complexity: O(N^2)
static void allDecreasingPermutations(int a[], int k, int n)
{
	int i, ncandidates, c[MAX];
	if(isASolution(k, n))
		printPermutation(a, n);
	else
	{
		k++;
		candidatesForNextPlace(a, k, n, c, &ncandidates);
		for(i=0; i<ncandidates; i++)
		{
			a[k] = c[i];
			allDecreasingPermutations(a, k, n);
		}
	}
	return;
}

//main driver method
void generateDecreasingPermutationsDriver(char *numbers[], int n)
{
	int a[MAX]; /* solution vector */
    // trivial to sort in decreasing order, hence omitted the below function.
    //Complexity: O(N*lg(N))
	QuickSortdecreasingOrder(numbers, n); 
	allDecreasingPermutations(a,-1,n); // Complexity: O(N^2)
    
    return;
}

- pavi.8081 September 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the key point is how we sort the array

public class sortpermutation {
public static void main(String arg[]){
int a[]={12,4,66,8,9};
sorted(a);
}
public static void sorted(int a[]){
sort(a);
ArrayList<String> res=permutation(a);
for(String r:res){
System.out.println(r);
}
}
public static ArrayList<String> permutation(int a[]){
if(a.length==1){
ArrayList<String> res=new ArrayList<String>();
res.add(String.valueOf(a[0]));
return res;
}else{
HashSet<String> in=new HashSet<String>();
ArrayList<String> res=new ArrayList<String>();
for(int i=0;i<a.length;i++){
int next[]=new int[a.length-1];
int p=0;
int q=0;
while(p<a.length){
if(p!=i){
next[q]=a[p];
q++;
}
p++;
}
ArrayList<String> temp=permutation(next);
for(String t:temp){
String newstring=a[i]+t;
if(!in.contains(newstring)){
res.add(newstring);
in.add(newstring);
}
}
}
return res;
}
}
public static void sort(int a[]){
for(int i=0;i<a.length;i++){
int max=a[i];
int maxi=i;
for(int j=i+1;j<a.length;j++){
String or=String.valueOf(max);
String cur=String.valueOf(a[j]);
if(Integer.parseInt(cur+or)>Integer.parseInt(or+cur)){
max=a[j];
maxi=j;
}
}
a[maxi]=a[i];
a[i]=max;
}
}
}

- Anonymous September 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void permuteLexOrderRev (int arr[], int i, int n, boolean[] flagSelected) {
        if (i == n ) {
            for (int j : arr) {
                System.out.print (j);                
            }
            count++;
            System.out.println();
        }
        else {
            for (int j=n-1; j>=0; j--) {
                if (!flagSelected[j]) {
                    arr[i] = j;
                    flagSelected[j] = true;
                    permuteLexOrderRev (arr, i+1, n, flagSelected);
                    flagSelected[j] = false;
                }
            }
        }
    }

- vamsi360 September 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 bool comp(int a, int b) {
7 while(a>=10) a/=10;
8 while(b>=10) b/=10;
9 return (a>b);
10 }
11
12 void swap(int *a, int *b) {
13 int tmp = *a;
14 *a = *b;
15 *b = tmp;
16 }
17
18 void permutation(int arr[], int len, int *start, int *end) {
19 if(arr == 0) return;
20 if(start == end) {
21 for(int i = 0; i < len; i++)
22 cout << arr[i];
23 cout << endl;
24 return;
25 }
26
27 for(int *begin = start; begin < end ; begin++) {
28 swap(start, begin);
29 permutation(arr, len, start+1, arr+len);
30 swap(start, begin);
31 }
32 }
33
34 int main() {
35 int arr[] = {12,4,66,8,9};
36 // int arr[] = {1,2,3};
37 int len = sizeof(arr)/sizeof(int);
38 sort(arr, arr+len, comp);
39
40 permutation(arr, len, arr, arr+len);
41
42 return 0;
43 }

- cjmemory September 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just for a tricky case:

{2,22,3} how to sort this array?

if you sort it to {3,2,22} then the next permutation can give us the result like:
{3,2,22}
{3,22,2}
{2,3,22}
{2,22,3}
{22,3,2}
{22,2,3}
but actually {22,3,2} is larger than {2,22,3}

for the sorted array like {3,22,2}
{22,2,3} is larger than {2,3,22}

In conclusion, we cannot just use nextpermutation() to solve this problem

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

Yes, it's not simply to choose array order then permute them, one example is, { 5, 52, 1, 4}, obviously,
{5, 4} should be before {52}, but
{5, 1} is after {52}, then how to determine the order of 5 and 52?
Maybe we have to compare 2-number combination with other number, i.e. {5,4} vs {52}. Then how about complicated case like, { 9, 99, 9997, 8, 6...}, need check 3-number's , i.e({9, 99, 8} vs {9997} ?! Still no clear idea yet.
I

- Anonymous December 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have written a sort function which sorts the given integer array to an array with decreasing numbers (as required in the permutation). After this the permutation can be done the way explained in the first comment.

public static int[] sort(int[] input) {
        int[] factor = new int[input.length];
        double[] basedInput = new double[input.length];
        
        int itr = 0;
        
        // Convert all the input to "0.something" so that we use that to sort
        // the elements in the order we need. Also remember the number of times
        // we have to divide the number by 10 to 
        for (int i : input) {
            int count = 0;
            double d = i;
            while (d >= 1 ) {
                count++;
                d /= 10;
            }
            factor[itr] = count;
            basedInput[itr] = d;
            itr++;
        }

        Map<Double, List<Integer>> numbers = new HashMap<Double, List<Integer>>();
        
        // If two numbers are converted to the same number after the above
        // conversion, we also need to remember the power of 10 we divided
        // them by, use the power to break the tie in these cases.
        for (itr = 0; itr < input.length; itr++)  {
            double currentNumber = basedInput[itr];
            List<Integer> currentList;
            if (numbers.containsKey(currentNumber)) {
                currentList = numbers.get(currentNumber);
                currentList.add(factor[itr]);
            }
            else {
                currentList = new LinkedList<Integer>();
                currentList.add(factor[itr]);
            }
            numbers.put(currentNumber, currentList);
        }
         
        List<Double> uniqueBasedInput = new LinkedList<Double>();
        uniqueBasedInput.addAll(numbers.keySet());
        Collections.sort(uniqueBasedInput);
        Collections.reverse(uniqueBasedInput);
        
        int[] output = new int[input.length];
        
        itr = 0;
        for (double d : uniqueBasedInput) {
            List<Integer> factors = numbers.get(d);
            Collections.sort(factors);
            
            for (double f : factors) {
                System.out.println(f);
                output[itr++] = (int)Math.round((d * Math.pow(10, f)));
            }
        }
        
        // For debug
        for (int i : output) {
            System.out.print(i + "\t");
        }

        return output;
    }

- Sameer October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Some of the input and output

Input: 	1	2	330	4	10	100	
Output:	4	330	2	1	10	100

Duh, but fails for this input

Input: 	2	22	3	
Output:	3	22	2

- Sameer October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public ArrayList<String> permutation(String[] num)
{
   Arrays.sort(num);
   Arrays.reverse(num);

   ArrayList<String> res = new ArrayList<String>();
   pHelper(0, num, res);

   return res;
}

public void pHelper(int p, String[] num, ArrayList<String> res)
{
   if(p == num.length)
   {
      String v = "";
      for(int i = 0; i < num.length; i++)
        v += num[i];
      res.add(v);
      return;
   }

   pHelper(p+1, num, res);
   for(int i = p+1; i < num.length; i++)
   {
       swap(num, p, i);
       pHelper(p+1, num, res);
       swap(num, p, i);
   }
}

public void swap(String[] num, int p, int i)
{
   String h = num[i];
   num[i] = num[p];
   num[p] = h;
}

- panxin0718 February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool cmp(int x, int y)
{
        string X = getstr(x+y);
        string Y = getstr(y+x);
        return X < Y;
}
vector<int> a; // input
sort(a.begin(), a.end(), cmp);
do {
    for (auto it = a.begin(); it != a.end(); it++)
           cout << *it ;
    cout << endl; 
} while(next_permutation(a.begin(), a.end());

- Anonymous August 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the sort comparator should like this and
it can compare "5566"with"5566557" or "5566554"

DP from"5566" "5566557"
to"5566" "557"

public class Solution{

  public void printPermutation(ArrayList<String> strs){
    Comparator<String> com = new Comparator<String>(){
      @override
      public int compare(String a , String b){
        if(a.length()*b.length() ==0) return 0;
        int key = a.charAt(0);
        if(key > b.charAt(0)) return 1;
        if(key < b.charAt(0)) return -1;
        return compare_DP( a, b);
      }
      public int compare_DP(String a, String b){
        if(a.length() < b.length()) {
          String tem = a;
          a = b;
          b = a;
        }
        int lena = a.length();
        int lenb = b.length();
        for(int i = 0 ; i < lenb ; i++){
          if(a.charAt(i) > b.charAt(i)) return 1;
          if(a.charAt(i) < b.charAt(i)) return -1;
        }
        if(lena == lenb) return 0;
        a = a.substring(lenb);
        return compare_DP(a,b);
      }
    }
    Collections.sort(strs, com); 
    printPermutation_DP(strs , 0);
  }
  public void printPermutation_DP(ArrayList<String> strs , int index){
    if(index == strs.size()){
      for(String str : strs){
        printf(str);
      }
      println("");
      return ;
    }
    for(int j = index ; j < strs.size() ; j++){
       String tem = strs.get(start);
       strs.set(start,strs.get(j));
       strs.set(j,tem);
       printPermutation_DP(strs,index+1); 
       reverse(strs,  j , strs.size()-1);
    }
  }
  public void revers(ArrayList<String> strs , int p , int q){
    for(int i = p , j = q ; i < j ;i++,j-- ){
      String tem = strs.get(i);
       strs.set(i,strs.get(j));
       strs.set(j,tem);
    }
  }
}

- huihancarl September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would just write a permutations function and add each permutation to a BST and later traverse through the BST.

- bp September 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from math import log, floor
def ordered_perms(array, swap_index = 0):

    # initialize (sort the array in reverse by the first digit of every number)
    if swap_index == 0:
        array = sorted(array, key = lambda x: pow(10, int(floor(log(x, 10)))))
        array.reverse()

    # if we have swapped enough times, print
    if swap_index == len(array):
        print array
        return

    # start new recursion trees with each descending value in the highest place
    for i in range(swap_index, len(array)):

        # copy the array, because we'll mutate it throughout its own call stack
        array_copy = [val for val in array]

        # do the swap
        array_copy[i], array_copy[swap_index] = array_copy[swap_index], array_copy[i]

        # recurse onto the next swap index
        ordered_perms(array_copy, swap_index + 1)

- asdf January 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Permutate the given array and push the result into an ArrayList
2. Sort in decreasing ordering using comparator

import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Map;


public class Main {
	
	public static ArrayList<Integer> result = new ArrayList<Integer>();
	public static void main(String args[]){
		Integer[] input = {30,33,3};
		ArrayList<Integer> inp = new ArrayList<Integer>(Arrays.asList(input));
		ArrayList<Integer> current = new ArrayList<Integer>(); 
		permutate(inp,current, inp.size());
		ValueComparator vc = new ValueComparator(Main.result);
		Collections.sort(Main.result,vc);
		for(int i=0;i<Main.result.size();i++){
			System.out.println(Main.result.get(i));
		}
	}
	public static void permutate(ArrayList<Integer> inp, ArrayList<Integer> current, int length){
		
		if(current.size() == length){
			String res = "";
			for(int i=0;i<current.size();i++){
				res += String.valueOf(current.get(i));
			}
			Main.result.add(Integer.parseInt(res));
		}
		for(int i=0;i<inp.size();i++){
				ArrayList<Integer> tempinp = new ArrayList<Integer>(inp);
				int temp = tempinp.get(i);
				ArrayList<Integer> tempcurrent = new ArrayList<Integer>(current);
				tempcurrent.add(temp);
				tempinp.remove(i);
				permutate(tempinp, tempcurrent,length);
			
		}
	}
}
class ValueComparator implements Comparator<Integer>{
	ArrayList<Integer> base;
	public ValueComparator(ArrayList<Integer> base){
		this.base=base;
	}
	public int compare(Integer arg0, Integer arg1){
		if(arg0>arg1)
			return -1;
		else
			return 1;
	}
}

- nitesh.kedia5 March 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is just a matter of getting the next smallest permutation till no smaller values are possible. I solved this iteratively. Essentially it boils down to
1. Identify what two elements need to be swapped to get the next lowest permutation
2. Swapping the the identified elements
Here are the steps
1. Starting from the rightmost element keep going left till you find an element that is larger than the previous element. Let's call this John. I have used to pointers for this
2. Once the pivot has been identified find the closest element(by value) right of John that is larger than pivot (by value). Lets call this Doe
3. Swap the values of John and Doe
4. Reverse sort the array starting from the index next to the original position of John all the way till the end.
Repeat 1-4 till no John is found in step 1
This particular question has an annoying peculiarity that the numbers in the array are not digits. So you'll need to write a custom comparator to compare the numbers. Below is a python implementation

from functools import cmp_to_key


def generate_permutations_desc(array):
    custom_sort(array, 0, len(array))
    yield array
    while True:
        current = len(array) - 2
        prev = len(array) - 1
        index = -1
        swap_index = -1
        while current >= 0:
            if custom_compare(array[prev], array[current]) < 0:
                index = current
                break
            current -= 1
            prev -= 1
        if index == -1:
            return
        max_val = 0
        for i in range(index+1, len(array)):
            if custom_compare(array[i], array[index]) < 0 and custom_compare(max_val, array[i]) < 0:
                swap_index = i
                max_val = array[i]
        array[index], array[swap_index] = array[swap_index], array[index]
        custom_sort(array, index+1, len(array))
        yield array[:]


def custom_sort(array, start, end):
    array[start:end] = sorted(array[start:end], key=cmp_to_key(custom_compare_rev))


def custom_compare(x, y):
    n = str(x) + str(y)
    np = str(y) + str(x)
    return int(n) - int(np)


def custom_compare_rev(x, y):
    n = str(x) + str(y)
    np = str(y) + str(x)
    return int(np) - int(n)


arr = [12, 4, 66, 8, 9]
for p in generate_permutations_desc(arr):
    print(p)

- lalat.nayak June 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Permutation(Int[] array, recLength, n)

       if(recleng == n)
      {
           list<int[]> permutation = new list<int>();
          permutation.add(array);
      }
    
        for(int i= recLegn, i <n; i++)
       {

             swap(int[i], int[recLen])
            permutation(array, k+1, n)
            //BackTrack
          swap(int[i], int[k])
        }

Once this is done, Sort the list and print it.

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

What is 'k' here?

- mytestaccount2 October 08, 2013 | 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