Description: https://leetcode.com/discuss/interview-question/373006 Leetcode playground: https://leetcode.com/playground/5QpmuQti

FavoriteGenre.java

// https://leetcode.com/discuss/interview-question/373006
// Hash table solution
// Time: O(s + u), s: # of <song, genre> mapping, u: # of songs like by all users
// Space: O(s): s: # of <song, genre> mapping
public class Main {
    public static Map<String, List<String>> favoriteGenre(Map<String, List<String>> userMap, Map<String, List<String>> genreMap) {
        Map<String, List<String>> ans = new HashMap<>();
        
        // Build a song to genre map
        Map<String, String> songToGenre = new HashMap<>();
        if(genreMap != null) {
            for(String genre : genreMap.keySet()) {
                List<String> songs = genreMap.get(genre);
                if(songs == null) continue; // Edge case: song without any genre
                for(String song : songs) {
                    songToGenre.put(song, genre);
                }
            }
        }
        
        // Count freq of genre for each user
        Map<String, Integer> freq = new HashMap<>();
        if(userMap != null) {
            for(String user : userMap.keySet()) {
                // Count freq
                freq.clear();
                List<String> songs = userMap.get(user);
                int max = 0;
                for(String song : songs) {
                    String genre = songToGenre.get(song);
                    if(genre == null) continue; // Edge case: song without any genre
                    int f = freq.getOrDefault(genre, 0) + 1;
                    freq.put(genre, f);
                    max = Math.max(max, f);
                }

                // Put max genre(s) into the ans
                List<String> genres = new ArrayList<>();
                for(String genre : freq.keySet()) {
                    if(freq.get(genre) == max) {
                        genres.add(genre);
                    }
                }
                ans.put(user, genres);
            }
        }
        
        return ans;
    }
    
    public static void main(String[] args) {
        Map<String, List<String>> userMap1 = new HashMap<>();
        userMap1.put("David", Arrays.asList("song1", "song2", "song3", "song4", "song8"));
        userMap1.put("Emma", Arrays.asList("song5", "song6", "song7"));
        Map<String, List<String>> genreMap1 = new HashMap<>();
        genreMap1.put("Rock", Arrays.asList("song1", "song3"));
        genreMap1.put("Dubstep", Arrays.asList("song7"));
        genreMap1.put("Techno", Arrays.asList("song2", "song4"));
        genreMap1.put("Pop", Arrays.asList("song5", "song6"));
        genreMap1.put("Jazz", Arrays.asList("song8", "song9"));
        for(Map.Entry<String, List<String>> entry : favoriteGenre(userMap1, genreMap1).entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        System.out.println(" ");
        
        Map<String, List<String>> userMap2 = new HashMap<>();
        userMap2.put("David", Arrays.asList("song1", "song2"));
        userMap2.put("Emma", Arrays.asList("song5", "song6"));
        Map<String, List<String>> genreMap2 = new HashMap<>();
        for(Map.Entry<String, List<String>> entry : favoriteGenre(userMap2, genreMap2).entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        System.out.println(" ");
        
        Map<String, List<String>> userMap3 = new HashMap<>();
        userMap3.put("David", Arrays.asList("song1", "song2", "song3", "song4", "song8"));
        userMap3.put("Emma", Arrays.asList("song5", "song6", "song7"));
        userMap3.put("John", new ArrayList<>());
        userMap3.put("Joe", Arrays.asList("song15", "song16", "song1"));
        Map<String, List<String>> genreMap3 = new HashMap<>();
        genreMap3.put("Rock", Arrays.asList("song1", "song3"));
        genreMap3.put("Dubstep", Arrays.asList("song7"));
        genreMap3.put("Techno", Arrays.asList("song2", "song4"));
        genreMap3.put("Pop", Arrays.asList("song5", "song6"));
        genreMap3.put("Jazz", Arrays.asList("song8", "song9"));
        genreMap3.put("Metal", null);
        genreMap3.put("Rap", new ArrayList<>());
        for(Map.Entry<String, List<String>> entry : favoriteGenre(userMap3, genreMap3).entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        System.out.println(" ");
        
        Map<String, List<String>> userMap4 = new HashMap<>();
        Map<String, List<String>> genreMap4 = new HashMap<>();
        Map<String, List<String>> ans4 = favoriteGenre(userMap4, genreMap4);
        System.out.println(ans4.size());
        for(Map.Entry<String, List<String>> entry : ans4.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        System.out.println(" ");
        
        Map<String, List<String>> ans5 = favoriteGenre(userMap3, null);
        for(Map.Entry<String, List<String>> entry : ans5.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}