Microsoft Interview Question
Software Engineer / DevelopersCountry: 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 ?