Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
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).
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).
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.
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.
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;
}
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.
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();
}
}
}
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;
}
- Anonymous October 02, 2014