Put ages within a supplied range into a HashMap

Question

I'm looking for general considerations to make for the next time I'm writing code. I'm wondering if in this case it's better to have another auxiliary storage (another map?) in this case (and how to do so?). I haven't yet learned about complexity, so I'm not sure if I'm completing that part of the question (running in O(N log N) time).

Write a method byAge that accepts three parameters: 1) a Map where each key is a person's name (a string) and the associated value is that person's age (an integer); 2) an integer for a minimum age; and 3) an integer for a maximum age. Your method should return a new Map with information about people with ages between the min and max, inclusive.

In your result map, each key is an integer age, and the value for that key is a string with the names of all people at that age, separated by "and" if there is more than one person of that age. Your result map's pairs should be sorted in ascending order by age (keys). Include only ages between the min and max inclusive, where there is at least one person of that age in the original map. If the map passed is empty, or if there are no people in the map between the min/max ages, return an empty map.

For example, if a Map named ages stores the following key=value pairs:

{Paul=28, David=20, Janette=18, Marty=35, Stuart=98, Jessica=35, Helene=40, Allison=18, Sara=15, Grace=25, Zack=20, Galen=15, Erik=20, Tyler=6, Benson=48}

The call of byAge(ages, 16, 25) should return the following map (the contents can be in any order):

{18=Janette and Allison, 20=David and Zack and Erik, 25=Grace}

For the same map, the call of byAge(ages, 20, 40) should return the following map:

{20=David and Zack and Erik, 25=Grace, 28=Paul, 35=Marty and Jessica, 40=Helene}

Obey the following restrictions in your solution:

1. You will need to construct a map to store your results, but you may not use any other structures (arrays, lists, etc.) as auxiliary storage. (You can have as many simple variables as you like.)
2. You should not modify the contents of the map passed to your method.
3. Your solution should run in no worse than O(N log N) time, where N is the number of pairs in the map.

---

public Map<Integer, String> byAge(Map<String, Integer> namesAges, int min, int max) {   
    Map<Integer, String> range = new HashMap<Integer, String>();
    for (String name : namesAges.keySet()) {
        int age = namesAges.get(name);
        if (range.containsKey(age)) {
            range.put(age, range.get(age) + " and " + name);
        } else if (min <= age && age <= max) {
            range.put(age, name);
        }
    }
    return range;
}

Answer 1

range.put(age, range.get(age) + " and " + name);

This is expensive.

Specifically, string construction that is done over and over via creating longer and longer strings. You're basically building the same string over and over and over. And strings are basically arrays of char, so that's a lot of copying.

And there's nothing you can do about it because of this rule:

You will need to construct a map to store your results, but you may not use any other structures (arrays, lists, etc.) as auxiliary storage. (You can have as many simple variables as you like.)

If you were to ignore this one rule for a moment, what you could do is make a Map<Integer, List<String>>. And then put the names of people in the list. Then, when you're done, as per this stackoverflow answer... https://stackoverflow.com/a/22577565/540837

You can use a stream and Collectors.joining.

But you can't, because you're not allowed any other lists or arrays or whatnot.

I'd personally consider the problem unsolvable because the strings could get very long and become a larger part of the problem than the actual pairs would.

What I'd change about your code is this bit:

for (String name : namesAges.keySet()) {
    int age = namesAges.get(name);

You're first getting the keys, and then you're using the keys to get the value. Maps have .entrySet to get a set of entries, and then you can have the key and the value in one go.

Also, "Your result map's pairs should be sorted in ascending order by age (keys)." sorting already takes O(N log N) time, so basically your instructors are expecting that you'll find a way to get N log N string concatenation which doesn't exist when you're not allowed to create arrays.