CODEWITHSUNDEEP
javaarraysarraylist
RShome
RShome

Reputation: 537

How can I implement a function to return true if array or arrayList refers to a previous element?

A playlist is considered a repeating playlist if any of the songs contain a reference to a previous song in the playlist. Otherwise, the playlist will end with the last song which points to null.

I need to Implement a function isRepeatingPlaylist that, returns true if a playlist is repeating or false if it is not.

For example, the following code prints "true" as both songs point to each other.

Song first = new Song("Hello");
Song second = new Song("Eye of the tiger");    
first.setNextSong(second);
second.setNextSong(first);    
System.out.println(first.isRepeatingPlaylist());

Again, this is not a homework exercise, I am doing coding challenges because when I read theory about programming concepts, I can almost understand, but when faced with writing a program I don't know where to start, or how to apply. 

public class Song {

    private String name;
    private Song nextSong;

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

    public void setNextSong(Song nextSong) {
        this.nextSong = nextSong;
    }

    public boolean isRepeatingPlaylist() {
        //throw new UnsupportedOperationException("Waiting to be implemented.");
        List<String> list = new ArrayList<String>();
        list.add(one);
        list.add(two);
        list.add(three);
        list.add(four);

        if list.contains()
        return true;
        else
            return false;

    }

    public static void main(String[] args) {
        Song first = new Song("Hello");
        Song second = new Song("Eye of the tiger");
        Song third = new Song("a test");
        Song fourth = new Song("survivor");

        first.setNextSong(second);
        second.setNextSong(first);

        System.out.println(first.isRepeatingPlaylist();
    }
}

Upvotes: 7

Views: 7958

Answers (8)

xubo peng
xubo peng

Reputation: 1

This is my c++ code, it runs greatly!

#include <stdexcept>
#include <iostream>
#include <string>
#include <set>
using namespace std;

class Song
{
public:
    Song(std::string name): name(name), nextSong(NULL) {}

    void next(Song* song)
    {
        this->nextSong = song;
    }

    bool isRepeatingPlaylist()

    {

        set<string> playlist;
        Song *temp=this;
        while(temp->nextSong!=NULL){
            if (!playlist.insert(temp->name).second) return true;
             temp=temp->nextSong;
        }
        return false;

    }

private:
    const std::string name;
    Song* nextSong;
};

#ifndef RunTests
int main()
{
    Song* first = new Song("Hello");
    Song* second = new Song("Eye of the tiger");

    first->next(second);
    second->next(first);

    std::cout << std::boolalpha << first->isRepeatingPlaylist();
}
#endif  */

Upvotes: -1

Alexander Borisov
Alexander Borisov

Reputation: 21

Please check the answer below:

using System.Collections.Generic;


public bool IsRepeatingPlaylist()
{
    HashSet<Song> songs = new HashSet<Song>();
    Song current = this;
    while (current.NextSong != null && !songs.Contains(current.NextSong))
    {
        songs.Add(current);
        current = current.NextSong;
    }
    return songs.Contains(current.NextSong);
}

Upvotes: 0

Mehdi M
Mehdi M

Reputation: 70

I used this code, it will work but the site tells that it is not correct. Is it ok to add another int member to the class?

public class Song {
private String name;
private Song nextSong;
private int rep = 0 ;

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

public void setNextSong(Song nextSong) {
    this.nextSong = nextSong;
}

public boolean isRepeatingPlaylist() {
    if (this.nextSong == null){
        return false;
    } else {
        rep++;
        if (rep > 1){
            return true;
        }
        return this.nextSong.isRepeatingPlaylist();
    }

}

public static void main(String[] args) {
    Song first = new Song("Hello");
    Song second = new Song("Eye of the tiger");



    first.setNextSong(second );
    second.setNextSong(first );

    System.out.println(first.isRepeatingPlaylist());
}

}

Upvotes: 0

Champ-Java
Champ-Java

Reputation: 121

Please check the answer below: 

    public boolean isRepeatingPlaylist() {
                Song slow = this.nextSong;
                Song fast = slow == null ? null : slow.nextSong;
                while (fast != null) {
                    if (slow == this || slow == fast)
                        return true;
                    slow = slow.nextSong;
                    fast = fast.nextSong;
                    if (fast != null)
                        fast = fast.nextSong;
                }
                return false;
            }

Upvotes: 4

Sabir Khan
Sabir Khan

Reputation: 10142

  1. The issue with most answers ( esp. one by Conffusion ) is that its not talking about hasCode() & equals(...) method for Song class even though approach is correct. uniqueSongs.contains will not give correct result if these two methods are not properly implemented.

OP has also not shown structure of Song class.

