Microsoft Interview Question for Software Engineer / Developers


Country: United States




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

radix sort won't work...

here we need to decide if we want to swap numbers or not

int numdigit(int ip)
{
	int recnt = 0;
	while(ip > 0)
	{
		recnt++;
		ip /=10;
	}
	return recnt;
}

bool isSwapNeeded(int i,int j)
{
	int iposnum = i*pow(10,numdigit(j))+j;
	int jposnum = j*pow(10,numdigit(i))+i;

	return iposnum < jposnum;
}

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

could you explain/give your logic instead?

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

you can even use simple bubble sorting and swap two elements if by their exchange can produce a bugger number.

simple code follows:

String[]s = new String[n]; // take input

for (int i = 0 ; i < n;i++)
s[i]= in.next();


/** simple bubble sort **/

for (int i = 0 ;i < n ; i++)
for (int j = i+1;j<n;j++) {


String p=s[j]+s[i];

if ( p.compareTo(s[i]+s[j])>0)
{

String t = s[i];
s[i]=s[j];
s[j]=t;
}
}

/** print largest number *******/

for (int i = 0;i<n;i++)
System.out.print(s[i]);
System.out.println("");

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

Here is the logic:

Basically, sorting means arrangement of number. To do so we need to swap numbers based on some condition...
|Below is the logic of that condition...

we have 2 numbers lets say
94 and 9
calculate number of digits. which are 2 and 1 respectively.
then
inumber = 9*(10^2)+94;
jnumber = 94*(10^1)+9;

compare above numbers and then make decision of swapping....

I hope it helps....

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

ANONYMOUS ....awsome aproach yr....good one

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

I dont think approach suggested by ANONYMOUS would work as here we cant break integers as in 19 as 1 and 9, make 91 out of it. 19 would appear in final output as 19 only.

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

It will work. What he meant was :
it you have number 'xy' and number 'z' then create two number out of them
A = xyz
B = zxy

now compare A and B , and perform 'swap' based on the comparison.

- ABCD October 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

It is just an simple sorting question with a little twist by changing the elementary compare operator so I don't think there is one answer to this problem. Any algorithm would work but O(n log n) type algorithms like mergesort and quicksort should be a good answer. Any comparison based sorting algorithms would do. Here I have implemented both in java for random arrays. Have a look those interested but there is absolutely no change in these basic algorithms except for the change in compare operator:

import java.util.Arrays;
import java.util.Random;

public class AnyClass 
{

	private final static int MAX_SIZE = 10	;
	private final static int MAX = 20;

	public static void mergeSort(int a[])
	{
		if(a.length <= 1)
			return;
		int first[] = new int[a.length / 2];
		int second[] = new int[a.length - first.length];
		for(int x = 0; x < first.length; x++)
			first[x] = a[x];
		for(int x = first.length, y = 0; x < a.length; x++, y++)
			second[y] = a[x];
		//Split the array again
		mergeSort(first);
		mergeSort(second);

		merge(first, second, a);
	}

	private static int[] merge(int first[], int second[], int[] a)
	{
		int x = 0;
		int y = 0;
		int z = 0;
		
		while(x < first.length && y < second.length){
			if(compareInt(first[x],second[y])){
				a[z] = first[x];
				x++;
			}
			else{
				a[z] = second[y];
				y++;
			}
			z++;
		}
		//copy remaining elements to the tail of a[];
		for(int i = x; i < first.length; i++){
			a[z] = first[i];
			z++;
		}
		
		for(int i = y; i < second.length; i++){
			a[z] = second[i];
			z++;
		}
		return a;
	}
	
	public static boolean compareInt(int x, int y){
	 return (Integer.parseInt(Integer.toString(x)+Integer.toString(y))>
		Integer.parseInt(Integer.toString(y)+Integer.toString(x)));	
	}

    public static void quickSort(int[] a, int p, int r)
    {
        if(p<r)
        {
            int q=partition(a,p,r);
            quickSort(a,p,q);
            quickSort(a,q+1,r);
        }
    }

