CODEWITHSUNDEEP
algorithmdata-structuresframework-design
Thangakumar D
Thangakumar D

Reputation: 774

What is the better data structure to design a class for song play station with my requirement?

I have to come up with a Class and Data Structure Design for a "metric" system to determine the top song of a * band..

The class should have Two Web Service calls 

void play(String bandname, String songname);/*This method has to play song with the requested brandname and songname. Also have to keep track of the song payed count to support the below method.*/

String topSong(String bandname);/* This method has to play mostly played song under the requested brand*/

Sample inputs:
BrandName:"Lady Gaga", Song : "Pokerface";
BrandName:"Lady Gaga", Song : "Pokerface";
BrandName:"Lady Gaga", Song : "Alejandro";
BrandName:"Bruno Mars",Song : "Treasure";

Please advice!

Upvotes: 2

Views: 155

Answers (3)

kmkaplan
kmkaplan

Reputation: 18960

You need two storages.

  1. A dictionnary that maps bandname to it's top songname. Let's call it topBandSong.
  2. A dictionnary that maps (bandname, songname) to the number of times this song has been played. Let's call it bandSongPopularity.

With this topSong is pretty simple (leaving aside the case where nothing is known about the band yet):

Map<String, String> topBandSong = new HashMap();
String topSong(String bandname) {
    return topBandSong.get(bandname);
}

The play function has to update both maps. This is really easy:

Map<String, BigInteger> bandSongPopularity = new HashMap();
void play(String bandname, String songname) {
    /* First update bandSongPopularity */
    String k = bandname + "\000" + songname;
    BigInteger popularity = bandSongPopularity.get(k);
    if (popularity == null) {
        popularity = BigInteger.valueOf(1);
    }
    else {
        popularity = popularity.add(BigInteger.valueOf(1));
    }
    bandSongPopularity.put(k, popularity);
    /* then update topBandSong */
    String top = topSong(bandname);
    if (top == null) {
        topBandSong.put(bandname, songname);
    }
    else {
        String topK = bandname + "\000" + top;
        BigInteger topPopularity = bandSongPopularity.get(topK);
        /* topPopularity can not be NULL */
        if (popularity.compareTo(topPopularity) > 0) {
            topBandSong.put(bandname, songname);
        }
    }
    /* Finally really play this song. But this is left as an exercise ;-) */
}

The complexity is the one of the underlying dictionnary you choose, i.e. a tree or a hash.

Note that the code reserves character number 0.

Upvotes: 0

Shihab Shahriar Khan
Shihab Shahriar Khan

Reputation: 5475

If I understand correctly, you need to maintain a dictionary, where key is band name and value is a priority queue. Each object inside priority queue will have "song name" and "play count" attributes and priority queue needs to be sorted by "play count" attributes. Each time a song is played, increment it's play count and heapify the queue.

Doing the above is a bit complicated and based on programming languages, implementation approach might vary wildly. You shouldn't do this unless the number of songs of a band can be huge, which is pretty unlikely.

Anyway, that's practical implementation detail. The text book answer for questions like these is always priority queue.

Upvotes: 1

Raymond Hettinger
Raymond Hettinger

Reputation: 226524

If kept in memory, this looks like a job for a hash table, associative array, or dictionary. If kept in a persistent store, a database would be the easiest way to go.

Upvotes: 0

Related Questions