Microsoft Interview Question for Software Engineer / Developers


Country: India




Comment hidden because of low score. Click to expand.
6
of 8 vote

#python code
s = [2,1, 3, 5, 7,6]

even_index = 0
odd_index = 1

while(len(s) > even_index and len(s) > odd_index):
    if s[even_index]%2 == 0:
        even_index += 2
    else:
        if(s[odd_index]%2 == 0):
            temp = s[even_index]
            s[even_index] = s[odd_index]
            s[odd_index] = temp
            even_index += 2
        odd_index += 2

print s

- bluesky October 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What will happen if overflow occurs?

- Anand October 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Sugarcane_farmer May 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

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] + ",");
		}
		
	}
}

- Anonymous October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}	
}
}

- Hitman October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Jason October 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

#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] << " ";
}

- mittalpradeep84 October 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You should test your code on a few more samples :) This would reveal an error in your logic: Always swapping the i-th with the (size-1)-th value does not solve the problem. Just try {1,3,5,2,4,6} to see why.

- croesnick February 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
                        }

                    }

                }

            }

        }
    }
}

- Dr.H October 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

}

- Chengyun Zuo October 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static void swap(int[] test,int o1,int o2){
int tmp=test[o1];
test[o1]=test[o2];
test[o2]=tmp;
}

- Chengyun Zuo October 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void evenOdd(int[] A)
        {
            int Ieven = 0;

            for (int i = 0; i < A.Length; i++)
            {
                if (A[i] % 2 == 0)
                {
                    if (i != Ieven)
                    {
                        int temp = A[Ieven];
                        A[Ieven] = A[i];
                        A[i] = temp;
                        i--;
                    }
                    Ieven += 2;

                    if (Ieven >= A.Length - 1)
                        break;
                }
            }

}

- Anonymous October 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void evenOdd(int[] A)
        {
            int Ieven = 0;

            for (int i = 0; i < A.Length; i++)
            {
                if (A[i] % 2 == 0)
                {
                    if (i != Ieven)
                    {
                        int temp = A[Ieven];
                        A[Ieven] = A[i];
                        A[i] = temp;
                        i--;
                    }
                    Ieven += 2;

                    if (Ieven >= A.Length - 1)
                        break;
                }
            }
        }

- Umut Koseali October 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
    }
}

- coder October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void rearrange(int ary[], int n){
int i = 0, j = 1;
while(i < n && j < n){
while(i < n && ary[i] % 2 == 0) i += 2;
while(j < n && ary[j] % 2 == 1) j += 2;
if(i < n && j < n)swap(ary[i], ary[j]);
}
}

- ych October 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- chandan.jc October 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);

}
}
}

- P.vamsikrishna February 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

how about using a temporary array. and iterate the original array, and put all elements in corresponding place in the temporary array?

- Anonymous October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What would be the size of the temporary array? It definitely has to be larger than the original original... What if all the elements in the original array are odd nos?

- Bonnie October 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great answer, but wrap in code tags next time.

- Ryan Latham October 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

check it

codes-to-problem.blogspot.in/2012/10/re-arrange-oddeven-to-oddeven-places.html

- niraj.nijju October 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
 }
}
}

- jk October 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think a small error correction would be MAX_SIZE different for odd finder and even finder loop....
for this array :

A{2,1,3,5,7,6}

It would be not get out of while loop !!!

- Anonymous October 02, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More