Facebook Interview Question
Solutions EngineersCountry: Europe
Interview Type: Phone Interview
public class NonZeroElements {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = new int[]{ 1, 0, 2, 0, 0, 3, 4};
System.out.println(Arrays.toString(arr));
//Using selection sort technique
int lastIndex = arr.length - 1;
for(int index = 0; index < arr.length;){
if(index == lastIndex)break;
if(arr[index] == 0){
//swap to last index
int temp = arr[lastIndex];
arr[lastIndex] = arr[index];
arr[index] = temp;
lastIndex--;
}else{
index++;
}
}
System.out.println(Arrays.toString(arr));
}
}
//Time: O(N) Space: O(1)
public int[] shiftElems(int[] arr){
if(arr == null || arr.length == 0){
throw new IllegalArgumentException();
}
if(arr.length == 1){
return(arr[0] == 0? 0: 1);
}
boolean allNonZeros = true;
for(int i = 0; i < arr.length; i++){
if(arr[i] == 0){
break;
allNonZeros = false;
break;
}
}
if(allNonZeros){
return 0;
}
boolean arrangedOkay = true;
i = 1;
while(i < arr.length){
if(arr[i -1] == 0 && arr[i] != 0){
arrangedOkay = false;
break;
}
i++;
}
if(arrangedOkay){
for(int j = 0; j < arr.length; j++){
if(arr[j] ==0){
return j + 1;
}
}
}
int i = 0;
int j = arr.length - 1;
while(i <= j){
if(arr[i] == 0){
swap(i,j,arr);
j--;
}
}
return i + 1;
<?php
$data = [1,0,2,0,0,3,4];
function filter_array($data) {
$data_length = count($data);
$data_length = count($data);
$last_index = $data_length - 1;
for ($i = 0; $i < $data_length; $i++) {
if ($data[$i] == 0) {
$current_data = $data[$i];
for ($j = $i; $j<$data_length; $j++) {
if ($data[$j] > 0) {
$data[$i] = $data[$j];
$data[$j] = $current_data;
break;
}
}
}
}
return $data;
}
filter_array($data);
?>
public class CareerCupPlaceAllNonZero {
public static void main(String[] args){
int arr[] ={4,-1,-2,0,-3,-2,0,-7};
/*for(int i=0; i < arr.length; i++){
if(arr[i] <= 0){
swap(arr,i,0);
}
}*/
System.out.println((sortOnNonZero(arr,0,arr.length)+1));
}
private static int sortOnNonZero(int[] arr, int lo, int hi){
int j = partition(arr,lo,hi);
//sortOnNonZero(arr,lo,j-1);
//sortOnNonZero(arr,j+1,hi);
return j;
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static int partition(int[] arr, int lo, int hi){
int i=lo-1;
int j=hi;
while(lo <=hi){
while(arr[++i] > 0){
if(i==hi) break;
}
while(arr[--j] <= 0){
if(j==lo) break;
}
if(i>=j) break;
swap(arr,i,j);
}
return j;
}
}
Modified version of quick sort will work as following -
public class CareerCupPlaceAllNonZero {
public static void main(String[] args){
int arr[] ={4,-1,-2,0,-3,-2,0,-7};
/*for(int i=0; i < arr.length; i++){
if(arr[i] <= 0){
swap(arr,i,0);
}
}*/
System.out.println((sortOnNonZero(arr,0,arr.length)+1));
}
private static int sortOnNonZero(int[] arr, int lo, int hi){
int j = partition(arr,lo,hi);
//sortOnNonZero(arr,lo,j-1);
//sortOnNonZero(arr,j+1,hi);
return j;
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static int partition(int[] arr, int lo, int hi){
int i=lo-1;
int j=hi;
while(lo <=hi){
while(arr[++i] > 0){
if(i==hi) break;
}
while(arr[--j] <= 0){
if(j==lo) break;
}
if(i>=j) break;
swap(arr,i,j);
}
return j;
}
}
Modified version of quick sort will work -
public class CareerCupPlaceAllNonZero {
public static void main(String[] args){
int arr[] ={4,-1,-2,0,-3,-2,0,-7};
/*for(int i=0; i < arr.length; i++){
if(arr[i] <= 0){
swap(arr,i,0);
}
}*/
System.out.println((sortOnNonZero(arr,0,arr.length)+1));
}
private static int sortOnNonZero(int[] arr, int lo, int hi){
int j = partition(arr,lo,hi);
//sortOnNonZero(arr,lo,j-1);
//sortOnNonZero(arr,j+1,hi);
return j;
}
private static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static int partition(int[] arr, int lo, int hi){
int i=lo-1;
int j=hi;
while(lo <=hi){
while(arr[++i] > 0){
if(i==hi) break;
}
while(arr[--j] <= 0){
if(j==lo) break;
}
if(i>=j) break;
swap(arr,i,j);
}
return j;
}
}
Python solution:
# x=[0,6,8,0,0,1,2,0,0,0,3,7,8,0,0,3,5,0,6,0,0,0]
# x=[1,2,3,4,0,0,5,6,7,8]
x=[0,1,2,3,4,5,6,7,8,8]
zero=-1
_iter=0
print "input: ",
for j in xrange(0,len(x)):
print x[j],
print
for i in xrange(0,len(x)):
if x[i] == 0:
if zero == -1:
zero=i
continue
else:
_iter+=1
if zero != -1:
x[zero]=x[i]
x[i]=0
zero+=1
else:
continue
for j in xrange(0,len(x)):
print x[j],
print
print "Total number of non-zero ints are: " + str(_iter)
python
# x=[0,6,8,0,0,1,2,0,0,0,3,7,8,0,0,3,5,0,6,0,0,0]
# x=[1,2,3,4,0,0,5,6,7,8]
x=[0,1,2,3,4,5,6,7,8,8]
zero=-1
_iter=0
print "input: ",
for j in xrange(0,len(x)):
print x[j],
print
for i in xrange(0,len(x)):
if x[i] == 0:
if zero == -1:
zero=i
continue
else:
_iter+=1
if zero != -1:
x[zero]=x[i]
x[i]=0
zero+=1
else:
continue
for j in xrange(0,len(x)):
print x[j],
print
print "Total number of non-zero ints are: " + str(_iter)
# x=[0,6,8,0,0,1,2,0,0,0,3,7,8,0,0,3,5,0,6,0,0,0]
# x=[1,2,3,4,0,0,5,6,7,8]
x=[0,1,2,3,4,5,6,7,8,8]
zero=-1
_iter=0
print "input: ",
for j in xrange(0,len(x)):
print x[j],
print
for i in xrange(0,len(x)):
if x[i] == 0:
if zero == -1:
zero=i
continue
else:
_iter+=1
if zero != -1:
x[zero]=x[i]
x[i]=0
zero+=1
else:
continue
for j in xrange(0,len(x)):
print x[j],
print
print "Total number of non-zero ints are: " + str(_iter)
Reasonable, but not bug free.
a = list( [ 0:10 ] ) -> { random(true)? 0 : random(10) + 1 }
def move_0_right(arr){
first_zero = 0
last_non_zero = size(arr) - 1
while ( true ){
while ( arr[last_non_zero] == 0 ) { last_non_zero -= 1 }
while ( arr[first_zero] != 0 ) { first_zero += 1 }
break( first_zero > last_non_zero )
arr[first_zero] = arr[last_non_zero]
arr[last_non_zero] = 0
}
last_non_zero + 1
}
println(a)
x = move_0_right(a)
println(a)
println(x)
public static void moveZeroToLeft(int[] arr)
{
if (arr.Length <= 1)
return;
for (int i = 0, j = arr.Length - 1; i -1 != j && j >= 0 ; j--)
{
if (arr[i] == 0)
{
i++;
j++;
}
else
{
if (arr[j] == 0)
{
arr[j] = arr[i];
arr[i] = 0;
i++;
}
}
}
Console.WriteLine("");
for (int i = 0; i < arr.Length; i++)
Console.Write(arr[i] + ", ");
}
#include<iostream>
using namespace std;
class ArraySort{
public:
int arrange()
{
int i,end,temp;
int len=length();
end=len-1;
for(i=0;i<len;i++)
{
if(arr[i]==0)
{ //swap required
while(arr[end]==0 && end>i)
{ end--;
}
arr[i]=arr[end];
arr[end]=0;
}
}
}
void printArr()
{ int i;
for (i=0;i<length();i++)
{
cout<<arr[i]<<"\t";
}
cout<<"\n";
}
private:
int arr[8]={0,0,0,4,5,6,0,0};
int length()
{
return (sizeof(arr))/(sizeof(int));
}
};
int main()
{
ArraySort array;
array.printArr();
array.arrange();
array.printArr();
return 0;
}
public class Solution {
// Takes O(N) time and minimum writes to the array
public void moveNonZeroElementsLeft(int[] array) {
int lastNonZeroElement = this.getLastNonZeroElement(array.length);
if(lastNonZeroElement < 0) {
return array.length;
}
for(int i = 0; i < array.length; i++) {
if(i >= lastNonZeroElement) {
break;
}
else if(array[i] == 0) {
array[i] = array[lastNonZeroElement];
lastNonZeroElement = this.getLastNonZeroElement(lastNonZeroElement);
}
}
return i + 1;
}
private int getLastNonZeroElement(int[] array, int index) {
int i = index - 1;
while(i >= 0) {
if(array[i] != 0) {
return i;
}
i--;
}
return i;
}
}
I wonder if this is really the question
#include <iostream>
using namespace std;
inline void swap(int *x, int *y ) {
if (x !=y) {
int z = *x;
*x = *y;
*y = z;
}
}
void print(int a[], int n) {
for(int i=0; i<n; i++) {
cout << a[i] << " ";
}
}
int main() {
int arr[] = {4,0,5,7,0,1,0,0,4,0,1,2,0,0,0,6};
int length = sizeof(arr)/sizeof(arr[0]);
int begin = 0;
for(int i=0; i<length; i++)
{
if (arr[i] != 0)
{
swap(&arr[i],&arr[begin]);
begin++;
}
}
cout << begin << endl;
print(arr,length);
return 0;
}
import java.util.Arrays;
import java.util.Collections;
public class NonZeroElements {
private static int nonZeroCount(Integer[] arr) {
int count = 0;
for(Integer val : arr) {
if(val != 0) {
count++;
}
}
return count;
}
public static void main(String[] args) {
Integer[] arr = {1,0,2,0,0,3,4};
Arrays.sort(arr, Collections.reverseOrder());
System.out.println(" Result count : " +nonZeroCount(arr));
}
}
import java.util.Arrays;
import java.util.Collections;
public class NonZeroElements {
private static int nonZeroCount(Integer[] arr) {
int count = 0;
for(Integer val : arr) {
if(val != 0) {
count++;
}
}
return count;
}
public static void main(String[] args) {
Integer[] arr = {1,0,2,0,0,3,4};
Arrays.sort(arr, Collections.reverseOrder());
System.out.println(" Result count : " +nonZeroCount(arr));
}
}
public class Movenonzeroleft |
public static int ivalues[] = new int[] | 1, 4, 5, 0, 6, 7, 0 |;
public static void main(String[] args) |
// TODO Auto-generated method stub
System.out.println("No of Non Zeros " + movenonzerotoleft(ivalues));
|
public static int movenonzerotoleft(int iArray[]) |
try |
int iNonZeros = 0;
int iZeros = 0;
int endIndex = iArray.length - 1;
// This is to calculate the end index non zero value
for (int iEnd = endIndex; iEnd >= 0; iEnd--) |
System.out.println("End is " + iArray[iEnd]);
if (iArray[iEnd] == 0) |
endIndex--;
iZeros++;
| else
break;
|
System.out.println("End index is now " + endIndex);
// This is to swap the zero values to the last
for (int i = 0; i <= endIndex; i++) |
if (iArray[i] == 0) |
int temp = iArray[endIndex];
// This is to make sure the endIndex is a non zero value
while (temp == 0) |
endIndex--;
temp = iArray[endIndex];
iZeros++;
|
iArray[endIndex] = 0;
iArray[i] = temp;
endIndex--;
iZeros++;
|
|
// To Print the array
System.out.print("|");
for (int i = 0; i < iArray.length; i++)
System.out.print(iArray[i] + " ");
System.out.println(" |");
System.out.println("No of zeros " + iZeros);
iNonZeros = iArray.length - iZeros;
return iNonZeros;
| catch (Exception e) |
|
return -1;
|
|
public int getNonZeroCount(int[] input) {
int end = input.length - 1;
while (end > 0) {
if (input[end] > 0) {
break;
}
end--;
}
for (int i = 0; i < end; i++) {
if (input[i] < 0) {
swap(input, i, end);
end--;
}
}
return end;
}
public void swap(int input[], int x, int y) {
input[x] = input[x] + input[y];
input[y] = input[x] - input[y];
input[x] = input[x] - input[y];
}
public int getNonZeroCount(int[] input) {
int end = input.length - 1;
while (end > 0) {
if (input[end] > 0) {
break;
}
end--;
}
for (int i = 0; i < end; i++) {
if (input[i] < 0) {
swap(input, i, end);
end--;
}
}
return end;
}
public void swap(int input[], int x, int y) {
input[x] = input[x] + input[y];
input[y] = input[x] - input[y];
input[x] = input[x] - input[y];
}
public class BringNonZeroELementsToLeft {
public static void main(String[] args) {
int arr[] = { 1, 0, 2, 0, 0, 3, 4 };
call(arr);
}
private static void call(int[] arr) {
int zeroCounter = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
zeroCounter++;
} else {
arr[i - zeroCounter] = arr[i];
}
}
for (int i = zeroCounter + 1; i < arr.length; i++) {
arr[i] = 0;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
public class BringNonZeroELementsToLeft {
public static void main(String[] args) {
int arr[] = { 1, 0, 2, 0, 0, 3, 4 };
call(arr);
}
private static void call(int[] arr) {
int zeroCounter = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
zeroCounter++;
} else {
arr[i - zeroCounter] = arr[i];
}
}
for (int i = zeroCounter + 1; i < arr.length; i++) {
arr[i] = 0;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
import java.util.Scanner;
public class ArrayShifting {
/**
* @param args
*/
static int arr[];
//static int j=0;
public static void main(String[] args) {
//Scanner sc = new Scanner(System.in);
//int n=sc.nextInt();
arr=new int[]{0,0,4,0,7,6,0,2};
for(int i=0;i<arr.length;i++){
try {
if(arr[i]==0){
findAndSwap(arr,i);
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
for(int i:arr){
System.out.println("data is" + i);
}
}
public static void findAndSwap(int arr[],int k){
for(int j=arr.length-1;j>=0;j--){
if(arr[j]!=0 && j>=k){
int temp;
temp=arr[j];
arr[j]=arr[k];
arr[k]=temp;
break;
}
}
}
}
import java.util.Scanner;
public class ArrayShifting {
/**
* @param args
*/
static int arr[];
//static int j=0;
public static void main(String[] args) {
//Scanner sc = new Scanner(System.in);
//int n=sc.nextInt();
arr=new int[]{0,0,4,0,7,6,0,2};
for(int i=0;i<arr.length;i++){
try {
if(arr[i]==0){
findAndSwap(arr,i);
}
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
for(int i:arr){
System.out.println("data is" + i);
}
}
public static void findAndSwap(int arr[],int k){
for(int j=arr.length-1;j>=0;j--){
if(arr[j]!=0 && j>=k){
int temp;
temp=arr[j];
arr[j]=arr[k];
arr[k]=temp;
break;
}
}
}
}
function moveZeroes(arr) {
let end = arr.length - 1;
for (let i = 0; i < arr.length; i++) {
if (arr[i] === 0) {
while (arr[end] === 0 && (end > i)) {
end = end - 1;
}
if (end > i) {
let temp = arr[end];
arr[end] = arr[i];
arr[i] = temp;
end = end - 1;
} else {
return arr;
}
}
}
return arr;
}
In python for any list having only positive integers
correct me if any error
import json
x1=input("Enter the list:")
x=json.loads(x1)
def arrange_nonzero(list1):
list1.sort(reverse=True)
count=0
for i in list1:
if i!=0:
count+=1
print("Number of non-zero element:",count)
return list1
arrange_nonzero(x)
- deep March 16, 2017