Speed dating algorithm to select the pair of dates

Question

Lets say there are 10 boys and 10 girls in speed date. 10 boys select 4 girls and rank them. 10 girls select 4 boys and rank them. In the end the winning pairs would be returned.

Finer details such as tie-breakers, rules of input params etc, are well documented. Looking for code review, optimization and best practices.

final class Pair {

    private final String male;
    private final String female;

    public Pair(String male, String female) {
        this.male = male;
        this.female = female;
    }

    public String getMale() {
        return male;
    }

    public String getFemale() {
        return female;
    }

    @Override
    public String toString() {
        return male + "  dates: " + female;
    }
}

/**
 * 
 * Provides a thread safe solution Solves the speed date problem.
 * 
 * Example:
 * --------
 * - Lets say there are 10 boys and 10 girls in speed date
 * - 10 boys  select 4 girls and rank them.
 * - 10 girls select 4 boys  and rank them.
 * - in the end the winning pairs would be returned.
 * 
 * Complexity:
 * Time complexity: O(nlogn)
 * Space complexity: O(n)
 * 
 */
public class SpeedDateCompute {

    private final Map<String, List<String>> maleChoices;
    private final Map<String, List<String>> femaleChoices;

    /**
     * Does not make a deep copy of maps thus client is not expected to change maleChoice, femaleChoice.
     * Expects consistency in males and female maps, else results are unpredictable.
     * 
     * By consistency it means:
     * - The number of boys and girls should be the same.
     * - Each boy and each girl should make same number of choices
     * - Choices should mention "only existing members of opposite sex"
     * 
     * 
     * @param maleChoices
     * @param femaleChoices
     */
    public SpeedDateCompute(Map<String, List<String>> maleChoices, Map<String, List<String>> femaleChoices) {
        validate(maleChoices, femaleChoices);

        this.maleChoices = maleChoices;
        this.femaleChoices = femaleChoices;
    }

    private static class Edge {
        String male;
        String female;
        int malesPreference;  // what does male   ranks this female ?
        int femalePreference; // what does female ranks this male ?

        Edge (String male, String female, int malesPreference, int femalePreference) {
            this.male = male;
            this.female = female;
            this.malesPreference = malesPreference;
            this.femalePreference = femalePreference;
        }
    }

    private static class EdgeComparator implements Comparator<Edge> {
        @Override
        public int compare(Edge edge1, Edge edge2) {
            int val = rank (edge1.femalePreference - 1, edge1.malesPreference - 1)
                    - rank (edge2.femalePreference - 1, edge2.malesPreference - 1);
            return val;
        }

        /*
         * Ranking algorithm. 
         * 
         * Let notation (1,2) mean - femalePrerence is 1 and malePreference is 2.
         * (1, 1) means both rank each other as their best so this pair triumps over (2, 2)
         * but there is a tie between (1, 2) and (2, 1)
         * As a tie breaker we give preference to feelings of women 
         * thus (1,2) > (2, 1)
         * 
         * Thus the rule is expanded to 
         * 
         * (1, 1) > (1, 2) > (2, 1) > (2, 2)
         * 
         * This can be thought of as a matrix of the form
         * (lil lazy to retype the whole thing, plz check the link)
         * http://math.stackexchange.com/questions/720797/whats-the-name-of-this-sort-of-matrix
         * http://codereview.stackexchange.com/questions/44939/a-matrix-with-square-diagonals-and-transpose-being-increments-of-other
         * 
         * @param row   the female choice
         * @param col   the male choice
         * @return      
         */
        private int rank(int row, int col) {
            if (row == col) {
                return row * row;
            }

            int rank = (col) * (col) + 1 + (2 * row) ;

            if (row < col) {
                return rank;
            } else {
                return rank + 1;
            }
        }
    }

