NVIDIA Interview Question: how to find the second smalle... | Glassdoor

## Interview Question

Verification Engineer 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 &quot;10,20,15&quot;.

Nima on Sep 13, 2012
0

You can do it in O(n);
for(i=0 ; isecond_small)
continue;
else
{
if(a[i]&gt;small)
second_small = a[i];
else
{
second_small = small;
small = a[i];
}
}
}
}

Pavan on Jul 27, 2015
0

Quick select

A on Jun 29, 2016