## Microsoft Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

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

``````public int findMin(int[] inputArr) {
int min = inputArr;
int cnt = 0;
for (int i = 1; i < inputArr.length; i++) {
if (min > inputArr[i]) {
min = inputArr[i];
cnt++;
}
}
console.writeLine("Number of increments: " + cnt);
return min;
}``````

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

``````public int findMin(int[] inputArr) {
int min = inputArr;
int cnt = 0;
for (int i = 1; i < inputArr.length; i++) {
if (min == int.MinValue) {
break;
}
if (min > inputArr[i]) {
min = inputArr[i];
cnt++;
}
}
console.writeLine("Number of increments: " + cnt);
return min;
}``````

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

The second half is indeed a very interesting question: How many assignment operations happen within the loop? The answer is approximately log(n), the natural log of the length of the unsorted array n.

Why? Let f(n) denote the expected (average) number of assignment operations (EAO) for size n. We will look at the relationship between f(n) and f(1), f(2), ..., f(n-1). For size n, the minimum integer can be located at position 1, 2, ..., n with equal probability 1/n. If the minimum integer is at location k, then there will be no assignment operation after k (k+1, k+2, ..., n). And the expected assignment operations is f(k-1) + 1 where 1 is the operation for the minimum integer.

With f(0) = 0, we have

f(n) = ((f(0)+1) + (f(1)+1) + ... + (f(n-1)+1))/n

The values of f(n) can be solved successively. Let g(n+1) = f(n).

g(n+1) = ((g(1)+1) + (g(2)+1) + ... + (g(n)+1))/n

I claim that it is approximately log(n). Without proving it, I will just justify it.

From wikipedia we have Stirling's formula:

log(n!) = n*log(n) - n + O(log(n))

Dropping off O(log(n)), dividing both sides by n and rearranging terms, we have

log(n) <> 1 + log(n!)/n = RHS(n) (<> means approximation)

RHS(n) = 1 + (log(1) + log(2) + ... + log(n))/n
RHS(n) = ((log(1) + 1) + (log(2)+1) + ... + (log(n)+1))/n

We have g(n+1) = RHS(n), the approximating formula. Hence f(n) is approximately log(n).

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

Very good analysis!

I just help to prove f(n) = O(log n), as following:

``f(n) = (n + f1 + f2 +...+ f(n-1))/n;``

Then (multiply both sides by n):

``````n.f(n) 	= n + f1 + f2 +...+ f(n-1);
= 1 + [n-1 + f1 + f2 +...+ f(n-2)] + f(n-1)
= 1 + (n-1).f(n-1) + f(n-1);
= 1 + n.f(n-1);``````

Hence (divide both side by n):

``````f(n) 	= f(n-1) + 1/n
= [ f(n-2) + 1/(n-1) ] + 1/n
= [ f(n-3) + 1/(n-2) ] + 1/(n-1) + 1/n
=...
= f(0) + 1/1 + 1/2 + 1/3 + ... + 1/n
= 0 + H(n)
= O(log n)``````

Where H(n) is the harmonic series, which is known to be O(log n);

Thus, f(n) = O(log n).

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

If f(n) is average then how f(k) = f(k-1) +1 . AFAIK averages don't work like that.
imo, if no. of comparison is g(k), then g(k) = k+1 ; then f(n) = 1/n(sum(g(k))) where k goes 0 to n-1.

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

Expected number of asignments for minimum element can be logn only when
u assume that that array size can be atmost n.
If the array is of size exactly n.
Then Expected number of comarisions will be (n+1)/2

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

The code to this interview is pretty straightforward. Just keep a record of the min value and compare it the next value you see until you reach the end of the list.

The hard part is to prove "how many compares". The easy way to solve it is to use indicator random variables.

Say X = random variables describing number of comparison
And Xi = indicator random variables, that i was the smallest item so far

So we know that X = sum(Xi) (by laws of probability)
By the definition of Indicator random variables we know that E(Xi) = Pr(ith element being the smallest).

Since we are trying to get the E(X) (where E= expectation) we put both together and we have
E(X) = E(sum(xi)) which is equal to E(X) = sum(E(xi)) // by linearity of expectations
So E(X) = sum(1/n) //by the definition of indicator random variables above, and becease the probability of finding the min in position n is 1/n.

And the sum(1/n) = ln n.

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

You mean assignment, not comparison.

Good approach, though. +1.

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

I am not sure what's the question? Was the person asking for complexity analysis on what's the worst case for assignment statements? If that's the case the worst case would be O(n) operations since if you are given an array sorted with a decremented array elements then your assignment operation will take place for each element. However if he's looking for average case that would be almost O(1) amortized over a large data set. I am writing the code in java.

``````public int findMin(int[] a)  {
int min = 0, cnt = 0;
for (int i = 0; i < a.length; i++) {
// number of comparisons would be the entire array elements: a.length
if (a[i] <= min) {
min = a[i];
cnt++;   // increments each time for assignment
}
}
return cnt;
}``````

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

it was a written round. so i don't know what they were expecting. There's a bug in your code though. for an array with integers all greater than zero, your program would still return the min as zero.

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

It should actually be min = a , cnt = 0;

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 ConsoleApplication1
{
class Program
{
public static int FindMin( ref int[] arrayInt )
{
int nMin = arrayInt;
int nCount = 0;

for (int i = 0; i < arrayInt.Length; i++)
{
if (nMin > arrayInt[i])
{
nMin = arrayInt[i];
nCount++;
}
}

Console.WriteLine("Number of increments: " + nCount);
return nMin;
}

static void Main(string[] args)
{
int[] arrayInt = new int;
Random r = new Random();

for (int i = 0; i < 10; i++)
{
arrayInt[i] = r.Next(1, 100);

}

int nMin = FindMin(ref arrayInt);
Console.WriteLine("Min Number: " + nMin);

}
}
}

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

Why not sort the array first and return the first element?

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

Sonia, that would be O(n log n) as opposed to O(n)

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

Hi mates. I suggest to find min element using heapify approach, the code below is the implementation, what about assignments, the count of assignments is O(n)

``````#include <iostream>

using namespace std;

void minHeap(int aArr[],int aRoot,int aSize)
{
int left = 2*aRoot;
int right = 2*aRoot + 1;

int lMin = aArr[aRoot];
if(left < aSize && aArr[lMin] > aArr[left]) lMin = left;
if(right < aSize && aArr[lMin] > aArr[right])lMin = right;

if(lMin != aRoot)
swap(aArr[aRoot],aArr[lMin]);
}

void Heapify(int aArr[],int aSize)
{
for(int i = aSize/2; i >= 0; --i)
minHeap(aArr,i,aSize) ;

}

int main()
{
int Arr[] = {3,7,9,7,4,15,8};
Heapify(Arr,sizeof(Arr)/sizeof(int));
cout << Arr;
return 0;
}``````

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

Python:

``````def findMin(arr):
m = arr
for i in arr:
if i < m:
m = i``````

CoffeeScript:

``````findMin = (arr) ->
m = arr
for i in arr
if i < m then m = i
m``````

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

Sorry, the first one is incorrect:

``````def findMin(arr):
m = arr
for i in arr:
if i < m:
m = i
return m``````

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.