    private void validate (Map<String, List<String>> maleChoices, Map<String, List<String>> femaleChoices) {
        if (maleChoices == null || femaleChoices == null) {
            if (maleChoices != null) {
                throw new NullPointerException("female choice map should not be null");
            }
            if (femaleChoices != null) {
                throw new NullPointerException("male choice map should not be null");
            }
            throw new NullPointerException("no choice map should be null.");
        }

        if (maleChoices.size() == 0 || femaleChoices.size() == 0) {
            if (maleChoices.size() == 0) {
                throw new IllegalArgumentException("male choice map should not be empty.");
            }
            if (femaleChoices.size() == 0) {
                throw new IllegalArgumentException("female choice map should not be empty.");
            }
            throw new IllegalArgumentException("no choice map should be empty.");
        }
    }


    public List<Pair> getPairs() {
        final Collection<Edge> edges = parseChoiceMaps();
        final List<Edge> sortedEdges = sort(edges);
        return createPairs(sortedEdges);
    }

    /**
     * Given a directed bipartite graph, it converts bipartite graph into 
     * undirected map.
     * 
     * @param choiceMap the bipartite graph of choices
     * @return 
     */                 
    private Collection<Edge> parseChoiceMaps() {

        final Map<String, Edge> combinedMaleChoice = new HashMap<String, Edge>();

        synchronized (maleChoices) {
            // parsing male choices.
            for (Entry<String, List<String>> maleChoice : maleChoices.entrySet()) {
                String maleName = maleChoice.getKey();
                List<String> females = maleChoice.getValue();
                for (int i = 0; i < females.size(); i++) {
                    // mark female preference as "size" thus assigning the worst rank as default.
                    combinedMaleChoice.put(maleName + females.get(i), new Edge(maleName, females.get(i), i + 1,
                            maleChoices.size()));
                }
            }
        }

        synchronized (femaleChoices) {
            // parsing female choices
            for (Entry<String, List<String>> femaleChoice : femaleChoices.entrySet()) {
                List<String> males = femaleChoice.getValue();
                for (int i = 0; i < males.size(); i++) {
                    String name = males.get(i) + femaleChoice.getKey();
                    // check if any male has chosen this female, else skip.
                    if (combinedMaleChoice.containsKey(name)) {
                        combinedMaleChoice.get(males.get(i) + femaleChoice.getKey()).femalePreference = i + 1;
                    }
                }
            }
        }

        return combinedMaleChoice.values();
    }


    private List<Edge> sort(Collection<Edge> edges) {
        final List<Edge> edgeList = new ArrayList<Edge>(edges);
        Collections.sort(edgeList, new EdgeComparator());
        return edgeList;
    }

    private List<Pair> createPairs(List<Edge> edges) {
        final Set<String> hookedUpMales = new LinkedHashSet<String>();
        final Set<String> hookedUpFemales = new LinkedHashSet<String>();

        for (Edge edge : edges) {            
            if (hookedUpMales.contains(edge.male) || hookedUpFemales.contains(edge.female)) {
                continue;
            }
            hookedUpMales.add(edge.male);
            hookedUpFemales.add(edge.female);
        }

        return mapSetsToPairs(hookedUpMales, hookedUpFemales);
    }

    private List<Pair> mapSetsToPairs(Set<String> hookedUpMales, Set<String> hookedUpFemales) {
        Iterator<String> maleItr = hookedUpMales.iterator();
        Iterator<String> femaleItr = hookedUpFemales.iterator(); 

        final List<Pair> pairs = new ArrayList<Pair>();

        while (maleItr.hasNext() && femaleItr.hasNext()) {
            pairs.add(new Pair(maleItr.next(), femaleItr.next()));
            maleItr.remove();   // just to optimize space
            femaleItr.remove(); // just to optimize space
        }
        return pairs;
    }


