Facebook Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

1. Find the largest number (I called it A) from the array and remember its index.
2. Find the next largest number (I called it B) from the array. If B comes before A, we're good, otherwise move B to the front, MoveToFront(B).
3. A = B, and repeat (2). it needs to loop n-2 times to check all other numbers.

It's not the fastest algorithm, but it should be very easy to understand. The time complexity is O(n^2).

- jiahuang July 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Only way I could think of minimizing the number of move operations is if the array is already sorted in chunks with some un-sorted jumbled numbers in between them all of which are smaller than the first sorted chunk.

Then move them by moving them starting with largest among them.

Or start by finding the max element and if its already in the last position skip it and go on as long as we have a sorted chunk already in correct position at the end of the array. Then keep them moving each element to the front starting from largest among them.
I dont know if we can solve it in less than O(n^2).

- Anonymous July 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

void sortArray(int[] array){
	if(array==null){
                    return;
	}
          
	for(int start = 0; start < array.lenth; start++){
		int max = 0;
           	for(int i = start; i < array.lenth; i++){
          			if(array[i]>max){
				max=array[i];
			}
		}
	
		MoveToFront(array, max);
	}
}

- funover July 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void sort(int [] arr) {
		for(int s = 0;s<arr.length;s++) {
			moveFirst(arr,findMax(arr,s,arr.length-1));
		}
	}
	
	public static int findMax(int [] arr, int s, int e) {
		int idx = s;
		int tmp = arr[s];
		for(int i=s;i<=e;i++) {
			if( arr[i] > tmp ) {
				idx = i;
				tmp = arr[i];
			}
		}
		return idx;
	}
	
	public static void moveFirst(int [] arr,int idx) {
		int tmp = arr[idx];
		while(idx>0) {
			arr[idx] = arr[--idx];
		}
		arr[0] = tmp;
	}

- jhoon July 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes selection sort. This code finds biggest and puts in the front of the array. MoveToFront(x) assumes x is an index or else we will need to write a find function.

public void sort(){
		for (int i = 0; i < a.length; i++){
			int big = findBiggestIndex(i);
			move(big);
		}
	}
	
	
	private int findBiggestIndex(int x) {
		int big = x;
		for(int i = x ; i< a.length; i++){
			if(a[i] > a[big]) 
				big = i;
		}
		return big;
	}

	public void move(int x){
		int temp = a[x];
		for (int i = x; i > 0; i--){
			a[i] = a[i-1];
		}
		a[0] = temp;
	}

- Rakesh July 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sortArray(int[] array){
if(array==null){
return;
}

for(int start = 0; start < array.lenth; start++){
int max = 0;
for(int i = start; i < array.lenth; i++){
if(array[i]>max){
max=array[i];
}
}

MoveToFront(array, max);
}
}

- funover July 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sortArray(int[] array){

if(array==null){

return;

}

for(int start = 0; start < array.lenth; start++){

int max = 0;

for(int i = start; i < array.lenth; i++){

if(array[i]>max){

max=array[i];

}

}

MoveToFront(array, max);

}

}

- funover July 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void sort_xx(int *ar) {

        int i, j, max;

        for(i = 0; i < (sizeof(ar)); i++) {
                for(j = i; j < (sizeof(ar)); j++) {
                        if(j == i) {
                                max = i;
                        } else {
                                if(ar[max] < ar[j]) {
                                        max = j;
                                }
                        }
                }

                moveToFront(max, ar);
    
        }
}

- Golan August 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

You can actually do better than O(n^2)

void inlineSort(int[] arr) {
	int[] copy = arr.clone();
	Arrays.sort(copy); // Ascending
	for(int i=copy.length-1; i>=0; i--) {
		MoveToFront(copy[i]);
	}
}

- bosung90 August 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

func moveToFront(arr: [Int], max: Int, atIndex: Int) -> [Int]{
    var newArr = arr
    newArr.removeAtIndex(atIndex)
    newArr.insert(max, atIndex: 0)
    return newArr 
}

func sortArray(arr: [Int]) {
    var newArr = arr
    for i in 0..<newArr.count {
        var max = 0
        var maxIndex = -1
        for j in i..<newArr.count {
            if newArr[j] > max {
                max = newArr[j]
                maxIndex = j
            }
        }
        newArr = moveToFront(newArr, max: max, atIndex: maxIndex)
        print(newArr)
    }
    print(newArr)
}

sortArray([12,3,4,3,24,22,4,224,453,232])

