## Facebook Interview Question for Software Engineer Interns

Country: United States
Interview Type: Phone Interview

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

Here is the java code for dutch national flag problem. Catering this scenario.

The logic is to align 1's to the left and 3's to the right. the 2's will automatically get into their respective positions.

``````import java.util.Arrays;

public class DutchNationalFlag {

public static void dnf(int[] a, int low, int high) {
int startIndex = 0;
int endIndex = a.length - 1;
int temp;

for (int i = 0; i <= endIndex ;) {
if (a[i] < low) {
temp = a[i];
a[i] = a[startIndex];
a[startIndex] = temp;
i++;
startIndex++;
} else if (a[i] > high) {
temp = a[i];
a[i] = a[endIndex];
a[endIndex] = temp;
endIndex--;
// do not increment i. We have to revisit this again
} else {
i++;
}
}
}

public static void main(String[] args) {
int[] a = new int[] {1,3,2,2,3,1,1,1,3,2,2,1,1};
DutchNationalFlag.dnf(a, 2, 2);
System.out.println(Arrays.toString(a));

}

}``````

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

will arr = { 1, 2, 2, 1, 1, 3, 1, 2, 1 }; give the expected result for the above code?

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

I think you need ((a[i] > high) && (i<endIndex)) in the second check

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

Your solution is wrong as you should also check for the endIndex >= i and startIndex <= i

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

dutch national flag problem.

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

I had no idea that this was a famous problem, thank you.

Comment hidden because of low score. Click to expand.
-2

``````public class Test {
int a[]={1,2,1,3,1,2,3,2};
int b[]= new int[20];
static int index=0;
void arrange(int val)
{
for(int i=0;i<a.length;i++)
{
if(a[i]==val)
{
b[index] = a[i];
index++;
}
}
}

public static void main(String args[]){

Test obj = new Test();
obj.arrange(1);
obj.arrange(2);
obj.arrange(3);
for(int j=0;j<index;j++)
{
System.out.print(obj.b[j]);
}
}``````

}

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

the solution above is 3 passes, the problem states that it should be 1 pass. And it is possible to do it in exactly 1 pass

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

In my opinion it is not good solution because of fact that in the task there is: "No extra list allocations are allowed" and "You are only permitted to swap elements." and in Your solution e.g.: You have got extra b[].

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

A java solution below. Note that given that I do have to keep track of where the ones and threes go, it'd only take an extra variable to count the twos as well and do a bucket sort... but I think this is most in keeping with the spirit of the question.

``````public static void sort123s(int [] arr)
{
int oneAt = 0;
int threeAt = arr.length-1;

int at = 0;
while(at <= threeAt)
{
if(arr[at] == 1)
{
swap(arr, at, oneAt);
if(at == oneAt)
at++;
oneAt++;
}
else if(arr[at] == 3)
{
swap(arr, at, threeAt--);
}
else
{
at++;
}
}
}

private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}``````

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

Its like two values in array just 0 and 1
Now here there are three values 1, 2, 3. Run a loop,with three indexes for three values. two at start and one at the last

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

#include<iostream>

using namespace std;

#define SIZE 10

