Microsoft student Interview Question Students
Country: India
Interview Type: Phone Interview
public static void rearrange( int[] arr ){
int cur = arr.length-1;
int copyPos = cur;
while( cur >= 0 ){
if( arr[cur] != 0 && cur != copyPos ){
arr[copyPos] = arr[cur];
--copyPos;
}
--cur;
}
while( copyPos >= 0 ){
arr[copyPos] = 0;
--copyPos;
}
}
the code won't work for this:
1,9,8,4,0,0,2,7,0,6,7
u will loose the last digit 7...
a little modification is required... i.e. start ur code from 1st 0 from right...
i think that ll work...
@ashish, you are right !!
#include "stdio.h"
#include<conio.h>
#define size 11
using namespace std;
int main()
{
int arr[size] = {1,9,8,4,0,0,2,7,0,6,7};
int cur = size-1,current;
for(int j=size; j>0;j--)
{ if(arr[j]==0)
{
current=j;
break;
}}
int copyPos = current;
while( current >= 0 ){
if( arr[current] != 0 && current != copyPos )
{
arr[copyPos] = arr[current];
--copyPos;
}
--current;
}
while( copyPos >= 0 )
{
arr[copyPos] = 0;
--copyPos;
}
for(int i=0;i<size;i++)
printf("%d",arr[i]);
getch();
return 0;
}
#include<stdio.h>
#include<stdlib.h>
int main()
{
int a[10], i, j, k = -1, m, n;
printf("\nEnter the number of elements in an array\n");
scanf("%d", &n);
printf("\nEnter the elments\n");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
i = 0;
while(i < n)
{
if(a[i] == 0)
{
k++;
for(j = i-1; j >= k; j--)
{
m = j;
a[++m] = a[j];
}
a[k] = 0;
i++;
}
else
++i;
}
printf("\nAfter rearrangement numbers are as follows\n");
for(i = 0; i < n; i++)
printf("%d\t", a[i]);
system("pause");
return 0;
}
#include <iostream>
#include <cstdlib>
using namespace std;
int main() {
int arr[] = {1, 3, 0, 2, 0, 0, 24, 9, 0, 1, 44, 0, 0};
for (int i = 0; i < sizeof (arr) / sizeof (int); ++i) {
cout << arr[i] << " ";
}
cout << endl;
for (int i = 0; i < sizeof (arr) / sizeof (int); ++i) {
if (arr[i] == 0) {
int k = i;
for (int j = i - 1; j >= 0; --j) {
arr[k--] = arr[j];
}
arr[0] = 0;
}
}
for (int i = 0; i < sizeof (arr) / sizeof (int); ++i) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Output:
1 3 0 2 0 0 24 9 0 1 44 0 0
0 0 0 0 0 0 1 3 2 24 9 1 44
Start from the end, move all non-zero values to end and fill the remaining elements with zeros.
main()
{
int a[11] = {1,9,8,4,0,0,2,7,0,6,0};
int N = 11, i, j;
for(i = N-1, j = N-1; i >= 0; i--)
{
if(a[i] != 0)
{
a[j] = a[i];
j--;
}
}
for(i = 0; i <= j; i++)
{
a[i] = 0;
}
/* Print */
for (i = 0; i < N; i++)
{
printf("%d", a[i]);
}
}
since there is no ordering among zeroes ..first move all the zeroes at the end..
then..reverse the array..and reverse the non zero numbers...
public class ShiftZero {
public static void main(String args[]){
int [] arr = {1,19,0,5,6,0,11,0,7,6};
for(int i = 0; i< arr.length ; i++){
if(arr[i]==0){
for(int j = i ; j >0 ; j--){
arr[j] = arr[j-1];
}
arr[0]=0;
}
}
for(int i = 0; i< arr.length ; i++){
System.out.println(arr[i]);
}
}
}
public class ShiftZero {
public static void main(String args[]){
int [] arr = {1,19,0,5,6,0,11,0,7,6};
for(int i = 0; i< arr.length ; i++){
if(arr[i]==0){
for(int j = i ; j >0 ; j--){
arr[j] = arr[j-1];
}
arr[0]=0;
}
}
for(int i = 0; i< arr.length ; i++){
System.out.println(arr[i]);
}
}
}
1) First count of zeros. O(n)
2) Init curp to first non-zero value, reduce count of zeros by number of zeros skipped.
3) Set nextp to curp+1 (if not end of array)
4) Do swap loop until count-of-zeros > 0:
if (*nextp == 0) --count-of-zeros
swap(curp, nextp)
if (*curp == 0) ++curp
++nextp
Maybe missing some error checks above. Algo is O(n)
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
using namespace std;
void sort(int * a,int len)
{
int i= 0, j = len,t;
while(j>i){
if(a[i] == 0){
i++;
continue;
}
while(a[--j] != 0);
if(j>i) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
int main() {
int a[5] = {0,1,0,6,5};
sort(&a[0],5);
for(int i =0;i <5;i++) {
cout << a[i];
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[]={1,2,3,4,5,9,7,4,0,6};
for(int i=0;i<arr.length;i++)
{
if(arr[i]==0)
{
for(int c=i;c>0;c--)
{
int temp=arr[c-1];
arr[c-1]=arr[c];
arr[c]=temp;
}
}
}
for(int i=0;i<arr.length;i++)
System.out.print(arr[i]);
}
one can do an insertion sort kind of thing. The following code does the sorting of 0 and non-0 elements.
#include "stdio.h"
#include<conio.h>
using namespace std;
void sortarrayinorder(int arr[],int size)
{
int i,j,tem,k;
for(i=1;i<size;i++)
{
for(j=0;j<i;j++)
{
if(arr[j]!=0 && arr[i]==0)
{
tem=arr[j];
arr[j]=arr[i];
for(k =i;k>j;k--)
arr[k]=arr[k-1];
arr[k+1]=tem;
}
}
}
}
int main ()
{
int arr[7] = {2,0,3,0,1,0,6};
sortarrayinorder(arr,7);
for(int t=0;t<7;t++)
printf("%d ",arr[t]);
getch();
return 0;
}
void rearrange(int a[], int length)
{
//find non 0s from the end of array
int idx = length-1;
for (int j = length-1; j>=0; j--)
{
if (a[j]!=0)
{
a[idx] = a[j]; //shift non 0s to the end, idx--, point to the previous member of the array
idx--;
}
}
//replace beginning space with 0s.
for (int k = idx; k >= 0; k--)
{
a[k] = 0;
}
}
public void shirft(int []num)
{
int pointer,i;
pointer = num.length-2;
for( i = num.length-1 ; i >-1; i-- )
{
if(i<pointer)
pointer = i-1;
if(num[i] == 0)
{
while(pointer > -1 && num[pointer] == 0)
pointer--;
if(pointer < 0)
break;
num[i] = num[pointer];
num[pointer] = 0;
pointer--;
}
}
System.out.println(Arrays.toString(num));
}
#include<iostream>
using namespace std;
void Transfer( int *A , int n )
{
int i = 0;
while(i <n )
{
if( A[i] == 0 )
{
for( int j=i ; j>0 ;j-- )
{
A[j] = A[j-1];
A[j-1] = 0;
}
}
i++;
}
for( int k=0 ; k<n ; k++ )
cout << A[k];
}
int main()
{
int Ar[] = {1,9,0,0,0,0,4,0,8,6,5,0};
Transfer( Ar , 12 );
return 0;
}
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
int arr[]={0,0,1,3,4,0,54,0,0,5};
int i,j,temp;
for(i=-1,j=0;j<10;j++)
{
if(arr[j]==0)
{
i++;
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
for(i=0;i<10;i++)
{
cout<<*(arr+i)<<endl;
}
return 0;
}
This solution is wrong, It will change the order of numbers. Out put should be 0,0,0,0,1,9,8,4,2,7,6, but it is printng different output
This solution is wrong, It will change the order of numbers. Out put should be 0,0,0,0,1,9,8,4,2,7,6, but it is printng different output
void shiftZero(int *a,int n) //array has zero and sm non zero numbers , shift zero to begining and order same for non zero
{
int index = n-1,count=0; //count counts the zero occurences
int toBshift = 0; //if element is zero then increment the count and copy the next left integer
for(;index>= 0;index--)
{
a[index + count] = a[index];
if(a[index] == 0)
{
count++;
}
}
while(count != 0)
{
a[count-1] = 0;
count--;
}
return;
}
int [] number ;
void setup()
{
int[] number = {1,9,8,4,0,0,2,7,0,6,0};
for(int i = 0; i<number.length ; i++)
{
if(number[i] == 0)
{
for(int j=0; j< i; j++)
{
if(number[j] != 0)
{
int temp = number[j];
number[j] = number[i];
number[i] = temp;
}
}
}
}
for(int i =0 ; i<number.length; i++)
{
println (" \n" + number[i]);
}
}
#include<conio.h>
#include<stdio.h>
int main()
{
int arr[11],b[11];
int i, k;
static int j;
printf("Enter the array :");
for(i=0;i<11;i++)
{
scanf("%d",&arr[i]);
printf("\n");
}
j=0;
for(i=0;i<11;i++)
{
if(arr[i]==0)
{
b[j]=arr[i];
j++;
}
}
for(i=0;i<11;i++)
{
if(arr[i]!=0)
{
b[j]=arr[i];
j++;
}
}
for(j=0;j<11;j++){
printf("%d",b[j]);
}
getch();
return 0;
}
public class Examplearray{
public static void main(String[] args){
int num[] = {1,9,8,4,0,0,2,7,0,6,0};
int l = num.length;
int i,j,k,count0=0;
for(j=0;j<l;j++)
{
if(num[j]==0)
count0++;
}
for(j=0,i=l-1,k=l-1;j<l;j++)
if(num[i]==0)
{
i--;
}
else
{
num[k]=num[i];
k--;
i--;
}
for(i=0;i<count0;i++)
{
num[i]=0;
}
System.out.print("After Shifting : ");
for(i = 0;i < l;i++){
System.out.print(" " + num[i]);
}
}}
So mine works by swapping the current index of an array when looping through it in reverse with the next nonzero value position, then setting that nonzero position's value to 0.
Here's a step by step
{ 1 0 0 2 0 3 0 } index = 6 nonZeroPosition = 6
{ 1 0 0 2 0 0 3 } index = 5 nonZeroPosition = 5
{ 1 0 0 0 0 2 3 } index = 4 nonZeroPosition = 3
{ 0 0 0 0 1 2 3 } index = 3 nonZeroPosition = 0
Code is in C#
void arrange(ref int[] array)
{
// Assume last position is nonzero (but code handles it it isn't)
int nonZeroPosition = array.Length - 1;
for (int index = array.Length - 1; index >= 0; index--)
{
if (array[index] == 0)
{
// Find the first index in reverse array where the value isn't 0
while (array[nonZeroPosition] == 0)
{
nonZeroPosition--;
// If your index walker reaches end, return because array is sorted
if (nonZeroPosition < 0)
{
return;
}
}
// Swap current index with the nonzero value
array[index] = array[nonZeroPosition];
// Set the nonzero value index to 0
array[nonZeroPosition] = 0;
}
else
{
nonZeroPosition--;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/// <summary>
/// TODO: Update summary.
/// </summary>
public class Move0ToBeginning
{
//...read numbers
private int valueN;
private List<int> numbers = new List<int>();
public Move0ToBeginning()
{
start();
}
private void start()
{
Console.WriteLine("Please enter value for n: ");
string readN = Console.ReadLine();
valueN = Int32.Parse(readN);
Console.WriteLine("Please enter {0} numbers: ",valueN);
for (int i = 0; i < valueN; i++)
{
numbers.Add(Int32.Parse(Console.ReadLine()));
}
for (int i =valueN-1, count0 = 0; i >=0 ; i--)
{
if (numbers[i] == 0)
{
count0++;
}
else if(count0!=0)
{
//swap the number by the count0 positions
numbers[i + count0] = numbers[i];
numbers[i] = 0;
}
}
foreach (var num in numbers)
Console.WriteLine("-> " + num);
}
}
tell me if i am wrong
Flawless code....Enjoy!!
void putZerosInFront(int arr[], int len)
{
if(!arr || len < 1)
return;
int i = len-1;
while( i > 0 )
{
if(arr[i] == 0)
{
for(int j = i-1; j >= 0; j--)
{
if(arr[j] != 0)
{
swap(arr[i],arr[j]);
break;
}
}
}
i--;
}
}
Flawless? LOL!
Example: You pass in an array and check for NULL?
And it looks quadratic while a linear time algorithm is possible.
First of all, thanks for pointing out the Time complexity... Below goes the code with O(n) ...
Secondly, there is nothing to laugh about NULL check. What if caller passes a NULL pointer ( acceptable in C++ )?
O(n) code...
void putZerosInFront(int arr[], int len)
{
if(!arr || len < 1)
return;
int i = len-1;
for(int j = i-1; j >=0; j--)
{
if(arr[i] == 0)
{
if(arr[j] != 0)
{
swap(arr[i],arr[j]);
i--;
}
}
else
{
i--;
}
}
}
O(n) time and O(1) space solution in Java
package arrays;
public class MoveZeroesToBegin {
public static void main(String[] args) {
int a[] = { 1, 2, 0, 4, 0, 0, 8,9,0,2,3,0,4,5 };
move_zeroes_to_begin(a);
for (int i : a) {
System.out.print(i+" ");
}
}
private static void move_zeroes_to_begin(int[] a) {
int index = -1;
// find the first zero from the end
for (int i = a.length-1; i >= 0; i--) {
if (a[i] == 0) {
index = i;
break;
}
}
if (index != -1) {
int j = index - 1;
while (j >=0) {
if (a[j] != 0) {
a[index] = a[j];
index--;
j--;
} else if (a[j] == 0) {
j--;
}
}
while(index >=0){
a[index--]=0;
}
}
}
}
1. Start from the end of array and copy non-zero number in-place.
void ReArrangeNums()
{
int arr[] = {1,9,8,4,0,0,2,7,0,6,0};
int n = sizeof(arr)/sizeof(arr[0]);
int i, in_scr = n - 1, in_des = n - 1;
printf("\n Input\n");
for (i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
while(in_des >= 0)
{
if (arr[in_des] != 0)
{
arr[in_scr] = arr[in_des];
in_scr--;
}
in_des--;
}
for (i = 0; i <= in_scr; i++)
{
arr[i] = 0;
}
printf("\n Output\n");
for (i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
int* ZeroRepla(int* str, int len)
{
int in=len-1, it = len-1;
if( str == NULL )
return NULL;
while( it >= 0)
{
if( str[it] == 0)
{
static int c= it-1;
while( (str[c] == 0) && (c >= 0 ))
{
c--;
}
if( c < 0 ) break;
str[in] = str[c];
str[c]=0;
in--;
}
else
{
str[in] = str[it];in--;
}
it--;
}
return str;
}
c# code:
using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void sepearte(int[] array)
{
int start = 0;
int end = array.Length - 1;
while (start < end)
{
if (array[start] == 0)
start++;
else if (array[end] != 0)
end--;
else
{
array[end] = array[start];
array[start] = 0;
}
}
}
static void print(int[] array)
{
foreach (int i in array)
Console.Write(i + ":");
Console.WriteLine();
}
static void Main(string[] args)
{
int[] array = new int[10] { 0, 1, 2, 0, -1, 0, 2, 3, 0, 0 };
print(array);
sepearte(array);
print(array);
}
}
}
- getjar.com/todotasklist my android app March 09, 2012void arrange(int a[],int n) { int i=n-1,zero=n-1; for(;i>=0;) { if(a[i]==0) { i--; } else { int t=a[i]; a[i]=0; a[zero]=t; zero--; i--; } } }