Facebook Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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.
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
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)
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);
}
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;
}
}
}
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;
}
#!/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)
// 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);
}
}
}
}
}
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))
#!/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))
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;
}
}
// 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--')
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);
}
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
}}
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/>";
}
?>
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)
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))
# 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]]
{{
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);
}
}
}
}}
DFS solution
- Justin Gao May 09, 2019