- AT September 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void MoveToFront(int[] arr, int i)
        {
            if(i >= arr.Length || i < 1)
            {
                return;
            }

            int t = arr[i];
            while(i > 0)
            {
                arr[i] = arr[i - 1];
                --i;
            }
            arr[i] = t;
        }

        public static int SortUsingMoveToFront(int[] arr)
        {
            int calls = 0;
            
            while (true)
            {
                int max = Int32.MinValue;
                int maxI = 0;
                for (int i = 0; i < arr.Length; ++i)
                {
                    if(arr[i] < arr[0] && arr[i] > max)
                    {
                        maxI = i;
                        max = arr[i];
                    }                    
                }
                if(maxI == 0)
                {
                    break;
                }
                MoveToFront(arr, maxI);
                calls++;
            }          

            return calls;
        }

- Anonymous September 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void test(int[] nums){
Set<Integer> visited = new HashSet();

int max = 0, secondMax = -1;
for(int i=0;i<nums.length;i++){
if(nums[i]>nums[max]){
max = i;
}
}
visited.add(nums[max]);
int times = nums.length;
int len = nums.length;
while(times>0){
int i =0;
secondMax = -1;
while(i<len){
if(!visited.contains(nums[i])&&secondMax ==-1&& i!=max){
secondMax = i;
}
else if(!visited.contains(nums[i])&&nums[i]>max[secondMax]){
secondMax = i;
}
i++;
}
visited.add(nums[max]);
if(secondMax>max){
Move(nums[secondMax]);
max =0;
}else{
max = secondMax;
}
times--;

}
}

- win2 September 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Swift:

func moveToFront(idx: Int, array: inout [Int]) {
    let num = array[idx]
    array.remove(at: idx)
    array.insert(num, at: 0)
}

func moveToFrontSort(array: inout [Int]) {
    guard array.count > 1 else { return }
    
    for sortCursor in 0..<array.count {
        var maxIdx = sortCursor
        for idx in maxIdx..<array.count {
            if array[idx] > array[maxIdx] {
                maxIdx = idx
            }
        }
        
        moveToFront(idx: maxIdx, array: &array)
    }
}

var array = [12, 3, 4, 24, 22, 4, 224, 453, 232]
moveToFrontSort(array: &array)

- tomkowz October 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class sortedarraysquare {

public static void sortsquare(int[] array)
{
int negativeIntIndex = 0;
for (int i=0 ;i<array.length-1;i++)
{
if(array[i] > array[i+1])
{
array = movearray(0,i+1,array);
}

}

for(int i=0;i<array.length;i++)
{
System.out.println(array[i] );
}
}


public static int[] movearray(int fromIndex,int toIndex,int[] array)
{
int temp = array[toIndex];
for(int i = toIndex;i>= fromIndex+2;i--)
{
array[i] =array[i-1];

}
int temp2 = array[fromIndex];
array[fromIndex+1]=temp2;
array[fromIndex] = temp;
return array;
}

public static void main (String args[])
{
int[] array = new int[]{1,2,6,8,-10,11,-15,-16,17};
sortsquare(array);

}

}

- dipa October 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about nlogn solution? Sort it like in merge sort:
- pick up a random index pivot, move to front
- do pass over array all values larger than pivot move to front
- at this point array is partitioned left pivot right where left is larger than pivot and right
- do similar partition recursively on left portion
- end recursion when o ly 2 or less elements left
- when left recursion returns do right.
- in the end array will be sorted in ascending order left to right
- one catch is when inserting elements in front position of pivot moves this can be fixed by returning number of insertions from recursion and adjusting pivot

- Coder123 October 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What does MoveToFront actually do? Swaps the current value for the front value or actually moves it to front and shift rest of them by one? I don't understand how "Move" operation does on arrays. Does it mean to SwapForFront?

- Andrea October 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Really simple algorithm, as we are not allowed to do other operations:

public void sort(int[] array){
	int size = array.length;
	for(int i = 0; i < size; i++){
		int minimum = i;
		for(int j = i; j < size; j++){
			if(array[j] < array[minimum]){
				minimum =j;
			}
		}
		moveToFront(minimum);

	}

}

- libertythecoder October 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What does MoveToFront actually do? Does it move the given number and all other number shift by one, which takes O(n) times? or just swap the first number and the given number?
It's confusing since it's array and we usually don't do move front then push all others back by one.

- pppz November 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a = [4, 5, 10, 1, 2, 7, 11, 8, 9]
b = a[:]
b.sort(reverse=True)

moves = len(a)
last_index = None
for i in xrange(len(b)):
    cur_index = a.index(b[i])
    if not last_index or cur_index < last_index:
        last_index = cur_index
        moves -= 1
    else:
        break
print len(a), moves

- Nitish Garg January 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

no, if B is before A then we leave it as is, then, how does it guarantee that it is in sorted order. consider this example
input : 5 3 10 1 2 8 6 after sort it would be 1 2 6 8 5 3 10, as 5 and 3 where before 10, they didn't get moved they are not in the order.