    private static int partition(int[] a, int p, int r) {

        int x = a[p];
        int i = p-1 ;
        int j = r+1 ;

        while (true) {
            i++;
            while ( i< r && compareInt(x,a[i]))
                i++;
            j--;
            while (j>p && compareInt(x,a[j]))
                j--;

            if (i < j)
                swap(a, i, j);
            else
                return j;
        }
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
	
	public static void main(String args[]){
		Random generator = new Random();
		int[] numbers = new int[generator.nextInt(MAX_SIZE)];
		for (int i = 0; i < numbers.length; i++) {
			numbers[i] = generator.nextInt(MAX);
		}
		//int[] numbers = {4, 94, 9, 14, 1};
		System.out.println("Unsorted Array:"+Arrays.toString(numbers));
		mergeSort(numbers);
		System.out.println("Sorted Array via Mergesort:"+Arrays.toString(numbers));

		for (int i = 0; i < numbers.length; i++) {
			numbers[i] = generator.nextInt(MAX);
		}

		System.out.println("Unsorted Array:"+Arrays.toString(numbers));
		quickSort(numbers, 0, numbers.length - 1);
		System.out.println("Sorted Array via QuickSort:"+Arrays.toString(numbers));

	}
}

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

hi simply compare the string is not working.
For example for 94,9 and 4, in the result 9 comes before 94 and 4 comes after 94, while they are both smaller than 94 if you treat them as strings.

- maillist.danielyin October 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

#include<stdio.h>
#include<stdlib.h>

int greater(int k,int l)
{

    int temp=0;
    int templ;
    int tempk;
    int kl;
    int lk;
    if(k==-100000)
        return(0);
    if(l==-100000)
        return(1);
    temp=10;
    templ=l;
    tempk=k;
    while(templ/10!=0)
    {
        templ=templ%10;
        temp=temp*10;
    }
    kl=k*temp+l;
    temp=10;
    while(tempk/10!=0)
    {
        tempk=tempk%10;
        temp=temp*10;
    }
    lk=l*temp+k;
    if(kl>lk)
        return(1);
    else
        return(0);
}
Modified_Merge(int A[],int p,int r,int q)
{
    int *l1;
    int *l2;
    int n1;
    int n2;
    int i;
    int j;
    int k;
    n1=r-p+1;
    n2=q-r;
    l1=(int *)malloc((n1+1)*sizeof(int));
    l2=(int *)malloc((n2+1)*sizeof(int));
    for(i=0;i<n1;i++)
        l1[i]=A[p+i];
    for(j=0;j<n2;j++)
        l2[j]=A[r+1+j];
    l1[n1]=-100000;
    l2[n2]=-100000;
    i=0;
    j=0;
    k=p;
    while(i!=n1||j!=n2)
    {
        if(greater(l1[i],l2[j]))
        {
            A[k]=l1[i];
            i++;
            k++;
        }
        else
        {
            A[k]=l2[j];
            j++;
            k++;
        }
    }
}

Modified_Merge_Sort(int A[],int p,int q)
{
    int r;
    if(p<q)
    {
       // printf("yessss%d,%d\n",p,q);
        r=(p+q)/2;
        Modified_Merge_Sort(A,p,r);
        Modified_Merge_Sort(A,r+1,q);
        Modified_Merge(A,p,r,q);
    }
    else
        return;
}
int main()
{
    int n;
    int *A;
    int i=0;
    printf("Inter the number of Integer:\n");
    scanf("%d",&n);
    A=(int *)malloc(n*sizeof(int));
    while(i<n)
    {
        scanf("%d",A+i);
        i++;
    }
    Modified_Merge_Sort(A,0,n-1);
    for(i=0;i<n;i++)
        printf("%d,",A[i]);
}

- ivikas007 October 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Most of the codes given here are joining the two nos. and comparing them and then taking decisions which no wud come first. The logic is fine but we'll have problems in handling big nos. if its a 5-6 digit no. how wud u keep a 12 digit no in int variable ( it cud b bigger than 12 digits also)

one approach i think is to reverse the nos. nd then sort them acc to the remainder they give wen divided by 10 ( we hav to do it recursively if last digit is same )
after sorting with this rule ... reverse the nos again back.

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

Yes, you may have a valid point but it won't happen if you override the compare operator for comparing two integers by joining them as string and reconverting to long number. You can check Long.MAX_VALUE is bigger two Intger.MAX_VALUE joined side by side. After all you just need a boolean value in the end.

However, if you are still not satisfied, there is a very simple technique to override compare operator without getting into problems like you mentioned. Just compare the integers as strings, character by character. With this logic any string that begins with a higher order number gets preference. For. eg.
'9'> '81' (because second string begins with 8)or '76'>'597' (because second string begins with 5). I don't think this is something very difficult to implement.

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

radix sort

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

you can even use simple bubble sort and swap two elements if their exchange can produce a bigger number.

simple code follows:

String[]s = new String[n]; // take input

for (int i = 0 ; i < n;i++)
s[i]= in.next();


/** simple bubble sort **/

for (int i = 0 ;i < n ; i++)
for (int j = i+1;j<n;j++) {


String p=s[j]+s[i];

if ( p.compareTo(s[i]+s[j])>0)
{

String t = s[i];
s[i]=s[j];
s[j]=t;
}
}

/** print largest number *******/

for (int i = 0;i<n;i++)
System.out.print(s[i]);
System.out.println("");

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

logic should be to arrang i+2 location aray elemt in decreasin order ...where
i=0;
.......
i++

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

import java.util.*;

public class IntegerSort {


public static void main(String args[]) {

IntegerSort is = new IntegerSort();
is.printSort();

}
public void printSort(){
Integer[] input = new Integer[]{4,94,9,14};

Arrays.sort(input, new MyIntegerComparator());

System.out.println(Arrays.toString(input));

}



public class MyIntegerComparator implements Comparator {

public int compare(Object io1, Object io2){
Integer i1 = (Integer)io1;
Integer i2 = (Integer)io2;
if(i1*Math.pow(10,intLength(i2))+i2 > i2*Math.pow(10,intLength(i1)) + i1){
	return -1;
}else if(i1*Math.pow(10,intLength(i2))+i2 == i2*Math.pow(10,intLength(i1)) + i1) {
	return 0;
}else{
	return 1;
}
	}
}

public int intLength(int i){

return  1 + (int)Math.floor(Math.log10(i));


}


}

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

How about using permutation?

package algos.pq;


public class Permutation {

