Amazon Online Assessment (OA) - Favorite Genres

Given a map Map<String, List<String>> userSongs with user names as keys and a list of all the songs that the user has listened to as values.

Also given a map Map<String, List<String>> songGenres, with song genre as keys and a list of all the songs within that genre as values. A song can only belong to one genre.

The task is to return a map Map<String, List<String>>, where the key is a user name and the value is a list of the user's favorite genre(s). Favorite genre is the most listened to genre. A user can have more than one favorite genre if he/she has listened to the same number of songs per each of the genres.

Examples

Example 1:

Input:

1userSongs = {
2 "David": ["song1", "song2", "song3", "song4", "song8"],
3 "Emma":  ["song5", "song6", "song7"]
4}
5songGenres = {
6    "Rock":    ["song1", "song3"],
7    "Dubstep": ["song7"],
8    "Techno":  ["song2", "song4"],
9    "Pop":     ["song5", "song6"],
10    "Jazz":    ["song8", "song9"]
11}

Output:

1{
2 "David": ["Rock", "Techno"],
3 "Emma":  ["Pop"]
4}

Explanation:

David has 2 Rock, 2 Techno and 1 Jazz songs. So, he has 2 favorite genres. Emma has 2 Pop and 1 Dubstep songs. Pop is Emma's favorite genre.

Example 2:

Input:

1userSongs = {
2 "David": ["song1", "song2"],
3 "Emma":  ["song3", "song4"]
4},
5songGenres = {}

Output:

1{
2 "David": [],
3 "Emma":  []
4}

Try it yourself

1from collections import Counter
2from heapq import heapify, heappop
3from typing import Dict, List
4
5
6def top(items):
7    h = [(-c, s) for s, c in Counter(items).items()]
8    if len(h) == 0:
9        return
10    heapify(h)
11    tc, ts = heappop(h)
12    yield ts
13    while h:
14        c, s = heappop(h)
15        if c != tc:
16            break
17        yield s
18
19
20def favorite_genres(
21        user_songs: Dict[str, List[str]],
22        genre_songs: Dict[str, List[str]],
23) -> Dict[str, List[str]]:
24    '''
25    >>> favorite_genres({
26    ...     "David": ["song1", "song2", "song3", "song4", "song8"],
27    ...     "Emma":  ["song5", "song6", "song7"]
28    ... }, {
29    ...     "Rock":    ["song1", "song3"],
30    ...     "Dubstep": ["song7"],
31    ...     "Techno":  ["song2", "song4"],
32    ...     "Pop":     ["song5", "song6"],
33    ...     "Jazz":    ["song8", "song9"]
34    ... })
35    {'David': ['Rock', 'Techno'], 'Emma': ['Pop']}
36    >>> favorite_genres({
37    ...     "David": ["song1", "song2"],
38    ...     "Emma":  ["song3", "song4"]
39    ... }, {})
40    {'David': [], 'Emma': []}
41    '''
42
43    song_genres = {
44        s: g
45        for g, ss in genre_songs.items()
46        for s in ss
47    }
48    return {
49        u: list(top(song_genres[s] for s in ss))
50        for u, ss in user_songs.items()
51    }
52
53
54if __name__ == '__main__':
55    import doctest
56    doctest.testmod()