    public static void main(String[] args) {
        /*
         * Test case 1
         */
        Map<String, List<String>> maleChoice1 = new HashMap<String, List<String>>();
        Map<String, List<String>> femaleChoice1 = new HashMap<String, List<String>>();

        maleChoice1.put("male1", Arrays.asList("female1", "female2"));
        maleChoice1.put("male2", Arrays.asList("female2", "female1"));
        femaleChoice1.put("female1", Arrays.asList("male1", "male2"));
        femaleChoice1.put("female2", Arrays.asList("male2", "male1"));
        SpeedDateCompute speedDateCompute = new SpeedDateCompute(maleChoice1, femaleChoice1);
        List<Pair> actualValues = speedDateCompute.getPairs();
        assertEquals("male1", actualValues.get(0).getMale());
        assertEquals("female1", actualValues.get(0).getFemale());
        assertEquals("male2", actualValues.get(1).getMale());
        assertEquals("female2", actualValues.get(1).getFemale());

        /*
         * Test case 2
         */
        Map<String, List<String>> maleChoice2 = new HashMap<String, List<String>>();
        Map<String, List<String>> femaleChoice2 = new HashMap<String, List<String>>();
        maleChoice2.put("male1", Arrays.asList("female2", "female1"));
        maleChoice2.put("male2", Arrays.asList("female1", "female2"));
        maleChoice2.put("male3", Arrays.asList("female1", "female2"));
        femaleChoice2.put("female1", Arrays.asList("male2", "male1"));
        femaleChoice2.put("female2", Arrays.asList("male1", "male2"));
        femaleChoice2.put("female3", Arrays.asList("male1", "male2"));
        speedDateCompute = new SpeedDateCompute(maleChoice2, femaleChoice2);
        actualValues = speedDateCompute.getPairs();

        assertEquals("male1", actualValues.get(0).getMale());
        assertEquals("female2", actualValues.get(0).getFemale()); 
        assertEquals("male2", actualValues.get(1).getMale());
        assertEquals("female1", actualValues.get(1).getFemale());

        assertEquals(2, actualValues.size());
    }
}

Where are 10 boys/girls and where are their 4 choices in your test cases? — abuzittin gillifirca
– abuzittin gillifirca, Commented Mar 26, 2014 at 8:08

amon · Accepted Answer · 2014-03-26 15:27:08Z

This code is really beautiful and well-documented. There are very few parts which could be criticized:

Don't use objects where they are not applicable. Your SpeedDateCompute class is essentially only characterized by its getPairs method. We might as well make that static, and invoke it as SpeedDateCompute.getPairs(maleChoices, femaleChoices).

Such single-method classes encpasulating an algorithm should only be instantiable if we need to pass the algorithm around as an object.

Your validate is a bit too complicated. This refactoring produces almost as good error messages, but is less confusing to read.

private void validate (Map<String, List<String>> maleChoices, Map<String, List<String>> femaleChoices) {
    if (femaleChoices == null) {
        throw new NullPointerException("female choice map should not be null");
    }
    if (maleChoices == null) {
        throw new NullPointerException("male choice map should not be null");
    }

    if (maleChoices.size() == 0) {
        throw new IllegalArgumentException("male choice map should not be empty.");
    }
    if (femaleChoices.size() == 0) {
        throw new IllegalArgumentException("female choice map should not be empty.");
    }
}

Synchronizing on maleChoices and femaleChoices makes little sense. Your documentation already states that the “client is not expected to change maleChoice, femaleChoice”. I would have left it with that, and hope that any users of this class aren't insane enough to share this data between threads. Synchronizing is a fairly expensive operation, so I would wish to avoid it if unnecessary, and offload the responsibility to the client.

The keys in combinedMaleChoice are a simple concatentation of the male and female names. While in practice very unlikely, this could lead to clashes (along the lines of "AA" + "B" vs. "A" + "AB"). You could use a Map<String, Map<String, Edge>> instead, or a separator that is guaranteed to not occur in the name: maleName + "\0" + femaleName.

This is part of a larger issue that names are not unique. For real-world code, you need some unique identifier. This is one reason why I would like to encapsulate the involved persons in a class of their own, e.g:

public static abstract class Person<Likes extends Person> {
    private final String name;
    private final List<Likes> likes = new ArrayList<>();

    public Person(String name) {
        this.name = name;
    }

    public String name() {
        return this.name;
    }

    public List<Likes> likes() {
        return this.likes;
    }

    public List<Likes> likes(List<Likes> others) {
        this.likes.addAll(others);
        return this.likes;
    }

    @Override
    public String toString() {
        return this.name();
    }

    // "equals" defaults to pointer equivalence, which is what we want
}

public static class Male extends Person<Female> {
    public Male(String name) {
        super(name);
    }

    @Override
    public boolean equals(Object that) {
        return that instanceof Male && super.equals(that);
    }
}

