## 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++) {
}
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) {
}
}
if (resultVals.size() == n) {
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);

}``````

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

what's the time complexity of this solution?

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

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.

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

Did you test with input other than 3?

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

nnn kjnjkbk kj

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

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

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++) {
}
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) {
}
}
if (resultVals.size() == n) {
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);

}``````

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

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

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

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

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.

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

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

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

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

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

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

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

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

inonionionoinoinini

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

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

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

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

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

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

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

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 []

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 []``````

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

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

?>``````

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

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

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

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

}}

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.