Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Java Implementation
3.import java.util.*;
4.import java.lang.*;
5.import java.io.*;
6.
7./* Name of the class has to be "Main" only if the class is public. */
8.class Ideone
9.{
10. public static void main (String[] args) throws java.lang.Exception
11. {
12. Integer[] input={1,2,3,4};
13. List<List<Integer>> ans=permute(input);
14. System.out.println(ans.size());
15. for (List<Integer> lstChild : ans){
16. System.out.println();
17.
18. for (Integer lstelement : lstChild)
19. System.out.print(lstelement);
20. }
21.
22. }
23.public static List<List<Integer>> permute(Integer...myInts){
24.
25. if(myInts.length==1){
26. List<Integer> arrayList = new ArrayList<Integer>();
27. arrayList.add(myInts[0]);
28. List<List<Integer> > listOfList = new ArrayList<List<Integer>>();
29. listOfList.add(arrayList);
30. return listOfList;
31. }
32.
33. Set<Integer> setOf = new HashSet<Integer>(Arrays.asList(myInts));
34.
35. List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();
36.
37. for(Integer i: myInts){
38. ArrayList<Integer> arrayList = new ArrayList<Integer>();
39. arrayList.add(i);
40.
41. Set<Integer> setOfCopied = new HashSet<Integer>();
42. setOfCopied.addAll(setOf);
43. setOfCopied.remove(i);
44.
45. Integer[] isttt = new Integer[setOfCopied.size()];
46. setOfCopied.toArray(isttt);
47.
48. List<List<Integer>> permute = permute(isttt);
49. Iterator<List<Integer>> iterator = permute.iterator();
50. while (iterator.hasNext()) {
51. List<java.lang.Integer> list = iterator.next();
52. list.add(i);
53. listOfLists.add(list);
54.
55. }
56. }
57.
58.return listOfLists;
59. }
60.}
3.import java.util.*;
4.import java.lang.*;
5.import java.io.*;
6.
7./* Name of the class has to be "Main" only if the class is public. */
8.class Ideone
9.{
10. public static void main (String[] args) throws java.lang.Exception
11. {
12. Integer[] input={1,2,3,4};
13. List<List<Integer>> ans=permute(input);
14. System.out.println(ans.size());
15. for (List<Integer> lstChild : ans){
16. System.out.println();
17.
18. for (Integer lstelement : lstChild)
19. System.out.print(lstelement);
20. }
21.
22. }
23.public static List<List<Integer>> permute(Integer...myInts){
24.
25. if(myInts.length==1){
26. List<Integer> arrayList = new ArrayList<Integer>();
27. arrayList.add(myInts[0]);
28. List<List<Integer> > listOfList = new ArrayList<List<Integer>>();
29. listOfList.add(arrayList);
30. return listOfList;
31. }
32.
33. Set<Integer> setOf = new HashSet<Integer>(Arrays.asList(myInts));
34.
35. List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();
36.
37. for(Integer i: myInts){
38. ArrayList<Integer> arrayList = new ArrayList<Integer>();
39. arrayList.add(i);
40.
41. Set<Integer> setOfCopied = new HashSet<Integer>();
42. setOfCopied.addAll(setOf);
43. setOfCopied.remove(i);
44.
45. Integer[] isttt = new Integer[setOfCopied.size()];
46. setOfCopied.toArray(isttt);
47.
48. List<List<Integer>> permute = permute(isttt);
49. Iterator<List<Integer>> iterator = permute.iterator();
50. while (iterator.hasNext()) {
51. List<java.lang.Integer> list = iterator.next();
52. list.add(i);
53. listOfLists.add(list);
54.
55. }
56. }
57.
58.return listOfLists;
59. }
60.}
void printPerm(nums, s, p){
if( s == -1 || s == p) return;
if(p < nums.length) {
//swap
tmp = nums[p];
nums[p] = nums[p-1];
nums[p-1] = tmp;
}
for (num : nums) {
print num + " ";
}
print "\n"
printPerm(num, p, num.length -1);
p -= 1;
printPerm(num, s, p);
}
void main(...){
printPerm(nums, 0, nums.length)
}
void printPerm(nums, s, p){
if( s == -1 || s == p) return;
if(p < nums.length) {
//swap
tmp = nums[p];
nums[p] = nums[p-1];
nums[p-1] = tmp;
}
for (num : nums) {
print num + " ";
}
print "\n"
printPerm(num, p, num.length -1);
p -= 1;
printPerm(num, s, p);
}
void main(...){
printPerm(nums, 0, nums.length)
}
void printPerm(nums, s, p){
if( s == -1 || s == p) return;
if(p < nums.length) {
//swap
tmp = nums[p];
nums[p] = nums[p-1];
nums[p-1] = tmp;
}
for (num : nums) {
print num + " ";
}
print "\n"
printPerm(num, p, num.length -1);
p -= 1;
printPerm(num, s, p);
}
void main(...){
printPerm(nums, 0, nums.length)
}
void printPerm(nums, s, p){
if( s == -1 || s == p) return;
if(p < nums.length) {
//swap
tmp = nums[p];
nums[p] = nums[p-1];
nums[p-1] = tmp;
}
for (num : nums) {
print num + " ";
}
print "\n"
printPerm(num, p, num.length -1);
p -= 1;
printPerm(num, s, p);
}
void main(...){
printPerm(nums, 0, nums.length)
}
public void permutation(int[] array) {
int size = factorial(array.length);
for (int i = 0; i < size; i++) {
int i1 = i % array.length;
int i2 = (i + 1) % array.length;
int tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
printArray(array);
}}
public static int factorial(int value) {
if (value == 1) {
return 1;
}
return value * factorial(value - 1);
}
One random permutation?
private static void permutate(int arr[], int n) {
Random rand = new Random();
for(int i = n - 1; i > 0; --i) {
int j = rand.nextInt(i + 1);
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
Lexicografically generated permutations O(n*n!)
- EPavlova January 19, 2016