NVIDIA

www.nvidia.com
Engaged Employer

Interview

# how to find the second smallest number out of iven n

integers

0

quick sort

Interview Candidate on Jul 11, 2011
1

I think you wrong :) Where N is the number of the integers, quick sort's complexity is: o( (N)log(N) ) I will show you haw can you do it in o(N) You can do i by keeping 2 variables: smallest second_smallest smallest = second_smallest = fist number While (there are still numbers to iterate) { if (next_integer &lt; smallest) { second_smallest = smallest smallest = next_number; } }

The Dude on May 20, 2012
1

No, you need to also check for the second_smallest as well. For instance your code does not work for the sequence of "10,20,15".

Nima on Sep 13, 2012
0

You can do it in O(n); for(i=0 ; i<n; i++) { if(i == 0) { if(a[i] < a[i+1]) { small = a[i]; second_small = a[i+1]; } else { small = a[i+1]; second_small = a[i]; } } else { if(a[i]>second_small) continue; else { if(a[i]>small) second_small = a[i]; else { second_small = small; small = a[i]; } } } }

Pavan on Jul 27, 2015