Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

Keep low, mid, and high indices. Low and high are the points at which everything to the left of low has low importance, and everything to the right of high has high importance (a.k.a. the indices at which new low/high will be insert). Mid is the index you're currently checking. Step through mid and swap until mid and high converge.
Space: O(1)
Time: O(n)

``````enum Importance
{
LOW = 0,
MED = 1,
HIGH = 2
};

void importancesort(vector<Importance> &patients)
{
int low = 0, mid = 0, high = patients.size() - 1;
while (mid <= high)
{
switch (patients[mid])
{
case LOW: swap(patients[mid++], patients[low++]); break;
case HIGH: swap(patients[mid], patients[high--]); break;
default: mid++; break;
}
}
}``````

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

This is called the dutch national flag problem, look it up.

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

Good call! Here's some example Java code

``````public class ThreeWayPartition {
public static final void main(String[] args) {
int[] intArray = new int[] { 1, 0, 0, 1, 2, 2, 1 };
System.out.print("start: ");
printArray(intArray);

int low = 0;
int mid = 0;
int hi  = intArray.length - 1;

while (mid <= hi) {
switch (intArray[mid]) {
case 0:
swap(intArray, low++, mid++);
break;
case 1:
mid++;
break;
case 2:
swap(intArray, mid++, hi--);
break;
}
}

System.out.print("end: ");
printArray(intArray);
}

public static final void printArray(int[] intArray) {
for (int i = 0; i < intArray.length; i++) {
System.out.print(String.format("%s ", intArray[i]));
}
System.out.println();
}

public static final void swap(int[] intArray, int a, int b) {
int tmp = intArray[a];
intArray[a] = intArray[b];
intArray[b] = tmp;
}
}``````

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

I don't think that you should increase mid in 2nd case, the swap brings a new number from the end.

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

Initialize 2 indexes one to the beginning of the array and other to the end of the array.
Swap and move all the high importance files to the beginning of the and same way move low importance to the end of the array until the 2 indices meet.

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

This is not the preferred way !

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

counting sort

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

Say High = 0;
Mid = 1;
Low = 2;

Suppose Arr[] contains key 0,1,2

void Sort(int Arr[], int n)
{
int low = 0;
int mid = 0;
int high = n-1;

while( mid<= high)
{
switch(Arr[mid])
{
case 0;
swap(&Arr[low],&Arr[mid]);
low++;
mid++;
case 1:
mid++;
case 2:
swap(&Arr[mid],&Arr[high]);
high --;
}
}
}

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

A simple counting is the answer here.

``````enum Priority
{
High = 0,
Med = 1,
Low = 2
}

IEnumerable<Priority> SortPriorities(IEnumerable<Priority> priorities)
{
Dictionary<Priority, int> hResult = new Dictionary<Priority, int>();

Priority[] ordered = new Priotity[](){ High, Med, Low}

foreach(Priority op in ordered )
{
}

foreach(p in priorities)
{
hResult[p]++;
}

List<Priority> result = new List<Priority>();

foreach(Priority op in ordered )
{
for(int i = 0; i < hResult[op];i++)
{
}
}

return result;
}``````

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

``````public char[] sort(char[] x) {

char[] out = new char[x.length];
int a, b;
a =  0;
b = x.length - 1;

for (int i = 0; i < char.length[]; i++) {

if (x[i] == 'h') { out[a++] = 'h'; }
if (x[i] == 'l') { out[b--] = 'l'; }
}

while (b > a) {

out[b--] = 'm';
}

return out;
}``````

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

I think you are off by one in your 'm' loop. Needs to say while b>= a since out[a] should be set to 'm'.

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

This is what I've come come up with. DNF standing for Dutch National Flag as pointed out above. I believe the first for loop runs in O(n) time and the second for loop (along with the nested loop) run in O(k + n) time where k is the number of indices in the "count" array, or number of different values that we're considering (in this case, 3). n is just the number of inputs in the original array "arr".

I've run some minor tests (not counting invalid input yet), but I'm just wondering if anyone could provide input/feedback on this one. Thank you!

``````private static int K = 3;

