Find the Biggest Traveler

Question

This is from one of those online test sites, so the result had to be contained in a single class.

The problem was stated as follows:

Your java method will be given a 2-D array trip[n][2] of strings, representing a travel log for a group of people. For each 'n', trip[n][0] is the name of the person and travel [n][1] is the name of the city visited by the person in the respective trip. More than one person can visit the same city, and an individual can visit the same city more than once.

Your java method will output a string, containing the name of the biggest traveler. The biggest traveler will be determined like this:

1. Who made the most trips?

2. Tie breaker: who visited the most cities?

3. Tie breaker of tie breaker: who' s travel is most distributed? (fewest trips to their most visited city)

So you can test your algorithm, you can try it with data formatted like this:

12
Person A, City 1
Person A, City 2
Person B, City 1
Person B, City 3
Person B, City 3
Person B, City 4
Person B, City 4
Person C, City 1
Person C, City 2
Person C, City 2
Person C, City 2
Person C, City 4

Note: the 12 at the top indicates how many trip there are in the data set
Note: Order of the lines may be jumbled in an actual example

In the above example:

1. Person B and person C each made 5 trips...Tie

2. Person B and person C each visited 3 cities...Tie

3. Person C visited the same city 3 times; Person B's most visited is 2.

Correct return value: "Person B"

And my solution was as included below. I added a main method to test the example problem, but in practice the input would be handled by the default code provided in the web site:

import java.util.*;

public class BiggestTraveler {

    public static class TravelerInfo {
            //map that contains the cities a person has visited and how times they have visited it
        String name; //not including setters just because they make no sense in this context (and data isn't changing)
        int totalTrips = 0;
        int maxVisitedCity = 0;
        Map<String, Integer> cityVisits = new HashMap<String, Integer>();

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

        public String getName() {
            return name;
        }

        public Map< String, Integer > getCityVisits() {
            return cityVisits;
        }

        public void setCityVisits( final Map< String, Integer > cityVisits ) {
            this.cityVisits = cityVisits;
        }

        public void addVisit(String city){
            int numVisits = 1;
            if( cityVisits.containsKey( city ) ){
                numVisits += cityVisits.get( city );

                if( numVisits > maxVisitedCity ){
                    maxVisitedCity = numVisits;
                }
            }
            cityVisits.put( city, numVisits );
            totalTrips++;
        }

        public int getTotalTrips() {
            return totalTrips;
        }

        public int getDistinctCityCount(){
            return cityVisits.keySet().size();
        }

        public int getMaxVisitedCity() {
            return maxVisitedCity;
        }
    }

    public static class TravelsComparator implements Comparator<TravelerInfo> {
        @Override
        public int compare( final TravelerInfo o1, final TravelerInfo o2 ) {
            if( o1.getTotalTrips() < o2.getTotalTrips() ){
                return 1;
            }else if( o1.getTotalTrips() > o2.getTotalTrips() ){
                return -1;
            }
            return 0;
        }
    }

    public static class DistinctCitiesComparator implements Comparator<TravelerInfo>{
        @Override
        public int compare( final TravelerInfo o1, final TravelerInfo o2 ) {
            if( o1.getDistinctCityCount() < o2.getDistinctCityCount() ){
                return 1;
            }else if( o1.getDistinctCityCount() > o2.getDistinctCityCount() ){
                return -1;
            }
            return 0;
        }
    }

    public static class DistributedTravelsComparator implements Comparator<TravelerInfo>{
        @Override
        public int compare( final TravelerInfo o1, final TravelerInfo o2 ) {
            if( o1.getMaxVisitedCity() < o2.getMaxVisitedCity() ){
                return -1;
            }else if( o1.getMaxVisitedCity() > o2.getMaxVisitedCity() ){
                return 1;
            }
            return 0;
        }
    }

    static String pickBiggestTraveler(String[][] trips) {
        BiggestTraveler bt = new BiggestTraveler();

        Map<String, TravelerInfo > travelRecords = new HashMap<String, TravelerInfo >();

        for(int i=0; i < trips.length; i++){
            if( travelRecords.containsKey( trips[ i ][ 0 ] ) ){
                    //if we've dealt with this traveler just add a new visited city
                travelRecords.get( trips[ i ][ 0 ] ).addVisit( trips[i][1] );
            }else{
                    //we've found a new traveler so let's add him
                TravelerInfo info = new TravelerInfo( trips[i][0] );
                info.addVisit( trips[i][1] );
                travelRecords.put( info.getName(), info );
            }
        }

        List<Comparator> comparators = new ArrayList< Comparator >( 3 );
        comparators.add( new TravelsComparator() );
        comparators.add( new DistinctCitiesComparator() );
        comparators.add( new DistributedTravelsComparator() );

        List<TravelerInfo> travelInfo = new ArrayList<TravelerInfo>( travelRecords.values() );

        TravelerInfo currentMax = null;
        for(Comparator comparator : comparators ){
                //if we're not down to a single winner then continue
            if( travelInfo.size() > 1 ){
                Collections.sort( travelInfo, comparator );

                currentMax = travelInfo.get( 0 );

                int lastIndex = travelInfo.size();

                    //find the last traveler that is tied with the current max
                for(int i = 0; i < travelInfo.size(); i++ ){
                    if( comparator.compare( currentMax, travelInfo.get(i) ) < 0 ){
                        lastIndex = i;
                    }
                }
                    //remove values lower than the highest
                travelInfo = travelInfo.subList( 0, lastIndex );
            }else{
                //if we've found a winner no need to continue iterating over comparators
                break;
            }
        }

        if( travelInfo.size() > 1 ){
            return "Tie";
        }else{
            return travelInfo.get(0).getName();
        }
    }



