Practice-It

Write a method named highlyPaidWomen that returns a set of names of women who earn more money than their husbands. The method accepts two parameters: 1) a marriage BiMap from strings to strings, where each key/value pair represents the name of a husband and wife; and 2) a salary Map from strings to real numbers, where each key/value pair represents a person's name and that person's salary at his/her job. Your method should examine these collections and return a Set of names of all women who are employed and earn a salary that is strictly greater than than their husband's salary. The set should be in sorted alphabetical order. Note that not every person has a job; if not, they will be absent from the salary map. If the wife is employed and the husband is not, by default she makes more money than her husband and should be included in the set.

For example, suppose your method is passed the following marriage bi-map and salary map:

{Fred=Wilma, Homer=Marge, Peter=Lois, Tarzan=Jane, Simba=Nala, Ricky=Lucy, ...}
{Lois=29.0, Fred=44.0, Nala=97.0, Marge=8.0, Peter=13.0, Lucy=11.0, Homer=5.0, Ricky=22.0}

Your method would return the set [Lois, Marge, Nala] because Lois makes 29.0 to Peter's 13.0, Marge makes 8.0 to Homer's 5.0, and Nala makes 97.0 while Simba is unemployed. Wilma and Jane are not in the set because they are unemployed, and Lucy is not in the set because she makes less salary than Ricky.

Your code should run in O(N log N) time where N is the number of key/value pairs in the salary map. For the purposes of this problem, we will assume that the marriage bi-map is likely to be much larger than the salary map, therefore it is inefficient and inappropriate to loop over every single key/value pair in the bi-map. You may assume that every name in the salary map appears in the bi-map as a key or value.

You may assume that none of the collections passed, nor any of the keys/values in them, are null. Do not construct any auxiliary collections other than the set to return. You should not modify any of the collections passed in.