😏 keep them in suspense

Oh my gosh, so darn impressive!

```
public class Main
{
public static void main(String[] args) {
int[] numbers = {1,3,5,3,28,22,84,93,88,10};
int largest = Integer.MIN_VALUE;
int secondLargest = Integer.MIN_VALUE;
for (int num: numbers) {
if (num > largest) {
secondLargest = largest;
largest = num;
} else if (num > secondLargest) {
secondLargest = num;
}
}

System.out.println("Largest: " + largest + ", second: " + secondLargest);
}
}
```

@netikras What about generalising it to find the N-th largest / smallest number, and doing it without keeping a list of N numbers? Hint: it can be done in linear time 😉

@hitko scandalous 😧

Is this a Fang interview question for yet another role where you'll never need to write any algorithms?

1. Find the largest number by iteration.
2. Find the largest number less than said number by iteration.
There, second largest number without sorting.

@nibor finding some minimal or maximal value in a list is actually quite common. (Compared to other interview tasks, that is).
The instinct would probably tell you to sort it but it can be done quicker (linear complexity).
Most languages support some kind of functional style of doing it without the need of for loops and tracking the numbers in variables.

I like Swift the most:

let largest = numbers.max()
let secondLargest = numbers.filter{$0!=largest}.max()

@Lensflare @d4ng3r0u5 @nibor Finding the second largest number is trivial and not very useful. However, as I tried to hint in my first comment, the point is in finding the N-th largest or smallest number. Let's say you're trying to get a colour from user's logo for your app; there's 14936 different shades in the image, but the top 1% most represented shades probably belong to the background, so you're trying to take the 150th (14936 / 100 + 1) most represented shade from the list as your app colour. Or whatever else, maybe you're just trying to quickly find the percentiles from some data without importing a whole data-processing library...

@hitko Care to link the solution?

@hitko this is a bit tricky indeed.
I thought about it for a few minutes and I can’t come up with a linear time solution without sorting. And sorting takes at least n*log(n) if I remember correctly. So, not linear.
Now I’m curious for the solution :)

0. Create a variable N, which represents the Nth largest number you want to fetch from the list.

1. Create a counter called n

2. A temporary variable v to hold the nth largest number found so far

3. Iterate list, if current item is smaller than v, then v=current item.

4. If v was replaced in last step, increment n

5. Once n equals N, return v.

Done.

@Wisecrack that can’t be right.
It would return the number 2 asking for the 2nd largest number from the following list: [3,2,1,100,101,102]

Or it would return the number 1, if you initialize n with 0.

It should return 101 though.

@apan @Lensflare It's basically the same as quicksort, but you're only interested in one branch in each iteration, because you know the other branch doesn't contain the number you're interested in.

E.g. 3rd smallest number in [4,1,7,5,3,2,9,8]:
- use 4 as a pivot, split numbers into [1,3,2] and [7,5,9,8]; left part has size 3, so 3rd smallest number is in the left part
- use 1 as a pivot, split into [] and [3,2]; 3rd smallest number is in the right part; taking the right part, we need to remember offset = size of the left part + 1 = 0 + 1 = 1
- use 3 as a pivot, split into [2] and []; the size of the left part is 1 (+ offset from the previous step), so the 3rd smallest number is pivot, which is 3

This took 8 + 3 + 2 = 13 operations, or about O(2*n), as opposed to sorting, which would take O(n*log(n)). It would take a bit more work if we're dealing with duplicates, but the basic algorithm and time efficiency remain the same.

@Lensflare I blame this error on being half asleep.