CareerCup

public static void moveZeroes(int[] a){
  	int pos = 0;
  	for(int i = 0; i < a.length; i++)
  		if(a[i] != 0)
  			a[pos++] = a[i];
  	for(int i = pos; i < a.length; i++)
  		a[i] = 0;
  }

public static int[] MoveZeros(int[] arr)
        {
            int cnt = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                if(arr[i] != 0)
                {
                    arr[i - cnt] = arr[i];
                }
                else
                {
                    cnt++;
                }
            }


            for (int i = 1; i <= cnt; i++)
            {
                arr[arr.Length - i] = 0;
            }
            return arr;
        }

Iterate through the array, keeping track of how many zeroes you've seen. For each value, set arr[i-count] to the current value a[i]. If i + count is equal to the length, set a[i] to 0 (i.e. If you're within "count" of the end, start filling in zeroes.

Time: O(n)
Space: O(1)

Something like this:

public void MoveZeroes(int[] arr) {
   int zeroCount = 0;
   for (int i=0; i<arr.Length; i++) {
      if (arr[i] == 0)
         zeroCount++;
      else
         a[i - zeroCount] = a[i];
      if (arr.Length < i + zeroCount)
         arr[i] = 0;
    }
}

moveZeroes(std::vector<int>& v)
    {
         // remove zero and get the iterator past the last nonzero element
         auto it = std::remove(v.begin(), v.end(), 0);
         std::fill(it, v.end(), 0);
    }

public static void placeZeroAtEnd1(int arr[])
	{
		int i = 0;
		while (true)
		{
			while (i < arr.length && arr[i] != 0)
			{
				i++;
			}
			int j = i + 1;
			while (j < arr.length && arr[j] == 0)
			{
				j++;
			}
			if (i >= arr.length || j >= arr.length)
			{
				break;
			}
			if (j > i)
			{
				int temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
				i++;
				j++;

			}

		}
		System.out.println(Arrays.toString(arr));
	}

void ReorganizeArray(int arr[], int n)
{
	int write_indx = 0, read_indx = 0;
	while (read_indx < n)
	{
		if (arr[read_indx] != 0)
		{
			if (write_indx != read_indx)
				arr[write_indx++] = arr[read_indx];
			else
				write_indx++;
		}
		read_indx++;
	}
	while (write_indx < n)
		arr[write_indx++] = 0;
}

public static void moveZeroes(int[] a){
  	int pos = 0;
  	for(int i = 0; i < a.length; i++)
  		if(a[i] != 0)
  			a[pos++] = a[i];
  	for(int i = pos; i < a.length; i++)
  		a[i] = 0;
  }