I think we need O(n) MoveToFront calls.

- Raj January 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@jiahuang
will this work for 3 1 10 ?

- Raj January 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We need O(n) MOveToFrontcalls

- Raj January 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var len = array.length;
	for (var i = 0; i < len; i++) {
		moveToFirst(array, findMax(array, i, len));
	}
	return array;
}
function findMax(array, start, len) {
	var big = array[start];
	var index = start;
	for (var i = start+1; i < len; i++) {
		if (array[i] > big) {
			big = array[i];
			index = i;
		}
	}
	return index;
}
function moveToFirst(array, index) {
	var v = array[index];
	for (var i = index; i > 0; i--) {
		array[i] = array[i-1];
	}
	array[0] = v;
	return array;
}

- jbxx January 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If you can use a heap (additional memory) you can do it in O(NxLogN): by keeping track of the minimum value and its index in the original array.

- Ionut February 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use bubble sort technique.
Look for adjacent elements and swap i.e for each i , if arr[i] < arr[i-1] , call moveToFront(i)
Keep doing until on each pass we have atleast one moveToFront calls ( use boolean flag to know that).

//Complete code
public class SortArrayMoveFront {
	
	public static void moveToFront(int[] arr , int pos){
		int tmp = arr[pos];
		for(int j=pos;j>0;j--){
			arr[j] = arr[j-1]; // shift	
		}
		arr[0] = tmp;
	}
	
	//bubbles sort technique O(N^2)
	public static void sortArray(int[] arr){
		
		boolean moved = true;
		
		while(moved){
			moved=false;
			for(int i=1;i<=arr.length-1;i++){
				if(arr[i] < arr[i-1]){
					moveToFront(arr,i); // moved
					moved=true; // a move was made
				}
			}
		}
	}
	
	public static void main(String[] args) {
	
		//int[] arr = {11,4,5,4,7};
		int[] arr = {12,3,4,3,24,22,4,224,453,232};
		sortArray(arr);
		//moveToFront(arr,0);
		
		System.out.println(Arrays.toString(arr));
	}
}

- Mayank Jain August 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Insertion sort?

- Anonymous July 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Selection sort?

- a July 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

isnt this a selection sort?

- eob July 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Selection sort algorithm?

- Aye July 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<bits/stdc++.h>
using namespace std;

void moveFront(vector<int>& a,int num)
{
	
	int i = find(a.begin(),a.end(),num) - a.begin();
	int temp = a[i];
	for(int j=i-1;j>=0;--j)
	{
		a[j+1] = a[j];
	
	}
	a[0] = temp;
	for_each(a.begin(),a.end(),[](int i){cout << i << " ";});
			cout << "\n";
}

int main()
{
	vector<int> arr={0,2,3,4,5,6,7,8,1};
	int n = arr.size();
	priority_queue<int> pq;
	for(int i: arr)
	{
		pq.push(i);
	}
	
	int max1 = pq.top();
	pq.pop();
	int begin = find(arr.begin(),arr.end(),max1) - arr.begin();
	int count = 1;
	
	while(pq.top()==arr[begin-1])
	{
		count++;
		pq.pop();
		begin--;
	}
	int moves = n - count;
	cout << "minimum moves  " << moves <<"\n";
	for(int i=0;i<moves;++i)
	{
		int elem = pq.top();
		pq.pop();
		moveFront(arr,elem);
		
	}
}

- Shilpa July 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Wouldn't MoveToFront(x) or MTF(x) be an O(n) operation?
Don't quite get the point of this problem.

- random July 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use selection sort since it utilizes the least swap(i.e. Move to front)

function sort_array($arr) {
        $arrCount = count($arr);
        for($i=0;$i<$arrCount;++$i) {
            $maxKey=$i;
            $maxKeySet = false;
            for($j=$i; $j<$arrCount; ++$j){
                if($arr[$j]>=$arr[$maxKey]){
                    $maxKey = $j;
                    $maxKeySet = true;
                }
            }
            if($maxKeySet){
                $arr = $this->moveToFront($arr,$maxKey);
            }
        }
        return $arr;
    }
    
    
    function moveToFront($arr, $moveKey){
        $arrCount = count($arr);
        $newArr[0] = $arr[$moveKey];
        $z = 0;
        for($i=0;$i<$arrCount; ++$i){
            if($i!=$moveKey){
                $newArr[++$z] = $arr[$i];
            }
        }
        return $newArr;
    }

- nicholasappiah July 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

func main() {
	a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
	fmt.Println(a)
	a = append([]int{a[len(a)-1]}, a[:len(a)-1]...)
	fmt.Println(a)
}

- Anonymous July 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Create a max heap
keep removing the head and call moveToFront() with that element.

- haris July 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.


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