Efficient way to merge map with another map on partial matches of a field

Question

Say I have the following classes:

class PersonWithFirstName {
    String firstName;
}
class PersonWithFullName {
    String fullName; // note assume this is not delimited in any way
}
class PersonWithFirstNameAndFullName {
    String firstName;
    List fullNames; 
}

Now given a Map<Integer, PersonWithFirstName> and a Map<Integer, PersonWithFullName> where the key is the id (but the ids from the two maps are not coorelated), I want to write a function that returns PersonWithFirstNameAndFullName which for each firstName in Map<String, PersonWithFirstName>, finds any full names in the other map that begin with this firstName.

As an example:

Map<Integer, PersonWithFirstName> mapPersonsWithFirstName = new HashMap<>();
Map<Integer, PersonWithFulltName> mapPersonsWithFullName = new HashMap<>();

mapPersonsWithFirstName.set(1, new PersonWithFirstName("bob"));
mapPersonsWithFirstName.set(2, new PersonWithFirstName("alice"));
mapPersonsWithFullName.set(1, new PersonWithFullName("bobjohnson"));
mapPersonsWithFullName.set(2, new PersonWithFullName("bobjames"));



myFunction(mapPersonsWithFirstName, mapPersonsWithFullName)
/* should return
{
  1: {
    firstName: "bob"
    fullNames: ["bobjohnson", "bobjames"]
  },
  2: {
    firstName: "alice"
    fullNames: []
  }
}
*/

The only way I came up with is looping through the entryset of mapPersonsWithFirstName, and for each PersonWithFirstName doing another loop through mapPersonsWithFullName to find any PersonWithFullName.fullName that starts with PersonWithFirstName.firstName. This runs is exponential time, but I'm really thinking this can be solved in linear time. Any help is appreciated!

Answer 1

I think this way It is not exponential anymore:

public static void main(String[] args) {

    Map<Integer, PersonWithFirstName> firstNames = new HashMap<>();
    Map<Integer, PersonWithFullName> fullNames = new HashMap<>();

    firstNames.put(1, new PersonWithFirstName("bob"));
    firstNames.put(2, new PersonWithFirstName("alice"));
    firstNames.put(3, new PersonWithFirstName("test1"));
    firstNames.put(4, new PersonWithFirstName("test2"));
    firstNames.put(5, new PersonWithFirstName("test3"));
    fullNames.put(1, new PersonWithFullName("bobjohnson"));
    fullNames.put(2, new PersonWithFullName("bobjames"));
    fullNames.put(3, new PersonWithFullName("test1aaaa"));
    fullNames.put(4, new PersonWithFullName("aliceSurname"));

    Map<String, Set<String>> firstToFull = new HashMap<>();

    List<String> firstNamesSorted = firstNames.values().stream().map(it -> it.firstName).sorted().collect(Collectors.toList());
    List<String> fullNamesSorted = fullNames.values().stream().map(it -> it.fullName).sorted().collect(Collectors.toList());

    int indexFirstName = 0;
    int indexFullName = 0;
    while (indexFirstName < firstNamesSorted.size() && indexFullName < fullNamesSorted.size()) {
        String firstName = firstNamesSorted.get(indexFirstName);
        String fullName = fullNamesSorted.get(indexFullName);
        if (fullName.startsWith(firstName)) {
            firstToFull.computeIfAbsent(firstName, n -> new HashSet<>())
                    .add(fullName);
            indexFullName++;
        } else {
            if(compare(firstName, fullName) == 1) {
                indexFullName++;
            } else {
                indexFirstName++;
            }
        }
    }

    int firstNamesSize = firstNamesSorted.size();
    int i = 0;
    while (firstToFull.size() < firstNamesSize) {
       String name = firstNamesSorted.get(i);
       firstToFull.computeIfAbsent(name, n -> new HashSet<>());
       i++;
    }
    
    System.out.println(firstToFull);

}

private static int compare(String firstName, String fullName) {
    String substring = fullName.substring(0, firstName.length());
    return firstName.compareTo(substring);
}

Answer 2

You could use TreeSet for ordering all your names and then just get desired subsequences (using tailSet and headSet methods):

    private static List<PersonWithFirstNameAndFullName> myFunction(List<String> firstNames, List<String> fullNames) {
        List<PersonWithFirstNameAndFullName> res = new ArrayList<>();
        firstNames.sort(Comparator.reverseOrder());
        NavigableSet<String> allNames = Stream.concat(firstNames.stream(), fullNames.stream()).collect(Collectors.toCollection(TreeSet::new));
        for (String firstName : firstNames) {
            final SortedSet<String> tail = allNames.tailSet(firstName, false);
            allNames = new TreeSet<>(allNames.headSet(firstName));
            res.add(new PersonWithFirstNameAndFullName(firstName, new ArrayList<>(tail)));
        }
        return res;
    }

If the code above doesn't quite meet your requirements, you can change it. But, in general, the main idea is to use TreeSet or TreeMap.

Update (to match the signature of your methods):

    public static List<PersonWithFirstNameAndFullName> myFunction(Map<Integer, PersonWithFirstName> mapPersonsWithFirstName, Map<Integer, PersonWithFullName> mapPersonsWithFullName) {
        return myFunction(mapPersonsWithFirstName.values().stream().map(PersonWithFirstName::getFirstName).collect(Collectors.toList()),
                mapPersonsWithFullName.values().stream().map(PersonWithFullName::getFullName).collect(Collectors.toList()));
    }