Bloomberg LP Interview Question
Developer Program EngineersCountry: United States
Interview Type: Phone Interview
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;
}
}
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));
}
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++]);
}
}
}
}
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;
}
}
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++;}
}}
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));
}
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]);
}
}
}
#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;
}
//
// 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);
}
}
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)
}
- Roman August 13, 2016