public static void moveZeroes(int[] arr){
for (int i =0 ;i <arr.length;i++)
{
if (arr[i]==0 ){
for (int j=i+1;j<arr.length;j++){
if ( arr[j]!=0 ) {
arr[i]=arr[j];
arr[j]=0;
break;
}
}

}

}

I would suggest two approaches for linear time.
1. Use first loop to places all non-zeros at position counter <index> and keep count for zeros also. In second loop, iterate over only zeros to places zeros at the end. The time complexity will be O(n) still in this case.
2. Do only in one loop -

void placeZeros(int a[],int n) {
	int j = 0;
	int i = 0;

	while(j<n) {
		if(a[i] != 0)	i++, j++;
		else  {
			if(a[j] == 0)
				j++;
			else {
				swap(a[i++],a[j++]);
			} 
		}
	}
}

I hope, my interview question is this easy..
Python 3

def moveZerosToTheRight(arglist):
    
    for i in range(len(arglist)):
        
        if arglist[i] == 0:
            del arglist[i]
            arglist.append(0)
            
    return arglist

Straightforward. Iterate over the array keeping track of all numbers except zeros. This will overwrite the zeroes in between with the non-zeroes. Fill the rest with Zeroes.

public class Test
{
 public static void main(String ...args)
 {
  int arr[] = {1,3,0,8,1,2,0,4,0,7};

  moveZeroes(arr);
  for(int i =0;i<arr.length;i++)
  {
   System.out.print(arr[i]);
  }


 }




 private static void moveZeroes(int[] arr)
 {
  int pos=0;

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

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

  }
 }

First question is: Do i have to make the transformation in place or can i use extra space and other data structures?

def move_zeros(input_list) :
    place_holder = len(list) - 1
    i = 0
    while i <= place_holder :
        if list[i] == 0 :
            list.append(0)
            del list[i]
            place_holder -= 1
        else :
            i += 1
    return list

#test
list = [0,1,0,0,20,0,0,4,5]
print(move_zeros(list))

func moveZeros() {
arr := []int{1,3,0,8,1,2,0,0,4,0,7}
fmt.Println(arr)
index := -1
for i := 0; i < len(arr); i++ {
if arr[i] == 0 {
if index == -1 {
index = i
}
} else if index > -1 {
arr[index] = arr[i]
arr[i] = 0
index++
}
}
fmt.Println(arr)
}

func moveZeros() {
arr := []int{1,3,0,8,1,2,0,0,4,0,7}
fmt.Println(arr)
index := -1
for i := 0; i < len(arr); i++ {
if arr[i] == 0 {
if index == -1 {
index = i
}
} else if index > -1 {
arr[index] = arr[i]
arr[i] = 0
index++
}
}
fmt.Println(arr)
}

func moveZeros() {
	arr := []int{1,3,0,8,1,2,0,0,4,0,7}
	fmt.Println(arr)
	index := -1
	for i := 0; i < len(arr); i++ {
		if arr[i] == 0 {
			if index == -1 {
				index = i
			}
		} else if index > -1 {
			arr[index] = arr[i]
			arr[i] = 0
			index++
		}
	}
	fmt.Println(arr)
}

Just a little improvement:

public static void moveZeroes(int[] a){
  	int pos = 0;
  	for(int i = 0; i < a.length; i++)
  		if(a[i] != 0)
		{
  			a[pos] = a[i];
			if(pos != i)
				a[i] = 0;
			pos++; 
		}
  	
  }

import java.util.Scanner;


public class goog_1 {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
System.out.println("enter the number of elements :");
int n=sc.nextInt();
int[] a=new int[n];
int c=0;
for(int i=0;i<n;i++)
a[i]=sc.nextInt();
for(int i=0;i<n;i++)
{
if(a[i]!=0)
{
System.out.print(a[i]+" ");
c++;
}
}
while(c!=n)
{
System.out.print("0 ");
c++;
}
}

}

import java.util.Scanner;
public class goog_1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
System.out.println("enter the number of elements :");
int n=sc.nextInt();
int[] a=new int[n];
int c=0;
for(int i=0;i<n;i++)
a[i]=sc.nextInt();
for(int i=0;i<n;i++)
{
if(a[i]!=0)
{
System.out.print(a[i]+" ");
c++;
}}
while(c!=n)
{
System.out.print("0 ");
c++;}
}}

moveZeroes(std::vector<int>& v)
{
auto it = std::remove(v.begin(), v.end(), 0);
int nzeroes = std::distance(it, v.end());
std::fill_n(it, nzeroes, 0);
}

for (counter = 0; counter < a.length; counter++) {
	if (a[counter] === 0) { a.splice(counter,1); a.push(0)}
}

for (counter = 0; counter < a.length; counter++) {
	if (a[counter] === 0) { a.splice(counter,1); a.push(0)}
}

I think this can be achieved by one loop
public void MoveZeroes(int[] arr) {
int pos = 0;
int zeroCOunt=0;
int a[] = new int[arr.length];
for (int i=0; i<arr.length; i++) {
if (arr[i] != 0){
a[pos]=arr[i];
pos++;
} else{
a[arr.length-1-zeroCOunt] = 0;
zeroCOunt++;
}
}
System.out.println(Arrays.toString(a));
}

This can be achieved within one loop
public void MoveZeroes(int[] arr) {
int pos = 0;
int zeroCOunt=0;
int a[] = new int[arr.length];
for (int i=0; i<arr.length; i++) {
if (arr[i] != 0){
a[pos]=arr[i];
pos++;
} else{
a[arr.length-1-zeroCOunt] = 0;
zeroCOunt++;
}

}

System.out.println(Arrays.toString(a));
}

Work backwards (Python):

arr = [1,3,0,8,12,0,4,0,7]

