patternjavaModerate

Speed dating algorithm to select the pair of dates

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

datingthedatesalgorithmselectspeedpair

Problem

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> maleChoices;
private final Map> 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> maleChoices, Map> femaleChoices) {
validate(maleChoices, femaleChoices);

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

private static class Edge {
St

Solution

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> maleChoices, Map> 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> 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 {
    private final String name;
    private final List likes = new ArrayList<>();

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

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

    public List likes() {
        return this.likes;
    }

    public List likes(List 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 {
    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 {
    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 createPairs(List edges) {
    final Set hookedUpMales = new HashSet<>();
    final Set hookedUpFemales = new HashSet<>();
    final List 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 edgeList = new ArrayList(edges);
final List 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:

Test that the number of returned pairs is correct

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

Code Snippets

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.");
    }
}

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);
    }
}

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;
}

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

male1 likes female1
male2 likes female2
female1 likes male1
female2 likes male1

Context

StackExchange Code Review Q#45371, answer score: 10

Revisions (0)

No revisions yet.