## Facebook Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 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 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)
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 =  * n * 2 # get the buf
back_track(buf, n)
print("== back tracking == ")
main(4)``````

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 =  * (2 * n), 
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 =  * (2 * n), 
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);
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;
}
}``````

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.