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

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

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


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