## Microsoft Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Written Test

public void FinMin(int[] array)

{

int minVal = array[0];

int cnt = 0;

for(int i=1; i<array.length; i++)

{

if(array[i] < min)

{

min = array[i];

cnt++;

}

}

Console.WriteLine("Min Value: {0}, number of assignments: {1}", minVal, cnt);

}

I would assume that this is the solution they get most often, is there a better way? if we were first to sort the array via mergeSort, would we get a better efficiency?

The simplest(yet efficient) solution for the above problem would be the one that most guys are posting here :-

int min(int nArray[], int nLength)

//

int nMin <- infinite

for int i <- 0 to nLength - 1

do

- if nArray[i] < nMin

then

- - nMin <- nArray[i]

return nMin

Time Complexity :- O(n)

Assignment operations :-

Worst case :- n, where n is the length of array (Array sorted in decreasing order)

Best case :- 1, Only for the first time (Array sorted in increasing order)

```
#include<stdio.h>
int main()
{
int a[20],small,n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
small=a[0];
for(i=1;i<n;i++)
{
if(a[i]<small)
{
small=a[i];
}
}
printf("smallest=%d",small);
}
as the array is unsorted,so we have to go for linear search
worst case=n assignments within the loop
best case=1 assignment within the loop
```

Correct me if I am wrong . What if we try to develop an algorithm similar to quick sort ?

- Srikandh October 11, 20141. Set two pointers , one at index(0) as i and other at index(n) as j.

2. If a(i) > a(j) , Increment i else decrement j

3. Stop when i=j

4. No assignments needed right ?