Linkedin Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
static ArrayList<String[]> permutations(String[] a) {
ArrayList<String[]> ret = new ArrayList<String[]>();
permutation(a, 0, ret);
return ret;
}
public static void permutation(String[] arr, int pos, ArrayList<String[]> list){
if(arr.length - pos == 1){
list.add(arr.clone());
// System.out.println(arr[0] + arr[1] +arr[2] );
}else{
for(int i = pos; i < arr.length; i++){
swap(arr, pos, i);
permutation(arr, pos+1, list);
swap(arr, pos, i);
}
}
}
public static void swap(String[] arr, int pos1, int pos2){
String h = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = h;
}
package com;
import java.util.ArrayList;
import java.util.List;
public class Permutations {
public <T> List<List<T>> generate(List<T> listOfItems) {
List<List<T>> result = new ArrayList<List<T>>();
if (listOfItems == null) {
return null;
}
if (listOfItems.size() == 0) {
return result;
}
if (listOfItems.size() == 1) {
result.add(listOfItems);
return result;
}
// take out one item from the list
T pulledOutItem = listOfItems.get(0);
// get the sub list without that "pulled out item"
List<T> subList = listOfItems.subList(1, listOfItems.size());
// this method will return the permutations for the remaining items
List<List<T>> generatedListOfListOfItems = generate(subList);
// for each permutation of items
for (List<T> items : generatedListOfListOfItems) {
// clone that items permutation and put the "pulled out item" at
// each index location in the cloned permutation
for (int i = 0; i <= items.size(); i++) {
List<T> clonedItems = clone(items);
clonedItems.add(i, pulledOutItem);
result.add(clonedItems);
}
}
return result;
}
public static void main(String... args) {
List<Integer> listOfItems = new ArrayList<Integer>();
listOfItems.add(1);
listOfItems.add(2);
listOfItems.add(3);
listOfItems.add(4);
List<List<Integer>> listOfListOfItems = new Permutations()
.generate(listOfItems);
for (List<Integer> items : listOfListOfItems) {
for (Integer item : items) {
System.out.print(item + ",");
}
System.out.println("--");
}
}
public <T> List<T> clone(List<T> list) {
List<T> newList = new ArrayList<T>();
newList.addAll(list);
return newList;
}
}
Can you pls explain what permutation in best time means? Are you talking about all possible permutations of size 3 like 123, 321, 132, 213 etc?
static ArrayList<String[]> permutations(String[] a) {
ArrayList<String[]> ret = new ArrayList<String[]>();
permutation(a, 0, ret);
return ret;
}
public static void permutation(String[] arr, int pos, ArrayList<String[]> list){
if(arr.length - pos == 1){
list.add(arr.clone());
// System.out.println(arr[0] + arr[1] +arr[2] );
}else{
for(int i = pos; i < arr.length; i++){
swap(arr, pos, i);
permutation(arr, pos+1, list);
swap(arr, pos, i);
}
}
}
public static void swap(String[] arr, int pos1, int pos2){
String h = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = h;
}
Try this.
Integer[] a = { 1, 10, 13, 14, 18 };
Integer[] prefix = new Integer[0];
permutation(prefix, a);
private void permutation(Integer[] prefix, Integer[] input){
if(input == null || input.length == 0) {
System.out.println(Arrays.toString(prefix));
}
for(int i = 0; i < input.length; i++){
List<Integer> prefixList = new ArrayList<Integer>(Arrays.asList(prefix));
prefixList.add(input[i]);
prefix = prefixList.toArray(new Integer[prefixList.size()]);
List<Integer> l = new ArrayList<Integer>(Arrays.asList(input));
l.remove(i);
input = l.toArray(new Integer[l.size()]);
permutation(prefix, input);
}
}
Output:
[1, 10, 13, 14, 18]
[1, 10, 13, 18, 14]
[1, 10, 14, 13, 18]
[1, 13, 10, 14, 18]
[1, 13, 10, 18, 14]
[1, 13, 18, 10, 14]
public class PermuteCharsInString {
private String in;
StringBuilder out = new StringBuilder();
boolean[] used;
public void permutation(String str) {
in = str;
used = new boolean[in.length()];
permute();
}
public void permute() {
if (in.length() == out.length())
System.out.println(out.toString());
else {
for (int i = 0; i < in.length(); i++) {
if (used[i])
continue;
out.append(in.charAt(i));
used[i] = true;
permute();
used[i] = false;
out.setLength(out.length() - 1);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
PermuteCharsInString ps = new PermuteCharsInString();
char[] input = { 'a', 'b', 'c', 'd' };
String inp = new String(input);
ps.permutation(inp);
}
}
void permute(int[] data, int start){
if(data.length==start)
print(data);
else{
for(int i = start; i<data.length;i++){
if(i+1 < data.length && data[i] == data[i+1])
continue;
swap(data, i, start);
for(int j=start+1;j<=i;j++){
if(data[j] > data [i])
swap(data, i, j);
}
permute(data, start+1);
for(int j=i;j>=start+1;j--){
if(data[j] < data [i])
swap(data, i, j);
}
swap(data, i,start);
}
}
}
void swap(int[] data, int pos1, int pos2){
int tmp = data[pos1];
data[pos1] = data[pos2];
data[pos2] = tmp;
}
For now printed all results on screen , we can store it in list/set.
public static void finCombination(int[] input , int index){
int tmp;
if(index == (input.length-1)) {
System.out.println(i);
return;
}
for(int i=index; i<input.length;i++) {
tmp = input[index];
input[index] = input[i];
input[i] = tmp;
finCombination(input,index+1);
}
}
Whats time complexity of it? O(nlogn) ?
Time complexity of this solution would be O(nlogn) and Space complexity would be O(1) since we are not using additional space
public static List<String> findPermutation(char[] a, int pos, List<String> list) {
while (pos < a.length - 1) {
int swapWithIndex = pos + 1;
while (swapWithIndex < a.length) {
swap(a, pos, swapWithIndex);
storePermutation(a, list);
swap(a, pos, swapWithIndex);
swapWithIndex++;
}
pos++;
}
return list;
}
public static void storePermutation(char[] a, List<String> list) {
list.add(new String(a));
}
public static void swap(char[] a, int pos, int swapWithIndex) {
char temp = a[pos];
a[pos] = a[swapWithIndex];
a[swapWithIndex] = temp;
}
You can just use the principles of counting to get your answer. You first find the total number of possibilities of rearrangement which would be your length of the array factorial. Then you divide out all the duplicates factorial, and you get the total valid reorderings.
def permutations(nums):
numCount = {}
for num in nums:
if num not in numCount:
numCount[num] = 1
else:
numCount[num] += 1
total = factorial(len(nums))
for key, value in numCount.iteritems():
total /= factorial(value)
return total
def factorial(num):
if num == 0:
return 0
total = 1
for i in range(1, num + 1):
total *= i
return total
I kind of wonder about the following: am I in the minority of explaining my answer or do people just throw code at their interviewers? I really think for a complete answer we should quickly explain how one can conceptualize a permutation.
A permutation of a sequence X can elegantly be described in a recursive fashion as the permutations of the sub-sequence X' missing an arbitrary element e from X, with e inserted at each possible position in all permutations of X'.
We can proof using induction that we will generate no duplicate sequences that way, the following being the core argument of the proof: assuming that all permutations of X' have no duplicates, insertion at any position of a new element (e from above) will keep elements unique, because the arrangements of all elements other than e is unique. Since we do not remove any elements, the sequence remains unique after insertion of e.
Now translate the approach from above directly into code (Caution: code may contain LINQ):
Permutation of an empty sequence is a sequence containing the empty sequence. In all other cases, select all permutations missing the first element and add that first element into each position of the sequence.
- The Internet August 13, 2014Note that the only properties we need is for the argument to retrieve a sequence of integers, so the most abstract way of expressing this is to use the IEnumerable interface.