Top Recommended Song


  • 0
    N

    Given a song, return the recommended song with the highest rating. A recommendation can be any song within the network of similarities. (for example, similarities of similarities, etc)

    function getTopRecommendedSong(song) {
    }
    

    Example:

    songA = {
    rating: 2.0,
    similarities: [songB, songC, songD]
    }

    songB is similar to songA, songE, songF

    songC is similar to .....

    songD is similar to .....

    songE is similar to songF

    getTopRecommendedSong(songA) = songD


  • 1
    V

    Simply DFS/BFS in this graph.

    Here's solution with DFS-

    private Song getTopRec(Song song)
    {
    	HashSet<Song> visited = new HashSet<Song>();
    	visited.add(song);
    	return helper(song, visited);
    }
    
    private Song helper(Song song, Set<Song> visited)
    {
    	Song top = song;
    	for (Song s : song.similar)
    	{
    		if (!visited.contains(s))
    		{
    			visited.add(s);
    			Song result = helper(s, visited);
    			if (result.rating > top.rating)
    			{
    				top = result;
    			}
    		}
    	}
    	
    	return top;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.