	private static int greatestNumber;

	public static void main(String[] args) {

		int a[] = { 4, 94, 1, 14, 9 };
		int[] expectedResult = { 9, 94, 4, 14, 1 };

		permutation(a, a.length);

		if (greatestNumber == getAsNumber(expectedResult)) {
			System.out.println("Goal");
			System.out.println(greatestNumber);
		} else {
			System.out.println("fail");
			System.out.println(greatestNumber);
		}

	}

	private static void permutation(int[] a, int n) {
		if (n == 1) {
			int maybeTheNumber = getAsNumber(a);
			if (greatestNumber < maybeTheNumber)
				greatestNumber = maybeTheNumber;
			return;
		}

		for (int i = 0; i < n; i++) {
			swap(a, i, n - 1);
			permutation(a, n - 1);
			swap(a, i, n - 1);
		}

	}

	private static void swap(int[] a, int i, int j) {
		int c;
		c = a[i];
		a[i] = a[j];
		a[j] = c;

	}

	//quick and dirty
	private static int getAsNumber(int[] expectedResult) {
		StringBuilder builder = new StringBuilder();

		for (int i = 0; i < expectedResult.length; i++) {
			builder.append(expectedResult[i]);
		}
		return Integer.parseInt(builder.toString());
	}

}

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

import java.util.Arrays;
import java.util.Comparator;

public class TestMe {
    static class LexComparator implements Comparator<Integer> {
        public static final LexComparator INSTANCE = new LexComparator();

        private LexComparator() {
        };

        @Override
        public int compare(Integer o1, Integer o2) {
            return String.valueOf(o1).compareTo(String.valueOf(o2));
        }
    }

