Microsoft Interview Question
Software Engineer / DevelopersCountry: India
C++ code:
bool ensure_all_even_odd(char arr[], int n)
{
if(n==1 && arr[n-1]%2 == 0)
return true;
else
return false;
int even=0;
int odd=1;
while(even<n && odd<n)
{
while(even<n && arr[even]%2 == 0)
{
even+=2;
}
while(odd<n && arr[odd]%2 == 1)
{
odd+=2;
}
if(even < n && odd <n)
{
SWAP(arr[even], arr[odd]);
}
}
return true;
}
public class OddEvenRearranger {
public static void main(String[] args) {
int A[] = new int[] { 2, 1, 3, 5, 7, 6 };
int B[] = new int[A.length];
int evenIndex = 0;
int oddIndex = 1;
for (int i = 0; i < A.length; i++) {
if (A[i] % 2 == 0) { // even
if (evenIndex < A.length) {
B[evenIndex] = A[i];
evenIndex += 2;
} else { // overflow for even, write at odd places, there's no escape!
B[oddIndex] = A[i];
oddIndex += 2;
}
} else // odd
if (oddIndex < A.length) {
B[oddIndex] = A[i];
oddIndex += 2;
} else { // overflow for odd, write at even places, , there's no escape!
B[evenIndex] = A[i];
evenIndex += 2;
}
}
for (int i = 0; i < B.length; i++) {
System.out.print(B[i] + ",");
}
}
}
void Rearrange(vector<int>& vec)
{
int oddCount = 0;
int evenCount = 0;
for(int i=0;i<vec.size();i++)
{
if(vec[i]%2 == 0) evenCount++;
else oddCount++;
}
if(oddCount >= evenCount)
{
int oddPtr = 1;
int P = 0;
while(oddPtr < vec.size() && vec[oddPtr]%2 == 1)
{
oddPtr+=2;
}
while(P<vec.size() && oddPtr < vec.size())
{
if(ar[P]%2 == 1)
{
swap(ar[P],ar[oddPtr]);
oddPtr+=2;
}
P+=2;
}
}
else
{
int evenPtr = 0;
int P = 1;
while(evenPtr < vec.size() && vec[evenPtr]%2 == 0)
{
evenPtr+=2;
}
while(P<vec.size() && evenPtr < vec.size())
{
if(ar[P]%2 == 0)
{
swap(ar[P],ar[evenPtr]);
evenPtr+=2;
}
P+=2;
}
}
}
#include <iostream>
#include <queue>
#include <cassert>
inline void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
void rearrange(int *a, int size) {
std::queue<int> eveninoddloc;
std::queue<int> oddinevenloc;
// check for validity of the array
for (int i = 0; i < size; ++i) {
if ((a[i] - i) % 2 != 0) {
if (a[i] % 2 == 0) {
if (!oddinevenloc.empty()) {
swap(a[i], a[oddinevenloc.front()]);
oddinevenloc.pop();
}
else {
eveninoddloc.push(i);
}
}
else {
if (!eveninoddloc.empty()) {
swap(a[i], a[eveninoddloc.front()]);
eveninoddloc.pop();
}
else
oddinevenloc.push(i);
}
}
}
assert(eveninoddloc.empty() || oddinevenloc.empty());
}
void printArray(const int *a, const int size) {
for (int i = 0; i < size; i++) {
std::cout << a[i] << ",";
}
std::cout << std::endl;
}
int main(void) {
int a[6] = {2, 1, 3, 5, 7 ,6};
std::cout << "original array: " << std::endl;
printArray(a, 6);
rearrange(a, 6);
std::cout << "swapped array: " << std::endl;
printArray(a, 6);
return 0;
}
#include<stdafx.h>
#include<iostream>
using namespace std;
int main()
{
const int size = 10;
int a[size] = {1,0,3,2,5,4,7,6,9,8};
for(int i =0; i<size;i++)
{
if((i%2) != 0)
{
if((a[i]%2) == 0)
{
int temp = a[i];
a[i] = a[size-1];
a[size-1] =temp;
}
}
else
{
if((a[i]%2) != 0)
{
int temp = a[i];
a[i] = a[size-1];
a[size-1] =temp;
}
}
}
for(int i =0; i<size;i++)
cout << a[i] << " ";
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LetUsTry
{
class Program
{
static void Main(string[] args)
{
//int[] arr = { 2, 1, 3, 5, 7, 6,8,4 };
//int[] arr = { 2, 1, 3, 5, 7, 6 };
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
Shuffle(arr);
Console.WriteLine(string.Join(",", arr));
Console.Read();
}
private static void Shuffle(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
if (i%2 != arr[i]%2) // that mean they don't match and we need to swap
{
int k = i;
//this is o(k) total algorithm will be o(n+k) ~ o(n)
while (k < arr.Length - 1)
{
if (i % 2 == 0) //even
{
// we need to swap with even number
if ((k < arr.Length - 1) && (arr[k + 1] % 2 != 0))
{
k++;
continue;
}
else k++;
}
//odd
else
{
// we need to swap with odd number
if ((k < arr.Length - 1) && (arr[k + 1] % 2 == 0))
{
k++;
continue;
}
else k++;
}
if ((k <= arr.Length - 1) && (k != i))
{
// we found a number to swap
// let us swap it in one line of code ;)
arr[k] = (arr[i] + arr[k]) - (arr[i] = arr[k]);
break;
}
else
{
break;
}
}
}
}
}
}
}
public static void SortByOddEvenWay(int [] test){
if(test==null){
return;
}
if(test.length==1){
return;
}
int evenIndex=0;
int oddIndex=1;
int endIndex=test.length-1;
while(evenIndex<test.length&&oddIndex<test.length){
if(test[endIndex]%2==0){
swap(test,endIndex,evenIndex);
evenIndex+=2;
}
else{
swap(test,endIndex,oddIndex);
oddIndex+=2;
}
}
}
void arrangeNumbers(int arr[],int size){
for(int i =0; i<size;i++){
if((i%2) != 0)
{
if(!(arr[i]%2))
{
int temp = arr[i];
arr[i] = arr[size-1];
arr[size-1] = temp;
}
}
else
{
if(arr[i]%2)
{
int temp = arr[i];
arr[i] = arr[size-1];
arr[size-1] = temp;
}
}
}
for(int i =0; i<size;i++){
printf(" %d", arr[i]);
}
}
Algorithm:
1) Initialize all the output array values to -1.
2) Find even_count and odd_count
2) If (odd_count > even_count)
First fill up even numbers in even places by traversing input array
Then traverse the input array from behind, and fill up the output array from behind, wherever you see a -1, for all odd nos in the input array.
Else if(odd_count < even_count)
Similar to the above step.
Else //If the counts are same
Traverse from front and fill up the output array //Trivial case
import java.util.*;
import java.util.Map.Entry;
public class doprogram {
public static void main(String args[]) {
int a[]={2,1,3,4};
for (int i = 0; i < a.length; i++) {
if(a[i]%2==0){
int temp=a[i/2];
a[i/2]=a[i];
a[i]=temp;
}
}
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}
}
}
how about using a temporary array. and iterate the original array, and put all elements in corresponding place in the temporary array?
void swap(int *a,int k,int i){
temp =a[k];
a[k] = a[i]
a[i] = temp;
}
void fun(int *a,int n){
int i=0,n = a.lengh(),oddCount=0;
while(i<n){
if(a[i++]%2)
oddCount++;
}
if(oddCount>(n-oddcount)){
//means we r not able to put odd element in odd position
i=0,k=n-1,flag = 1;
while(i<n){
if(flag){
if(a[i]%2 != 0){
while(k>i&&a[k--]%2);
if(k!=i){
swap(a,k,i);
}
else
break;
}
flag = 0
}
else{
if(a[i]%2 == 0)
if(k<n-1){
swap(a,++k,i);
}
else{
j=k;
while(j>i&&a[j--]%2 == 0);
if(j!=i){
swap(a,j,i);
}
else{
swap(a,i,i+1);
break;
}
}
flag = 1
}
i++;
}
}
else{
//means we r not able to put even element in even position
i=0,k=n-1,flag = 0;
while(i<n){
if(flag){
if(a[i]%2 == 0){
while(k>i&&!a[k--]%2);
if(k!=i){
swap(a,k,i);
}
else
break;
}
flag = 0
}
else{
if(a[i]%2 != 0)
if(k<n-1){
swap(a,++k,i);
}
else{
j=k;
while(j>i&&a[j--]%2 != 0);
if(j!=i){
swap(a,j,i);
}
else{
swap(a,i,i+1);
break;
}
}
flag = 1
}
i++;
}
}
}
time complexity o(n) space complexity o(1) ..
let me know if any thing is wrong
raunak
check it
codes-to-problem.blogspot.in/2012/10/re-arrange-oddeven-to-oddeven-places.html
static int MAX_COUNT = 5;
int a[MAX_COUNT] = { 2, 4, 3, 2, 5}
void ArrangeEvenAndOdds(int* a, size_t MAX_SIZE)
{
int oddFinder = 0;
int evenFinder = 1;
while (true)
{
while(oddFinder < MAX_SIZE && isEven(a[oddFinder]))
{
oddFinder+=2;
}
while(evenFinder < MAX_SIZE && isodd(a[evenFinder]))
{
evenFinder+=2;
}
if (oddFinder < MAX_SIZE && evenFinder < MAX_SIZE)
{
swap(&a[oddFinder], &a[evenFinder]);
}
else
{
break;
}
}
}
- bluesky October 03, 2012