@abhijit:quicksort take O(n^2)..We can use counting sort which is O(n).
On Sun, Feb 6, 2011 at 6:32 PM, coolfrog$
<[email protected]>wrote:
> @Decipher
> Microsoft is coming in over college.. can you Give some more question which
> are recently asked ...in MS test...
> @everone.. do share question of MS if some body has given the recently this
> Test..
>
> Algorithm:
> 1. maintain min_diff so far
> 2. maintain max_element so far
> complexity is O(n) , and space == O(1)
> #include<stdio.h>
> #include<conio.h>
> #include<stdlib.h>
> int minDiff(int arr[], int arr_size)
> {
> int min_diff = abs(arr[1] - arr[0]);
> int max_element = arr[0];
> int i;
> for(i = 1; i < arr_size; i++)
> {
> if(abs(arr[i] - max_element) < min_diff)
> min_diff = abs(arr[i] - max_element);
> if(arr[i] > max_element)
> max_element = arr[i];
> }
> return min_diff;
> }
>
>
> int main()
> {
> int arr[] = {5, 13, 7, 0, 10,20,1,15,4,19};
> printf("Maximum difference is %d", minDiff(arr, 10));
> getchar();
> return 0;
>
> }
>
> On Sun, Feb 6, 2011 at 3:37 PM, Abhijit K Rao <[email protected]>wrote:
>
>> How about , using a sorting algorithm like Quick sort and return diff of
>> last and the before last element.
>>
>> Best Regards
>> Abhijit
>>
>>
>>
>> On Sun, Feb 6, 2011 at 3:29 PM, Decipher <[email protected]> wrote:
>>
>>>
>>> Algorithm to find the two numbers whose difference is minimum among the
>>> set of numbers.
>>>
>>> For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19
>>>
>>> The algorithm should return min diff = 20-19 = 1.
>>>
>>> Constraint - Time Complexity O(N) & Space is not a constraint [upto
>>> O(3N)]
>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> *Divesh*
> (¨`·.·´¨) Always
> `·.¸(¨`·.·´¨ ) Keep
> (¨`·.·´¨)¸.·´Smiling!
> `·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
>
> of reasons 2Smile"
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Regards,
Kamakshi
[email protected]
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