  1. Second thing in code samples of OP is that which class should have which responsibility is not clear & if I already have a custom linkedlist then Java ArrayList won't be needed - though I have added both versions. Use of words - array & arrayList in question title is confusing because OP has a traditional LinkedList & that has noting to do with Java while arrayList is a Java specific DS.

    public class Song {

    private String data;
private Song nextSong;

public Song(String data) {
    this.data=data;
}

public String getData() {
    return data;
}

public void setData(String data) {
    this.data = data;
}

public Song getNextSong() {
    return nextSong;
}

public void setNextSong(Song nextSong) {
    this.nextSong = nextSong;
}


@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((data == null) ? 0 : data.hashCode());
    return result;
}


@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Song other = (Song) obj;
    if (data == null) {
        if (other.data != null)
            return false;
    } else if (!data.equals(other.data)) {
        return false;
    }
    return true;
}

    }

Ideally , there should be a PlayList class to create playlist and method isRepeatingPlaylist should belong there. I have added in main driver class for simplicity , 

    import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;

    public class RepetablePlaylist {

        public static void main(String[] args) {

            // Begin - construct Song list 
            Song first = new Song("Hello");
            Song second = new Song("Eye of the tiger");
            Song third = new Song("a test");
            Song fourth = new Song("survivor");

            first.setNextSong(second);
            second.setNextSong(first);

            List<Song> list = new ArrayList<>();
            list.add(first);
            list.add(second);
            list.add(third);
            list.add(fourth);
            // End - construct Song list 

            boolean isRepeatable = isRepeatingPlaylist(list);
            System.out.println(" isRepeatable : "+isRepeatable);

isRepeatable = isRepeatingPlaylist(first);
        System.out.println(" isRepeatable : "+isRepeatable);
        }

         private static boolean isRepeatingPlaylist(List<Song> playList) {
             Set<Song> previous = new HashSet<>();
             for(Song song : playList) {
                 if(song.getNextSong() != null && previous.contains(song.getNextSong())) {
                     return true;
                 }
                 previous.add(song);
             }
             return false;
         }

private static boolean isRepeatingPlaylist(Song head) {
         Set<Song> previous = new HashSet<>();
         Song currentNode = head;
         while(currentNode.getNextSong() != null ) {
             if(previous.contains(currentNode.getNextSong())) {
                 return true;
             }
             previous.add(currentNode);
             currentNode=currentNode.getNextSong();
         }
         return false;
     }
    }

Upvotes: 1

TongChen
TongChen

Reputation: 1430

This problem can be consider the classic problem: linked list has a circle or not.You can find method from here to solve but for your it's not easy to construct linked list，we use another method to solve this problem：count the nextSong,code like this:

public static boolean isRepeatingPlaylist(List<Song> songs) {
    int counts = 0;
    for (Song song : songs) {
        if (null !=song.getNextSong()){
            counts ++;
        }
    }
    return songs.size() - counts != 1;
}

Upvotes: 1

Henrique Sabino
Henrique Sabino

Reputation: 545

I think this might work:

public boolean isRepeatingPlaylist() 
{
    Set<Song> songs = new HashSet<Song>();
    songs.add(this);
    Song current = this.getNextSong();
    //if you did not implment a getter for the nextSong property I think you should
    while (current.getNextSong() != null && !songs.contains(current.getNextsong())) {

        songs.add(current);
        current = current.getNextSong();
    }

    return songs.contains(current.getNextsong()); 
}

Edit 1: As mentioned in the comments of this answer, the == in some cases might not be the best because it compares the memory location of each object. In order to fix this issue, implementing the methods hashCode() and equals() are recommended, if you don't know what they are, try reading this.

Upvotes: 1

Conffusion
Conffusion

Reputation: 4475

You can loop through the playlist and add every song to a set on condition it is not yet in the set. Once you reach the end of the list your list is not a repeating list. If you find a song which exists already in the set, you have a repeating list.

public boolean isRepeatingList(Song firstSong)
{
    Set<Song> uniqueSongs=new HashSet<>();
    uniqueSongs.add(firstSong);
    Song current=firstSong;
    while(current.getNextSong()!=null)
    {
        if(uniqueSongs.contains(current.getNextSong()))
            return true;
        // add the song to the set, and assign current to the next song
        uniqueSongs.add(current=current.getNextSong());
    }
    // we reached the end of the list without finding any doubles, so:
    return false;
}

Upvotes: 2

Related Questions