Expedia Interview Question
Software Engineer in TestsTeam: SDET
Country: India
Interview Type: Phone Interview
I agree with abcd. It is o(n) the least possible complexity (since it is required to know each and every element). And it is inplace algorithm. And the code is
void arrange(int a[],int n)
{
int i=0;
int j = n-1;
while(i<j)
{
while(a[i] == 0) i++;
while(a[j] != 0) j--;
if(i<j)
swap(a,i,j);
}
}
Initiaze another Array of same lengh...
Iterate the input Array from back, copy non-zero numbers into resultArray from back.
When iteration completes, put Zeros in all initial indexes of result Array
public static int[] unusualSort(int[] inputArr) {
//Chk null conditions, isEmpty etc
int result[] = new int[inputArr.length] ;
int i = inputArr.lengh - 1;
int j = result.length - 1;
while(i >= 0) {
if (inputArr[i] != 0) {
resultArray[j] = inputArr[i] ;
j--;
}
i--;
}
while(j >=0) {
resultArr[j] = 0;
}
return resultArr;
}
It is a very good answer. Just a comment for improvement: You don't have to assign 0 to remaining position, their default value is already zero. So:
private static int[] sort(int[] arr){
int[] res = new int[arr.length];
int count = arr.length - 1;
for(int i = 0; i < arr.length; i++){
if(arr[i] != 0)
res[count--] = arr[i];
}
return res;
}
It is bad answer. You are using extra memory. What if you have to do that in-place.
See my answer below
#include<stdio.h>
int main()
{
int index,len;
int arr[20];
len=(sizeof(arr)/sizeof(arr[1]))-1;
for(index=0;index<=len;index++)
scanf("%d",&arr[index]);
for(index=0;index<len;index++)
{
if(arr[index]==0 && arr[len]==0)
{
;
}
else if(arr[index]==0 && arr[len]!=0)
{
len--;
}
else if(arr[index]!=0 && arr[len]!=0)
{
index--;
len--;
}
else
{
arr[len]=arr[index];
arr[index]=0;
}
}
return 0;
}
void arrange(int array[]){
int len = sizeof(array)/ sizeof(array[0]);
int low, mid;
for(low = mid = 0; mid < len; ) {
array[mid] == 0 ? swap(&array[low++], &array[mid++]) : mid++;
}
}
There are two solutions to deal with this problem.
1.From head to tail
2.From tail to head
Below is the code, since the logic is not very complicated, so I believe the code is enough.
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cassert>
#include <climits>
using namespace std;
void swap(int& a, int& b){ int c = a; a = b; b = c; }
void rearrangeArray1(int n, int data[])
{
int i = 0;
int j = 0;
for(i = 0; i < n; i++)
{
if(data[i] != 0 && i < n - 1)
{
for(j = i + 1; j < n; j++)
{
if(data[j] == 0)
{
swap(data[i], data[j]);
break;
}
}
/* which means the elements after i are all not zero */
if(j == n)
{
break;
}
}
}
}
void rearrangeArray2(int n, int data[])
{
int i = 0;
int j = 0;
for(i = n - 1; i > 0; i--)
{
if(data[i] == 0)
{
for(j = i - 1; j >= 0; j--)
{
if(data[j] != 0)
{
swap(data[i], data[j]);
break;
}
}
if(j == 0)
{
break;
}
}
}
}
int main()
{
int a[10] = {10, 9, 0, 8, 7, 0, 12, 0, 0, 20};
rearrangeArray1(10, a);
rearrangeArray2(10, a);
for(int i = 0; i < 10; i++)
{
cout << a[i] << endl;
}
return 0;
}
You start from end, have two pointers pushPointer where the data will do and data pointer from where the data will come, if data at dataPointer is not 0 move it to push pointer if it is 0 skip, when you are finished you have skipped all 0s and pushed all non zeros to end, now push all 0up to push pointer, kind of two sorted linklist merge problem.
void MoveZeroToStart(int[] input){
// Do input validation
if (input == null || input.Length = 0)
return;
int pushPointer = input.Length-1;
int dataPointer = input.Length-1;
for (int dataPointer = input.Length-1; dataPointer>= 0;dataPointer --){
if (input[dataPointer] != 0){
input[pushPointer] = input[dataPointer];
pushPointer--;
dataPointer--;
}
}
for (int j = pushPointer; j >= 0; j--){
input[pushPointer] = 0;
pushPointer--;
}
}
#include <iostream>
using namespace std;
void zerosToOneEnd(int* arr, int N);
int main()
{
int N = 0;
int input = 0;
cout << "Enter the array size: ";
cin >> N;
int arr[N];
cout << endl;
cout << "Enter the elements one by one: ";
for(int i = 0; i < N; i++){
cin >> input;
arr[i] = input;
}
cout << "Unsorted: ";
for(int x = 0; x < N; x++){
cout << arr[x] << " ";
}
zerosToOneEnd(arr, N);
cout << "Sorted: ";
for(int x = 0; x < N; x++){
cout << arr[x] << " ";
}
return 0;
}
void zerosToOneEnd(int* arr, int N){
int i = 0;
int j = N-1;
while(i < j){
while(arr[i] == 0){
i++;
}
while(arr[j] != 0){
j--;
}
if(i <= j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
}
public class TestArray {
private static int[] sort(int[] arr){
int i =0;
int j= arr.length-1;
boolean leftReplace = false;
boolean rightReplace = false;
while(i<=j){
if(arr[i] !=0){
leftReplace=true;
}
if(arr[j] ==0){
rightReplace = true;
}
if(leftReplace && rightReplace){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
leftReplace = false;
rightReplace = false;
}
i++;
j--;
if(leftReplace && !rightReplace){
i--;
}
if(!leftReplace && rightReplace){
j++;
}
}
return arr;
}
public static void main(String[] args) {
int arr[]={0,3,4,6,2,0,2,0,1,1,1,0,2,2,4,1,1,0,0};
int k[] = sort(arr);
for(int i=0;i<k.length;i++){
System.out.println(k[i]);
}
}
}
if asked to do inplace
- abcd May 16, 2013Take 2 pointers, one from Start, other From End
and Keep Swapping 0 and non-zero