i = len(arr) - 1

while i >= 0:
    if arr[i] == 0:
        del arr[i]
        arr.append(0)
    i -= 1

Work backwards instead (using Python):

arr = [1,3,0,8,12,0,4,0,7]

i = len(arr) - 1

while i >= 0:
    if arr[i] == 0:
        del arr[i]
        arr.append(0)
    i -= 1

public static void moveZeroLast() {
int a[] = { 1, 7, 0, 4, 5, 0, 7, 7, 0, 8 };
int count = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] == 0) {
count++;
} else {
a[i - count] = a[i];
}
if (i + count >= a.length - 1) {
a[i] = 0;
}

}
}

Using Python:

def place_zeros(n,ls):
    x=0
    for i in range(n):
        if ls[i]==0:
            x=ls[i]
            ls.remove(x)
            ls.append(x)
            return ls

def place_zeros(n,ls):
    x=0
    for i in range(n):
        if ls[i]==0:
            x=ls[i]
            ls.remove(x)
            ls.append(x)
            return ls

public class AllZerosAtEnd {

static int[] a = { 1, 3, 0, 0,0,0,8, 12, 0, 4, 0, 7 };

public static void main(String[] args) {

System.out.print("Before :");
for(int k=0;k<a.length;k++){
System.out.print(a[k]+", ");
}
System.out.println();
moveZeroToEnd(a);
}

static void moveZeroToEnd(int[] a) {

int zeroStartIndex = 0, nonZeroIndex = 0;
while (a[zeroStartIndex] != 0)
zeroStartIndex++;

// find next non zero start Index
nonZeroIndex = zeroStartIndex + 1;
int zeroCountLength = 1;
while (a[nonZeroIndex] == 0) {
nonZeroIndex++;
zeroCountLength++;
}

for (int i = 0; i < zeroCountLength && nonZeroIndex < a.length; i++) {
if(a[nonZeroIndex]!=0){
a[zeroStartIndex++] = a[nonZeroIndex];
a[nonZeroIndex++] = 0;
i--;
} else{
zeroCountLength++;
nonZeroIndex++;
}
}

System.out.print("After :");
for(int k=0;k<a.length;k++){
System.out.print(a[k]+", ");
}
}
}

public class AllZerosAtEnd {

	static int[] a = { 1, 3, 0, 0,0,0,8, 12, 0, 4, 0, 7 };

	public static void main(String[] args) {

		System.out.print("Before :");
		for(int k=0;k<a.length;k++){
			System.out.print(a[k]+",  ");
		}
		System.out.println();
		moveZeroToEnd(a);
	}

	static void moveZeroToEnd(int[] a) {

		int zeroStartIndex = 0, nonZeroIndex = 0;
		while (a[zeroStartIndex] != 0)
			zeroStartIndex++;

		nonZeroIndex = zeroStartIndex + 1;
		int zeroCountLength = 1;
		while (a[nonZeroIndex] == 0) {
			nonZeroIndex++;
			zeroCountLength++;
		}

		for (int i = 0; i < zeroCountLength && nonZeroIndex < a.length; i++) {
			if(a[nonZeroIndex]!=0){
				a[zeroStartIndex++] = a[nonZeroIndex];
				a[nonZeroIndex++] = 0;
				i--;
			} else{
				zeroCountLength++;
				nonZeroIndex++;
			}
		}
		
		System.out.print("After  :");
		for(int k=0;k<a.length;k++){
			System.out.print(a[k]+",  ");
		}
	}

}

public class ArrayTest {

public static void main(String[] args) throws Exception{
int[] input = {1,3,0,8,12,0,4,0,7};

for(int i = 0; i < input.length; i++) {
if (input[i] == 0){
for (int j = i; j < input.length -1; j++){
input[j] = input[j+1];
}
input[input.length - 1] = 0;
}
System.out.println(input[i]);
}
}
}

Python solution:

def shift_zeroes(l):
shift = 0
for i in range(0, len(l)):
if l[i] == 0:
shift += 1
else:
temp = l[i-shift]
l[i-shift] = l[i]
l[i] = temp

return l

Python solution:

