VMWare Inc Interview Question
Java DevelopersCountry: United States
Interview Type: Phone Interview
I like this. I wrote one where I explicitly keep track of the first odd index as well, but your solution is simpler. In the swap, you just have to make sure to avoid swapping the same element with itself.
i came up with this but your's is so much more elegant.
private static void rearrangeArray(Integer[] intarry) {
// count the number of evens
int count = 0;
for (int i : intarry) {
if (i % 2 == 0)
count++;
}
int i = 0, j = intarry.length - 1;
while (true) {
if (i >= count) {
break;
}
while (intarry[i] % 2 == 0) {
i++;
}
while (intarry[j] % 2 != 0) {
j--;
}
exchangeValues(intarry, i, j);
i++;
j--;
}
}
@Chris: I am not sure but aren't you also swapping an element with itself, if this is implicitly assumed. You can perhaps add an if statement in the swap function
if( i != j).
public static void moveEvenToLeft(int[] array) {
int i = 0;
for (int j = 0; j < array.length; j++) {
if (array[j] % 2 == 0 && i != j) {
swap(array, i, j);
i++;
}
}
}
This could be done in one scan.
We use 2 pointers evenRef and oddRef.
evenRef points to the first element of the array and oddRef to the last.
Now we increment and decrement the even and odd references respectively according to the element we encounter in the array and make appropriate swaps.
This process is repeated until both the references meet.
public static void reArrangeArray(int[] inputArray)
{
int n = inputArray.length;
int evenRef=0,oddRef=n-1;
while(evenRef<oddRef)
{
while(inputArray[evenRef]%2==0)
evenRef++;
while(inputArray[oddRef]%2!=0)
oddRef--;
swapAtIndices(inputArray,evenRef,oddRef);
evenRef++;
oddRef--;
}
}
private static void swapAtIndices(int[] inputArray, int evenRef, int oddRef) {
int temp=inputArray[evenRef];
inputArray[evenRef]=inputArray[oddRef];
inputArray[oddRef]=temp;
}
Please correct me if I'm wrong.
while(j<k)
{
System.out.println("j"+j+"k"+k);
if(arrayList.get(j)%2==0)
j++;
else if(arrayList.get(k)%2==1)
k--;
else
{
temp=arrayList.get(j);
arrayList.set(j, arrayList.get(k));
arrayList.set(k, temp);
}
}
Working java code:
public static void seperate_evens_odds(int array[]){
int i=0;
int j=array.length-1;
while (true){
if(array[i] % 2 == 0) ++i;
if(array[j] % 2 == 1) --j;
if(i >= j) break;
if(array[i] % 2 == 1 && array[j] % 2 == 0)
{
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
int even(int n)
{
if(n==1) return 0;
else if(n%2==0) return 1;
else return 0;
}
int odd(int n)
{
if(n==1) return 1;
else if (n%2==0) return 0;
else return 1;
}
void separate_the_array(int a[],int i,int j)
{
int n=j;
while(1)
{
while(i<j && even(a[i]))
i++;
while(i<j && odd(a[j]))
j--;
if(i>=j) break;
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
for(i=0;i<=n;i++)
printf("%d ",a[i]);
}
void main()
{
int a[]={4,5,10,3,2,11,14,7,6};
int n=sizeof(a)/4;
separate_the_array(a,0,n-1);
}
package com.ad.test.string;
public class EvenOdd {
/**
* @param args
*/
int test[]={4,6,2,5,7,1,2,3,4,5,6,7,8,9,7,6,5,4,3,2,34,5,56,6};
void setEvenOdd(){
int temp=0;
for(int i=0;i<test.length;i++){
// even
if(test[i]%2!=0){
for(int j=i+1;j<test.length;j++){
if(test[j]%2==0){
test[j]=test[i]+test[j];
test[i]=test[j]-test[i];
test[j]=test[j]-test[i];
break;
}
}
}
}
for(int i=0;i<test.length;i++){
System.out.print(" "+test[i]);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
new EvenOdd().setEvenOdd();
}
}
For moving the elements that is the even to the left and odd to the right we could take the following approach:
a.Consider two references such that one reference points to the start of the array and another points to the last of the array. Increment the first reference and decrement the second reference until first is equal to second.
b.Now if the both references point to even element then increment the first reference as the second reference now points to the even element and whenever we find that the first points to the odd then we swap both the elements.
c.If last points to even and first points to odd then first swap and then decrement the second and increment the first pointer
d.If first points to even and second points to odd then decrement the second reference as it is already that is the odd element is already in the right side of the array.
e.If both the elements are odd then also decrement the second reference as the odd element should be to the right and for the first one pointing to the odd whenever an even element is found that condition is handled in the c. condition. Below is the code:
void swap(int arr[],int i,int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
void placeElements(int arr[],int n)
{
int i=0,j=n-1;
while(i<j)
{
if(arr[j]%2==0&&arr[i]%2==0)
{
i++;
}
else if(arr[j]%2==0&&arr[i]%2!=0)
{
swap(arr,i,j);
j--;
i++;
}
else if(arr[j]%2!=0&&arr[i]%2==0)
{
j--;
}
else
{
j--;
}
}
}
void printArray(int arr[],int n)
{
int i;
for(i=0;i<n;i++)
printf("%d ",arr[i]);
}
int main()
{
int arr[]={3,3,3,5};
int n=sizeof(arr)/sizeof(arr[0]);
placeElements(arr,n);
printArray(arr,n);
}
public void doIt(int[] arr) {
for (int left = 0, right = arr.length - 1; left < right;) {
if ((arr[left] & 1) != 0) {
int temp = arr[left];
arr[left] = arr[right];
arr[right--] = temp;
} else {
++left;
}
}
}
How is it working here you are checking for whether the element is not odd that is even and then exchanging with the element at the right whereas even elements should be at the left and not the right.
void dis(int *a, int len);
void even_odd(int *a, int len)
{
int i=0;
int e,o;
int i_e=0;
int i_o=len-1;
for(i=0; i<len; i++)
{
//printf("i = %d , i_e = %d , i_o = %d\n", i, i_e, i_o);
if(i > i_o)
break;
if(a[i] % 2 == 0)
{
a[i_e++] = a[i];
}
else
{
int t;
t=a[i];
a[i] = a[i_o];
a[i_o] = t;
i_o--;
i--;
//dis(a,len);
}
}
dis(a,len);
//dis(a,i_e);
}
void dis(int *a, int len)
{
int i;
for(i=0; i<len; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
#include<stdio.h>
int main()
{
int *a,n,i,j,temp;
int evenCount=0;
printf("enter the number of elements u want in the array");
scanf("%d",&n);
a=(int *)malloc(sizeof(int)*n);
printf("\n\nenter the %d elements u want in the array",n);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(i=0;i<n;i++){
if(a[i]%2==0)
evenCount++;
}
for(i=0;i<evenCount;i++){
if(a[i]%2!=0){
for(j=n-1;j>=evenCount;j--){
if(a[j]%2==0){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}
printf("\n\nthe final array is ");
for(i=0;i<n;i++){
printf("%d ",a[i]);
}
return 0;
}
// Given +ve numbers in an array.
// Put the even #s to the left of the array and the odd to the right side of the array . Don't use extra array.
public static void Question1()
{
// assumption, left and right sides of the array are un-orderd.
int[] input = new int[] { 1, 2, 3, 4, 6, 2, 1, 5, 6, 7, 8, 2, 2, 2, 2 };
int start = 0;
int end = input.Length - 1;
Console.WriteLine(string.Join(",", input));
while (start < end)
{
if (input[start] % 2 == 0) // start is even - skip it
{
start++;
continue;
}
if (input[end] % 2 != 0) // end is odd - skip it
{
end--;
continue;
}
int temp = input[start];
input[start] = input[end];
input[end] = temp;
start++;
end--;
}
Console.WriteLine(string.Join(",", input));
}
u can use the simple concept of partitioning.take two pointer one start from front one from end then start moving 1st ponter from left till u wont get the odd no do same for other pointer and check for even.if 1st pointer doesnot overpass the second pointer then then swap other wise u reach to the solution.
public static void main(String[] args)
{
int arr[]=new int[20];
Scanner scn=new Scanner(System.in);
System.out.println("enter elements in array");
for(int i=0;i<20;i++)
{
arr[i]=scn.nextInt();
}
for(int i=0;i<20;i++)
{
if(arr[i]%2==0)
{
break;
}
else
{
for(int j=i+1;j<20;j++)
{
if(arr[j]%2==0)
{
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
break;
}
}
}
}
for(int i=0;i<20;i++)
{
System.out.print(arr[i]+",");
}
}
public class SwipeEvenOdd {
private int a[] = {2,3,2,3,2,3};
public void reArrange(){
int i = 0, j = a.length-1;
while(i<=j){
if(a[i] % 2 == 0 && a[j] % 2 !=0){
i++;
j--;
}else{
exchange(i,j);
i++;
j--;
}
}
}
private void exchange(int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public void display(){
for(int i=0;i<a.length-1;i++){
System.out.println(a[i]);
}
}
public static void main(String[] args) {
SwipeEvenOdd obj = new SwipeEvenOdd();
System.out.println("Before reArrange");
obj.display();
System.out.println("After reArrange");
obj.reArrange();
obj.display();
}
}
def OddEven(vec, start, end):
if start == end:
return vec
else:
if vec[start]%2 == 0:
start += 1
else:
if vec[end]%2 == 0:
vec[start], vec[end] = vec[end], vec[start]
start += 1
end -= 1
else:
end = end-1
return OddEven(vec, start, end)
import numpy as np
vec = np.random.randint(1, 10, 10)
print vec
print OddEven(vec,0, len(vec)-1)
def OddEven(vec, start, end):
if start == end:
return vec
else:
if vec[start]%2 == 0:
start += 1
else:
if vec[end]%2 == 0:
vec[start], vec[end] = vec[end], vec[start]
start += 1
end -= 1
else:
end = end-1
return OddEven(vec, start, end)
import numpy as np
vec = np.random.randint(1, 10, 10)
print vec
print OddEven(vec,0, len(vec)-1)
Partition the given array into all even numbers followed by odd numbers.
void even_odd_partition(int A[], int i, int j) {
while (i < j) {
if (A[i] % 2 != 0) {
while (i < j && A[j] % 2 != 0)
--j;
if (i < j)
swap(A, i, j);
} else if (A[i] % 2 == 0) {
while (i < j && A[j] % 2 == 0)
++i;
if (i < j)
swap(A, i, j);
}
}
}
```def Bubble(a):
# Bubbles the even number to the right end of the array
# Time : O(N^2)
# Space : O(1)
for i in range(0,len(a)):
for j in range(0,len(a)-i-1):
if a[j] % 2 == 0:
a[j],a[len(a)-j-1] = a[len(a)-j-1],a[j]
return a
Bubble([2,4,6,8,10,1,3,5,7,9])```
# [9, 7, 5, 3, 1, 10, 8, 6, 4, 2]
Keep a pointer next to the last even number found and traverse through the array. Keep swapping the elements whenever an even number is found.
- Chris June 05, 2013