Facebook Interview Question
Android EngineersTeam: London office
Country: India
Interview Type: Phone Interview
Use two pointers, one for iterating through the array and another one for maintaining the last seen zero index. Every time you see a non-zero index, swap it with the previous seen zero index. Simple solution in Python
Solution:
def moveZeroes(arr):
i, j = 0, 0
while i < len(arr):
if arr[i] != 0:
arr[i], arr[j] = arr[j], arr[i]
j += 1
i += 1
return arr
Test code:
print(moveZeroes([0, 3, 1, 0, 2, 6, 7, 0])) # Output: [3, 1, 2, 6, 7, 0, 0, 0]
print(moveZeroes([0,0,1,0,0])) # Output: [1, 0, 0, 0, 0]
print(moveZeroes([0,3])) # Output: [3, 3]
import java.util.*;
public class HelloWorld{
public static void main(String []args){
int[] arr = {1, -2, 5, 6, 0, 1,0,3,0,0,0, 6,8,9};
for(Integer a: moveAndPrint(arr)){
System.out.println(a);
}
}
private static int[] moveAndPrint(int[] arr){
int i =0;
for(int j=arr.length-1; i<j; j--){
if(arr[i] != 0){
if(arr[j] == 0){
arr[j] = arr[i];
arr[i] = 0;
i++;
}
}
}
System.out.println(arr.length - i);
return arr;
}
}
import java.util.*;
public class HelloWorld{
public static void main(String []args){
int[] arr = {1, -2, 5, 6, 0, 1,0,3,0,0,0, 6,8,9};
for(Integer a: moveAndPrint(arr)){
System.out.println(a);
}
}
private static int[] moveAndPrint(int[] arr){
int i =0;
for(int j=arr.length-1; i<j; j--){
if(arr[i] != 0){
if(arr[j] == 0){
arr[j] = arr[i];
arr[i] = 0;
i++;
}
}
}
System.out.println(arr.length - i);
return arr;
}
}
import java.util.*;
public class HelloWorld{
public static void main(String []args){
int[] arr = {1, -2, 5, 6, 0, 1,0,3,0,0,0, 6,8,9};
for(Integer a: moveAndPrint(arr)){
System.out.println(a);
}
}
private static int[] moveAndPrint(int[] arr){
int i =0;
for(int j=arr.length-1; i<j; j--){
if(arr[i] != 0){
if(arr[j] == 0){
arr[j] = arr[i];
arr[i] = 0;
i++;
}
}
}
System.out.println(arr.length - i);
return arr;
}
}
Using above test inputs.
public static void main(String[] args){
int[] arr = {0, 3, 1, 0, 2, 6, 7, 0};
System.out.println(Arrays.toString(nonZero(arr)));
int[] arr1 = {0, 0, 1, 0, 0, 0};
System.out.println(Arrays.toString(nonZero(arr1)));
int[] arr2 = {0, 3};
System.out.println(Arrays.toString(nonZero(arr2)));
}
public static int[] nonZero(int[] arr) {
int i=0;
int length = arr.length;
int result[] = new int[length];
int j=0;
while(i<length){
if(arr[i] == 0) {
i++;
}else{
result[j++] = arr[i++];
}
}
return result;
}
Results
[3, 1, 2, 6, 7, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[3, 0]
public class MoveZerosToLast {
public static void main(String[] args) {
int[] a = { 1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9 };
int j = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] != 0) {
if (i == j) {
j++;
} else {
a[j] = a[i];
a[i] = 0;
j++;
}
}
}
System.out.println(Arrays.toString(a));
}
}
public static void main(String[] args)
{
int arr1[] = {0};
int arr2[] = {0, 1};
int arr3[] = {0, 1, 0};
int arr4[] = {1, 0};
int arr5[] = {1, 0, 0};
int arr6[] = {0, 1, 0, 2};
int arr7[] = {1, 0, 0, 2};
System.out.println(Arrays.toString(moveAndPrint(arr1)));
System.out.println(Arrays.toString(moveAndPrint(arr2)));
System.out.println(Arrays.toString(moveAndPrint(arr3)));
System.out.println(Arrays.toString(moveAndPrint(arr4)));
System.out.println(Arrays.toString(moveAndPrint(arr5)));
System.out.println(Arrays.toString(moveAndPrint(arr6)));
System.out.println(Arrays.toString(moveAndPrint(arr7)));
}
public static int[] moveAndPrint(int[] arr)
{
if (arr == null) return null;
int i = 0, j = arr.length-1;
while (i < j) {
while (arr[j] == 0)
j--;
while (arr[i] != 0)
i++;
// Swap elements
if (i < j) {
arr[i] = arr[j];
arr[j] = 0;
}
}
return arr;
}
import java.util.Arrays;
public class MoveNonZeroElementsToEndOfArray {
public static void main(String[] args){
int test1[] = new int[] {1,0,-2,0,3};
int test2[] = new int[] {0,0};
int test3[] = new int[] {1,2,3};
System.out.println(Arrays.toString(test1));
compactify(test1);
System.out.println(Arrays.toString(test1));
System.out.println(Arrays.toString(test2));
compactify(test2);
System.out.println(Arrays.toString(test2));
System.out.println(Arrays.toString(test3));
compactify(test3);
System.out.println(Arrays.toString(test3));
}
public static int compactify(int[] inp) {
int n = inp.length;
int destIndex = -1;
for (int i = n-1; i >= 0; i--) {
if ((destIndex > 0) && (inp[i] != 0)){
// swap inp[i] and inp[destIndex]
int tmp = inp[i];
inp[i] = inp[destIndex];
inp[destIndex] = tmp;
destIndex--;
} else if ((destIndex < 0) && (inp[i] == 0)) {
destIndex = i;
}
}
System.out.println("#non zero " + (n-(destIndex+1)));
return destIndex+1;
}
}
- Tejas April 09, 2018