[D E Shaw] One to One Mapping of wrestlers!!

Background

I attended an interview at D E Shaw last year and during face-to-face interview they usually have a puzzles round where they give you a puzzle and ask you to device an algorithm for solving it. I could not solve this particular problem during my interview but later on i kept thinking about it and now, I feel I've got a solution to this problem.

Problem Definition

There are two groups of wrestlers say Group A and Group B. Each group has 10 wrestlers. Given are two conditions:

• For a wrestler with given strength in group A there is a wrestler in group B of equal strength.
• No two wrestlers in a group have equal strength.

You have to find one-to-one mapping by arranging fights between wrestlers. Discuss the strategy/algorithm for the same.

Solution

Convention Let us name wrestlers in each group as:

Group A - WrestlerA1, WrestlerA2, .... WrestlerA10.

Group B- WrestlerB1, WrestlerB2, .... WrestlerB10.

Basic approach

Arrange a fight between WrestlerA1 and all the Wrestlers of Group B to find the matching wrestlers. Same way arrange a fight between WrestlerA2 and other remaining wrestlers of group B and keep following this strategy.

In a worst,

First wrestler has to fight with 9 wrestlers

Second has to fight 8 Wrestlers

Third has to fight 7 Wrestlers

And so on....

So this approach is not that efficient.

Quick Sort

If we correlate this to the quick sort algorithm, let us see what conclusion we can draw from it. Let us sort members of one group by arranging fights between themselves. In Group A - ramdomly select a member say wrestlerA5 and arrange fights between wrestlerA5 and all others and divide them among two groups - WinA5, LoseA5. where, WinA5 contain all the wrestlers who won from wrestlerA5 and LoseA5 contains all the member who lost to wrestlerA5.

Now among each sub-group use same kind of strategyand we get a group sorted like this. Avg Case Complexity in this case is O(NlogN).

Same way we can sort member in Group B and we get one-to-one correspondence based on given conditions.

Please leave a comment in case you have got a better solution than this one!!