public static int[] DNF(int[] arr) {
int[] count = new int[K];
for (int i = 0; i < arr.length; i++)
count[arr[i]]++;
int[] ret = new int[arr.length];
int curr = 0;
for (int i = 0; i < count.length; i++)
for (int j = 0; j < count[i]; j++) {
ret[curr++] = i;
}
return ret;
}``````

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

Hah my code is grossly formatted in multiple aspects... But let's try to ignore that for now ;)

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

Just walk through the list, high priority gets swapped to a list growing from the front, low priority grows from the back. Need to keep track of 3 positions, current location, where the next high priority will go, where the next low priority will go. You can stop when you hit the low list.

``````public static void sortPriority(Priority[] priorities) {
int cur = 0, high = 0, low = priorities.length - 1;
int temp;
while (cur < low) {
if (priorities[cur] == Priority.HIGH) {
temp  = priorities[high];
priorities[high] = priorities[cur];
priorities[cur] = temp;
high++;
} else if (priorities[cur] == Priority.LOW) {
temp  = priorities[low];
priorities[low] = priorities[cur];
priorities[cur] = temp;
low--;
}
cur++;
}
}``````

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

Correct code

public static void sortPriority(char[] priorities) {
int cur = 0, high = 0, low = priorities.length - 1;
char temp;
while (cur < low) {
if (priorities[cur] == 'H') {
if (cur == high) {
cur++;
continue;
}
temp = priorities[high];
priorities[high] = priorities[cur];
priorities[cur] = temp;
high++;
} else if (priorities[cur] == 'L') {
temp = priorities[low];
priorities[low] = priorities[cur];
priorities[cur] = temp;
low--;
} else
cur++;
}
System.out.println(priorities);
}

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

