Facebook Interview Question
InternsCountry: United States
Interview Type: In-Person
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;
// swap start with end
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}
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--;
int[] move_zeroes(int[] arr)
{
ArrayList<Integer> ar=new ArrayList<>();
for(int i=0;i<arr.length;i++)
{
if(arr[i]==0)
ar.add(i);
}
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;
}
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]) +" " );
}
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
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++;
}
}
}
#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;
}
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+" "); }
}
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+" "); }
}
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]);
}
}
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";
}
}
#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";
}
}
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--;
}
}
}
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);
}
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;
}
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
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 }
Complexity: O(n)
- R@M3$H.N October 28, 2015