Facebook Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

DFS solution

public class PermutationDistance {
    public static List<List<Integer>> findPermutaionInDistance(int n) {
        List<List<Integer>> retList = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n * 2; i++) {
            result.add(0);
        }
        helper(retList, result, n);
        return retList;
    }
    public static void helper(List<List<Integer>> retList, List<Integer> result, int n) {
//        printOne(result);
        Set<Integer> resultVals = new HashSet<>();
        for (int val : result) {
            if (val != 0) {
                resultVals.add(val);
            }
        }
        if (resultVals.size() == n) {
            retList.add(new ArrayList<>(result));
            return;
        }
        for (int i = 1; i < n + 1; i++) {
            if (resultVals.contains(i)) {
                continue;
            }
            for (int j = 0; j < result.size() - i -1; j++) {
                if (result.get(j) == 0 && result.get(j + i + 1) == 0) {
                    result.set(j, i);
                    result.set(j + i + 1, i);
                    helper(retList, result, n);
                    result.set(j, 0);
                    result.set(j + i + 1, 0);
                }
            }
        }
    }

    public static void print(List<List<Integer>> res) {
        for (List<Integer> result : res) {
            for (int va : result) {
                System.out.print(va + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> res = findPermutaionInDistance(3);
        print(res);

    }

- Justin Gao May 09, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what's the time complexity of this solution?

- robb.krakow May 09, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Time complexity Analysis :

+ total N candidates and 2N positions:
+ at given iteration you can have N * 2N = 2 N^2 options, dropping const N^2
+ once you take a candidate, size of candidate goes down by 1, ( thus N-1).And size of positions goes down by 2 , thus 2n-2 = 2( n-1 )
+ same things happends next iterations
+ if we ignore constants, we see N * 2N * (n-1) * 2(n-1) * (n-2) * 2(n-2)
+ this is n! * n!

Correct me if wrong. Thanks.

- code reviewer May 09, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Did you test with input other than 3?

- Sumant May 09, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nnn kjnjkbk kj

- kj jkn July 07, 2019 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

def call_counter(func):
    def helper(*args):
        helper.calls += 1
        return func(*args)
    helper.calls = 0
    return helper

@call_counter
def fill_i(l, n, i):
    #print(l)
    for ind in range(0, 2*n-(i+1)):
        if l[ind] == 0 and l[ind+i+1] == 0:
            l[ind] = i
            l[ind+i+1] = i
            if i == 1:
                print('found:', l)
            else:
                fill_i(l, n, i-1)
            l[ind] = 0
            l[ind+i+1] = 0


def permu(n):
    l = [0] * 2 * n
    fill_i(l, n, n)


if __name__ == '__main__':
    permu(7)
    print('total attempts:', fill_i.calls)

Outputs:
found: [4, 1, 3, 1, 2, 4, 3, 2]
found: [2, 3, 4, 2, 1, 3, 1, 4]
total attempts: 18

- yuhechen2018 March 05, 2020 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

def back_track( tmp, n ){
  //println( str(tmp) )
  if ( n == 0 ) {
    println( str( tmp ) )
    return 
  }
  N = size( tmp )
  for ( i = 0; i < N - n -1 ; i+= 1 ){
    j = i + n + 1 
    continue( tmp[i] != 0 || tmp[j] != 0 )
    tmp_next = list(tmp) // deep copy 
    tmp_next[i] = tmp_next[j] = n 
    back_track( tmp_next, n-1 )
  }
}

def do_fb(n){
  buf = list( [0:n * 2 ] ) as { 0 } // get the buf
  back_track( buf , n  )
}
N = 4 
println( "== back tracking == ")
do_fb(N)

- NoOne May 09, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DFS solution

public class PermutationDistance {
    public static List<List<Integer>> findPermutaionInDistance(int n) {
        List<List<Integer>> retList = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n * 2; i++) {
            result.add(0);
        }
        helper(retList, result, n);
        return retList;
    }
    public static void helper(List<List<Integer>> retList, List<Integer> result, int n) {
//        printOne(result);
        Set<Integer> resultVals = new HashSet<>();
        for (int val : result) {
            if (val != 0) {
                resultVals.add(val);
            }
        }
        if (resultVals.size() == n) {
            retList.add(new ArrayList<>(result));
            return;
        }
        for (int i = 1; i < n + 1; i++) {
            if (resultVals.contains(i)) {
                continue;
            }
            for (int j = 0; j < result.size() - i -1; j++) {
                if (result.get(j) == 0 && result.get(j + i + 1) == 0) {
                    result.set(j, i);
                    result.set(j + i + 1, i);
                    helper(retList, result, n);
                    result.set(j, 0);
                    result.set(j + i + 1, 0);
                }
            }
        }
    }

    public static void print(List<List<Integer>> res) {
        for (List<Integer> result : res) {
            for (int va : result) {
                System.out.print(va + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> res = findPermutaionInDistance(3);
        print(res);

    }

- flyingforce May 09, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this is simpler to understand (simple arrays instead of list of lists):

import java.util.*;

public class HelloWorld {

    public static void main(String[] args) {
        myfunc(4);
    }
    
    public static void myfunc(int num) {
        int[] arr = new int[num * 2];
        boolean[] used = new boolean[num + 1];  // index 0 is not used
        myfunc(arr, used, 0);
    }
        
    public static void myfunc(int[] arr, boolean[] used, int nextAvailableIdx) {
        if (nextAvailableIdx == arr.length) {
            for (int i = 1; i < used.length; i++) {
                if (!used[i]) {
                    return;
                }
            }
            System.out.println(Arrays.toString(arr));
        }
        
        for (int tryNum = 1; tryNum < used.length; tryNum++) {
              int complimentIdx = nextAvailableIdx + tryNum + 1;
              if (used[tryNum] || complimentIdx >= arr.length || arr[complimentIdx] != 0) {
                continue;
              }
              arr[nextAvailableIdx] = tryNum;
              arr[complimentIdx] = tryNum;
              used[tryNum] = true;
              int j = nextAvailableIdx + 1;
              while (j < arr.length && arr[j] != 0) {
                j++;
              }
              myfunc(arr, used, j);
              arr[nextAvailableIdx] = 0;
              arr[complimentIdx] = 0;
              used[tryNum] = false;
        }
    }
}

- ofekpearl May 11, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here, I have used backtracking hopefully this fits within given constraints.

#include <bits/stdc++.h>
#define ll long long 
#define ld long double
#define F first
#define S second
#define pb push_back 
#define all(v) v.begin(),v.end()
#define pii pair <int,int >
#define pll pair <ll,ll >
#define pld pair <long double,long double>
#define SET(arr,val) memset(arr,val,sizeof arr)
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
using namespace std;
const int MAXN=100005;
const int MOD=1000000000+7 ;

bool getans(std::vector<int > &v,int n){
	if(n==0 ){
		for(int i: v){
			if(i==0)
				return false;
		}
		return true;
	}
		for(int j=0;j<v.size();j++){
			if(j+1+n>=v.size()){
				return false;
			}
			if(v[j]==0 and v[j+1+n]==0)
				v[j]=n,v[j+1+n]=n;
			else
				continue;
			bool to=getans(v,n-1);
			if(to){
				return true;
			}

			if(v[j]==n and v[j+1+n]==n)
				v[j]=0,v[j+1+n]=0;
			else
				continue;

		}
		return false;
}

int main()
{
	int n=2;
	// si(n);
	std::vector<int > ans;
	for(int i=0;i<2*n;i++){
		ans.pb(0);
	}
	bool yo=getans(ans,n);
	if(ans[0]==0)
		cout<<"-1";
	else
		for(int i:ans)
			cout<<i;
	return 0;
}

- cse150001038@iiti.ac.in May 13, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/env python3
"""
    Given an integer 'n', create an array such that each value is repeated twice. For example
    n = 3 -> [1,1,2,2,3,3]
    n = 4 -> [1,1,2,2,3,3,4,4]
    After creating it, find a permutation such that each number is spaced in such a way,
    they are at a "their value" distance from the second occurrence of the same number.
    For example: n = 3 -> This is the array - [1,1,2,2,3,3]
    Your output should be [3,1,2,1,3,2]
    The second 3 is 3 digits away from the first 3.
    The second 2 is 2 digits away from the first 2.
    The second 1 is 1 digit away from the first 1.
    Return any 1 permutation if it exists. Empty array if no permutation exists.
    Follow up: Return all possible permutations.
    Solution: O(n!.n!) uncomment the line to debug
"""
def back_track(buf, n):
    N = len(buf)
    if (n == 0):
        print(buf)
        return
    for i in range(N - n - 1):
        j = i + n + 1
        # print(buf, N, n, i, j) # uncomment to debug
        if buf[i] != 0 or buf[j] != 0:
            continue
        buf_next = list(buf) # deep copy
        buf_next[i] = buf_next[j] = n
        back_track(buf_next, n-1)
def main(n):
    buf = [0] * n * 2 # get the buf
    back_track(buf, n)
print("== back tracking == ")
main(4)

- KB2 May 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Deep copy is not frugal. It can be replaced by:

#buf_next = list(buf) # deep copy
        buf[i] = buf[j] = n
        back_track(buf, n-1)
        buf[i] = buf[j] = 0

Another optimization would be avoiding mirroring solutions and just print buf directly and in reverse.

- sergiy.lozovsky August 11, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{{{{ int arry[2*n]= {0}; //check for langford pairing exist if(n == 1 || n == 2 || n ==5) { exit; }else { temp = n; for(int j = 0;j<n;j++){ //check for if permutation exists else return empty array if(temp > 0){ for(int i = 0;i < 2*n;i++) { if ((arry[i+temp+1] == 0)&& (arry[i] == 0) ) { arry[i] = temp; arry[i+temp+1] = temp; temp--; } } } } }}}}} - Ammy May 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def dArray(n):

m = n+1

listA = list(range(1,m))

listB = listA.copy()

listC = sorted(listA+listB)

return listC

- Brian Mayrose May 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python:

def dArray(n):
m = n+1
listA = list(range(1,m))
listB = listA.copy()
listC = sorted(listA+listB)
return listC

- Brian Mayrose May 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def dArray(n):
m = n+1
listA = list(range(1,m))
listB = listA.copy()
listC = sorted(listA+listB)
return listC

- tmcs.brian May 28, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import itertools
extended_result=[]

def repeat_function(arr, k):
for i in range(1,k+1):
arr.extend(list(itertools.repeat(i,k)))
return arr

print(repeat_function(extended_result, 2))

- Anonymous June 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import itertools
extended_result=[]

def repeat_function(arr, k):
for i in range(1,k+1):
arr.extend(list(itertools.repeat(i,k)))
return arr

print(repeat_function(extended_result, 2))

- Kishore Raj June 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// C# code
using System;
using System.Collections.Generic;

namespace DoubleNumberArrayPermutation
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("please enter n:");
            int n = Convert.ToInt32(Console.ReadLine());
            if (n <= 0)
            {
                return;
            }

            int[] doubleNumbers = CreateDoubleNumberArray(n);
            Console.WriteLine(String.Join(',', doubleNumbers));

            Console.WriteLine("Permutations:");
            var res = GetPermu(n);
            res.ForEach(a => Console.WriteLine(String.Join(',', a)));

            Console.WriteLine("Press any key to exit.");
            Console.ReadKey();
        }

        public static int[] CreateDoubleNumberArray(int n)
        {
            int[] arr = new int[n * 2];
            int j = 0;
            for (int i = 0; i < n; ++i)
            {
                arr[j] = i;
                ++j;
                arr[j] = i;
                ++j;
            }

            return arr;
        }

        public static List<int[]> GetPermu(int n)
        {
            int[] state = new int[n*2];
            List<int[]> results = new List<int[]>();

            PermuOneNumber(state, n, results);

            return results;
        }


        public static void PermuOneNumber(int[] state, int current, List<int[]> results)
        {
            /*if (results.Count > 0)
            {
                return;
            }*/

            if (current == 0)
            {
                results.Add(state);
                return;
            }

            for (int i = 0; i < state.Length - current - 1; ++i)
            {
                /*if (results.Count > 0)
                {
                    return;
                }*/

                if (state[i] == 0 && state[i + current + 1] == 0)
                {
                    var stateNew = state.Clone() as int[];
                    stateNew[i] = current;
                    stateNew[i + current + 1] = current;
                    PermuOneNumber(stateNew, current - 1, results);
                }
            }
        }
    }
}

- lix246 July 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

inonionionoinoinini

- jknjknk July 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Brute force search over all permutations. Using a stack to back-track.

#!/usr/bin/env python
"""Given an integer 'n', create an array such that each value is repeated twice. For example
n = 3 -> [1,1,2,2,3,3]
n = 4 -> [1,1,2,2,3,3,4,4]
After creating it, find a permutation such that each number is spaced in such a way,
they are at a "their value" distance from the second occurrence of the same number.
For example: n = 3 -> This is the array - [1,1,2,2,3,3]
Your output should be [3,1,2,1,3,2]
The second 3 is 3 digits away from the first 3.
The second 2 is 2 digits away from the first 2.
The second 1 is 1 digit away from the first 1.
Return any 1 permutation if it exists. Empty array if no permutation exists.
Follow up: Return all possible permutations.

Complexity: O(n!^2) worst case, since we search all permutations."""

def valid_permutation(n):
    if n <= 1: return
    # a is the current permutation ("game board state").
    # Stack[k-1] = index of first ocurrence of the value k in a
    a, stack = [0] * (2 * n), [0]
    while stack:
        k = len(stack)
        x = stack[-1] # peek
        # Attempt to place value k at position x.
        if a[x] == 0 and a[x + k + 1] == 0:
            # Can place.
            a[x] = k
            a[x + k + 1] = k
            if k == n:
                # Placed all digits, found solution. Make sure to shallow-copy
                # since a keeps changing.
                yield a.copy()
                increment(a, stack, n)
            else:
                # Try to place the next value, starting at position 0.
                stack.append(0)
        else:
            # Can't place value, try the next configuration.
            increment(a, stack, n)

def increment(a, stack, n):
    """Updates a and stack to the next configuration. This means undoing
    the move in 'a' when we pop from 'stack'."""
    k = len(stack)
    x = stack.pop()
    # Undo placing 'k' at position 'x' -if it was placed there-.
    if a[x] == k:
        a[x] = 0
        a[x + k + 1] = 0
    while stack and x == 2 * n - k - 2:
        # Exhasted all search positions for value 'k', undo it and go
        # to the previous value.
        k -= 1
        x = stack.pop()
        a[x] = 0
        a[x + k + 1] = 0
    if k > 1 or x < 2 * n - 3:
        # Not at the end of the entire search space (which happens when
        # we're back at value 1 and have no more positions to search),
        # increment the search position of the current value (k).
        stack.append(x + 1)

from collections import Counter

def check_solution(a, n):
    return len(a) == 2 * n and sorted(Counter(a).items()) == [(k, 2) for k in range(1, n + 1)] \
        and all(a[x] == a[x + a[x] + 1] for x in range(2 * n) \
                if x + a[x] + 1 < 2 * n and (x - a[x] - 1 < 0 or a[x - a[x] - 1] != a[x]))

def num_solutions(n):
    count = 0
    for solution in valid_permutations(n):
        assert check_solution(solution, n)
        count += 1
    return count
    
if __name__ == "__main__":
    for n in range(10):
        print('n', n, '#solutions', num_solutions(n))

- prefertostayanonymous July 18, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/usr/bin/env python
"""Given an integer 'n', create an array such that each value is repeated twice. For example
n = 3 -> [1,1,2,2,3,3]
n = 4 -> [1,1,2,2,3,3,4,4]
After creating it, find a permutation such that each number is spaced in such a way,
they are at a "their value" distance from the second occurrence of the same number.
For example: n = 3 -> This is the array - [1,1,2,2,3,3]
Your output should be [3,1,2,1,3,2]
The second 3 is 3 digits away from the first 3.
The second 2 is 2 digits away from the first 2.
The second 1 is 1 digit away from the first 1.
Return any 1 permutation if it exists. Empty array if no permutation exists.
Follow up: Return all possible permutations.

Complexity: O(n!^2) worst case, since we search all permutations."""

def valid_permutation(n):
    if n <= 1: return
    # a is the current permutation ("game board state").
    # Stack[k-1] = index of first ocurrence of the value k in a
    a, stack = [0] * (2 * n), [0]
    while stack:
        k = len(stack)
        x = stack[-1] # peek
        # Attempt to place value k at position x.
        if a[x] == 0 and a[x + k + 1] == 0:
            # Can place.
            a[x] = k
            a[x + k + 1] = k
            if k == n:
                # Placed all digits, found solution. Make sure to shallow-copy
                # since a keeps changing.
                yield a.copy()
                increment(a, stack, n)
            else:
                # Try to place the next value, starting at position 0.
                stack.append(0)
        else:
            # Can't place value, try the next configuration.
            increment(a, stack, n)

def increment(a, stack, n):
    """Updates a and stack to the next configuration. This means undoing
    the move in 'a' when we pop from 'stack'."""
    k = len(stack)
    x = stack.pop()
    # Undo placing 'k' at position 'x' -if it was placed there-.
    if a[x] == k:
        a[x] = 0
        a[x + k + 1] = 0
    while stack and x == 2 * n - k - 2:
        # Exhasted all search positions for value 'k', undo it and go
        # to the previous value.
        k -= 1
        x = stack.pop()
        a[x] = 0
        a[x + k + 1] = 0
    if k > 1 or x < 2 * n - 3:
        # Not at the end of the entire search space (which happens when
        # we're back at value 1 and have no more positions to search),
        # increment the search position of the current value (k).
        stack.append(x + 1)

from collections import Counter

def check_solution(a, n):
    return len(a) == 2 * n and sorted(Counter(a).items()) == [(k, 2) for k in range(1, n + 1)] \
        and all(a[x] == a[x + a[x] + 1] for x in range(2 * n) \
                if x + a[x] + 1 < 2 * n and (x - a[x] - 1 < 0 or a[x - a[x] - 1] != a[x]))

def num_solutions(n):
    count = 0
    for solution in valid_permutations(n):
        assert check_solution(solution, n)
        count += 1
    return count
    
if __name__ == "__main__":
    for n in range(10):
        print('n', n, '#solutions', num_solutions(n))

- test July 18, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class DistanceSort{
    static boolean ans = false;
    public static void main(String[] args){
        List<List<Integer>> res = new ArrayList<>();
        int in = Integer.valueOf(args[0]);
        int[] arr = new int[in * 2];
        int pos = 0;
        for(int i=1; i<=in; i++){
            arr[pos++] = i;
            arr[pos++] = i;
        }
        System.out.println(Arrays.toString(arr));
        dfs(arr, new boolean[in * 2], new ArrayList<>(), res);
        System.out.println(ans);
        for(List<Integer> li : res){
            System.out.println(li.toString());
        }
    }

    public static void dfs(int[] arr, boolean[] visited, List<Integer> temp, List<List<Integer>>res){
        if(temp.size() == arr.length){
            if(check(temp)){
                res.add(new ArrayList<>(temp));
                ans = true;
                return;
            }
        }

        int k = -1;
        for(int i=0; i<arr.length; i++){
            if(visited[i]) continue;
            if(arr[i] == k) continue;
            k = arr[i];
            visited[i] = true;
            temp.add(arr[i]);
            dfs(arr, visited, temp, res);
            visited[i] = false;
            temp.remove(temp.size()-1);
        }
    }

    public static boolean check(List<Integer> temp){
        for(int i=0; i<temp.size(); i++){
            int right = i + temp.get(i) + 1;
            int left = i - temp.get(i) - 1;
            if(right < temp.size() && left >= 0){
                if(temp.get(right) != temp.get(i) && temp.get(left) != temp.get(i)){
                    return false;
                }
            }else if((right >= temp.size()) && (left < 0)){
                return false;
            }else if((right < temp.size()) && (temp.get(right) != temp.get(i))){
                return false;
            }else if((left >= 0) && (temp.get(left) != temp.get(i))){
                return false;
            }
        }
        return true;
    }
}

- xzhan211@binghamton.edu July 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// given an array w/ occupied slots, fill the rest slots
// e.g. given [4, 0, 0, 0, 0, 4, 0, 0], fill 0 w/ 1, 2, 3

function fillSlots(slots, digit) {
  //  console.debug(slots + ", digit: " + digit)

  if (digit < 1)
    console.log(slots)

  if (slots.length == 0 || digit < 1) {
    return slots;
  }

  var copySlots = []
  var exist = false
  for (var i = 0; i < slots.length - digit; i++) {

    //  console.debug(i+":"+slots[i] + ", digit: " + digit)

    if (slots[i]) {
      copySlots[i] = slots[i];
      continue
    }

    //  console.debug(copySlots)

    if (slots[i + digit + 1]) {
      copySlots[i] = slots[i];
      continue
    }

    if (i + digit + 1 > slots.length - 1) {
      copySlots[i] = slots[i];
      continue
    }

    copySlots[i] = digit
    for (var j = i + 1; j < slots.length; j++) {
      copySlots[j] = slots[j]
    }
    copySlots[i + digit + 1] = digit
    try {
      fillSlots(copySlots, digit - 1)

      // if (ret.length > 0)
      //   console.debug("<<< ret: " + ret)

      copySlots[i] = 0
      copySlots[i + digit + 1] = 0

      exist = true
    } catch (err) {
      // console.debug(err)
      copySlots[i] = 0
      copySlots[i + digit + 1] = 0
    }
  }


  if (!exist)
    throw "E_INVALID_" + digit
}

function permutation(digit) {
  var slots = [];

  for (var i = 0; i < digit; i++) {
    slots.push(0)
    slots.push(0)
  }

  return fillSlots(slots, digit)
}

try {
  permutation(7)
} catch (err) {
  console.debug(err)
}

console.log('--end--')

- sheng August 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int[] permute(int[] arr, int n) {
		for (int i = 0; i + n + 1 < arr.length; i++) {
			if (arr[i] == 0 && arr[i + n + 1] == 0) {
				arr[i] = n;
				arr[i + n + 1] = n;
				if (n == 1) {
					return arr;
				}
				int[] tmp = permute(arr, n - 1);
				if (tmp != null) {
					return tmp;
				}
				arr[i] = 0;
				arr[i + n + 1] = 0;
			}
		}
		return null;
	}

	static int[] nteger(int n) {
		return permute(new int[2 * n], n);
	}

- avico81 August 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def repeat_n(num_range, freq):
         data = []
         for i in range(1, num_range+1):
             temp = freq
             while temp:
                 data.append(i)
                 temp -= 1
         return data

- Anonymous October 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def repeat_n_linear(num_range, freq):
    iter_range = num_range * freq
    data = [0]*iter_range
    temp = 0
    for i in range(1, iter_range+1, freq):
        temp += 1
        data[i] = temp
    for d in range(len(data)):
        if not data[d]:
            data[d] = data[d+1]
    return data

- suyash October 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from itertools import permutations

def solution(n: int) -> list:
arr = [y for x in range(1, n + 1) for y in (x, ) * 2]
for perm in permutations(arr):
for i in range(1, n + 1):
if not (n*2 - perm[::-1].index(i) - 1) - perm.index(i) - 1 == i:
break
else:
return list(perm)
return []

- ololo October 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

from itertools import permutations

def solution(n: int) -> list:
    arr = [y for x in range(1, n + 1) for y in (x, ) * 2]
    for perm in permutations(arr):
        for i in range(1, n + 1):
            if not (n*2 - perm[::-1].index(i) - 1) - perm.index(i) - 1 == i:
               break
        else:
            return list(perm)
    return []

- ololo October 17, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python 2
O(N^2) runtime, O(N) memory

{{
def print_deployment(N):
a = [None]*(N*2)
print_deployment_rec(N, a)


def print_deployment_rec(N, a):
if N == 0:
print a
else:
for i in range(0,len(a)-N-1):
if a[i] or a[i+N+1]:
continue
else:
a[i], a[i+N+1] = N,N
print_deployment_rec(N-1, a)
a[i], a[i+N+1] = None, None
}}

- creativeChips November 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using memorized index array to second occurrence number.

* loop from last number
-- Case 1, if value is greater than mid. look left side to swap. And chang memorized value of
-- Case 2, if value is mid, look to left or right to swap, if swap position is less than, swap value
-- Case 3, if value id less than mid, cannot swap. Do validation

* Best and Worst Case : O(n)

<?php
	function createRepeatedArray($n){
		$memorize = [];
		$array = [];
		$index = 1;
		for($i =1; $i <= $n; $i++){
			array_push($array, $i, $i);
			$memorize[$i] = $index;
			$index+=2;
		}

		return [$memorize, $array];
	}

	//permutation
	function permutationDistance($array, $memorize){
		$lastNumber = count($memorize);
		$midnumber = ceil($lastNumber/2);

		for($i =$lastNumber; $i > 0; $i--){
			
			if($midnumber > $i){ //if number is lower than mid value, do validate only, cannot swap
				$secondIndex = $memorize[$i];

				$firstIndex = $secondIndex - ($i +1);

				if($array[$firstIndex]){
					if($array[$secondIndex] != $array[$firstIndex]){
						$firstIndex = $secondIndex + ($i +1);
						if($firstIndex > $lastNumber){
							return false;
						}else if($array[$secondIndex] != $array[$firstIndex]){
							return false;
						}
					}
				}else{
					$firstIndex = $secondIndex + ($i +1);
					if($firstIndex > $lastNumber){
						return false;
					}else if($array[$secondIndex] != $array[$firstIndex]){
						return false;
					}
				}

			}else if($midnumber == $i){ // if mid value can swap both sides
				$index = ($memorize[$i] -1) - ($i +1); 

				if($index > -1 && $array[$index] < $i){
					
					//swap in array
					$temp = $array[$index];
					$array[$index] = $array[$memorize[$i]];
					$array[$memorize[$i]] = $temp;

					$memorize[$i] =  $memorize[$i]-1;
				}else{
					$index = ($memorize[$i] -1) + ($i +1);
					if($array[$index] < $i){

						//
						$swapnumber = $array[$index];
						$swaptemp = $memorize[$swapnumber];
						$memorize[$swapnumber] = $memorize[$i];
						
						
						//swap in array
						$temp = $array[$index];
						$array[$index] = $array[$memorize[$i]];
						$array[$memorize[$i]] = $temp;

						$memorize[$i] = $swaptemp;
					}

				}

			}else{ //can swap left side only

				$index = ($memorize[$i] -1) - ($i +1); 

				$swapnumber = $array[$index];
				if($memorize[$swapnumber] < $memorize[$i]){
					$memorize[$swapnumber] = $memorize[$i];
				}
				
				//swap in array
				$temp = $array[$index];
				$array[$index] = $array[$memorize[$i]];
				$array[$memorize[$i]] = $temp;

				$memorize[$i] =  $memorize[$i]-1;

			}

		}

		//var_dump($array);
		//var_dump($memorize);
		return true;
	}

	for($i= 50; $i < 100; $i++){

		list ($memorize, $array) = createRepeatedArray($i);
		$res = permutationDistance($array, $memorize);
		$res = $res? 1 : 0;
		print $i. ": ". $res . "<br/><br/>";
	}
	

?>

- kathy December 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not all N has solution. For instance N=6 gives no answer.

found: [7, 3, 6, 2, 5, 3, 2, 4, 7, 6, 5, 1, 4, 1]
found: [7, 2, 6, 3, 2, 4, 5, 3, 7, 6, 4, 1, 5, 1]
found: [7, 2, 4, 6, 2, 3, 5, 4, 7, 3, 6, 1, 5, 1]
found: [7, 3, 1, 6, 1, 3, 4, 5, 7, 2, 6, 4, 2, 5]
found: [7, 1, 4, 1, 6, 3, 5, 4, 7, 3, 2, 6, 5, 2]
found: [7, 1, 3, 1, 6, 4, 3, 5, 7, 2, 4, 6, 2, 5]
found: [7, 4, 1, 5, 1, 6, 4, 3, 7, 5, 2, 3, 6, 2]
found: [7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3, 1, 6, 1]
found: [5, 7, 2, 6, 3, 2, 5, 4, 3, 7, 6, 1, 4, 1]
found: [3, 7, 4, 6, 3, 2, 5, 4, 2, 7, 6, 1, 5, 1]
found: [5, 7, 4, 1, 6, 1, 5, 4, 3, 7, 2, 6, 3, 2]
found: [5, 7, 2, 3, 6, 2, 5, 3, 4, 7, 1, 6, 1, 4]
found: [1, 7, 1, 2, 6, 4, 2, 5, 3, 7, 4, 6, 3, 5]
found: [5, 7, 1, 4, 1, 6, 5, 3, 4, 7, 2, 3, 6, 2]
found: [1, 7, 1, 2, 5, 6, 2, 3, 4, 7, 5, 3, 6, 4]
found: [2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1, 6]
found: [6, 2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1]
found: [2, 6, 7, 2, 1, 5, 1, 4, 6, 3, 7, 5, 4, 3]
found: [3, 6, 7, 1, 3, 1, 4, 5, 6, 2, 7, 4, 2, 5]
found: [5, 1, 7, 1, 6, 2, 5, 4, 2, 3, 7, 6, 4, 3]
found: [2, 3, 7, 2, 6, 3, 5, 1, 4, 1, 7, 6, 5, 4]
found: [4, 1, 7, 1, 6, 4, 2, 5, 3, 2, 7, 6, 3, 5]
found: [5, 2, 7, 3, 2, 6, 5, 3, 4, 1, 7, 1, 6, 4]
found: [3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7, 1, 6, 1]
found: [3, 5, 7, 2, 3, 6, 2, 5, 4, 1, 7, 1, 6, 4]
found: [2, 4, 7, 2, 3, 6, 4, 5, 3, 1, 7, 1, 6, 5]
found: [5, 6, 1, 7, 1, 3, 5, 4, 6, 3, 2, 7, 4, 2]
found: [4, 6, 1, 7, 1, 4, 5, 2, 6, 3, 2, 7, 5, 3]
found: [1, 6, 1, 7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3]
found: [4, 6, 1, 7, 1, 4, 3, 5, 6, 2, 3, 7, 2, 5]
found: [5, 3, 6, 7, 2, 3, 5, 2, 4, 6, 1, 7, 1, 4]
found: [4, 5, 6, 7, 1, 4, 1, 5, 3, 6, 2, 7, 3, 2]
found: [3, 4, 6, 7, 3, 2, 4, 5, 2, 6, 1, 7, 1, 5]
found: [5, 2, 4, 7, 2, 6, 5, 4, 1, 3, 1, 7, 6, 3]
found: [3, 4, 5, 7, 3, 6, 4, 1, 5, 1, 2, 7, 6, 2]
found: [1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2, 6]
found: [6, 1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2]
found: [4, 6, 3, 5, 7, 4, 3, 2, 6, 5, 2, 1, 7, 1]
found: [2, 6, 3, 2, 7, 4, 3, 5, 6, 1, 4, 1, 7, 5]
found: [5, 3, 6, 4, 7, 3, 5, 2, 4, 6, 2, 1, 7, 1]
found: [4, 1, 6, 1, 7, 4, 3, 5, 2, 6, 3, 2, 7, 5]
found: [2, 3, 6, 2, 7, 3, 4, 5, 1, 6, 1, 4, 7, 5]
found: [1, 5, 1, 6, 7, 2, 4, 5, 2, 3, 6, 4, 7, 3]
found: [1, 4, 1, 6, 7, 3, 4, 5, 2, 3, 6, 2, 7, 5]
found: [1, 6, 1, 3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7]
found: [2, 6, 3, 2, 5, 7, 3, 4, 6, 1, 5, 1, 4, 7]
found: [5, 2, 6, 4, 2, 7, 5, 3, 4, 6, 1, 3, 1, 7]
found: [2, 5, 6, 2, 3, 7, 4, 5, 3, 6, 1, 4, 1, 7]
found: [5, 2, 4, 6, 2, 7, 5, 4, 3, 1, 6, 1, 3, 7]
found: [1, 5, 1, 6, 3, 7, 4, 5, 3, 2, 6, 4, 2, 7]
found: [1, 5, 1, 4, 6, 7, 3, 5, 4, 2, 3, 6, 2, 7]
found: [1, 4, 1, 5, 6, 7, 4, 2, 3, 5, 2, 6, 3, 7]
total attempts: 1283

Code:

def call_counter(func):
    def helper(*args):
        helper.calls += 1
        return func(*args)
    helper.calls = 0
    return helper

@call_counter
def fill_i(l, n, i):
    #print(l)
    for ind in range(0, 2*n-(i+1)):
        if l[ind] == 0 and l[ind+i+1] == 0:
            l[ind] = i
            l[ind+i+1] = i
            if i == 1:
                print('found:', l)
            else:
                fill_i(l, n, i-1)
            l[ind] = 0
            l[ind+i+1] = 0


def permu(n):
    l = [0] * 2 * n
    fill_i(l, n, n)


if __name__ == '__main__':
    permu(7)
    print('total attempts:', fill_i.calls)

- yuhechen2018 March 05, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import copy

def all_combinations(arr, element, n, res):
    
    # arr, partiallly filled array, and indexes which are empty contain value as -1
    # num_elements_filled : Elements processed till now
    # n --> given number -- num_elements_filled == can be 
    
    # Base condition; if num_elements_filled == n; append in the resutlt set
    
    if element > n:
        res.append(copy.deepcopy(arr))
        return
    
    for i in range(2*n):
        
        next_pos = i+element+1
        
        if arr[i] == -1 and next_pos<(2*n) and arr[next_pos] == -1:
            
            arr[i] = element
            arr[next_pos] = element
            
            all_combinations(arr,element+1, n, res)
            
            arr[i] = -1
            arr[next_pos] = -1
            
            
def all_combinations_helper(n):
    
    arr = [-1] * (2*n)
    
    res = []
    
    all_combinations(arr,1,n,res)
    
    return res

    
print(all_combinations_helper(3))

- satyans24 September 19, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Given an integer 'n', create an array such that each value is repeated twice. For example
#
# n = 3 --> [1,1,2,2,3,3]
# n = 4 --> [1,1,2,2,3,3,4,4]
#
# After creating it, find a permutation such that each number is spaced in such a way, they are at a "their value"
# distance from the second occurrence of the same number.
#
# For example: n = 3 --> This is the array - [1,1,2,2,3,3]
#
# Your output should be [3,1,2,1,3,2]
#
# The second 3 is 3 digits away from the first 3.
# The second 2 is 2 digits away from the first 2.
# The second 1 is 1 digit away from the first 1.
#
# Return any 1 permutation if it exists. Empty array if no permutation exists.
#
# Follow up: Return all possible permutations.
#
from itertools import permutations


def generate(n: int):
    for i in range(1, n + 1):
        yield i
        yield i


def complete_permutation(p):
    n = len(p)
    l = [None] * (n*2)
    i = 0
    for v in p:
        while l[i] is not None:
            i += 1

        l[i] = v
        j = i + v + 1
        if j >= n*2 or l[j] is not None:
            return None
        l[j] = v

    return l



def find_permutations(n: int):
    for p in permutations(range(1, n + 1)):
        l = complete_permutation(p)
        if l is not None:
            yield l

def find_first_perumtation(n:int):
    return list(find_permutations(n))

print(list(find_permutations(2)))
print(list(find_permutations(3)))
print(list(find_permutations(4)))
print(list(find_permutations(5)))
print(list(find_permutations(6)))
print(list(find_permutations(7)))

[]
[[2, 3, 1, 2, 1, 3], [3, 1, 2, 1, 3, 2]]
[[2, 3, 4, 2, 1, 3, 1, 4], [4, 1, 3, 1, 2, 4, 3, 2]]
[]
[]
[[1, 4, 1, 5, 6, 7, 4, 2, 3, 5, 2, 6, 3, 7], [1, 4, 1, 6, 7, 3, 4, 5, 2, 3, 6, 2, 7, 5], [1, 5, 1, 4, 6, 7, 3, 5, 4, 2, 3, 6, 2, 7], [1, 5, 1, 6, 3, 7, 4, 5, 3, 2, 6, 4, 2, 7], [1, 5, 1, 6, 7, 2, 4, 5, 2, 3, 6, 4, 7, 3], [1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2, 6], [1, 6, 1, 3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7], [1, 6, 1, 7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3], [1, 7, 1, 2, 5, 6, 2, 3, 4, 7, 5, 3, 6, 4], [1, 7, 1, 2, 6, 4, 2, 5, 3, 7, 4, 6, 3, 5], [2, 3, 6, 2, 7, 3, 4, 5, 1, 6, 1, 4, 7, 5], [2, 3, 7, 2, 6, 3, 5, 1, 4, 1, 7, 6, 5, 4], [2, 4, 7, 2, 3, 6, 4, 5, 3, 1, 7, 1, 6, 5], [2, 5, 6, 2, 3, 7, 4, 5, 3, 6, 1, 4, 1, 7], [2, 6, 3, 2, 5, 7, 3, 4, 6, 1, 5, 1, 4, 7], [2, 6, 3, 2, 7, 4, 3, 5, 6, 1, 4, 1, 7, 5], [2, 6, 7, 2, 1, 5, 1, 4, 6, 3, 7, 5, 4, 3], [2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1, 6], [3, 4, 5, 7, 3, 6, 4, 1, 5, 1, 2, 7, 6, 2], [3, 4, 6, 7, 3, 2, 4, 5, 2, 6, 1, 7, 1, 5], [3, 5, 7, 2, 3, 6, 2, 5, 4, 1, 7, 1, 6, 4], [3, 5, 7, 4, 3, 6, 2, 5, 4, 2, 7, 1, 6, 1], [3, 6, 7, 1, 3, 1, 4, 5, 6, 2, 7, 4, 2, 5], [3, 7, 4, 6, 3, 2, 5, 4, 2, 7, 6, 1, 5, 1], [4, 1, 6, 1, 7, 4, 3, 5, 2, 6, 3, 2, 7, 5], [4, 1, 7, 1, 6, 4, 2, 5, 3, 2, 7, 6, 3, 5], [4, 5, 6, 7, 1, 4, 1, 5, 3, 6, 2, 7, 3, 2], [4, 6, 1, 7, 1, 4, 3, 5, 6, 2, 3, 7, 2, 5], [4, 6, 1, 7, 1, 4, 5, 2, 6, 3, 2, 7, 5, 3], [4, 6, 3, 5, 7, 4, 3, 2, 6, 5, 2, 1, 7, 1], [5, 1, 7, 1, 6, 2, 5, 4, 2, 3, 7, 6, 4, 3], [5, 2, 4, 6, 2, 7, 5, 4, 3, 1, 6, 1, 3, 7], [5, 2, 4, 7, 2, 6, 5, 4, 1, 3, 1, 7, 6, 3], [5, 2, 6, 4, 2, 7, 5, 3, 4, 6, 1, 3, 1, 7], [5, 2, 7, 3, 2, 6, 5, 3, 4, 1, 7, 1, 6, 4], [5, 3, 6, 4, 7, 3, 5, 2, 4, 6, 2, 1, 7, 1], [5, 3, 6, 7, 2, 3, 5, 2, 4, 6, 1, 7, 1, 4], [5, 6, 1, 7, 1, 3, 5, 4, 6, 3, 2, 7, 4, 2], [5, 7, 1, 4, 1, 6, 5, 3, 4, 7, 2, 3, 6, 2], [5, 7, 2, 3, 6, 2, 5, 3, 4, 7, 1, 6, 1, 4], [5, 7, 2, 6, 3, 2, 5, 4, 3, 7, 6, 1, 4, 1], [5, 7, 4, 1, 6, 1, 5, 4, 3, 7, 2, 6, 3, 2], [6, 1, 5, 1, 7, 3, 4, 6, 5, 3, 2, 4, 7, 2], [6, 2, 7, 4, 2, 3, 5, 6, 4, 3, 7, 1, 5, 1], [7, 1, 3, 1, 6, 4, 3, 5, 7, 2, 4, 6, 2, 5], [7, 1, 4, 1, 6, 3, 5, 4, 7, 3, 2, 6, 5, 2], [7, 2, 4, 5, 2, 6, 3, 4, 7, 5, 3, 1, 6, 1], [7, 2, 4, 6, 2, 3, 5, 4, 7, 3, 6, 1, 5, 1], [7, 2, 6, 3, 2, 4, 5, 3, 7, 6, 4, 1, 5, 1], [7, 3, 1, 6, 1, 3, 4, 5, 7, 2, 6, 4, 2, 5], [7, 3, 6, 2, 5, 3, 2, 4, 7, 6, 5, 1, 4, 1], [7, 4, 1, 5, 1, 6, 4, 3, 7, 5, 2, 3, 6, 2]]

- Vassili Gorshkov April 10, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
void digit_distance_permutations_aux(int n, std::vector<std::vector<int>>& results) {
std::vector<int> candidate(n * 2, 0);
digit_distance_permutations(n, 1, candidate, results);
}

void digit_distance_permutations(int n, int digit, const std::vector<int>& candidate, std::vector<std::vector<int>>& results) {
if (digit == n + 1) {
results.push_back(candidate);
return;
}
for (int i = 0; i < candidate.size(); ++i) {
if (candidate[i] == 0 && i + digit + 1 < candidate.size() && candidate[i + digit + 1] == 0) {
std::vector<int> new_candidate = candidate;
new_candidate[i] = digit;
new_candidate[i + digit + 1] = digit;
digit_distance_permutations(n, digit + 1, new_candidate, results);
}
}
}

}}

- Omri.Bashari May 05, 2021 | 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