## Linkedin Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 3 vote

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):

``````private static IEnumerable<IEnumerable<int>> GeneratePermutations(IEnumerable<int> a)
{
if (a.Count() == 0)
return new int[][] { new int[0] };

return from sub in GeneratePermutations(a.Skip(1))
from i in Enumerable.Range(0, sub.Count() + 1)
select sub.Take(i).Concat(new[] { a.First() }).Concat(sub.Skip(i));
}``````

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.

Note 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.

Comment hidden because of low score. Click to expand.
0

I think your algorithm only works when all characters in the array are unique.

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````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){

//     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;
}``````

Comment hidden because of low score. Click to expand.
0

You can avoid some more comparisons using:

``````for(int i = pos; i < arr.length; i++){
if (i != pos) swap(arr, pos, i);
permutation(arr, pos+1, list);
if (i != pos) swap(arr, pos, i);
}``````

that would save a little bit of processing time

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

return result;
}

public static void main(String... args) {
List<Integer> listOfItems = new ArrayList<Integer>();
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>();
return newList;
}
}``````

Comment hidden because of low score. Click to expand.
0

Output:

1,2,3,4,--
2,1,3,4,--
2,3,1,4,--
2,3,4,1,--
1,3,2,4,--
3,1,2,4,--
3,2,1,4,--
3,2,4,1,--
1,3,4,2,--
3,1,4,2,--
3,4,1,2,--
3,4,2,1,--
1,2,4,3,--
2,1,4,3,--
2,4,1,3,--
2,4,3,1,--
1,4,2,3,--
4,1,2,3,--
4,2,1,3,--
4,2,3,1,--
1,4,3,2,--
4,1,3,2,--
4,3,1,2,--
4,3,2,1,--

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0

In best time complexity aka most optimized solution.

Comment hidden because of low score. Click to expand.
0

Scala implementation

``````def permut[T](data:List[T]):List[List[T]] = {
data match {
case Nil=>Nil
(0 to e.length) map { i=>
(e.slice(0,i):+tail)++e.slice(i,e.length)
}
}).reduce(_++_).toList
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Please clarify if you mean all permutations or next permutation.

Comment hidden because of low score. Click to expand.
0

all permutations.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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){

//     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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
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]``````

Comment hidden because of low score. Click to expand.
0

apperantly its not right...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Prints all permutations in Lexical order.
Also handles duplicates.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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) ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

public static void swap(char[] a, int pos, int swapWithIndex) {
char temp = a[pos];
a[pos] = a[swapWithIndex];
a[swapWithIndex] = temp;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

def factorial(num):
if num == 0:
return 0``````

total = 1

for i in range(1, num + 1):
total *= i

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.

### 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.

### 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.

### 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.