Google Interview Question
Country: United States
Interview Type: Written Test
Forgot to mention. This is eerily similar to the implementation of std::next_permutation (reverse and swap).
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
my mistake, should have read the code more carefully, ut's correct because it's entering the elements as strings.
sorry for the fuss!
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
Sorry, missing one 1 in the result, the correct result is
111001
111100
100111
100111
111100
110011
@JediKNight: The output generated by the above code is
111001
111100
100111
100111
111100
110011
What are you expecting the result to be?
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.
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
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
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!)
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.
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.
///////////////////////////////////////////////////////////////////////////////////////////////
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.
@Anonymous : Could you please explain which of the above solution is better and how? Also, what is the time and space complexity of it.
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 --;
}
}
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.
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
}
}
}
/*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;
}
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;
}
}
}
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;
}
}
}
}
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 }
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
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
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;
}
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;
}
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);
}
}
}
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)
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;
}
}
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)
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.
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.
Here is the output (snipped)
- Anonymous September 02, 2012