int main()
{
int two=0, three=0, size=SIZE-1;

int arr[SIZE] = {1,3,3,2,1,2,3,1,3,2};

for(int i=0;i<SIZE;i++)
{
if(arr[i]==1)
continue;
else if(arr[i]==2)
{
two++;
arr[i] = 1;
}
else if(arr[i]==3)
{
three++;
arr[i] = 1;
}
}

for(int i=0;i<SIZE;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;

cout<<"THREE:: "<<three<<endl;
cout<<"TWO:: "<<two<<endl;

while(three!=0)
{
arr[size] = 3;
three--;
size--;
}
while(two!=0)
{
arr[size] = 2;
two--;
size--;
}

for(int i=0;i<SIZE;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;

return 0;
}

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

Fail. You are only permitted to swap elements.

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

1. Have two pointers, one representing beginning index of 2 and the other representing beginning index of 3.
2.Let their initial values be -1.
3. Traverse from left to right. If you get 1 and the two indices are -1 just leave it, no swap required
4. Let i be the looping index
5. If threestartindex is -1 and twostartindex isnt or viceversa, swap a[correspondingpointer] and a[i], increment correpondingpointer by one
6. if twostartindex is -1 and the two startindex isnt -1 and we have 2 as input, no swaps are necessary, they are in order. Do similarly for vice versa
7. If none of the indices are -1 and we get 2 as input, swap a[i] and a[threestartingpointer] and increment threestartingpointer by one
6. If none of the indices are -1 and we get 1 as input, swap a[i] and a[threestartingpointer] and increment threestartingpointer by one. Swap a[threestartingpointer-1] and a[twostartingpointer] and increment a[twostartingpointer]
7. If none of the indices are -1 and the input is 3, no swap required.

Hope this will work.

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

/**
* time: O(n)
* space: O(1)
*/
void sort(int[] arr){

int one = -1;
int two = -1;

for( int i =0; i < arr.length; i++ ){
if( arr[i] == 2 ){
ArrayUtils.swap(arr, i, two+1);
++two;
}
else if( arr[i] == 1 ){
ArrayUtils.swap(arr, i, two+1);
ArrayUtils.swap(arr, two+1, one+1);
++one;
++two;
}
else if( arr[i] != 3 ){
throw new IllegalStateException("Incorrect value for array: " + arr[i]);
}
}
}

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

``````void sort012(int a[], int arr_size)
{
int lo = 0;
int hi = arr_size - 1;
int mid = 0;

while(mid <= hi)
{
switch(a[mid])
{
case 0:
swap(&a[lo++], &a[mid++]);
break;
case 1:
mid++;
break;
case 2:
swap(&a[mid], &a[hi--]);
break;
}
}
}``````

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

Its Dutch national flag problem.

``````void sort(int *arr, int len) {
int low, mid, high;
for(low = mid = 0, high = len - 1; mid < high; ) {
arr[mid] == 1 ? swap(&arr[mid++], arr[low++]) : arr[mid] == 2 ? mid++ : swap(&arr[mid], &arr[high--]);
}
}``````

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

Keep a pointer to the last position, one to the first position. Start parsing the array from the begging. If at current position is 1, swap it with the first element, increment the pointer which keeps the start position; if 3 swap it with last, decrement pointer keeping last position. When current position == with pointer keeping last position, you're done. Caveat - what if the at the first position is already a 1, or a 3 at last? Check for those and (in/de)crement the corresponding pointers.

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

So, what is problem in my code?

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

#include<iostream>
using namespace std;
int main()
{
int o,i,m=0,n=6,temp,max=7;
int a[]={3,3,2,1,1,2,2};
for(i=0;i<max;i++)
{if(a[i]==1)
{temp=a[m];
a[m]=a[i];
a[i]=temp;
m++;}
if(a[i]==3)
{temp=a[n];
a[n]=a[i];
a[i]=temp;
n--;max--;}
if(a[i]==2)
{temp=a[m];
a[m]=a[i];
a[i]=temp;}}
for(i=0;i<7;i++)
{ cout<<a[i]<<" ";}
return 0;
}

if this code is correct ans of question

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

There must be an i-- under the condition (a[i]==3)

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

Wouldn't the partition algorithm work?

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

``````void Sort(int[] array)
{
int below = -1;
int above = array.Length;

for (int i = 0; i < above; )
{
if (array[i] == 1)
{
// below
Swap(array, i, ++below);
i++;
}
else if (array[i] == 3)
{
// above
Swap(array, i, --above);
}
else
{
// middle
i++;
}
}
}

void Swap(int[] array, int i, int j)
{
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}``````

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

``````for(i=1;i<n;i++)
{
if(a[i]<a[i-1])
{
for(j=i;j>0;j--)
{
if(a[j-1]<=a[j])
break;
else
{
tmp=a[j];
a[j]=a[j-1];
a[j-1]=tmp;
}
}
}
}``````

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

This is my solution, with complexity O(n).

``````void sort(int v[], int n) {
int begin = 0;
int end = n - 1;
int i;
for ( i = 0; i <= end; i++) {
if (v[i] == 1)
swap(v[begin++], v[i]);
else if (v[i] == 3) {
while(v[end] == 3 && end > i)
end--;
swap(v[i], v[end]);
}
}
}``````

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

doesn't work if an array is like this, a[9] = {1, 2, 3, 3, 2, 2, 3, 1, 1}, the second element '2' stays where it was.

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

``````void swap(int * input,int i,int j)
{
int temp = input[j];
input[j] = input[i];
input[i] = temp;
}
void sorting(int length, int *input)
{
int onePointer = 0;
int threePointer = length-1;
for(int i = 0; i <= threePointer; i++)
{
while(input[onePointer]==1)
{
i++;
onePointer++;
}
while(input[threePointer]==3)
{
threePointer--;
}

if(input[onePointer] == 3 && input[threePointer] == 1)
{
onePointer++;
threePointer--;
swap(input,i,threePointer);
}
else if(input[i] == 1)
{
swap(input,i,onePointer);
onePointer++;
}
else if(input[i] == 3)
{
swap(input,i,threePointer);
threePointer--;
i--;
}

}
}``````

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

package array;

public class arrangeNumbers {

public void arrangeData(int arr[]){
int oneLen=-1;
//int twoLen=-1;
int threeLen=-1;
int arrLen=arr.length-1;
System.out.println("arrlen:"+arrLen);
for (int i=0;i<arr.length;i++){
if (arr[i]==3 && threeLen!=i){
if (threeLen<0){
threeLen=arrLen;
}

while(arr[threeLen]==3 ){
threeLen--;
}
swap(i,threeLen,arr);
threeLen--;
}

if (arr[i]==2){
swap(i,oneLen+1,arr);
}
if (arr[i]==1){
if (oneLen<0){
swap(i,0,arr);
}
else{
swap(oneLen+1,i,arr);
}
oneLen++;

//printnumbers(arr);
}

if (i==threeLen && threeLen>0){
break;
}
}
printnumbers(arr);
}
private void printnumbers(int arr[]){
for(int i:arr){
System.out.println(i);
}

}
private static void swap(int i, int j, int[] arr) {
if (arr[i]==arr[j]||i==j){
return;
}
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void main(String args[]){
int[] arr={1,2,2,2,2,1,3,2,3,1,2,3,3,2,2,3,1,1,2,3,2,1};
arrangeNumbers an=new arrangeNumbers();
an.arrangeData(arr);
}

}

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

``````public class arrangeNumbers {

public void arrangeData(int arr[]){
int oneLen=-1;
int threeLen=-1;
int arrLen=arr.length-1;
System.out.println("arrlen:"+arrLen);
for (int i=0;i<arr.length;i++){
if (arr[i]==3 && threeLen!=i){
if (threeLen<0){
threeLen=arrLen;
}

while(arr[threeLen]==3 ){
threeLen--;
}
swap(i,threeLen,arr);
threeLen--;
}

if (arr[i]==2){
swap(i,oneLen+1,arr);
}
if (arr[i]==1){
if (oneLen<0){
swap(i,0,arr);
}
else{
swap(oneLen+1,i,arr);
}
oneLen++;

//printnumbers(arr);
}

if (i==threeLen && threeLen>0){
break;
}
}
printnumbers(arr);
}
private void printnumbers(int arr[]){
for(int i:arr){
System.out.println(i);
}

}
private static void swap(int i, int j, int[] arr) {
if (arr[i]==arr[j]||i==j){
return;
}
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static void main(String args[]){
int[] arr={1,2,2,2,2,1,3,2,3,1,2,3,3,2,2,3,1,1,2,3,2,1};
arrangeNumbers an=new arrangeNumbers();
an.arrangeData(arr);
}

}``````

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

here is a python code. go through the elements of the list. when encountering 1, throw it to the front; when encountering 2, do nothing; when encountering 3, throw it to the end.

``````Seq = [input sequence of 1, 2, and 3]

i = 0
for j in range(len(Seq)):
if Seq[i] == 1:
del Seq[i]
Seq = [1] + Seq
i += 1
elif Seq[i] == 2:
i += 1
elif Seq[i] == 3:
del Seq[i]
Seq = Seq + [3]

print "Sorted sequence is", Seq``````

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

``````public static void dutchFlag(int [] array)
{
int top = 0;
int bottom = array.length-1;

int cursor = 0;
while (cursor <=bottom)
{
if (array[cursor] == 0)
{
swap(array, top, cursor);
top++;
cursor++;
}
else if (array[cursor] == 2)
{
swap(array, bottom, cursor);
bottom--;
}
else
{
cursor++;
}
}
}

public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}``````

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

``````/**
* You are given an array of 1's 2's and 3's. Sort this list so the 1's are first, the 2's come second, and the 3's come third.
*
* Ex: Input [1, 3, 3, 2, 1]
* Output [1, 1, 2, 3, 3]
*
* But there is a catch!! The algorithm must be one pass, which means no merge/quick sort. Also no extra list allocations are allowed, which means no bucket/radix/counting sorts.
*
* You are only permitted to swap elements.
*
* @author patrick
*
*/
public class App {

private static void swap(int[] values, int i, int j) {
int x = values[j];
values[j] = values[i];
values[i] = x;
}

public static void sort(int[] values) {
for(int i=1; i<values.length; i++) {
int j = i;
while(j>0) {
int v = values[j];
int pv = values[j-1];
//if current value is smaller than adjacent
if(v < pv) {
swap(values, j-1, j);
j--;
}
else {
break;
}
}
}
}

public static void main(String[] args) {
int[] values = new int[] {1, 3, 3, 2, 1};

sort(values);

for(int v : values) {
System.out.print(v + " ");
}
}

}``````

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

Here is my PHP code:

``````<?php
\$a = array(1, 2, 1, 2, 3, 3, 3, 1);
\$n = count(\$a);
\$beginOfOne=0;
\$beginOfThree = \$n-1;

for(\$i=0; \$i<\$n; \$i++)
{
a:
if(\$a[\$i]==1)
{
if(\$i==\$beginOfOne)continue;
swap(\$i, \$beginOfOne);
++\$beginOfOne;
goto a;
}
elseif(\$a[\$i]==2)
{
if(\$i==(\$beginOfOne+1))continue;
if(\$a[\$i]==\$a[\$beginOfOne+1])continue;
swap(\$i, (\$beginOfOne+1));
goto a;
}
elseif(\$a[\$i]==3)
{
if(\$i>=\$\$beginOfThree)continue;
swap(\$i, \$\$beginOfThree);
--\$\$beginOfThree;
goto a;
}
else die('Error, wrong number in array');
}

function swap(\$p, \$d)
{
global \$a;

\$swap = \$a[\$p];
\$a[\$p] = \$a[\$d];
\$a[\$d] = \$swap;
}

?>``````

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

shouldn't it be just a counting sort problem?

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

``````#include <stdio.h>

void swap(int *a, int i, int j) {
int temp = a[i] ;
a[i] = a[j] ;
a[j] = temp ;
}

void sort(int *a, int len) {

int low = 0 ;
int mid = 0 ;
int high = len -1 ;

while(mid <= high) {
switch(a[mid]) {
case 1:
swap(a, low, mid) ;
++low;
++mid;;
break;
case 2:
++mid;
break;
case 3:
swap(a, mid, high) ;
--high;
break;
}
}
}

int main() {
int a[] = {1,3,3,2,1,3,2} ;

sort(a, 7) ;

for(int i = 0 ; i < 7 ; ++i)
printf("%d ", a[i]) ;
printf("\n");

}``````

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

i dnt knw d exact code..... but what if we consider d 3,3 as single element nd swap it with 1 in i/p array... {1,3,3,2,1} swaping 3,3 with 1 in d end about 2 will just b a single pass... and d array wl b sorted....

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

My ruby code in O(n)

``````#!/usr/bin/ruby
#
#
#

require 'pp'

def sort_array array

def swap i,j,a
tmp = a[i]
a[i] = a[j]
a[j] = tmp
end

i = 0
one = 0
three = array.size - 1

while i <= three

i += 1
one += 1
next
end

if array[i] == 3
swap i,three,array
three -= 1

if array[i] == 1
swap i,one,array
one += 1
end

end

i += 1

end

return array

end``````

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

Posted by me :-)

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

Here is a simple C implementation with one swap

``````#include <stdio.h>

void sort(int a[], int n)
{
int i,one=0,two=0,three=0,temp=0;
for(i = 0;i<15; i++)
{
if(a[i] == 1)
{
a[one]=1;
if(two) a[one+two]=2;
if(three) a[one+two+three] = 3;one++;
}
else if(a[i] == 2)
{
a[one + two] = 2;
if(three) a[one + two + three] = 3;two++;
}
else
{
three++;
}
}
}

main()
{
int i;
int array[] = {1,2,3,3,3,2,2,1,1,2,3,3,2,1,2};
for(i=0;i<15;i++)
printf(" %d",array[i]);
printf("\n");
sort(array,15);
for(i=0;i<15;i++)
printf(" %d",array[i]);
printf("\n");
}``````

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

``````public class FacebookSort{

static int length;
static int[] a;
static int start;
static int end;
static int temp;

public static void sort(){
temp = start;
while(temp <= end){
if(a[temp] == 1){
a[start] = a[temp] + (a[temp] = a[start]) - a[start];
start ++;
temp ++;
}
else if(a[temp] == 3){
a[end] = a[temp] + (a[temp] = a[end]) - a[end];
end --;
}
else{
temp ++;
}
}
}

public static void display(){
for(int i = 0; i < length; i ++){
System.out.print(a[i] + " ");
}
}

public static void main(String[] args){
length = args.length;
a = new int[length];
end = length - 1;
for(int i = 0; i < length; i ++){
a[i] = Integer.parseInt(args[i]);
}
sort();
display();
}
}``````

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

``````public static void modify123OnePass(int[] array) {
int oneEnd = -1;
int twoEnd = -1;
int threeEnd = -1;
for (int c : array) {
if(c == 1) {
array[++OneEnd] = 1;
if (twoEnd != -1) {
array[++twoEnd] = 2;
}
if (threeEnd != -1) {
array[++threeEnd] = 3;
}
} else if (c == 2) {
if (twoEnd == -1 && oneEnd != -1) {
twoEnd = oneEnd;
}
array[++twoEnd] = 2;
if (threeEnd != -1) {
array[++threeEnd] = 3
}
} else {
if (threeEnd == -1) {
if (twoEnd != -1) {
threeEnd = twoEnd;
} else {
threeEnd = oneEnd;
}
}
str[++threeEnd] = 'B';
}
}
}``````

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

sorry the last line

``array[++threeEnd] = 3;``

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

``````void rearrange(vector<int>& v)
{
for (int i = 0, p = -1, q = v.size(); i < q; ) {
if (v[i] == 1 && i != p) {
++p;
swap(v[p], v[i]);
continue;
} else if (v[i] == 3 && i != q) {
--q;
swap(v[q], v[i]);
continue;
}

++i;
}
}``````

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

I think we need to check each element in the array twice for both 1 and 3. Here is my code with time complexity O(n):

``````void sort(int a[], int n)
{
int begin = 0;
int end = n - 1;
int i;
while(a[begin]==1)
{
begin++;
}
while(a[end]==3)
{
end--;
}
for(i=begin;i<=end;i++)
{
if(a[i]==1)
{
swap(a[i], a[begin++]);
if(a[i]==3)
swap(a[i], a[end--]);
}
else if(a[i]==3)
{
swap(a[i], a[end--]);
if(a[i]==1)
swap(a[i], a[begin++]);
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

g

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class Test {
int a[]={1,2,1,3,1,2,3,2};
int b[]= new int[20];
static int index=0;
void arrange(int val)
{
for(int i=0;i<a.length;i++)
{
if(a[i]==val)
{
b[index] = a[i];
index++;
}
}
}

public static void main(String args[]){

Test obj = new Test();
obj.arrange(1);
obj.arrange(2);
obj.arrange(3);
for(int j=0;j<index;j++)
{
System.out.print(obj.b[j]);
}
}
}

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

sorting is not allowed

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.