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.

- The Internet August 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- segfault0x November 22, 2014 | Flag
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){
	        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;
	}

- Anonymous May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- guilhebl January 08, 2015 | Flag
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) {
			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;
	}
}

- cornholio August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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,--

- cornholio August 07, 2014 | Flag
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?

- Saurabh May 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In best time complexity aka most optimized solution.

- Invhelper May 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Scala implementation

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

- sabz July 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please clarify if you mean all permutations or next permutation.

- nilukush May 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

all permutations.

- Invhelper May 18, 2014 | Flag
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){
	        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;
	}

- Anonymous May 07, 2014 | Flag Reply
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));
            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]

- Anonymous May 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

apperantly its not right...

- Anonymous June 10, 2014 | Flag
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);
	}

}

- sLion August 27, 2014 | Flag Reply
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;
	}

- Byll September 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

TimeComplexity: O(nlogn) ?? Can you please help me with the TimeComplexity

Prints all permutations in Lexical order.
Also handles duplicates.

- Byll September 17, 2014 | Flag
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) ?

- nileshpatel7048 October 19, 2014 | Flag Reply
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) {
        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;
    }

- coder June 25, 2015 | Flag Reply
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)


    return total

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

total = 1

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

return total

- anon October 20, 2016 | Flag Reply


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