## Facebook Interview Question for Interns

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
8
of 10 vote

Complexity: O(n)

``````class PushZeroToLast
{
public static void main (String[] args)
{
//int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9,0};
int n = arr.length;
pushZerosToLast(arr, n);
System.out.println("Output: ");
for (int i=0; i<n; i++)
System.out.print(arr[i]+" ");
}

static void pushZerosToLast(int arr[], int n)
{
int count = 0;

for (int i = 0; i < n; i++)
if (arr[i] != 0)
arr[count++] = arr[i];

while (count < n)
arr[count++] = 0;
}
}``````

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

``````public static void moveZeroesToEnd(int[] arr) {
int start = 0;
int end = arr.length - 1;

while (start < end) {
while (arr[start] != 0 && start < arr.length - 1)
start++;
while (arr[end] == 0 && end > 0)
end--;
if (start >= end) break;

int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}``````

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

Elegant solution, but checks 'start < arr.length -1' and 'end > 0' should be before arr[start] and arr[end] respectively. That is, the while statement should have looked like below -

``````while (start < arr.length - 1 && arr[start] != 0)
start++;
while (end > 0 && arr[end] == 0)
end--;``````

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

You are right Sean. Thanks for pointing that out!

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

``````public static int[] moveZeros(int[] array) {
int j = array.length-1;
for (int i = array.length-1; i >= 0; i --){
if (array[i] == 0) {
array[i] = array[j];
array[j] = 0;
j --;
}
}
return array;
}``````

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

``````void foo(int *a, int size)
{
int i, j, mid, k;
i = 0;j=size-1;mid=0;
for (k=0;k<size;k++) {
if (a[mid] > 0) {
i++;
mid++;
} else {
swap(a, mid, j);
j--;
}
}
}``````

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

public static int[] moveZeros(int[] array) {
int j = array.length-1;
for (int i = array.length-1; i >= 0; i --){
if (array[i] == 0) {
array[i] = array[j];
array[j] = 0;
j --;
}
}
return array;
}

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

``````int[] move_zeroes(int[] arr)
{

ArrayList<Integer> ar=new ArrayList<>();

for(int i=0;i<arr.length;i++)
{
if(arr[i]==0)
}

int start_index=arr.length-ar.size();

int index=start_index;

//System.out.println(start_index);

for(int j=0;j<ar.size();j++)
{

//System.out.println(ar.get(j));
if(ar.get(j)<start_index)
{
while(arr[index]==0)
{
index++;
}

int tmp=arr[index];
arr[index]=arr[ar.get(j)];
arr[ar.get(j)]=tmp;
}

}

return arr;

}``````

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

``````public void modify(int arr[])
{
int i =0;
int j =arr.length -1;

while(i<arr.length)
if(arr[i]==0)break;

while(j>0)
if(arr[j]!=0)break;

while(i<j)
{
swap(i,j)
while(i<arr.length)
if(arr[i]==0)break;

while(j>0)
if(arr[j]!=0)break;
}

return

}``````

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

``````int st=0;
for(int i=0;i<n;i++){
if(a[i]!=0){
a[st] = a[i];
st++;
}
}
while(st<n){
a[st]=0;
st++;
}``````

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

``````public static void MoveZerosToTheEnd(int[] arr)
{
int start = 0;
int end = arr.Length - 1;

while (start < end)
{
if (arr[end] == 0)
end--;
else if (arr[start] == 0)
{
int tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
end--;
start++;
}
else
start++;
}
}``````

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

``````#include<iostream>

using namespace std;

int main()
{
int a[10]={1,2,0,0,0,0,4,5,6,9},i,j,t;

for(i=0,j=9;i<j;i++)
{
if(a[i]==0)
{
if(a[j]!=0)
{
t=a[i];
a[i]=a[j];
a[j]=t;
j--;
}
else
{
--j;
t=a[i];
a[i]=a[j];
a[j]=t;
}

}

}
for(i=0;i<10;i++)
{
cout<<a[i];
}``````

}

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

#include<iostream>

using namespace std;

int main()
{
int a[10]={1,2,0,0,0,0,4,5,6,9},i,j,t;

for(i=0,j=9;i<j;i++)
{
if(a[i]==0)
{
if(a[j]!=0)
{
t=a[i];
a[i]=a[j];
a[j]=t;
j--;
}
else
{
--j;
t=a[i];
a[i]=a[j];
a[j]=t;
}

}

}
for(i=0;i<10;i++)
{
cout<<a[i];
}

}

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

``````private static void moveZeroesToTheEnd(int[] arr){

Stack zeroStack = new Stack();

Stack nonZeroStack = new Stack();

for(int i=0; i<arr.length; i++){
if(arr[i]==0)
zeroStack.push(0);
else
nonZeroStack.push(arr[i]);
}

int[] newArrayWithZeroesOnRight = new int[arr.length];

for(int i=0; i<newArrayWithZeroesOnRight.length; i++){

if(!nonZeroStack.isEmpty())
newArrayWithZeroesOnRight[i] = (Integer)nonZeroStack.pop();
else
newArrayWithZeroesOnRight[i] = (Integer)zeroStack.pop();

}

for(int i=0; i<newArrayWithZeroesOnRight.length; i++){
System.out.print(" " + String.valueOf(newArrayWithZeroesOnRight[i]) +" " );
}``````

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

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

``````void zeros2end(int a[], int size) {
int next = size-1;
int i = 0;

while (i < next) {
if (a[next] == 0) {
next--;
continue;
}
if (a[i] == 0) {
swap(a[i], a[next]);
next--;
i++;
}
else i++;
}``````

}

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

``````def zeros_on_right(numbers):
last_unused = len(numbers) - 1
curr_index = 0
while curr_index < last_unused:
if numbers[curr_index] == 0:
numbers[curr_index], numbers[last_unused] = numbers[last_unused], numbers[curr_index]
last_unused -= 1
if numbers[curr_index] != 0:
curr_index += 1
return numbers``````

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

``````void mover(int* arr, int n)
{
int end = n - 1;

// Checking inputs
if ((NULL == arr) || (n <= 0))
return;

// Iterate the array
while (i <= end)
{
// Check for zeros
if (arr[i] == 0)
{
// Swap the elements at positions "i" and "end"
arr[i] = arr[end];
arr[end] = 0;

// The next position for a zero decreases
end--;
}
else
{
// Not a zero, move on
i++;
}
}
}``````

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

``````public static void doIt(int[] arr) {
if (arr == null) {
return;
}
int low = 0;
int high = arr.length -1;
while (low < high) {
if (arr[right] == 0) {
--right;
continue;
}
if (arr[left] != 0) {
++left;
continue;
}
arr[left++] = arr[right];
arr[right--] = 0;
}
}``````

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

``````public static doIt(int[] arr) {
if (arr == null) {
return;
}
int left = 0;
int right = arr. length - 1;
while (left < right) {
if (arr[right == 0) {
--right;
continue;
}
if (arr[left] != 0) {
++left;
continue;
}
arr[left++] = arr[righht];
arr[right] = 0;
}
}``````

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

``````public static void doIt(int[] arr) {
if (arr == null) {
return;
}

int left = 0;
int right = arr.length - 1;
while (left < right) {
if (arr[left] != 0) {
++left;
continue;
}
if (arr[right] == 0) {
--right;
continue;
}
arr[left++] = arr[right];
arr[right--] = 0;
}
}``````

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

``````public static void doIt(int[] arr) {
if (arr == null) {
return;
}

int left = 0;
int right = arr.length - 1;
while (left < right) {
if (arr[left] != 0) {
++left;
continue;
}
if (arr[right] == 0) {
--right;
continue;
}
arr[left++] = arr[right];
arr[right--] = 0;
}
}``````

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

``````#include <iostream>
#include <vector>

using namespace std;

void swap(vector<int> & inArray, int i, int j) {
int temp = inArray[i];
inArray[i] = inArray[j];
inArray[j] = temp;
}

vector<int> moveZeros(vector<int> & inArr) {
int start = 0;
int end = (int) inArr.size() - 1;
while(start < end) {
while(inArr[start]!=0) {
++start;
}
while(inArr[end]==0) {
--end;
}
if(start<end) {
swap(inArr, start, end);
}
}
return inArr;
}``````

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

simple python code
O(n2)

``````def move_0(l):
for i in range(len(l)-1):
for j in range(0, len(l)-1-i):
if l[j] == 0:
l[j+1] , l[j] = l[j], l[j+1]

mylist = [1, 2, 4, 0, 0, 12]
move_0(mylist)
print(mylist)``````

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

Python
O(n)

``````def move0(l):
new = []
for i in l:
if i != 0:
new.append(i)
for i in l:
if i == 0:
new.append(i)
return new

z = move0([1, 2, 4, 0, 0, 12])
print(z)``````

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

``````public void MoveZeros(int[] values)
{
int start = 0;
int end = values.Length - 1;

while (start < end)
{
while (start < end && values[end] == 0)
end--;
while (start < end && values[start] != 0)
start++;
if (values[start] == 0)
{
values[start] = values[end];
values[end] = 0;
}
}
}``````

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

``````public static void main(String[] args) {

int[] num = {5,86,4,8,0,4,0,3,9,0,4,0,8,7,0,5,0};

int leftCounter = 0;
int rightCounter = num.length -1;
do{
if(0 == num[leftCounter]){

while(rightCounter > leftCounter && num[rightCounter] == 0){
rightCounter--;
}

num[leftCounter] = num[rightCounter];
num[rightCounter] = 0;
}

leftCounter++;
}while(leftCounter < rightCounter);

for(int i : num){ System.out.print(i+" "); }
}``````

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

``````public static void main(String[] args) {

int[] num = {5,86,4,8,0,4,0,3,9,0,4,0,8,7,0,5,0};

int leftCounter = 0;
int rightCounter = num.length -1;
do{
if(0 == num[leftCounter]){

while(rightCounter > leftCounter && num[rightCounter] == 0){
rightCounter--;
}

num[leftCounter] = num[rightCounter];
num[rightCounter] = 0;
}

leftCounter++;
}while(leftCounter < rightCounter);

for(int i : num){ System.out.print(i+" "); }
}``````

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

Python 2.7.x code:

def movezeros(arr):
n = arr.count(0)
for i in xrange(n):
arr.remove(0)
arr.append(0)
return arr

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

C code O(n)

``````#include "stdio.h"
#include "stdlib.h"

#define LENGTH 10

void main()
{
int a[10]= {1,0,3,4,5,0,7,8,0,10};

int start=0;
int end =LENGTH-1;
int temp;

while(start < end){
// set the end to a non zero element
while (a[end]==0) end--;

if (a[start]==0)
{
// swap the 0 with the end element
temp=a[end];
a[end]=a[start];
a[start]=temp;
}
start++;

} // end while
printf(" Array after processing is ");
for(int i=0;i<LENGTH;i++)
{
printf(" %d ",a[i]);
}
}``````

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

Output :
Array after processing is 1 10 3 4 5 8 7 0 0 0

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

O(N) implementation

``````// Shift all the zero's to the right of the array
void shift_zeros_right(int arr[], const int& sz)
{
int i = 0, j = sz;
while(i < j)
{
// Skip if the current element is a not zero
if (arr[i] != 0)
{
++i;
continue;
}

if (arr[j] != 0)
{
swap(arr, i, j);
++i;
}
--j;
}
}``````

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

``````#include<stdio.h>
#define MAX 50
int main()
{
int arr[MAX],n,i,j,temp,b[MAX];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
i=0;
j=0;
while(i<n)
{
if(arr[i]!=0)
{
b[j]=arr[i];
j++;
}
i++;
}
for(;j<n;j++)
{
b[j]=0;
}
for(i=0;i<n;i++)
printf("%d\t",b[i]);
return 0;
}``````

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

Time-complexity: O(n), Space-complexity: O(1)

``````public static void modify(int[] a) {
int end = a.length - 1;
for(int i=end;i >= 0;i--) {
if(i == end && a[i] == 0) end--;
else if(a[i] == 0) {
a[i] = a[end];
a[end] = 0;
end--;
}
}
}``````

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

Another Swift solution

``````func moveZerosToEnd(inputArray: [Int]) -> [Int] {
var nonZerosArray: Array = [Int]()
var zerosArray = [Int]()
for number in inputArray {
if number == 0 {
zerosArray.append(number)
}
else {
nonZerosArray.append(number)
}
}

return nonZerosArray + zerosArray
}``````

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

O(n) Two phase solution- (1) first shift the elements by so many zeros found so far; (2) fill the number of zeros in the end

``````#include<vector>
#include<iostream>
using namespace std;

void pushZerosToEnd(vector<int> &v) {
int count = 0;
for(unsigned int i=0; i < v.size(); i++) {
if (v[i] == 0) {
count++;
} else {
v[i-count] = v[i];
}
}
int i = v.size()-1;
while(count--) {
v[i] = 0;
i--;
}
}

int main() {

int a[] = { 0, 1, 0, 2, 4, 0, 7, 0, 8};
vector<int> v(a, a + sizeof(a)/sizeof(a[0]));

pushZerosToEnd(v);
for(auto itr = v.begin(); itr != v.end(); itr++) {
cout<<*itr<<"\t";
}

}``````

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

``````#include<vector>
#include<iostream>
using namespace std;

void pushZerosToEnd(vector<int> &v) {
int count = 0;
for(unsigned int i=0; i < v.size(); i++) {
if (v[i] == 0) {
count++;
} else {
v[i-count] = v[i];
}
}
int i = v.size()-1;
while(count--) {
v[i] = 0;
i--;
}
}

int main() {

int a[] = { 0, 1, 0, 2, 4, 0, 7, 0, 8};
vector<int> v(a, a + sizeof(a)/sizeof(a[0]));

pushZerosToEnd(v);
for(auto itr = v.begin(); itr != v.end(); itr++) {
cout<<*itr<<"\t";
}
}``````

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

void moveallZeros(int arr[], int arraySize)
{
int frontPointer=0;
int backPointer=arraySize-1;
while (frontPointer < backPointer)
{
while(arr[frontPointer] != 0 && frontPointer < backPointer)
{
printf("%d incrementing fp\n", frontPointer);
frontPointer++;
}
while(arr[backPointer] ==0 && frontPointer < backPointer)
{
printf("%d incrementing fp\n", backPointer);
backPointer--;
}
if (frontPointer < backPointer)
{
swap(arr, frontPointer, backPointer);
frontPointer++;
backPointer--;
}
}
}

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

``````int[] zeroToRight(int[] numbers) {
numbers.toList().sort { o1, o2 ->
o1 == 0 ? 1 : (o2 == 0 ? -1 : 0)
}
}``````

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

PHP version:

``````<?php
\$arr = [0, 4, 5, 7, 8, 0, 9, 0, 0, 4, 5];
rsort(\$arr);
print_r(\$arr);``````

P.S. I'm sure this is not facebook question.

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

Time Complexity : o(n) Space Complexity : o(n) ; requires additional array of the same size

Another solution could be write an sorting algo in descending order.

``````public static void modifyArray(int []input) {
int []modifiedArray = new int[input.length];
int startIndex = 0;
int lastIndex = input.length -1;
for(int i =0;i<input.length;i++) {
if(input[i] == 0) {
modifiedArray[lastIndex--] = input[i];
} else {
modifiedArray[startIndex++] = input[i];
}
}
printArray(modifiedArray);
}``````

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

You could define a comparison function and sort using std::sort().

``````bool myFunc(int a, int b)
{
if(a == 0 || b == 0)
return false;
else
return true;
}``````

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

Java:

``````private static int[] moveZerosToEnd(int[] arrayOfInteger){
int temp;
int end = arrayOfInteger.length -1;

for(int i = 0; i < arrayOfInteger.length -1; i++){
if(i < end){
if(arrayOfInteger[i] == 0){
if(arrayOfInteger[end] == 0){
arrayOfInteger[end--] = arrayOfInteger[i];

}else{
temp = arrayOfInteger[end]; // 1
arrayOfInteger[end--] = arrayOfInteger[i];
arrayOfInteger[i] = temp;
}

}
}

}

return arrayOfInteger;
}``````

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

``````def zeros2end(s):
i = 0
z = None # index of the first 0-element

while i < len(s) - 1:
if s[i] == 0:
if z is None:
z = i
if s[i+1] != 0:
s[z], s[i+1] = s[i+1], 0
z += 1
i += 1``````

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

``````def zeros2end(s):
i = 0
z = None # index of the first 0-element

while i < len(s) - 1:
if s[i] == 0:
if z is None:
z = i
if s[i+1] != 0:
s[z], s[i+1] = s[i+1], 0
z += 1
i += 1``````

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

We can do this in O(n) with O(1), constant, memory using the original array, by swapping elements.

We need two pointers, one starting at index zero (the right index), and one starting at n-1 (the right index).

We test each element at a[left_idx] to see if it's zero.

If it equal to zero, we swap it with the element at a[right_idx], or the element at the left size of the last zero we moved to the end. Since we put a zero at that index, we have to decrement right_idx.

If that element at the left_idx is not zero, we increment the right pointer.

We stop when the two pointers are at the same location.

``````def move_zeros_to_end(a):
n = len(a)
right_idx = n - 1
left_idx = 0

while left_idx < right_idx:
if a[left_idx] == 0:
a[left_idx], a[right_idx] = a[right_idx], a[left_idx]
right_idx -= 1
else:
left_idx += 1

return a``````

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

``````def movezeroes(self,s):
begin=0
end = len(s) - 1
while begin< end:
if s[begin] !=0:
begin+=1
continue
if s[begin] == 0:
while s[end] == 0:
end-=1
temp = s[end]
s[end]=s[begin]
s[begin] = temp
begin+=1
end-=1
return s``````

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

One Liner:

``````def movezeroes(self,s):
s.sort(key=lambda x:1 if x==0 else 0)
return s``````

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

``````public class PutZerosAtEnd {
public static void main(String[] args) {
int[] arr = { 1, 3, 5, 1, 5, 1, 0 ,3, 81, 32, 0, 12, 91, 0, 1, 0};
zerosToEnd(arr);
System.out.print("{ ");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println("}");
}

public static void zerosToEnd(int[] arr) {
//Sets position to swap to at the
//end of the array.
int swapPos = arr.length - 1;
//continue moving backwards until it is not
//equal to 0.
while (swapPos > -1 && arr[swapPos] == 0)
swapPos--;

//Go forward in the array until swapPos
for (int i = 0; i < swapPos; i++) {
//If an element is 0, swap it with
//the element at swapPose.
if (arr[i] == 0) {
int temp = arr[swapPos];
arr[swapPos] = arr[i];
arr[i] = temp;
// decrement swapPos until not pointing
// to a 0.
while (swapPos > -1 && arr[swapPos] == 0)
swapPos--;
}
}

}
}``````

output:

``{ 1 3 5 1 5 1 1 3 81 32 91 12 0 0 0 0 }``

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.