public static class Female extends Person<Male> {
    public Female(String name) {
        super(name);
    }

    @Override
    public boolean equals(Object that) {
        return that instanceof Female && super.equals(that);
    }
}

This also allows us to better leverage the type system than only relying on Strings – the downside is that the client will need more initialization code to prepare the Persons.

There is no substantial difference between Pair and Edge. I'd combine both into one class.

You made your code far more complicated than necessary by splitting logic into createPairs and mapSetsToPairs. You create two LinkedHashSets and then iterate over both in parallel. We can do all of that in one loop:

private List<Pair> createPairs(List<Edge> edges) {
    final Set<String> hookedUpMales = new HashSet<>();
    final Set<String> hookedUpFemales = new HashSet<>();
    final List<Pair> hookedUpPairs = new ArrayList<>();

    for (Edge edge : edges) {
        if (hookedUpMales.contains(edge.male) || hookedUpFemales.contains(edge.female)) {
            continue;
        }
        hookedUpPairs.add(new Pair(edge.male, edge.female));
        hookedUpMales.add(edge.male);
        hookedUpFemales.add(edge.female);
    }

    return hookedUpPairs;
}

If you are targeting Java 7, you don't have to spell out all generics, and can use the diamond operator instead:

// final List<Edge> edgeList = new ArrayList<Edge>(edges);
final List<Edge> edgeList = new ArrayList<>(edges);

Your tests are buggy. While you guarantee that you return the optimal pairs, you do not guarantee any order when two pairs have the same preferences. Therefore in your first test, actualValues.get(0).getMale() may be male2 rather than male1. Instead:
1. Test that the number of returned pairs is correct
2. Test that the collection of pairs contains an expected pair. This implies that you should override equals and hashCode for the Pair class.
In parseChoiceMaps, you assign i + 1 as a preference, then decrement that value again when calculating your rank. This index shuffling servers no purpose, and can be removed by using zero-based preferences

I did a bit of refactoring incl. introducing a Person class and unifying Edge and Pair, and the result is in fact quite nice: http://ideone.com/RSTcUu

Further observations:

Your JavaDoc contains Markdown-like lists. IIRC, you can use a restricted subset of HTML for formatting instead.
Your ranking algorithm seems terribly flawed. I understand that you need some absolute ordering, but a modified Manhattan Distance or Euclidean Distance would probably do a better job. For example with f = 10, m = 0 (where f is the female preference, m the male preference) we get a rank of 22. Now we might have another edge with f = 0, m = 9. I would expect this second edge to be sorted before the first one. But it has a rank of 101, which is far worse! In other words, the choice of males is weighted more heavily.

A related problem is that you assign a preference for females even when they have shown no interest in that specific male. For example, consider this:
```
male1 likes female1
male2 likes female2
female1 likes male1
female2 likes male1
```
The pairing male1 – female1 is expected, as both like each other. However, male2 – female2 is dubious. Due to your implementation, the reverse is not true:
```
male1 likes female1
male2 likes female1
female1 likes male1
female2 likes male2
```
will only return the male1 – female1 pairing.

Better rankings that use the female rankings to break ties could be a modified Manhattan Distance:
```
rank = (m + f) * max + f
```
or Euclidean Distance:
```
rank = (int) (Math.sqrt(m*m + f*f) * max + f)
```
where max is the maximum rating involved in this comparison.

Dan · Accepted Answer · 2014-03-26 12:19:32Z

5

Looks good, I didn't work through the logic of your algorithms, but generally looked if things could be done more efficiently and nothing grabbed my attention.

The one comment I do have is on your validate() method, it checks for null and empty maps, but I believe you have an additional requirement that they are the same size? If so, this should be part of the validate() method as well.

answered Mar 26, 2014 at 12:19

Dan

2161 silver badge3 bronze badges

Add a comment |

Stack Exchange Network

Speed dating algorithm to select the pair of dates

2 Answers 2

You must log in to answer this question.

Linked

Hot Network Questions

Speed dating algorithm to select the pair of dates

2 Answers 2

You must log in to answer this question.

Linked

Related

Hot Network Questions