## Microsoft Interview Question for Software Engineer in Tests

• 0

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.``````

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"

Comment hidden because of low score. Click to expand.
0

a little type: MAX -> MIN

Comment hidden because of low score. Click to expand.
0

typo

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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.

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

Heapify.

Comment hidden because of low score. Click to expand.
0

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

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.

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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 ?

Comment hidden because of low score. Click to expand.
0

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 ...

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!

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

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

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

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

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).

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.

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.

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 ?

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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).

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 :)

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

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

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]

--Tushar

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.

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!')``````

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

}
}
}``````

Comment hidden because of low score. Click to expand.
0

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

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

}

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

}``````

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.

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

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.

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.

### 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.