Amazon Interview Question
Quality Assurance EngineersCountry: India
Interview Type: In-Person
int size = size of array - 1;
for(int i = size, j =size; i >=0 ; i--){
if(a[i] == 0){
for(int k = i; k != j; k++){
a[k] = a[k+1];
}
a[j] = 0;
j--;
}
}
here my c++ solution:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void push_zeros_to_end(vector<int> &vec) {
int i = 0;
int j = vec.size() - 1;
while(i < j) {
while(i != j && vec[i] != 0) i++;
while(i != j && vec[j] == 0) j--;
if(i < j) {
swap(vec[i], vec[j]);
i++;
j--;
}
}
}
int main() {
// your code goes here
vector<int> vec= {0,2,0,1,4,5,6,7,0,1,2,3,4,5,0,0,1,4,0};
push_zeros_to_end(vec);
for_each(vec.begin(), vec.end(), [](int val) { cout << val << ' '; });
return 0;
}
This O(n) solution iterates over the array with two indexes. If an element is not 0, we copy it to the position of the first index (and advance both indexes), if it is a 0 then we only advance the second index, counting the 0s encountered.
When the second index gets to the end, we will have filled up the non-zero digits at the beginning, so we just need to make sure to fill the remaining elements at the end with 0s.
public void pushToEnd(int[] number) {
if (number == null || number.length == 0)
return;
int zeros = 0;
int numIndex = 0;
for (int i = 0; i < number.length; i++) {
if (number[i] == 0)
zeros++;
else
number[numIndex++] = number[i];
}
for (int i = 0; i < zeros; i++)
number[numIndex++] = 0;
}
int arr[] = {1,3,5,0,0,4,6,0};
std::vector<int> vect;
for(int i = 0; i < 8; i++)
{
vect.push_back(arr[i]);
}
unsigned int i = 0;
int zeroCnt = 0;
while((i < vect.size()) && (i < (vect.size() - zeroCnt - 1)))
{
if(vect.at(i) == 0)
{
if(vect.at(vect.size() - zeroCnt - 1) == 0)
{
zeroCnt++;
}
else
{
swap(vect.at(i),vect[vect.size() - zeroCnt - 1]);
zeroCnt++;
}
}
else
{
++i;
}
for(int i = 0; i < vect.size(); i++)
{
cout << vect.at(i) << ",";
}
cout << endl;
}
copy(vect.begin(),
vect.end(),
ostream_iterator<int> (cout, "\n"));
public static void main(String[] args){
int[] noArrayform = {0,2,0,1,4,5,6,7,0,1,2,3,4,5,0,0,1,4,0};
int[] outputArray = new int[noArrayform.length];
int loopCount = 0;
int outputLength = 0;
//copy the non zero values to the new output array
while(loopCount<noArrayform.length){
if(noArrayform[loopCount] != 0){
outputArray[outputLength] = noArrayform[loopCount];
outputLength++;
}
loopCount++;
}
//Display array
for(int i = 0; i< outputArray.length;i++){
System.out.println("PRINT OUTPUT: "+outputArray[i]);
}
}
I would use partition idea in the quick sort. A pointer at the beginning and a pointer at the end. Whenever the beginning pointer encounters a zero, swap the first pointers value with the second one. Then while there is an immediate zero before the second pointer move the second pointer back. Do it while (first pointer < second pointer).
public class PushZero {
public static void main(String...v){
ArrayDeque<Integer> num = new ArrayDeque<>();
int arr[] = {1,3,5,0,0,4,6,0};
for(int i=0;i<arr.length;i++){
if(arr[i]==0){
num.addLast(arr[i]);
}
else{
num.addFirst(arr[i]);
}
}
System.out.println(num.size());
for(Iterator itr = num.iterator();itr.hasNext();) {
System.out.println(itr.next());
}
}
}
void pushZero(int *array, int length) {
int zerocount = 0; // var to hold the num of Zeros in the given string
//Loop through all the elements of the array
for (int i = 0; i < length; i++) {
// if element = 0, do nothing, just increment the count
if (0 == array[i]) {
zerocount++;
continue;
}
//if not, then based on the zerocount, swap the elements
if (0 != zerocount) {
array[i - zerocount] = array[i];
array[i] = 0;
} // end if
} // end for
} // end pushZero()
You can use Partition, which uses "n - 1" comparisons and at most "n - 1" swaps using a customized comparator which assumes "0" is the largest number. Comparator code follows:
public class CustomComparator implements Comparetor<Integer> {
public int compareTo(Integer a, Integer b) {
if ((a == 0 && b == 0) || (a * b != 0))
return 0;
if (a != 0 && b == 0) {
return -1;
}
if (a ==0) {
return 1;
}
}
}
/**
* Manuel.
* Assuming there are 13 integers. Btw: I think the complexity reamins O(n) although I
* have outer loop here.
*/
#include <iostream>
void inline swap(int *a, int *b);
void pushZeros(int (&arr)[13]);
void printArr(int (&arr)[13]);
int main()
{
int size= 13;
int arr[13]={1,2,3,0,0,0,-3,-4,0,0,1,0,0};
printArr(arr);
std::cout<<"After pushing the zeros"<<'\n';
pushZeros(arr);
printArr(arr);
return -1;
}
void printArr(int (&arr)[13])
{
for(int i=0; i < 13 ; i++)
{
std::cout<<" "<<arr[ i ];
}
}
void pushZeros(int (&arr)[13])
{
int *ptr1= arr;
int *ptr2= arr+ 13 -1;
while(ptr1 < ptr2)
{
while(*ptr1!=0 ) ptr1++;
while(*ptr2==0) ptr2--;
if(ptr1 < ptr2) swap(ptr1, ptr2);
else break;
ptr1++;
ptr2--;
}
}
void inline swap(int *a, int *b)
{
int c= *a;
*a= *b;
*b= c;
}
#include <iostream>
#include <conio.h>
//WAP to shift all zeroes to the end of the array
using namespace std;
void sift(int a[],int n)
{
int i=0,j=n-1,t;
while(i<j)
{
while(a[j]==0)
{
j--;
}
while(a[i]!=0)
{
i++;
}
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
cout<<"\nArray is now:";
for(int k=0;k<n;++k)
cout<<a[k]<<" ";
}
int main()
{
int a[100],n;
cout<<"\nEnter the number of elements:";
cin>>n;
for(int i=0;i<n;++i)
cin>>a[i];
sift(a,n);
getch();
return 0;
}
#include <iostream>
using namespace std;
void moveZeroToEnd( int * data,size_t size)
{
if(!size) return;
size_t lastNonZeroPosition=size-1;
while(lastNonZeroPosition&&(!data[lastNonZeroPosition])) lastNonZeroPosition-- ;
for(size_t i=0;i<lastNonZeroPosition;i++)
{
if(!data[i])
{
data[i]=data[lastNonZeroPosition];
data[lastNonZeroPosition] = 0;
--lastNonZeroPosition;
}
}
}
int main()
{
//int data[]={0,1,2,0,3,4,5,0,1,0,2,6,0,0};
//int data[]={0,1};
int data[]={};
size_t size= sizeof(data)/sizeof(data[0]);
moveZeroToEnd(data,size);
for(size_t i=0;i<size;i++)
cout << data[i] << endl;
}
// Given a number in an array form, Come up with an algorithm to push all the zeros to the end.
// Expectation: O(n) solution
#include <iostream>
void print(int *arr, size_t size)
{
using namespace std;
for (size_t i = 0; i < size; ++i)
cout << arr[i] << ' ';
cout << endl;
}
void pushZeroToEnd(int *arr, size_t size)
{
int *start = arr;
int *end = arr + size - 1;
while (start < end)
{
// Find first zero
while (*start != 0) ++start;
// Find last not zero
while (*end == 0) --end;
// Swap
*start++ = *end;
*end-- = 0;
}
}
int main()
{
int arr[] = { 1, 3, 0, 0, 0, 2, 0, 5, 4, 0, 3, 9, 0, 8, 0, 0 };
size_t size = sizeof(arr) / sizeof(int);
print(arr, size);
pushZeroToEnd(arr, size);
print(arr, size);
std::cin.get();
return 0;
}
public static void main(String[] args)
{
int[] input = new int[]{ 0,5,6,0,0,2,4,0};
int nzpos = 0; //non-zero-position
int DigitToPush = 0;
for(int i = 0 ; i < input.length; i++)
{
if(arr[i] == DigitToPush)
continue;
else
input[nzpos++] = input[i];
}
// by this time all nonzero are at correct place; now fill-out rest of zeroes
for(int j = nzpoz; j < input.length() ; j++)
{
input[j] = DigitToPush;
}
}
pushing "0" is not the main part, this question can be asked to push any one number.
Ex: push all "9" at the end . Same code with DigitToPush = 5
Do a naive quiqsort implementation
public void QuickSort(int[] arr)
{
int strt =0;
int stop = arr.length-1;
while(strt< stop)
{
while(strt != 0) strt ++;
while(stop ==0) stop++;
if(strt == stop) break;
Swap(arr[strt],arr[stop]);
}
}
Nice Solution. I suppose you meant stop--, and bound checks for arrays would have been nice.
Following solution is inspired from your idea:
void PushAllZerosToEnd(int arr[], int size)
{
int start = 0;
int stop = size-1;
while(true)
{
while(start<size && arr[start]) start++;
while(stop>=0 && arr[stop]==0) stop--;
if(stop<=start) break;
int temp = arr[start];
arr[start] = arr[stop];
arr[stop] = temp;
}
};
void PushZereosToEnd(int* arr,int len)
{
int posZero = -1;
for(int i = 0; i < len; i++)
{
if(arr[i] == 0 && posZero == -1) //this is the zero index fisrt time
posZero = i;
else if(arr[i] != 0 && posZero != -1) //need to swap
{
int temp = arr[i];
arr[i] = arr[posZero];
arr[posZero] = temp;
posZero++;
}
}
for(int i = 0; i < len; i++)
std::cout<<arr[i]<<"\n";
}
int arr[] = {1,3,5,0,0,4,6,0};
std::vector<int> vect;
for(int i = 0; i < 8; i++)
{
vect.push_back(arr[i]);
}
unsigned int i = 0;
int zeroCnt = 0;
while((i < vect.size()) && (i < (vect.size() - zeroCnt - 1)))
{
if(vect.at(i) == 0)
{
if(vect.at(vect.size() - zeroCnt - 1) == 0)
{
zeroCnt++;
}
else
{
swap(vect.at(i),vect[vect.size() - zeroCnt - 1]);
zeroCnt++;
}
}
else
{
++i;
}
}
copy(vect.begin(),
vect.end(),
ostream_iterator<int> (cout, "\n"));
#include<iostream>
#include<algorithm>
#include<functional>
#include<vector>
using namespace std;
void Move(vector<int>&arr)
{
int m = arr.size();
int left = 0, right = m - 1;
while (left < right)
{
while (arr[left] != 0 && left < right)
left++;
while (arr[right] == 0 && left < right)
right--;
if (left < right){
swap(arr[left++], arr[right--]);
}
}
}
//Using STL
void Move1(vector<int>&arr)
{
partition(arr.begin(), arr.end(), bind1st(equal_to<int>(), 0));
reverse(arr.begin(), arr.end());
}
int main()
{
vector<int>cur{ 0, 1, 2, 0, 3, 2, 0, 4 };
Move(cur);
for (auto& i : cur){
cout << i << " ";
}
cout << endl;
return 0;
}
int a[] = { 0,1, 2, 1, 3, 7, 5, 6, 0, 8, 0, 0,0 };
int len = a.length;
int i = 0, j = len - 1;
while(a[j]==0){
j--;
}
while (i < len - 1 && j > 0 && i < j) {
if (a[i] == 0) {
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
j--;
if (a[j] == 0) {
j--;
}
}
i++;
}
for (int c : a) {
System.out.println(c);
}
// in place array manipulation.
#include <iostream>
#include <stdlib.h>
template<typename T>
size_t push_to_end(T *arr, size_t nelements, T value_to_end=0){
T *p = arr;
size_t ndigits = 0;
for (size_t ii = 0; ii < nelements; ++ii){
if (arr[ii] == value_to_end){
ndigits++;
continue;
}
*p++ = arr[ii];
}
memset(&(arr[nelements - ndigits]), value_to_end, sizeof(T)*ndigits);
return ndigits;
}
void usage(const char *pname){
std::cerr << "USAGE: " << pname << " <array> [digit to push]" << std::endl;
}
int main(int argc, char *argv[]){
if (argc < 2){
usage(argv[0]);
return -1;
}
char value_to_push = 0;
if (argc > 2)
value_to_push = (int)argv[2][0] - 48; // assumes 1 digit 0-9
// cast to int to make printable characters
std::cerr << "pushing " << (int)value_to_push << " to end" << std::endl;
std::cerr << "BEFORE: " << argv[1] << std::endl;
size_t size = strlen(argv[1]);
char *array = new char[size];
for (size_t ii = 0; ii < size; ++ii)
array[ii] = (int)argv[1][ii] - 48;
size_t npushed = push_to_end(array, size, value_to_push);
std::cerr << "AFTER: ";
for (size_t ii = 0; ii < size; ++ii)
// cast to int to make printable characters
std::cerr << (int)array[ii];
std::cerr << std::endl;
std::cerr << "Pushed " << npushed << " " << (int)value_to_push << "('s) to end" << std::endl;
delete [] array;
return 0;
}
package take3;
import java.util.*;
class b
{
static void shiftz(int a[])
{
int c = 0;
for(int i = 0; i < a.length; i++)
{
if(a[i] == 0)
c ++;
else
a[i-c] = a[i];
}
int i = a.length;
for(int j = 1; j <= c; j++)
{
a[i-j] = 0;
}
}
public static void main(String arg[])
{
int a[] = {0,2,0,4,0,5,0,0,6,8,0,0,10};
shiftz(a);
System.out.println(Arrays.toString(a));
}
}
//47
package take3;
import java.util.*;
class b
{
static void shiftz(int a[])
{
int c = 0;
for(int i = 0; i < a.length; i++)
{
if(a[i] == 0)
c ++;
else
a[i-c] = a[i];
}
int i = a.length;
for(int j = 1; j <= c; j++)
{
a[i-j] = 0;
}
}
public static void main(String arg[])
{
int a[] = {0,2,0,4,0,5,0,0,6,8,0,0,10};
shiftz(a);
System.out.println(Arrays.toString(a));
}
}
//47
public class PushZeroAtEndOfArray{
public static void main(String []args){
int[] arr = {1,0,3,0,2,0,4,6,0,5};
int[] arr1 = new int[arr.length];
int j = arr.length;
int k=0;
for(int i=0;i<arr.length;i++){
if(arr[i]==0){
arr1[k]=0;
}else{
arr1[k] = arr[i];
k++;
}
}
for(int i=0;i<j;i++)
System.out.println(arr1[i]);
}
}
public class MyQuickSort {
private int array[];
private int length;
public void sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
/** * In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a number
* from right side which is less then the pivot value. Once the search
* is done, then we exchange both numbers. */
while (array[i] > pivot) {
i++;
}
while (array[j] < pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]){
MyQuickSort sorter = new MyQuickSort();
int[] input = {24,2,45,20,0,75,2,0,99,53,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}
I believe this can be done in Log(n) time complexity also .. keep on dividing the array rexursively until there are only two elements, then .
If(Both elements are zero)
return the array as it is;
If(left is zero)
swap and return;
if(right is zero)
return as it is;
Then merge the two divided arrays from right to left until there are no zeroes left in the arrays. Then go for the right array and add all of its elements, then do the same for left array.
This will give u a Log(N) solution.
public class PushZero {
public static int[] pushzero(int[] arr)
{
int n = arr.length-1;
System.out.println(" " + n);
for(int i=0 ; i<arr.length-1 ; i++)
{
if(arr[i] == 0)
{
System.out.println("in for loop" + i );
System.out.println("\n");
int temp = arr[i];
System.out.println("temp is " + temp);
arr[i] = arr[n];
arr[n] = temp;
System.out.println("arr at nth pos " +n );
System.out.println("arr at nth value " +arr[n] );
n--;
}
}
return arr;
}
public static void main(String a[])
{
int[] arr = {1,0,4,5,0,3};
int[] arr2 = pushzero(arr);
for(int i:arr)
{
System.out.println(" " +i);
}
}
}
#include<stdio.h>
#include<string.h>
char str[2432];
int swap(int,int);
int main()
{
int y,last,i;
scanf("%s",str);
y=strlen(str)-1;
for(i=y;i>=0;i--)
{
if(str[i]=='0');
else break;
}
last=i;
for(;i>=0;i--)
{
if(str[i]=='0') {swap(last,i); last=last-1;}
}
printf("%s",str);
return 0;
}
int swap(int a,int b)
{
int k=str[a];
str[a]=str[b];
str[b]=k;
return 0;
}
{{
public class MovingZerosToEnd {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[]={1,4,0,0,2,3,0,3,0,0,1};
int finalArray[]=new int[array.length];
int j=0;
for(int i=0;i<array.length;i++){
if(array[i]!=0){
finalArray[j]=array[i];
j++;
}
}
for(int i=0;i<finalArray.length;i++){
System.out.print(finalArray[i]);
}
}
}
}}
#include <stdio.h>
#include <string.h>
void main()
{
int n[10] ={ 0,0,0,0,0,0,0,0,0,1};
int i,temp=0,index=0;
for( i=0;i<10;i++)
{
if(n[i]==0 && n[i+1]!=0 && (i+1<10))
{
if(index==0 && n[0]==0)
{
index =0;
}
else if(index==0)
{
index =i;
}
temp= n[index];
n[index]=n[i+1];
n[i+1]=temp;
index++;
}
}
for( i=0;i<10;i++)
{
printf("%d",n[i]);
}
getch();
}
you can take any no of inputs in an array ..just replace the fix count with the number of elements
Simple working code
#include <iostream>
using namespace std;
void pushZerotoEnd(int *arr, int len)
{
int *start = arr;
int *end = arr + len -1;
while (start < end)
{
while (*start != 0)
{
start++;
}
while (*end == 0)
{
end--;
}
if (start < end)
{
swap(*start, *end);
}
else
{
break;
}
++start;
--end;
}
}
void printArray(int* arr, int len)
{
for (int i = 0; i < len; ++i) {
cout<<*(arr+i)<<" ";
}
cout<<endl;
}
int main()
{
int a[] = {1, 12, 0,3, 2, 11, 0, 5,0, 6, 7};
pushZerotoEnd(a, sizeof(a)/sizeof(int));
printArray(a, sizeof(a)/sizeof(int));
return 0;
}
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Stream111 {
public static void main(String[] args) {
List <Integer> numbers = Arrays.asList(1,56,89,23,0,3,0,1,0,2,5,0);
List <Integer> all = numbers.stream().filter(s->s>0).collect(Collectors.toList());
List <Integer> zz = numbers.stream().filter(s->s.equals(0)).collect(Collectors.toList());
Stream.concat(all.stream(), zz.stream()).forEach(s->System.out.println(s));;
}
}
the original order/arrangement of zeroes is not conserved once they have been pushed to the end.
- Anonymous February 24, 2014