    // Is a prefix of b?
    static boolean isPrefix(int a, int b) {
        if (a == b) {
            return true;
        }
        while (b != 0 && a != b) {
            b /= 10;
        }
        return (a == b);
    }

    static boolean higherLexPart(int b, int a) {
        if (a == b) {
            return true;
        }
        int b_ = b;
        int c = 1;
        while (a != b_) {
            b_ /= 10;
            c *= 10;
        }
        c = b % c;
        return LexComparator.INSTANCE.compare(a, c) < 0;
    }

    static String maxCombo(Integer nos[]) {
        StringBuilder sb = new StringBuilder();

        Arrays.sort(nos, LexComparator.INSTANCE);

        int start, end;
        for (int i = nos.length - 1; i >= 0; --i) {
            start = end = i;
            while (start > 0 && isPrefix(nos[start - 1], nos[start])) {
                --start;
            }
            i = start;
            StringBuilder sb1 = new StringBuilder();
            sb1.append(nos[start++]);
            while (start <= end) {
                if (higherLexPart(nos[start], nos[start - 1])) {
                    sb1.insert(0, nos[start]);
                } else {
                    sb1.append(nos[start]);
                }
                ++start;
            }
            sb.append(sb1);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Integer nos[] = new Integer[] { 7, 78, 788, 7886 };
        System.out.println(maxCombo(nos));
        nos = new Integer[] { 7, 8, 89, 899, 8999, 8999 };
        System.out.println(maxCombo(nos));
        nos = new Integer[] { 123, 123, 123, 5456, 45236, 634534, 34345 };
        System.out.println(maxCombo(nos));
    }
}

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

I think a custom comparator is enough:

def wsort(ls):
    def _wcompare(x, y):
        sx = list(str(x))
        sy = list(str(y))
        while True:
            hx = sx.pop(0)
            hy = sy.pop(0)
            if hx != hy:
                return int(hx) - int(hy)
            else:
                if not sx:
                    return 1
                elif not sy:
                    return -1
    print _wcompare(95, 9)
    return sorted(ls, cmp=_wcompare, reverse=True)

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

import java.util.Arrays;
import java.util.Comparator;


class LengthCom implements Comparator<Integer> {

	@Override
	public int compare(Integer o1, Integer o2) {
		
		String s1 = o1.toString();
		String s2 = o2.toString();
		int len = s1.length() - s2.length();
		
		
		if(len>0){
			
			s1 = s1.substring( s2.length());
		}
		if(len <0 ){
			s2 =  s2.substring( s1.length());
			
		}
		
		int f1 = Integer.parseInt(s1);
		int f2 = Integer.parseInt(s2);
		
		if(f1>f2)
			return -1;
		if(f1<f2)
			return 1;
					
		return 0;
	}
	

	
}
public class NumberSorting {

	

	
	
	
	public static void main(String st[]){
		
		int a[] ={9,94,4,14,1};
		
		Integer []aInt = new Integer[a.length];
		int i = 0;
		while (a.length >i){
			aInt[i] = a[i];
			i++;
		}
		LengthCom com = new LengthCom();
		
		Arrays.sort(aInt,com);
		for(Integer ad : aInt)
				System.out.print(ad+", ");
	}

	
	
}

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

Its just sorting integers in lexicographical decreasing order. Isn't it?

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

lexicographic wont work..
take 94 and 9 ( 94>9 but 994 > 949)
15 and 1 (15>1 and 151 > 115)

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

public class IntComparator implements Comparator<Integer>{

	@Override
	public int compare(Integer arg0, Integer arg1) {
		if(Integer.parseInt(arg0+""+arg1)>Integer.parseInt(arg1+""+arg0))
			return 1;
		else if(Integer.parseInt(arg0+""+arg1)<Integer.parseInt(arg1+""+arg0))
			return -1;
		return 0;
		
	}

}

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

Here What I am thinking,

compare digit from left to right


it may not be the best approach but I would love to hear whats wrong in this algo.

I have implement my logic using bubble sort but bubble sort can be replaced with another efficient algos.

int a[8]={19,23,45,939,2,34,512,213};
    int len = sizeof(a)/sizeof(a[0]);
     jugardSort(a,len);

Code:

int numofdigits(int n){
    if (n == 0) return 1;
    int l;
    for (l = 0 ; n > 0 ;++l)
        n /= 10;
    return l;
}
int getDigit(int from, int index){
    return (int(from / pow(10.0, index))) % 10;
}
int isNeedSwap(int a,int b){
    int an         = numofdigits(a);
    int bn         = numofdigits(b);
    int max        = an < bn ? an: bn;
    int digitIndex = 1;
    do{
        int ad = getDigit(a,an-digitIndex);
        int bd = getDigit(b,bn-digitIndex);
        if(ad < bd){
            return 1;
        }
        else if(ad >  bd){
            return 0;
        }
        digitIndex++;
    }while(digitIndex <= max);
    return 0;
}
void jugardSort(int array[],int n){
     //Bubble Sort, You can use any sorting algo here
     for(int x=0; x<n; x++){
       for(int y=0; y<n-1; y++){
			int needSwap = isNeedSwap(array[y],array[y+1]);
            if(needSwap){
                int temp   = array[y+1];
				array[y+1] = array[y];
				array[y]   = temp;
			}
		}
	}
    for(int i=0;i<n;i++){
        printf(" %d ",array[i]);
    }
}

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

class MyComparater {
public int compareTo(int i, int j) {
String a = i.toString();
String b = j.toString();
if (a.length() > b.length()) {
String c = a;
a = b;
b = c;
}

for (int i=0; i<b.length(); i++) {
int mod_i = i % a.length();
if (a.charAt(mod_i) > b.charAt(i)) {
return 1;
}
if (a.charAt(mod_i) < b.charAt(i)) {
return -1;
}
}

return 0;
}
}

Arrays.sort(data_array, new MyComparator());

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

public static void main(String[] args) {
        // TODO code application logic here
        Integer a[] = { 4, 94, 9, 14, 1};
        Comparator<Integer> NewComparator = new MaxNumberOfTwoStringsComparator();
        
        Arrays.sort(a, NewComparator);
        
        for(int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    public class MaxNumberOfTwoStringsComparator implements Comparator{

    @Override
    public int compare(Object o1, Object o2) {
        String s1 = o1.toString();
        String s2 = o2.toString();
        int a = Integer.parseInt(s1);
        int b = Integer.parseInt(s2);
        
        int vala = a * (int)Math.pow(10, s2.length()) + b;
        int valb = b * (int)Math.pow(10, s1.length()) + a;
        
        return vala < valb ? 1 : vala == valb? 0 : -1; 
    }
    
}

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

compare 1st digits in numbers and sort them,
if two numbers have same first digit,check the 2nd digit.
here for ab..a is first digit.
for two numbers ab,c compare a and c if c is bigger swap numbers
else for ab and ad compare b and d swap if b<d an so on.

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

similarly if ab,a check if b<c then swap

- sandeep October 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

This is exactly the kind of stupid question I hate to give candidates because there's a non-obvious "trick". The trick is, as previously demonstrated, to simply replace the "less" predicate of a std sort algorithm and sort concatenated strings instead of integers. The quoted time complexity is technically incorrect, however, since most library quick-sorts degenerate to selection sort for small n (usually <32) giving the average time complexity for the sort as O(n) swaps (look it up if you don't believe me!)

We can further optimize by noting that the the int<==>string conversions of the earlier algorithms are cheaper than the log/pow versions and we can sacrifice a little memory to avoid converting to/from strings more than once. Here is the algorithm in D, and note also that I used the chain operation which avoids actually concatenating the strings in the inline closure-predicate.

void joinedSort(int[] values)
{
    write(values);
    auto svalues = to!(string[])(values);

    bool predicate(string a, string b) { return cmp( chain(a, b), chain(b, a) ) > 0; }
    sort!(predicate)(svalues);

    copy(to!(int[])(svalues), values);
    writeln(" => ", values);
}

int main(string[] argv)
{
    joinedSort([ 4, 94, 9, 14, 1 ]);
    return 0;
}

- Eric Fleegal July 09, 2013 | Flag Reply


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