CodingGyan

Copying a Playlist: Deep Copy

medium Object-Oriented Programming

Problem

A playlist has tracks, and each track has a title and a play count (it starts at 0). Commands: new P (an empty playlist), add P TITLE (add a track), play P TITLE (add 1 to the play count of that track in P; nothing happens if the title is not in P), copy P Q (Q becomes a copy of P), show P (print P: then the tracks as title(count) with single spaces, or empty). After a copy the two playlists must be completely independent.

Constraints

  • 1 <= commands <= 100
  • names and titles have no spaces

Examples

Input

new a
add a s
copy a b
play b s
show a
show b

Output

a: s(0)
b: s(1)

Solutions

Best approachTime O(total tracks)Space O(total tracks)

A shallow copy only copies the list, not the Track objects inside, so both playlists point to the same tracks. A deep copy makes a new Track for every old one, and then the copies cannot influence each other.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Run the commands.
 * Input   : Command lines.
 * Output  : One line per answer.
 * Approach: Copy constructor
 * Time    : O(total tracks)
 * Space   : O(total tracks)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A Track is a mutable object. If two playlists shared the same Track, a play in one would show up in the other.
        static class Track {
            final String title;
            int plays;

            Track(String title, int plays) {
                this.title = title;
                this.plays = plays;
            }
        }

        static class Playlist {
            final java.util.List<Track> tracks = new java.util.ArrayList<>();

            Playlist() {
            }

            // Step 2: The copy constructor makes a new Track for every old Track. This is a deep copy.
            Playlist(Playlist other) {
                for (Track track : other.tracks) {
                    tracks.add(new Track(track.title, track.plays));
                }
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        java.util.Map<String, Playlist> lists = new java.util.HashMap<String, Playlist>();
        java.util.List<String> out = new java.util.ArrayList<String>();
        for (String line : lines) {
            String[] part = line.split(" ");
            if (part[0].equals("new")) {
                lists.put(part[1], new Playlist());
            } else if (part[0].equals("add")) {
                lists.get(part[1]).tracks.add(new Track(part[2], 0));
            } else if (part[0].equals("play")) {
                for (Track track : lists.get(part[1]).tracks) {
                    if (track.title.equals(part[2])) {
                        track.plays++;
                    }
                }
            } else if (part[0].equals("copy")) {
                lists.put(part[2], new Playlist(lists.get(part[1])));
            } else {
                StringBuilder text = new StringBuilder(part[1] + ":");
                java.util.List<Track> tracks = lists.get(part[1]).tracks;
                if (tracks.isEmpty()) {
                    text.append(" empty");
                }
                for (Track track : tracks) {
                    text.append(" ").append(track.title).append("(").append(track.plays).append(")");
                }
                out.add(text.toString());
            }
        }
        return out.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (2)
  1. What does a shallow copy share?
  2. What must a deep copy create?