## Facebook Interview Question for Software Engineers

• 1
of 1 vote

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

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

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

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 = tmp;
}``````

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 = temp;
}``````

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

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

}

}

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

}
}``````

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

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])``````

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 && arr[i] > max)
{
maxI = i;
max = arr[i];
}
}
if(maxI == 0)
{
break;
}
MoveToFront(arr, maxI);
calls++;
}

return calls;
}``````

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;
}
}
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++;
}
if(secondMax>max){
Move(nums[secondMax]);
max =0;
}else{
max = secondMax;
}
times--;

}
}

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)``````

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

}

}

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

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?

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

}

}``````

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.

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``````

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.

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

@jiahuang
will this work for 3 1 10 ?

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

We need O(n) MOveToFrontcalls

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 = v;
return array;
}``````

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.

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

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

Insertion sort?

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

Selection sort?

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

isnt this a selection sort?

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

Selection sort algorithm?

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

}
}``````

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.

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 = \$arr[\$moveKey];
\$z = 0;
for(\$i=0;\$i<\$arrCount; ++\$i){
if(\$i!=\$moveKey){
\$newArr[++\$z] = \$arr[\$i];
}
}
return \$newArr;
}``````

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

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.

Comment hidden because of low score. Click to expand.

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.