Expedia Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
I've run your code and its wrong. The way your algorithm works is that you swap the value of the array if its zero into the counter from the start which is correct. But the thing there is that how the value stored in the temp will be moved? another thing about the question is that it is organized considering that the zero must be at the first position of the array.
The code certainly pushes all the zero to the begining but changes the order of the nonzero element.
O(N) solution:
int i, j;
for ( j=i=arr.length() ; i >=0 ; i--)
{
# Skip over zero elements
if(arr[i] == 0)
continue;
# i landed on index where there is a non-zero element,
# thus copy it back to position j, and move j to next spot to fill.
arr[j] = arr[i];
j--;
}
# Zero fill remaining leading spots in array.
while( j >= 0 )
{
arr[j]=0;
j--;
}
I've come up with this code. If someone gives me suggestions on its quality, it will be highly helpful.
#include<stdio.h>
int main()
{
int arr[] = {1,2,3,0,0,0,4,5,6};
int i = 0,count = 0,temp = 0;
for(i = 0;i < sizeof(arr)/sizeof(arr[0]); i++ )
{
if(arr[i] == 0)
{
arr[i] = arr[count];
arr[count] = 0;
count++;
}
}
for(i = 0;i < 9; i++ )
{
printf("%d ", arr[i]);
}
}
public static int[] moveZeros(int[] input) {
int zeroIndex = 0, noIndex = 0;
while(zeroIndex < input.length && noIndex < input.length) {
while(zeroIndex < input.length && input[zeroIndex] != 0) zeroIndex++;
while(noIndex < input.length && input[noIndex] == 0) noIndex++;
if(zeroIndex > noIndex && zeroIndex < input.length && noIndex < input.length) {
int temp = input[zeroIndex];
input[zeroIndex] = input[noIndex];
input[noIndex] = temp;
noIndex++; zeroIndex++;
}
}
return input;
}
public static int[] moveZeros(int[] input) {
int zeroIndex = 0, noIndex = 0;
while(zeroIndex < input.length && noIndex < input.length) {
while(zeroIndex < input.length && input[zeroIndex] != 0) zeroIndex++;
while(noIndex < input.length && input[noIndex] == 0) noIndex++;
if(zeroIndex > noIndex && zeroIndex < input.length && noIndex < input.length) {
int temp = input[zeroIndex];
input[zeroIndex] = input[noIndex];
input[noIndex] = temp;
noIndex++; zeroIndex++;
}
}
return input;
}
#include<stdio.h>
#include<conio.h>
int main()
{
int a[10];
int n,c,index,i,temp;
c=1;
printf(" enter the size of array:=>");
scanf("%d",&n);
printf(" enter the element of array :=>");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
if(a[i]>0 && c>0)
{
index=i;
temp=a[i];
c--;
}
else
{
if(a[i]==0 && c==0)
{
a[index]=a[i];
a[i]=temp;
index++;
temp=a[index];
}
}
}
printf(" now required array :=>");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
<!DOCTYPE html>
<html>
<body>
If you have any UI position available in Washington State plz reach me @ 425 949 6101
<p>A function can access variables defined inside the function:</p>
<button type="button" onclick="myFunction()">Click Me!</button>
<p id="demo"></p>
<script>
function myFunction() {
var arr = [1,2,3,0,0,0,1,0,4,5,0,5,0,9,6,0],i=0;
var arrN = [];
var arrN1 = [];
for(i=0;i<arr.length;i++){
if(arr[i] == 0){
arrN.push(0);
}
else{
arrN1.push(arr[i]);
}
}
arrN = arrN.concat(arrN1);
alert(arrN);
}
</script>
</body>
</html>
public static void pushZeroToStart(int[] a) {
int zeroIndex = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] == 0 && (i - zeroIndex) >= 2) {
int toReplace = a[i];
for (int j = zeroIndex; j <= i; j++) {
int temp = a[j];
a[j] = toReplace;
toReplace = temp;
}
zeroIndex++;
}
}
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
Please note that we need to make sure that:
- Move all zeros to the first
- Keeps the order of others
public static int[] moveZero2Firsts(int[] inp) {
int zeroCount = 0;
int otherCout = 0;
for(int i = 0;i < inp.length; i ++) {
if(inp[i] == 0)
zeroCount++;
else
otherCout++;
}
int[] out = new int[inp.length];
int j = zeroCount;
for(int i = 0;i < inp.length; i ++) {
if(inp[i] != 0) {
out[j] = inp[i];
j++;
}
}
return out;
}
public static void zeroFirstPlaceSortedArray(int[] arr){
int tempIndex = arr.length-1;
int zeroCount=0;
//to count zero
for(int i=0; i<arr.length;i++){
if(arr[i] == 0){
zeroCount++;
}
}
//to set non zero in ending indices
for(int i=tempIndex;i>=0 ;i--){
if(arr[i] != 0){
swap(arr, tempIndex, i);
tempIndex--;
}
}
//to set zero in initial indices
for(int i =0; i<zeroCount; i++)
arr[i]= 0;
}
private static void swap(int[] arr, int tempIndex, int i) {
int tempInt;
tempInt = arr[tempIndex];
arr[tempIndex]= arr[i];
arr[i]= tempInt;
}
public static int[] moveZeros(int[] array) {
int left = 0;
int right = array.length -1;
while (left < right) {
if (array[left] != 0 && array[right] == 0) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
} else if (array[left] != 0 && array[right] != 0) {
right--;
} else if (array[left] == 0){
left++;
}
}
return array;
}
public class MoveZeros {
private static int[] moveZerosToFront(int[] arr) {
int count = arr.length -1 ;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] != 0) {
arr[count--] = arr[i];
}
}
for (int j = 0; j <= count; j++) {
arr[j] = 0;
}
return arr;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 0, 0, 0, 4, 5, 0, 6, 7, 0 };
int[] ans = moveZerosToFront(arr);
for (int i = 0; i < ans.length; i++) {
System.out.println(arr[i]);
}
}
}
public class MoveZeros {
private static int[] moveZerosToFront(int[] arr) {
int count = arr.length -1 ;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] != 0) {
arr[count--] = arr[i];
}
}
for (int j = 0; j <= count; j++) {
arr[j] = 0;
}
return arr;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 0, 0, 0, 4, 5, 0, 6, 7, 0 };
int[] ans = moveZerosToFront(arr);
for (int i = 0; i < ans.length; i++) {
System.out.println(arr[i]);
}
}
}
public class MoveZeros {
private static int[] moveZerosToFront(int[] arr) {
int count = arr.length -1 ;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] != 0) {
arr[count--] = arr[i];
}
}
for (int j = 0; j <= count; j++) {
arr[j] = 0;
}
return arr;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 0, 0, 0, 4, 5, 0, 6, 7, 0 };
int[] ans = moveZerosToFront(arr);
for (int i = 0; i < ans.length; i++) {
System.out.println(arr[i]);
}
}
}
public class MoveZeros {
private static int[] moveZerosToFront(int[] arr) {
int count = arr.length -1 ;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] != 0) {
arr[count--] = arr[i];
}
}
for (int j = 0; j <= count; j++) {
arr[j] = 0;
}
return arr;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 0, 0, 0, 4, 5, 0, 6, 7, 0 };
int[] ans = moveZerosToFront(arr);
for (int i = 0; i < ans.length; i++) {
System.out.println(arr[i]);
}
}
}
and
public class MoveZeros {
private static int[] moveZerosToFront(int[] arr) {
int count = arr.length -1 ;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] != 0) {
arr[count--] = arr[i];
}
}
for (int j = 0; j <= count; j++) {
arr[j] = 0;
}
return arr;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 0, 0, 0, 4, 5, 0, 6, 7, 0 };
int[] ans = moveZerosToFront(arr);
for (int i = 0; i < ans.length; i++) {
System.out.println(arr[i]);
}
}
}
public class MoveZeros {
private static int[] moveZerosToFront(int[] arr) {
int count = arr.length -1 ;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] != 0) {
arr[count--] = arr[i];
}
}
for (int j = 0; j <= count; j++) {
arr[j] = 0;
}
return arr;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 0, 0, 0, 4, 5, 0, 6, 7, 0 };
int[] ans = moveZerosToFront(arr);
for (int i = 0; i < ans.length; i++) {
System.out.println(arr[i]);
}
}
}
public class MoveZeros {
private static int[] moveZerosToFront(int[] arr) {
int count = arr.length -1 ;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] != 0) {
arr[count--] = arr[i];
}
}
for (int j = 0; j <= count; j++) {
arr[j] = 0;
}
return arr;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 0, 0, 0, 4, 5, 0, 6, 7, 0 };
int[] ans = moveZerosToFront(arr);
for (int i = 0; i < ans.length; i++) {
System.out.println(arr[i]);
}
}
}
public class MoveZeros {
private static int[] moveZerosToFront(int[] arr) {
int count = arr.length -1 ;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] != 0) {
arr[count--] = arr[i];
}
}
for (int j = 0; j <= count; j++) {
arr[j] = 0;
}
return arr;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 0, 0, 0, 4, 5, 0, 6, 7, 0 };
int[] ans = moveZerosToFront(arr);
for (int i = 0; i < ans.length; i++) {
System.out.println(arr[i]);
}
}
}
public class MoveZeros {
private static int[] moveZerosToFront(int[] arr) {
int count = arr.length -1 ;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] != 0) {
arr[count--] = arr[i];
}
}
for (int j = 0; j <= count; j++) {
arr[j] = 0;
}
return arr;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 0, 0, 0, 4, 5, 0, 6, 7, 0 };
int[] ans = moveZerosToFront(arr);
for (int i = 0; i < ans.length; i++) {
System.out.println(arr[i]);
}
}
}
#include <stdio.h>
int main()
{
int i,count,n;
int arr[]={0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,8,0,9};
n=sizeof(arr)/sizeof(arr[0]);
// printf("%d\n",n);
count=n-1;
for(i=n-1;i>=0;i--)
{
if(arr[i]!=0)
arr[count--]=arr[i];
}
while(count>=0)
arr[count--]=0;
for(i=0;i<n;i++)
printf("%d",arr[i]);
return 0;
}
using System;
public class Program
{
public static void Main()
{
int [] array = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
MoveZeroesFront(array);
for(int i=0; i<array.Length; i++)
{
Console.WriteLine(array[i]);
}
}
public static void MoveZeroesFront(int [] array)
{
int count = array.Length-1;
for(int k = array.Length-1; k>=0;k--)
{
if(array[k] != 0)
{
int t = array[count];
array[count] = array[k];
array[k] = t;
count--;
}
}
}
}
using System;
public class Program
{
public static void Main()
{
int [] array = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
MoveZeroesFront(array);
for(int i=0; i<array.Length; i++)
{
Console.WriteLine(array[i]);
}
}
public static void MoveZeroesFront(int [] array)
{
int count = array.Length-1;
for(int k = array.Length-1; k>=0;k--)
{
if(array[k] != 0)
{
int t = array[count];
array[count] = array[k];
array[k] = t;
count--;
}
}
}
}
public class MoveAllZerosToBeginning {
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer a[]= {1,2,3,0,14,0,4,5,0,0,9,0,-2};
Arrays.sort(a, new CustomComparator(a));
System.out.println("Array after sorting: ");
for(int i: a) {
System.out.print(i+" ");
}
}
static class CustomComparator implements Comparator<Integer>{
Map<Integer,Integer> m=new HashMap<>();
public CustomComparator(Integer a[]) {
for(int i=0;i<a.length;i++) {
m.put(a[i], i);
}
}
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
if(o1==0) {
return o1.compareTo(o2);
}
else {
return m.get(o1).compareTo(m.get(o2));
}
}
}
}
#include <iostream>
using namespace std;
void pushZerosToEnd(int arr[], int n)
{
int count = n-1;
for (int i=n-1; i>=0; i--)
if (arr[i] != 0)
arr[count--] = arr[i];
while (count >= 0)
arr[count--] = 0;
}
// Driver program to test above function
int main()
{
int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
int n = sizeof(arr) / sizeof(arr[0]);
pushZerosToEnd(arr, n);
cout << "Array after pushing all zeros to end of array :n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
#include <iostream>
using namespace std;
void pushZerosToEnd(int arr[], int n)
{
int count = n-1;
for (int i=n-1; i>=0; i--)
if (arr[i] != 0)
arr[count--] = arr[i];
while (count >= 0)
arr[count--] = 0;
}
// Driver program to test above function
int main()
{
int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
int n = sizeof(arr) / sizeof(arr[0]);
pushZerosToEnd(arr, n);
cout << "Array after pushing all zeros to end of array :n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
- Vir Pratap Uttam May 23, 2015