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;
		}
	}
}

- Nick March 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
9
of 9 vote

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

- Anonymous December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
  }
}

- Tyr0 April 02, 2015 | Flag
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.

- hs May 11, 2015 | Flag
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.

- Harish December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is not the preferred way !

- Eknbrk December 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

counting sort

- naren December 19, 2014 | Flag Reply
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 --;
}
}
}

- Snehal Kumar January 07, 2015 | Flag Reply
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 )
	{
		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;
}

- Nelson Perez December 28, 2014 | Flag Reply
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;
	}

- Skor January 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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'.

- Anonymous January 04, 2015 | Flag
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;
    }

- Nate January 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nate January 03, 2015 | Flag
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++;
	}
}

- Anonymous January 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
}

- Abc January 09, 2015 | Flag
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]);
        }
    }

- Anonymous January 10, 2015 | Flag Reply
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]);
        }
    }

- zhangruichang January 10, 2015 | Flag Reply
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

- coder January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- fungled January 20, 2015 | Flag
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;
		
	}

- Resh January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the sort colors problem in leetcode

- shichaotan January 24, 2015 | Flag Reply
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));
		   
	   }
}

- just_do_it February 18, 2015 | Flag Reply
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--;
			}
		}
	}
}

- jasmine8gu March 28, 2015 | Flag Reply
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;
}

- hankm2004 August 20, 2015 | Flag Reply
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;
	}
}

- hnatsu December 05, 2016 | Flag Reply
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;
    }

}

- Russ July 13, 2017 | Flag Reply
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;
    }

}

- Russ July 13, 2017 | Flag Reply
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;
    }

- shanmuk December 22, 2014 | 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