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[0];
    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;
}

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

public int findMin(int[] inputArr) {
    int min = inputArr[0];
    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;
}

- FireShock October 29, 2014 | Flag
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).

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

Very good analysis!

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

We have (from your formula):

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

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

If f(n) is average then how f(k) = f(k-1) +1 . AFAIK averages don't work like that.
Please elaborate.
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.

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

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

- sairamch04 October 21, 2014 | Flag
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.

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

You mean assignment, not comparison.

Good approach, though. +1.

- Subbu. October 02, 2014 | Flag
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;
}

- ramlinuxprasad October 01, 2014 | Flag Reply
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.

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

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

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

Console.ReadLine();
}
}
}

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

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

- Sonia C October 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- roni October 02, 2014 | Flag
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[0];
   return 0;
}

- Vova October 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python:

def findMin(arr):
	m = arr[0]
	for i in arr:
		if i < m:
			m = i

CoffeeScript:

findMin = (arr) ->
    m = arr[0]
    for i in arr
        if i < m then m = i
    m

- Daniel November 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, the first one is incorrect:

def findMin(arr):
	m = arr[0]
	for i in arr:
		if i < m:
			m = i
	return m

- Daniel November 15, 2014 | 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