Facebook Interview Question Software Engineers
Country: United States
Interview Type: In-Person
With two pointer approach:
static private int getStart(int[] arr, int curr){
int i = curr;
int l = arr.length;
for(; i < l; i++){
if(arr[i] != 0)
return i;
}
return l;
}
static private int getEnd(int[] arr, int curr){
int i = curr;
int l = arr.length;
for(; i >= 0; i--){
if(arr[i] == 0)
return i;
}
return -1;
}
static private void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static public void moveNonZeroToEnd(int[] arr){
int l = arr.length;
if(l == 0 || l == 1)
return;
int start = getStart(arr, 0), end = getEnd(arr, l - 1);
while(start < end){
swap(arr, start, end);
start = getStart(arr, ++start);
end = getEnd(arr, --end);
}
}
public class SwapNonZeroIntegers {
static void dump(int a[]) {
for(int i=0; i < a.length; i++) {
System.out.print(a[i]+", ");
}
System.out.println("");
}
static void sortNonZero(int a[]) {
int end = a.length-1;
for(int i=0; i < a.length; i++) {
if(i > end)
break;
if(a[i] != 0) {
while(a[end] != 0 && end > i)
end--;
if(end == i)
break;
// do swap
int tmp = a[end];
a[end] = a[i];
a[i] = tmp;
end--;
}
}
}
public static void main(String args[]) {
int a[] = { 10, 0, 0, 15, 0, 0, 0, 10, 10 };
dump(a);
sortNonZero(a);
dump(a);
}
}
public int[] moveZerosToFront (int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
int i = 0;
int j = arr.length - 1;
while (i < j) {
if (arr[i] != 0 && arr[j] == 0) {
// swap
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
// increment indexes
i++;
j--;
}
if (arr[i] == 0) {
// zero, increment
i++;
}
if (arr[j] != 0) {
// nonzero, decrement
j--;
}
}
return arr;
}
Without swap, we can do it in linear time as below.
public void rearrange(int[] input){
int j= input.length-1;
//Start from the end and keep populating non zero values at the end.
for(int i=input.length-1; i>=0; i--){
if(input[i] != 0){
input[j] = input[i];
j--;
}
}
//from j to 0, everything can be marked as 0's
while(j>=0){
input[j] = 0;
j--;
}
}
javascript:
function movenonezero(arr) {
var moved = arr.length - 1;
for (var i = 0; i < arr.length; i++) {
if (arr[i] === 0) {
continue;
}
while (arr[moved] != 0 && moved > i) {
moved--;
}
var temp = arr[moved];
arr[moved] = arr[i];
arr[i] = temp;
if (moved === 0 || moved <= i) {
break;
}
}
return arr;
}
function movenonezero(arr) {
var moved = arr.length - 1;
for (var i = 0; i < arr.length; i++) {
if (arr[i] === 0) {
continue;
}
while (arr[moved] != 0 && moved > i) {
moved--;
}
var temp = arr[moved];
arr[moved] = arr[i];
arr[i] = temp;
if (moved === 0 || moved <= i) {
break;
}
}
return arr;
}
public int[] moveZerosToFront (int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
int i = 0;
int j = arr.length - 1;
while (i < j) {
if (arr[j] != 0 && arr[i] == 0) {
// swap
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
// increment indexes
i++;
j--;
}
if (arr[j] == 0) {
// zero, increment
j--;
}
if (arr[i] != 0) {
// nonzero, decrement
i++;
}
}
return arr;
}
public int[] moveZerosToFront (int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
int i = 0;
int j = arr.length - 1;
while (i < j) {
if (arr[j] != 0 && arr[i] == 0) {
// swap
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
// increment indexes
i++;
j--;
}
if (arr[j] == 0) {
// zero, increment
j--;
}
if (arr[i] != 0) {
// nonzero, decrement
i++;
}
}
return arr;
}
*Java Solution* with test cases
Runs like a charm! Easy Problem though
import java.util.Arrays;
public class ArrayProblems{
public static void print(String str){
System.out.println(str);
}
public static void main(String[] args){
int[] arr = {-1,-2,1,2,-100};
int[] arr2 = {1,-1,2,-2,3,-3};
int[] arr3 = {-1,-2,-3,-4,-5};
print(Arrays.toString(arr));
movePositiveToEndMinSwaps(arr);
print(Arrays.toString(arr));
print(Arrays.toString(arr2));
movePositiveToEndMinSwaps(arr2);
print(Arrays.toString(arr2));
print(Arrays.toString(arr3));
movePositiveToEndMinSwaps(arr3);
print(Arrays.toString(arr3));
}
public static void movePositiveToEndMinSwaps(int[] arr){
if(arr == null || arr.length <= 1) return;
int i =0, j= arr.length-1;
int swaps = 0;
while(i<j){
while(j>0 && arr[j]>0 ) j--;
while(i < arr.length && arr[i]<0) i++;
//swap i and j values
if (i >= j) break;
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
swaps++;
}
System.out.println("Moved all +ve nums to end in " + swaps + " swaps.");
}
}
// Using a second array. More memory consumption, but cleaner for small datasets
// Not tested
public static int[] sortZeros(int[] arr) {
if (arr == null)
return null;
int[] nArr = new int[arr.length];
int j = arr.length - 1;
for (int i = 0; i< arr.length; i++) {
if (arr[i] != 0)
nArr[j--] = arr[i];
}
return nArr;
}
import java.util.Arrays;
public class ZeroesInTheFront {
public static void main(String ... args) {
int[] a = {1, 2, 3, 4};
int[] b = {0, 0, 0, 0};
int[] c = {};
int[] d = {1};
int[] e = {0};
int[] f = {1, 0};
int[] g = {0, 1};
int[] h = {1, 0, 2, 0, 3, 0};
int[] i = null;
int[] j = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0};
for (int[] arr : Arrays.asList(a, b, c, d, e, f, g, h, i, j)) {
int allZeroBeforeThisIndex = zeroesInTheFront(arr);
printErrorIfInvariantViolated(arr, allZeroBeforeThisIndex);
}
}
// Given: {1, 0, 2, 0, 3, 0}
// nextZero | i | a[i] (before) | a[i] (after) | nextZero (after) | array (after)
// 0 0 1 1 0 {1, 0, 2, 0, 3, 0}
// 0 1 0 1 1 {0, 1, 2, 0, 3, 0}
// 1 2 2 2 1 {0, 1, 2, 0, 3, 0}
// 1 3 0 1 2 {0, 0, 2, 1, 3, 0}
// 2 4 3 3 1 {0, 0, 2, 1, 3, 0}
// 2 5 0 2 3 {0, 0, 0, 1, 3, 2}
public static int zeroesInTheFront(int[] arr) {
if (arr == null || arr.length < 2) {
return -1; // tacky
}
int nextZero = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
continue;
}
arr[i] = arr[nextZero];
arr[nextZero] = 0;
nextZero++;
}
return nextZero;
}
private static void printErrorIfInvariantViolated(int[] arr, int allZeroBeforeThisIndex) {
if (allZeroBeforeThisIndex == -1) {
return;
}
for (int idx = 0; idx < arr.length; idx++) {
if ((arr[idx] == 0 && idx >= allZeroBeforeThisIndex)
|| (arr[idx] != 0 && idx < allZeroBeforeThisIndex)) {
System.err.println("This array does not pack all zeroes into leading indexes. " + Arrays.toString(arr));
break;
}
}
}
}
public class ZeroesInTheFront {
public static void main(String ... args) {
int[] a = {1, 2, 3, 4};
int[] b = {0, 0, 0, 0};
int[] c = {};
int[] d = {1};
int[] e = {0};
int[] f = {1, 0};
int[] g = {0, 1};
int[] h = {1, 0, 2, 0, 3, 0};
int[] i = null;
int[] j = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0};
assert false;
for (int[] arr : Arrays.asList(a, b, c, d, e, f, g, h, i, j)) {
int allZeroBeforeThisIndex = zeroesInTheFront(arr);
printErrorIfInvariantViolated(arr, allZeroBeforeThisIndex);
}
}
// Given: {1, 0, 2, 0, 3, 0}
// nextZero | i | a[i] (before) | a[i] (after) | nextZero (after) | array (after)
// 0 0 1 1 0 {1, 0, 2, 0, 3, 0}
// 0 1 0 1 1 {0, 1, 2, 0, 3, 0}
// 1 2 2 2 1 {0, 1, 2, 0, 3, 0}
// 1 3 0 1 2 {0, 0, 2, 1, 3, 0}
// 2 4 3 3 1 {0, 0, 2, 1, 3, 0}
// 2 5 0 2 3 {0, 0, 0, 1, 3, 2}
public static int zeroesInTheFront(int[] arr) {
if (arr == null || arr.length < 2) {
return -1; // tacky
}
int nextZero = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
continue;
}
arr[i] = arr[nextZero];
arr[nextZero] = 0;
nextZero++;
}
return nextZero;
}
private static void printErrorIfInvariantViolated(int[] arr, int allZeroBeforeThisIndex) {
if (allZeroBeforeThisIndex == -1) {
return;
}
for (int idx = 0; idx < arr.length; idx++) {
if ((arr[idx] == 0 && idx >= allZeroBeforeThisIndex)
|| (arr[idx] != 0 && idx < allZeroBeforeThisIndex)) {
System.err.println("This array does not pack all zeroes into leading indexes. " + Arrays.toString(arr));
break;
}
}
}
}
public static int[] shiftZerosTofront(int arr[])
{
if(arr == null || arr.length ==0)
{
return null;
}
int[] temp = new int[arr.length];
int counter = arr.length-1;
for(int i=0; i<arr.length; i++)
{
if(arr[i] == 0)
{
temp[i] = arr[i];
}
else
{
temp[counter] = arr[i];
counter--;
}
}
return temp;
}
public static int[] shiftZerosTofront(int arr[])
{
if(arr == null || arr.length ==0)
{
return null;
}
int[] temp = new int[arr.length];
int counter = arr.length-1;
for(int i=0; i<arr.length; i++)
{
if(arr[i] == 0)
{
temp[i] = arr[i];
}
else
{
temp[counter] = arr[i];
counter--;
}
}
return temp;
}
public void sortArraySample(int[] arr){
// move non-zero numbers at the start of the array
// if array element which contains 0 is moved to start of the array increment j by 1
int j = 0;
int length = arr.length;
for(int i = 0 ; i < length; i++)
{
if(0 == arr[i])
{
// temporary variable for swaping values.
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
j++;
}
}
}
import java.util.*;
public class MoveNonZeros {
public static void main(String[] args) {
int[] arr = new int[]{ 0, 17, 29, 0, 11, 25, 0, 0, 55, 62, 21, 0, 1001, 11, 0, 55, 190, 0};
int pointer = arr.length -1;
for(int i = 0; i <= pointer ; i++){
if(arr[i] != 0){
for(int k = pointer; k >=0; k--){
if(arr[k] == 0) {
arr[k] = arr[i];
arr[i] = 0;
pointer = k-1;
break;
}
}
}
}
for(int value: arr){
System.out.println(value);
}
}
}
public int[] swapNonZeros(int[] arr)
{
if(arr == null || arr.length < 2)
return arr;
int nzPos = -1; //Non Zero Position
int temp = -1;
for (int i = 0; i < arr.length; i++)
{
// Set nzPos to the 1st non zero number index
// This is only set once
if(arr[i] != 0 && nzPos == -1)
nzPos = i;
// Swap values at i and nzPos if element at i = 0
if(arr[i] == 0 && nzPos != -1)
{
temp = arr[i];
arr[i] = arr[nzPos];
arr[nzPos] = temp;
// Increment nzPos, Values between nzPos and i are non zeros
nzPos++;
}
}
return arr;
}
public int[] swapNonZeros(int[] arr)
{
if(arr == null || arr.length < 2)
return arr;
int nzPos = -1; //Non Zero Position
int temp = -1;
for (int i = 0; i < arr.length; i++)
{
// Set nzPos to the 1st non zero number index
// This is only set once
if(arr[i] != 0 && nzPos == -1)
nzPos = i;
// Swap values at i and nzPos if element at i = 0
if(arr[i] == 0 && nzPos != -1)
{
temp = arr[i];
arr[i] = arr[nzPos];
arr[nzPos] = temp;
// Increment nzPos, Values between nzPos and i are non zeros
nzPos++;
}
}
return arr;
}
public int[] swapNonZeros(int[] arr)
{
if(arr == null || arr.length < 2)
return arr;
int nzPos = -1; //Non Zero Position
int temp = -1;
for (int i = 0; i < arr.length; i++)
{
// Set nzPos to the 1st non zero number index
// This is only set once
if(arr[i] != 0 && nzPos == -1)
nzPos = i;
// Swap values at i and nzPos if element at i = 0
if(arr[i] == 0 && nzPos != -1)
{
temp = arr[i];
arr[i] = arr[nzPos];
arr[nzPos] = temp;
// Increment nzPos, Values between nzPos and i are non zeros
nzPos++;
}
}
return arr;
}
My solution can do in the lowest swaps possible to get the answer.
int arr[] = { 10, 0, 0, 15, 0, 0, 0, 10, 10 };
int sz = sizeof(arr)/sizeof(arr[0]);
int ptr = 0;
//*algo start*
for(int i=0;i<sz;i++){
if(arr[i]==0){
swap(arr[i],arr[ptr++]);
}
}
//*algo end*
//Printing the solution
for(int i=0;i<sz;i++){
cout<<arr[i]<<" ";
}
My solution can do it with minimum swaps possible.
int arr[] = { 10, 0, 0, 15, 0, 0, 0, 10, 10 };
int sz = sizeof(arr)/sizeof(arr[0]);
int ptr = 0;
//**algo start**
for(int i=0;i<sz;i++){
if(arr[i]==0){
swap(arr[i],arr[ptr++]);
}
}
//**algo end**
//print result
for(int i=0;i<sz;i++){
cout<<arr[i]<<" ";
}
Assumes the order of the numbers need not be preserved
public class ZeroBegin {
public static void main (String [] args) {
int [] a = {0, 10, 20, 0, 0, 10, 0};
int k = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] != 0) {
continue;
}
else {
/* Encounter zero ==> Swap */
int tmp = a[k];
a[k] = 0;
a[i] = tmp;
k++;
}
}
}
}
My two pointer solution
- slvrhwk January 22, 2017public int[] moveNonZeroElements(int[] arr) { if (arr == null || arr.length == 0) { return arr; } int i = 0; int j = arr.length-1; while(true) { while (i < arr.length && arr[i] == 0) { i++; } while (j >= 0 && arr[j] != 0) { j--; } if (i < j) { swap(arr, i, j); } else { break; } } return arr; } public void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }