Microsoft Interview Question for Software Engineer in Tests






Comment hidden because of low score. Click to expand.
3
of 3 vote

I just spent awhile on this, so I figured I'd post what worked for me.

1  2  3  4  5  6  7  8
 \/    \/    \/    \/
 1      3    5      7
   \  /        \  /
     1          5
        \   /
          1

1 is the smallest, it took n-1 = 7 comparisons. Now compare all the numbers which 1 was compared to (compare 2,3,5).

2  3   5
 \/   /
  2  /
   \/
   2

2 is the second smallest. It took lg(n)-1 = 2 comparisons.

To understand where the ceiling comes from, try this with n odd.

- Josh March 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n + LOGN - 2 is a hint itself.

think about: how many number does the MAX have to "kill" to win its laurel ? Think something else than n-1, something "log"

- geniusxsy February 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

a little type: MAX -> MIN

- geniusxsy February 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

typo

- geniusxsy February 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just n: scan all n elements, and keep update two variables: first smallest and second smallest.

- Anonymous February 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if you will compare each element to both smallest, and second smallest, you will get 2*n.

- Anonymous February 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Which is why you store 2 pointers, if x < smallest, then secondSmallest = smallest and smallest = x. This is an operation of n.

- Vince February 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you missed one situation where the new item is between the values you stored:

say you have
1st_smallest = 1, 2st_smallest = 100
and what if the new item is 50?

- yibo February 20, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm confused. If you initiate the smallest and secondSmallest to some value in the array, say A[1], then you would never have the issue where i was pointing at a number in between the values for smallest and secondSmallest. Maybe I am wrong but I feel like it would still work for all cases.

- Brian April 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Heapify.

- Anonymous February 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

right track but regular heapify costs more than n+logn in terms of number of comparisions

- geniusxsy February 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

first round divide into n/2 group; then divide n/2 winner into n/4 group, go on until only 1 winner left. The whole process has logn rounds, total comparsion is 2^(logn)-1; the final winner beat logn numbers, so the 2nd smallest is these logn guys, which need logn-1 comparisons to find. So the total comparison is n+logn-2.

- ilikedeal February 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the correct answer. The problem is from Cormen's book, Exercise 9.1-1.

- Anonymous March 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

use the heap sort.
1. create min-heap O(n), get the smallest element
2. adjust the heap, use O(logn), pick the 2nd smallest element

- Anonymous February 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

but creating a minheap would take O(nlgn) time.

- vimit.gupta February 20, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about using Fibonacci heaps whose inserts are O(1) and delete min is O(log(n)).

My idea:
1. Loop over n elements and maintain the smallest element. Insert all the elements except for the smallest one in fibonacci heap. O(n)
2. Extract min from the heap. O(log(n-1))
= n + log(n-1)

I cannot get n + log(n-2), any ideas ?

- narendra February 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

see here the number of comparison is given should be exactly n + log(--- but when you will create the min/max heap.. the number of comparison is more than n ..it is like 1.5 n ..but its order is O(n) ,...so heap sort will not be the right solution ...

- racseism February 28, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the complete operation for finding first smallest and second smallest can be done in O(n) time, here is the code:

smallest = arr[0];
t_smallest = arr[1];

for(int ii = 1; ii < arr.size(); ii++) {
if(arr[ii] < smallest) {
t_smallest = smallest;
smallest = arr[ii];
}
else if(t_smallest > arr[ii])
t_smallest = arr[ii];
}

Comment if this can fly?

Thanks!

- ZooZoo February 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it is still 2n. Because you do two comparision each round.

- Anonymous March 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it is still 2n. Because you do two comparision each round.

- Anonymous March 01, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't know about the -2, but n + log(n) is the time for making the heap, and one sift down with the last element...Then the second element would be at the top. Sift down heap creation takes O(n), but the proof is tricky. Some people here have said that its O(n log n), but that's if you just insert each element in turn (sift up). Actually, it seems like after heap creation, the second element would have to be at the top of one or the other subheap, so it seems like it should be n + 1 comparison (of the sub-heap heads).

- DT March 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use tournament method to find the second largest element in the list.

Compare the adjacent elements from the array and advance the winner to the next round.
As you compare the adjacent elements keep track of maximum Seen So far and the element that lost to the Maximum. Store that value in a separate array.

That will give you the list of all elements that lost to the Maximum element.
finding the max among this list will give you the sec largest.

- Harish March 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n + logn - 2 because , we need n-1 comparison to find max among n elements and we need logn-1 comparisons to find second max among logn elements.
adding it togather : n+logn-2.

- Harish March 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I do not get the question. This is what I have understood so far. We are given a heap and we have to find the second smallest element.
This is what I think the answer should be. Since this is a min heap.We can find the smallest element in O(1). Remove the smallest element and heapify. O(log n). Now remove the second smallest element O(1). So the total cost should be O(log )
What am I missing here ?

- abhimanipal May 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ harish write method...in first pass we ll find minimum that requires n-1 comparisons and we also store all those elements which won over their adjacent in comparison so that leaves us with log(n) numbers which again require log(n)-1 comparisons so total of n+logn(n)-2

- Anonymous September 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about the case that maximum is the first one?
All comparison is just confirm the current element is the largest. The array kept is just a meaning less n-1 element without any order info.

- Anonymous November 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ok. I understand.

It takes O(n-1) to build the min heap and get the largest element. Since we have the min heap, we can take another O(lgn-1) to get the second largest using the normal heap operation.

The space complexity is O(n).

- Anonymous November 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The smallest of n numbers can be found with n − 1 comparisons by conducting a
tournament as follows: Compare all the numbers in pairs. Only the smaller of each
pair could possibly be the smallest of all n, so the problem has been reduced to that
of Þnding the smallest of n/2 numbers. Compare those numbers in pairs, and so
on, until there’s just one number left, which is the answer.
To see that this algorithm does exactly n −1 comparisons, notice that each number
except the smallest loses exactly once. To show this more formally, draw a binary
tree of the comparisons the algorithm does. The n numbers are the leaves, and each
number that came out smaller in a comparison is the parent of the two numbers that
were compared. Each non-leaf node of the tree represents a comparison, and there
are n − 1 internal nodes in an n-leaf full binary tree (see Exercise (B.5-3)), so
exactly n − 1 comparisons are made.
In the search for the smallest number, the second smallest number must have come
out smallest in every comparison made with it until it was eventually compared
with the smallest. So the second smallest is among the elements that were compared
with the smallest during the tournament. To Þnd it, conduct another tournament
(as above) to Þnd the smallest of these numbers. At most lg n (the height
of the tree of comparisons) elements were compared with the smallest, so Þnding
the smallest of these takes lg n − 1 comparisons in the worst case.
The total number of comparisons made in the two tournaments was
n − 1 + lg n − 1 = n + lg n − 2
in the worst case.

Source: CLRS :)

- aravind646 November 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about only n comparisons?

A = [ ... ]
first_min, second_min = very very big number

i = 0
while i < len(A):
if A[i] < first_min:
second_min = first_min
first_min = A[i]
i+=1

print second_min

- system_matrix December 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

## My solution using divide and conquer ##

Divide step : keep dividing input array into two equal sub arrays until it's length is 1.

Conquer step :
For the base of length 1 : no comparision required to find smallest and second smallest elements
For the base case of length 2 : 1 comparision is required to find smallest and second smallest elements
For the all other cases of length > 2 : 2 comparisions are required to find smallest and second smallest elements

## Code :) ##

/**
*
* @author gajera
*/
public class SecondSmallest {

int comparisionCount;

public int findSecondSmallest(int input[]) {
int mins[] = this.smallestTwoElements(input, 0, input.length-1);
return mins[1];
}


// Returns array of length two where [0] is smallest element and [1] is second smallest element found
// in input[] array from "start" index to "end" index inclusive.
public int[] smallestTwoElements(int input[], int start, int end) {
// Base case of length 1 [No comparision]
if(start == end) {
int mins[] = {input[start], input[start]};
return mins;
}

// Base case of length 2 [1 comparision]
if(end-start == 1) {
int mins[] = new int[2];
if(input[start] <= input[end]) {
mins[0] = input[start];
mins[1] = input[end];
} else {
mins[0] = input[end];
mins[1] = input[start];
}
return mins;
}


int middleIndex = start + (end-start)/2;
int rightMins[] = this.smallestTwoElements(input, start, middleIndex);
int leftMins[] = this.smallestTwoElements(input, middleIndex+1, end);

// Actual saving of comparision happens in following step. It reduces 3 comparisions to 2 comparisions.
// From pair of two smallest elements, it determines <min1,min2>
int mins[] = new int[2];
if(rightMins[0] <= leftMins[0]) {
mins[0] = rightMins[0];
mins[1] = (rightMins[1] <= leftMins[0]) ? rightMins[1] : leftMins[0];
} else {
mins[0] = leftMins[0];
mins[1] = (leftMins[1] <= rightMins[0]) ? leftMins[1] : rightMins[0];
}

return mins;
}

}


## Analysis ##
There are total n/2 nodes at last level (base case of length 1) = n/2 * 0 comparisions
There are total n/2 nodes at all other levels (base case of length 2 and > 2) = n/2 * 2 comparisions


Total comparisions = 0 + n - 2 [-2 because we don't need 2 comparisions at root node]


Please comment :)

--Tushar

- Tushar March 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A working, tested, simple and recursive solution in Python:

def two_min(L, i,j):
    if j==i+1:
        return [L[i]]        
    k= (i+j)/2
    return sorted(two_min(L, i,k)+two_min(L, k,j))[:2]

Actually, only two comparisons are needed in the last line.
'sorted' (of at most 4 elements) will use a bit more, but nicely simplifies the code.

- q April 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

And two tests:

Small Test:

L = [0,2,3,55, 7,4, 0, -1]
print two_min(L, 0, len(L))

Big Test:

import random
for j in xrange(100):
    L = [random.randint(1,100000) for i in xrange(10)]
    if two_min(L, 0, len(L)) != sorted(L)[:2]:
        raise Exception('something is wrong!')

- q April 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This algorithm works in worst case logn+n-2 comaprisons

public static void MinAndSecondMin(int[] arr, ref int min, ref int min2)
        {

            if (arr.Length <= 2)
            {
                return;
            }
            if (arr[0] < arr[1])
            {
                min = arr[0];
                min2 = arr[1];
            }
            else
            {
                min = arr[1];
                min2 = arr[0];
            }
            for (int i = 2; i < arr.Length; ++i)
            {
               
                if (arr[i] < min)
                {
                    min2 = min;
                    min = arr[i];
                }
                else if (arr[i] < min2)
                    {
                        min2 = arr[i];
                        
                    }
            }
        }

- BVarghese October 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

considering all cases

static void Main(string[] args)
        {
            int[] arr = { -1,-1,-1, -1, -1, -1, -1, -1,-1,
                        -2,-22,34,56,1111,34,567};
            int secondMin = 0;            
            if (SecondMin(arr, ref secondMin, arr.Length))
            {
                Console.WriteLine(secondMin);
            }
            else Console.WriteLine(" no secondMinimum");
           

            Console.Read();
        }
public static Boolean SecondMin(int[] arr,ref int secondMin, int n)
        {
         
            int min = 0;
            try
            {
                if (n >= 2)
                {
                    if (arr[0] < arr[1])
                    {
                        min = arr[0];
                        secondMin = arr[1];
                    }
                    else if (arr[0] > arr[1])
                    {
                        min = arr[1];
                        secondMin = arr[0];
                    }
                    else 
                    {
                        min = arr[1];
                        secondMin = arr[0];
                        if (arr[0] == arr[1] && n == 2)
                        return false;
                    }
                }
                if (n > 2)
                {

                    int i = 2;
                    while (i < n)
                    {

                        if (arr[i] < min)
                        {
                            secondMin = min;
                            min = arr[i];
                        }
                        else if (arr[i] < secondMin || arr[i] > secondMin&&min==secondMin)
                        {
                            if (arr[i] != min)
                            secondMin = arr[i];
                        }
                        i++;
                    }
                }
            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.ToString());
            }
            if(min!=secondMin)
                return true;
            else  return false;
        }

}

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

public int secondSmallestElement(int[] arr) {

		int[] tempArr = Arrays.copyOf(arr, arr.length);
		List<Map<Integer, Integer>> winnerList = new ArrayList<>();
		while (tempArr.length > 1) {
			int[] nextLevel = new int[tempArr.length % 2==0 ? tempArr.length/2:tempArr.length/2+1];
			int index = 0;
			int min = tempArr.length % 2 == 0 ? (arr[0] < arr[1] ? arr[0]
					: arr[1]) : arr[0];
			Map<Integer, Integer> pairs = new HashMap<>();

			int i = tempArr.length % 2 == 0 ? 1 : 2;
			if (tempArr.length % 2 != 0) {
				nextLevel[index++] = tempArr[0];
			}

			for (; i < tempArr.length; i += 2) {
				if (tempArr[i - 1] < tempArr[i]) {
					pairs.put(tempArr[i - 1], tempArr[i + 1]);
					nextLevel[index++] = tempArr[i - 1];
				} else {
					pairs.put(tempArr[i], tempArr[i - 1]);
					nextLevel[index++] = tempArr[i];
				}

			}
			tempArr = nextLevel;
			winnerList.add(pairs);
		}
		int min = tempArr[0];

		int[] losersToMin = new int[winnerList.size()];
		int index = 0;
		for (Map<Integer, Integer> num : winnerList) {
			losersToMin[index++] = num.get(min);
		}

		int secMin = losersToMin[0];
		for (int i = 1; i < losersToMin.length; i++) {
			if (secMin > arr[i]) {
				secMin = arr[i];
			}
		}
		return secMin;

	}

- martin.mathew.2k11 January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This question makes me wonder if either
A) OP forgot to say something about the question
or
B) the employer was checking your sanity

For the price of making a heap, you might as well store the second smallest element pointer/value which makes this an n operation. I mean, if you want that runtime you can just do a worthless spin at the end for log(n)-2.

- Vince February 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

use the quick sort idea!!!
find the position of the pivot element....
using the partition alorithm...
if the position is higher than the 2nd position...then apply partition to the left partition of the array...else the right one

- dream February 18, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

your conception might be correct but it is hard to verify because you used inadequate or improper language which is hard to make out.

- Anonymous February 18, 2010 | 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