Explain the example of providing the Kth largest number of numbers from each of N given sets?

Question

Today I tried to solve the Facebook Programming Program . The task I received is the Bar problem, which can be found here . My problem during the call was to understand the first example they provided.

The task can be summarized as follows:

Friends

N play a game. Each of them has a list of numbers in front of them.

Each of N friends selects a number from his list and informs the game administrator about it. Then the game administrator sorts the reported numbers and screams the largest number of Kth.

You want to know the score of all possible numbers that the game administrator can scream.

At this point, I thought I understood the problem, but then presented the following example:

In the above example, the examples for the first test are N = 3 and K = 3. The list for the first person is {2 5 3}, {8 1 6} for the second and {7 4 9} for the third. In this case, all numbers in {4, 5, 6, 7, 8, 9} have a chance to become the third largest selected number.

So my question is:

How will 7, 8 and 9 be the third largest selected number?

In my opinion, only the numbers {1, 2, 3, 4, 5} can be the third largest number, but maybe I misunderstood the algorithm.

Answer 1

I think you're right, they sorted the numbers incorrectly. The proposed answer to the example looks like the correct answer if you want to get the third smallest, and not the third largest. That is, sorting them from the smallest to the largest, you get a third. This is not what the question says (but English is not my first language, so I could be wrong).

Answer 2

The question should mean the third smallest.

Given the array of sets, S_1, S_2 ... S_N, select one and select this item. Suppose we know both the largest and smallest elements in each set, and divide the sets into three groups. Those in which all elements are larger than e, those in which all elements are smaller than e, and those in which there are elements that are larger and smaller than e.

For a set of N sets and smallest k, there must be at most k-1 sets with all elements less than e, and at most Nk sets with all elements greater than e. If these two conditions are preserved, I can take those sets that are larger and smaller than e, and arrange them so that e is selected.