``````void sortimp(vector<string>& v)//h, m, l
{//[low, i]:h, [i+1,j-1]: m, [k,high]: l
int n=v.size();
//int low=0, high=n-1;
int i=-1,  k=n;
for(int j=0;j<k;)
{
if(v[j]=="high")
{
swap(v[++i], v[j++]);
}
else if(v[j]=="mid") j++;
else
{
swap(v[j],v[--k]);
}
}``````

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

``````void sortimp(vector<string>& v)//h, m, l
{//[low, i]:h, [i+1,j-1]: m, [k,high]: l
int n=v.size();
//int low=0, high=n-1;
int i=-1,  k=n;
for(int j=0;j<k;)
{
if(v[j]=="high")
{
swap(v[++i], v[j++]);
}
else if(v[j]=="mid") j++;
else
{
swap(v[j],v[--k]);
}
}``````

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

``````a=["low","med", "med","med","high","low","low","med","high","low"]
length=len(a)

low=0
high=length-1;
mid=low

while (low < high and mid< high):
if a[low] =="low":
low=low+1
if a[high]=="high":
high=high-1
if a[low]=="med" and mid==0:
mid=low
if a[mid]=="med":
mid=mid+1
if a[mid]=="high":
a[mid]=a[high]
a[high]="high"
high=high-1
if a[mid]=="low":
a[mid]=a[low]
a[low]="low"
low=low+1

print a``````

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

This is great, but I'd think you'd be asked to at least use a single temp variable to not "lose" any data

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

``````public static void main(String[] args) {
String[] arr = {"high","low","low","med","high","low"};
System.out.println("original");

arr = dutchFlagPrb(arr);
System.out.println("after sorting");
for(String s:arr){
System.out.println(s);
}
}

public static String[] dutchFlagPrb(String[] arr){
int low = 0;
int mid = 0;
int high = arr.length-1;

/*
* this case is because if there is {0001112222} then everytime we are doing extra swaps so its good to chk initially
*/
while(mid<high&& arr[high].equals("high")){
high--;
}

while(mid<high){

if(arr[mid].equals("low")){
swap(arr,low,mid);
low++;
mid++;
}
if(arr[mid].equals("med")){
mid++;
}
if(arr[mid].equals("high")){
swap(arr,mid,high);
high--;
}
}
return arr;
}

private static void swap(String[] arr, int low, int mid) {
String temp = arr[low];
arr[low] = arr[mid];
arr[mid] = temp;

}``````

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

the sort colors problem in leetcode

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

``````// timing 15 minutes

import java.util.Arrays;

public class SortArrayComposedOf123 {

int begin, end;

public SortArrayComposedOf123() {

}

/*
* sorting in place
*/
void sort(int[] a){
if(a == null){
return;
}

int n = a.length;

// stage 1 get all 1 to left side
begin = 0;
end = n-1;

helper(a,1);

int numOnes = begin;
if(begin>0 && a[begin]!=1){
begin--;
}

// stage 2 get all 3's in remaining to right side
begin = numOnes;
end = n-1;

helper(a,2);
}

void helper(int[] a, int pivot){
while(begin < end ){
if(a[begin] == pivot){
begin++;
} else if(a[end] > pivot){
end--;
} else {
// swap
int x = a[begin];
a[begin] = a[end];
a[end] = x;
begin++; end--;
}
}
}

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

SortArrayComposedOf123 wrapper = new SortArrayComposedOf123();

System.out.println("BEFORE");
System.out.println(Arrays.toString(testcase));

wrapper.sort(testcase);

System.out.println("AFTER");
System.out.println(Arrays.toString(testcase));

}
}``````

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

``````public class Solution {
void swap(int[] array, int i, int j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}

void sort(int[] array) {
int l = 0;
int h = array.length - 1;

while (l < h) {
while (l < h && array[l] != 2) {
l++;
}
while (l < h && array[h] != 0) {
h--;
}
if (l < h) {
swap(array, l, h);
l++;
h--;
}
}

int pivot = l;
l = 0;
h = pivot;
while (l < h) {
while (l < h && array[l] != 1) {
l++;
}
while (l < h && array[h] != 0) {
h--;
}
if (l < h) {
swap(array, l, h);
l++;
h--;
}
}

l = pivot;
h = array.length - 1;
while (l < h) {
while (l < h && array[l] != 2) {
l++;
}
while (l < h && array[h] != 1) {
h--;
}
if (l < h) {
swap(array, l, h);
l++;
h--;
}
}
}
}``````

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

Here is C++ version of solution.
Since there are only three types, there is no needs for sorting.
I just put them in three lists. For simplification, I just take string as input.
Running time is O(N).

``````#include <string>
#include <vector>

using namespace std;
vector <string> sort_patient(string * input, int len)
{
vector<string> result;
vector<string> high;
vector<string> med;
vector<string> low;
for(int i = 0; i < len; i++)
{
if (input[i] == 'high')
high.push_back(input[i]);
else if (input[i] =='med')
med.push_back(input[i]);
else if (input[i] == 'low')
low.push_back(input[i]);
}
int h=0, m=0, l=0;
while (h < high.size() || m < med.size() || l <low.size())
{
if (h <high.size())
result.push_back(high[h++]);
else if ( m < med.size())
result.push_back(med[m++]);
else if (l < low.size())
result.push_back(low[l++]);
}
return result;
}

int main ()
{
string input[6] = {"high", "low", "low", "med", "high", "low"};
vector<string> result= sort_patient(input, 6);
return 1;
}``````

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

Count Sort

``````public enum Importance
{
High,
Midle,
Low,
}

// Option 1 - Count Sort, use two lista one at the begining and one at the end
public static void Sort(Importance[] patients)
{

int i=0;
int j=0;
int k = patients.Length-1;

while (i < k)
{
if (patients[i] == Importance.High)
{
var tmp = patients[j];
patients[j] = patients[i];
patients[i] = tmp;
j++;
}
else if (patients[i] == Importance.Low)
{
var tmp = patients[k];
patients[k] = patients[i];
patients[i] = tmp;
k--;
}
else
i++;
}
}

// Option 2 improved
public static void Sort(Importance[] patients)
{
int highCount = 0;;
int midleCount = 0;
int lowCount = 0;

var arr = new int[3];
foreach (var item in patients)
{
arr[(int)item]++;
}

int index=0;
for (int i=0; i < patients.Length; i++)
{
while (arr[index] == 0)
index++;
arr[index]--;

patients[i] = (Importance)index;
}
}``````

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

``````package com.company;

import java.util.Arrays;

public class Main {
private static int tacts;
public static void main(String[] args) {
char[] a = {'h', 'l', 'm', 'h', 'l', 'l', 'm', 'm', 'h', 'm', 'l', 'm', 'm', 'l', 'h'};
sort(a);
System.out.println(Arrays.toString(a));
System.out.println("tacts="+tacts);
System.out.println("a.length="+a.length);
}

public static void sort(char[] a) {
int h = 0, m = 0, l = 0;
int hi, mi, li;

for (int i = 0; i < a.length; i++) {
//  tacts++;
switch (a[i]) {
case 'l':
l++;
break;
case 'm':
m++;
break;
case 'h':
h++;
break;
}
}

hi = 0;
int mstart = mi = h;
int lstart = li = h + m;

while (hi < mstart || mi < lstart || li < a.length) {
tacts++;
char k;
if (hi < mstart) {
k = a[hi];
if (k == 'h') {
hi++;
continue;
} else if (k == 'm') {
swap(a, hi, mi);
mi++;
} else if (k == 'l') {
swap(a, hi, li);
li++;
}
}
if (mi < lstart) {
k = a[mi];
if (k == 'm') {
mi++;
continue;
} else if (k == 'h') {
swap(a, hi, mi);
hi++;
} else if (k == 'l') {
swap(a, mi, li);
li++;
}
}
if (li < a.length) {
k = a[li];
if (k == 'l') {
li++;
continue;
} else if (k == 'h') {
swap(a, hi, li);
hi++;
} else if (k == 'l') {
swap(a, mi, li);
mi++;
}
}
}
}

private static void swap(char[] a, int hi, int li) {
char t = a[hi];
a[hi] = a[li];
a[li] = t;
}

}``````

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

``````package com.company;

import java.util.Arrays;

public class Main {
private static int tacts;
public static void main(String[] args) {
char[] a = {'h', 'l', 'm', 'h', 'l', 'l', 'm', 'm', 'h', 'm', 'l', 'm', 'm', 'l', 'h'};
sort(a);
System.out.println(Arrays.toString(a));
System.out.println("tacts="+tacts);
System.out.println("a.length="+a.length);
}

public static void sort(char[] a) {
int h = 0, m = 0, l = 0;
int hi, mi, li;

for (int i = 0; i < a.length; i++) {
//  tacts++;
switch (a[i]) {
case 'l':
l++;
break;
case 'm':
m++;
break;
case 'h':
h++;
break;
}
}

hi = 0;
int mstart = mi = h;
int lstart = li = h + m;

while (hi < mstart || mi < lstart || li < a.length) {
tacts++;
char k;
if (hi < mstart) {
k = a[hi];
if (k == 'h') {
hi++;
continue;
} else if (k == 'm') {
swap(a, hi, mi);
mi++;
} else if (k == 'l') {
swap(a, hi, li);
li++;
}
}
if (mi < lstart) {
k = a[mi];
if (k == 'm') {
mi++;
continue;
} else if (k == 'h') {
swap(a, hi, mi);
hi++;
} else if (k == 'l') {
swap(a, mi, li);
li++;
}
}
if (li < a.length) {
k = a[li];
if (k == 'l') {
li++;
continue;
} else if (k == 'h') {
swap(a, hi, li);
hi++;
} else if (k == 'l') {
swap(a, mi, li);
mi++;
}
}
}
}

private static void swap(char[] a, int hi, int li) {
char t = a[hi];
a[hi] = a[li];
a[li] = t;
}

}``````

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

Simple C# code

``````public static void Main(String[] args)
{
int[] array = new int[]{ 2,  1, 2, 0, 1, 0, 0};
int[] sorted = Sort(array);
foreach(int i in sorted)
{
Console.WriteLine(i);
}
}

public static int[] Sort(int[] array)
{
// move all 0's to front
int count = MoveElemsAtPos(array, 0, 0);
// move all 1's next
MoveElemsAtPos(array, 1, count);
return array;
}

public static int MoveElemsAtPos(int[] array, int elem, int startPos)
{
int i=startPos;
int j = array.Length - 1;

while ( i < j )
{
if (array[i] != elem && array[j] == elem)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;

i++;
j--;
}
else if(array[i] == elem )
{
i++;
}
else
{
j--;
}
}

return i;
}``````

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.