def shift_zeroes(l):
    shift = 0
    for i in range(0, len(l)):
        if l[i] == 0:
            shift += 1
        else:
            temp = l[i-shift]
            l[i-shift] = l[i]
            l[i] = temp

    return l

Python solution:

def shift_zeroes(l):
    shift = 0
    for i in range(0, len(l)):
        if l[i] == 0:
            shift += 1
        else:
            temp = l[i-shift]
            l[i-shift] = l[i]
            l[i] = temp

    return l

def appendZeros(listIntegers):
    numZeros = listIntegers.count(0)
    listIntegers = filter(lambda a: a != 0, listIntegers)
    for i in range(0, numZeros):
        listIntegers.append(0)
    return listIntegers

int_list = [4,6,2,0,5,0,6,8,2]

print (appendZeros(int_list))

def appendZeros(listIntegers):
numZeros = listIntegers.count(0)
listIntegers = filter(lambda a: a != 0, listIntegers)
for i in range(0, numZeros):
listIntegers.append(0)
return listIntegers

int_list = [4,6,2,0,5,0,6,8,2]

print (appendZeros(int_list))

def appendZeros(listIntegers):
        numZeros = listIntegers.count(0)
        listIntegers = filter(lambda a: a != 0, listIntegers)
        for i in range(0, numZeros):
            listIntegers.append(0)
        return listIntegers

int_list = [4,6,2,0,5,0,6,8,2]

print (appendZeros(int_list))

def appendZeros(listIntegers):
    numZeros = listIntegers.count(0)
    listIntegers = filter(lambda a: a != 0, listIntegers)
    for i in range(0, numZeros):
        listIntegers.append(0)
    return listIntegers

int_list = [4,6,2,0,5,0,6,8,2]

print (appendZeros(int_list))

#include <iostream>
#include <vector>
using namespace std;
void move_zero(int * ,int);
int main()
{
int test_m[]={1,3,0,8,12,0,4,0,7};
const int arr_len=sizeof(test_m)/sizeof(int);
move_zero(test_m,arr_len);

for(int i=0;i< arr_len;i++)
cout << test_m[i] << endl;
}
void move_zero(int test_m[] ,const int arr_len)
{
int count=0;
for(int i=0;i< arr_len;i++)
{ if(test_m[i] != 0)
{
test_m[count++]=test_m[i];
}

}
for( ;count < arr_len ;count++)
test_m[count]=0;


}

a = [1,3,0,8,0,0,12,50,9,90,5,0,0,0,4,0,7]
i=0
j=len(a)-1
while i <= j:
    if a[i]==0:
        a.append(a.pop(i))
        j-=1
    else:
        i+=1

print a

a = [1,3,0,8,0,0,12,50,9,90,5,0,0,0,4,0,7]
i=0
j=len(a)-1
while i <= j:
    if a[i]==0:
        a.append(a.pop(i))
        j-=1
    else:
        i+=1

print a

void moveZeros(vector<int>& v)
{
   auto ite = remove(v.begin(), v.end(), 0);
   fill(ite, v.end(), 0);

    return 0;
}

//
// Given an unsorted integer array, place all zeros to the
// end of the array without changing the sequence of non-zero
// elements. ( ie. [1,3,0,8,12,0,4,0,7] => [1,3,8,12,4,7,0,0,0] )
//
// Run with VM arguments -ea to enable assert testing
//
// (c) 2016 Perry Anderson, All Rights Reserved, worldwide.
//
//

import java.util.Vector;
import java.util.Arrays;

public class LPMain002 {

	static Integer[] sortOut(Integer[] data) {
		
		Vector<Integer> results = new Vector<Integer>();
		int zeroCount = 0;
		
		for (int i = 0; i < data.length; i++) {
			if ( data[i]==0)
				zeroCount++;
			else
				results.add(data[i]);
		}
		
		while (zeroCount-->0) 
			results.add(new Integer(0));
		
		return results.toArray(new Integer[results.size()]);
	}

	public static void main(String[] args) {

		Integer[] data1 = new Integer[] { 1, 3, 0, 8, 12, 0, 4, 0, 7 };
		Integer[] data2 = new Integer[] { 1, 3, 8, 12, 4, 7, 0, 0, 0 };
	
		assert Arrays.equals(sortOut(data1), data2);
		assert !Arrays.equals(sortOut(data1), data1);
		assert Arrays.equals(sortOut(data2), data2);
		assert !Arrays.equals(sortOut(data2), data1);
		
	}

}

