Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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;
}
}
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.
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 --;
}
}
}
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 )
{
hResult.Add(op, 0);
}
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++)
{
result.Add(op);
}
}
return result;
}
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;
}
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;
}
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++;
}
}
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);
}
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
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;
}
// 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));
}
}
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--;
}
}
}
}
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;
}
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;
}
}
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;
}
}
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;
}
}
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;
}
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)
- Nick March 22, 2015