    public static void main(String args[] ) {
        String[][] trips = new String[12][2];
        trips[0][0] = "Person A";
        trips[0][1] = "City 1";
        trips[1][0] = "Person A";
        trips[1][1] = "City 2";
        trips[2][0] = "Person B";
        trips[2][1] = "City 1";
        trips[3][0] = "Person B";
        trips[3][1] = "City 3";
        trips[4][0] = "Person B";
        trips[4][1] = "City 3";
        trips[5][0] = "Person B";
        trips[5][1] = "City 4";
        trips[6][0] = "Person B";
        trips[6][1] = "City 4";
        trips[7][0] = "Person C";
        trips[7][1] = "City 1";
        trips[8][0] = "Person C";
        trips[8][1] = "City 2";
        trips[9][0] = "Person C";
        trips[9][1] = "City 2";
        trips[10][0] = "Person C";
        trips[10][1] = "City 2";
        trips[11][0] = "Person C";
        trips[11][1] = "City 4";
        pickBiggestTraveler( trips );
    }


}

Answer 1

Simplifying comparators

Your custom comparators all do this kind of thing:

if( o1.getTotalTrips() < o2.getTotalTrips() ){
    return 1;
}else if( o1.getTotalTrips() > o2.getTotalTrips() ){
    return -1;
}
return 0;

There is a simpler way using Integer.compare directly:

public static class TravelsComparator implements Comparator<TravelerInfo> {
    @Override
    public int compare(final TravelerInfo o1, final TravelerInfo o2) {
        return -Integer.compare(o1.getTotalTrips(), o2.getTotalTrips());
    }
}

public static class DistinctCitiesComparator implements Comparator<TravelerInfo> {
    @Override
    public int compare(final TravelerInfo o1, final TravelerInfo o2) {
        return -Integer.compare(o1.getDistinctCityCount(), o2.getDistinctCityCount());
    }
}

public static class DistributedTravelsComparator implements Comparator<TravelerInfo> {
    @Override
    public int compare(final TravelerInfo o1, final TravelerInfo o2) {
        return Integer.compare(o1.getMaxVisitedCity(), o2.getMaxVisitedCity());
    }
}

Simplifying comparators, round 2

In pickBiggestTraveler, once you have the list of travelInfo objects, an easier way to create the list of comparators:

    List<Comparator<TravelerInfo>> comparators = Arrays.asList(
            new TravelsComparator(), 
            new DistinctCitiesComparator(), 
            new DistributedTravelsComparator());

Notice that I also corrected the type declaration to List<Comparator<TravelerInfo>>.

Finally, instead of the tedious for loop, you can create a new Comparator as a composite of the other Comparator instances, and greatly simplify the second half of your method:

    List<TravelerInfo> travelInfo = new ArrayList<TravelerInfo>(travelRecords.values());

    Collections.sort(travelInfo, new Comparator<TravelerInfo>() {
        @Override
        public int compare(TravelerInfo o1, TravelerInfo o2) {
            for (Comparator<TravelerInfo> comparator : comparators) {
                int cmp = comparator.compare(o1, o2);
                if (cmp != 0) {
                    return cmp;
                }
            }
            return 0;
        }
    });

    return travelInfo.get(0).getName();

There is a difference though with your original code: this will never return a "Tie". But I didn't see that mentioned in the specs anyway. It seems that after the tie breaker conditions 1-2-3 are evaluated, there should always be a clear winner.

If that's not the case, you can adapt this code to handle that, by saving the anonymous composite comparator to an instance, and use that instance to compare the first two winners. If they are equal, it's a tie.

Answer 2

In main you can use the more concise syntax

String[][] trips = {
  { "Person A", "City 1" },
  { "Person A", "City 2" },
  { "Person B", "City 1" },
  { "Person B", "City 3" },
  { "Person B", "City 3" },
  { "Person B", "City 4" },
  { "Person B", "City 4" },
  { "Person C", "City 1" },
  { "Person C", "City 2" },
  { "Person C", "City 2" },
  { "Person C", "City 2" },
  { "Person C", "City 4" }
};