int n = 9, A[] = {1, 3, 0, 8, 12, 0, 4, 0, 7};
  int i = 0, j = n - 1;
  while(i < j) {
    while(i < j && A[i]) ++i;
    while(j > i && !A[j]) --j;
    swap(A[i], A[j]);
  }
  for(int a: A) 
    cout << a << " ";

private static void swap(int[] a, int i1,int i2) {
int temp = a[i1];
a[i1] = a[i2];
a[i2] = temp;
return;
}
private static void moveZerosInEnd() {
int[] arr = new int[] { 1, 3, 0, 8, 12, 0, 0, 99 };

int currIndex = 0;

for (int i = 0; i < arr.Length; i++) {
if (arr[i] != 0)
continue;
currIndex = i;
if (currIndex == arr.Length - 1)
continue;
for (int j=currIndex + 1; j < arr.Length; j++) {
if (arr[j] != 0) {
swap(arr, currIndex, j);
break;
}
}

}
foreach (var a in arr)
Console.WriteLine(a);
}

private static void swap(int[] a, int i1,int i2) {
            int temp = a[i1];
            a[i1] = a[i2];
            a[i2] = temp;
            return;
        }
        private static void moveZerosInEnd() {
            int[] arr = new int[] { 1, 3, 0, 8, 12, 0, 0, 99 };

            int currIndex = 0;
            
            for (int i = 0; i < arr.Length; i++) {
                if (arr[i] != 0)
                    continue;
                currIndex = i;                
                if (currIndex == arr.Length - 1)
                    continue;
                for (int j=currIndex + 1; j < arr.Length; j++) {
                    if (arr[j] != 0) {
                        swap(arr, currIndex, j);
                        break;
                    }
                }                   
                
            }
            foreach (var a in arr)
                Console.WriteLine(a);
        }

void moveZeroes(vector<int>& nums)
{
//1, 3, 0, 8, 5, 0, 78, 0, 5
for(int lastZeroDetected = 0, current = 0; current < nums.size(); current++)
{
if(nums[current] != 0)
{
swap(nums[lastZeroDetected++], nums[current]);

print(nums);
}
}
}

int main()
{
std::vector<int> numbers = {1, 3, 0, 8, 5, 0, 78, 0, 5};
moveZeroes(numbers);

return 0;
}

void moveZeroes(vector<int>& nums) 
{
    //1, 3, 0, 8, 5, 0, 78, 0, 5
    for(int lastZeroDetected = 0, current = 0; current < nums.size(); current++)
    {
        if(nums[current] != 0)
        {
            swap(nums[lastZeroDetected++], nums[current]);
            
            print(nums);
        }
    }
}

int main()
{
    std::vector<int> numbers = {1, 3, 0, 8, 5, 0, 78, 0, 5};
    moveZeroes(numbers);
    
    return 0;
}

Implementation done in Go that runs in linear time. Leverages the fact that slices are mutable in the Go language. A similar implementation can also be done in Ruby.

However, this approach will not work in Java or C where arrays are immutable.

func moveZeros(){
	arr := []int{1,3,0,8,1,2,0,4,0,7}
	fmt.Println(arr)
	for i := 0; i < len(arr); i++{
		if(arr[i] == 0){
			arr := append(arr[:i], arr[i+1:]...)
			arr = append(arr, 0)
		}
	}
	fmt.Println(arr)
}

func moveZeros(){
	arr := []int{1,3,0,8,1,2,0,4,0,7}
	fmt.Println(arr)
	for i := 0; i < len(arr); i++{
		if(arr[i] == 0){
			arr := append(arr[:i], arr[i+1:]...)
			arr = append(arr, 0)
		}
	}
	fmt.Println(arr)
}

Iterate through the array, keeping track of how many zeroes you've seen. For non-zero values, set a[i-count]=a[i]. As you approach the end, you'll want to see if i + numZeroes >= length. If it is, set a[i] to 0.

Time: O(n)
Space: O(1)