Calculate the Minimal Degrees of Separation Between Two Actors

Got this question in one of my interviews, even though my overall approach was right, I still didn't pass the interview because some of details can be improved. Below is my code.

import java.util.Arrays;

import java.util.HashMap;

import java.util.HashSet;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Queue;

import java.util.Set;

class Solution { 

  public static Map<Integer, String> moviesMap = new HashMap<>();

  public static Map<Integer, String> actorsMap = new HashMap<>();

  public static Map<Integer, Set<Integer>> moviesWithSameActorMap = new HashMap<>();

  public static Map<Integer, Set<Integer>> actorsInSameMovieMap = new HashMap<>();

  

  public static void main(String[] args) 

    { 

      loadData();

  

      System.out.println(getDegreesBetween(1,7));

      System.out.println(getDegreesStringBetween(1,7));

      System.out.println(getDegreesBetween(1,25));

      System.out.println(getDegreesStringBetween(1,25));

      System.out.println(getDegreesBetween(1,34));

      System.out.println(getDegreesStringBetween(1,34));

      

    } 

    

    public static Integer getDegreesBetween(Integer actorId1, Integer actorId2) {

      Queue<ActorDegreeNode> queue = new LinkedList<>();

      Set<Integer> visited = new HashSet<>();

      List<Integer> head = new LinkedList<>();

      head.add(actorId1);

      queue.add(new ActorDegreeNode(actorId1, 1, head));

      visited.add(actorId1);

      

      int actorId;

      int currentDegree = 0;

      ActorDegreeNode node;

      while(!queue.isEmpty()) {

        node = queue.poll();

        actorId = node.actorId;

        currentDegree = node.degree;

        Set<Integer> movies = moviesWithSameActorMap.get(actorId);

        Set<Integer> connectedActors = new HashSet<>();

          for(Integer i : movies) {

            if(actorsInSameMovieMap.get(i).contains(actorId2)) {

              return currentDegree;

            }

            connectedActors.addAll(actorsInSameMovieMap.get(i));

          }

          

          for(Integer actor:connectedActors) {

            if(!visited.contains(actor)) {

              List<Integer> path = new LinkedList<>(node.path);

                  path.add(actor);

              visited.add(actor);

              queue.add(new ActorDegreeNode(actor,currentDegree + 1, path));

            }

          }

      }

      

      return -1;

    }

     

  public static String pathString(List<Integer> path) {

    

    StringBuilder sb = new StringBuilder();

    String seperator = "";

    Integer prevActorId = 0;

    String movieName = "";

    for(Integer p:path) {

      if(prevActorId > 0 && p > 0) {

        movieName = findCommonMovieInActorIds(prevActorId, p);

        seperator = "->" + movieName + "->";

      }

      sb.append(seperator).append(actorsMap.get(p));

      prevActorId = p;

    }

    return sb.toString();

  }

  

  public static String findCommonMovieInActorIds(Integer id1, Integer id2) {

    String movieName = "";

    for(Map.Entry<Integer, Set<Integer>> entry : actorsInSameMovieMap.entrySet()) {

      if(entry.getValue().contains(id1) && entry.getValue().contains(id2))

        movieName = moviesMap.get(entry.getKey());

    }

    return movieName;

  }

  

    public static String getDegreesStringBetween(Integer actorId1, Integer actorId2) {

      Queue<ActorDegreeNode> queue = new LinkedList<>();

      Set<Integer> visited = new HashSet<>();

      List<Integer> head = new LinkedList<>();

      head.add(actorId1);

      queue.add(new ActorDegreeNode(actorId1, 1, head));

      visited.add(actorId1);

      

      int actorId;

      int currentDegree = 0;

      ActorDegreeNode node;

      while(!queue.isEmpty()) {

        node = queue.poll();

        actorId = node.actorId;

        currentDegree = node.degree;

        Set<Integer> movies = moviesWithSameActorMap.get(actorId);

        Set<Integer> connectedActors = new HashSet<>();

          for(Integer i : movies) {

            if(actorsInSameMovieMap.get(i).contains(actorId2)) {

              node.path.add(actorId2);

              return pathString(node.path);

            }

            connectedActors.addAll(actorsInSameMovieMap.get(i));

          }

          

          for(Integer actor:connectedActors) {

            if(!visited.contains(actor)) {

              List<Integer> path = new LinkedList<>(node.path);

                  path.add(actor);

              visited.add(actor);

              queue.add(new ActorDegreeNode(actor,currentDegree + 1, path));

            }

          }

      }

      

      return "";

    }

    

    public static void loadMoviesMap() {

      moviesMap.put(1, "GoldenEye");

      moviesMap.put(2, "Mama Mia!");

      moviesMap.put(3, "Good Will Hunting");

      moviesMap.put(4, "Ronin");

      moviesMap.put(5, "Awakenings");

      moviesMap.put(6, "Adaptation");

      moviesMap.put(7, "National Treasure");

      moviesMap.put(8, "Mission: Impossible");

    }

    

    public static void loadActorsMap() {

      actorsMap.put(1, "Pierce Brosnan");

      actorsMap.put(2, "Sean Bean");

      actorsMap.put(3, "Izabella Scorupco");

      actorsMap.put(4, "Judi Dench");

      actorsMap.put(5, "Desmond Llewelyn");

      actorsMap.put(6, "Minnie Driver");

      actorsMap.put(7, "Meryl Streep");

      actorsMap.put(8, "Amanda Seyfried");

      actorsMap.put(9, "Colin Firth");

      actorsMap.put(10, "Stellan Skarsgard");

      actorsMap.put(11, "Matt Damon");

      actorsMap.put(12, "Robin Williams");

      actorsMap.put(13, "Ben Affleck");

      actorsMap.put(14, "Robert De Niro");

      actorsMap.put(15, "Jean Reno");

      actorsMap.put(16, "Natascha McElhone");

      actorsMap.put(17, "Jonathan Pryce");

      actorsMap.put(18, "Julie Kavner");

      actorsMap.put(19, "John Heard");

      actorsMap.put(20, "Penelope Ann Miller");

      actorsMap.put(21, "Max von Sydow");

      actorsMap.put(22,"Nicolas Cage");

      actorsMap.put(23,"Chris Cooper");

      actorsMap.put(24,"Cara Seymour");

      actorsMap.put(25,"Tilda Swinton");

      actorsMap.put(26,"Ron Livingston");

      actorsMap.put(27,"Maggie Gyllenhaal");

      actorsMap.put(28,"Judy Greer");

      actorsMap.put(29,"Harvey Keitel");

      actorsMap.put(30,"Jon Voight");

      actorsMap.put(31,"Justin Bartha");

      actorsMap.put(32,"Diane Kruger");

      actorsMap.put(33,"Christopher Plummer");

      actorsMap.put(34,"Tom Cruise");

      actorsMap.put(35,"Emmanuelle Beart");

      actorsMap.put(36,"Ving Rhames");

      actorsMap.put(37,"Vanessa Redgrave");

      actorsMap.put(38, "Henry Czerny");

      actorsMap.put(39, "Emilio Estevez");

    }

    

    public static void loadActorsInSameMovieMap() {

      actorsInSameMovieMap.put(1, new HashSet<>(Arrays.asList(1,2,3,4,5,6)));

      actorsInSameMovieMap.put(2, new HashSet<>(Arrays.asList(7,8,1,9,10)));

      actorsInSameMovieMap.put(3, new HashSet<>(Arrays.asList(11,12,13,10,6)));

      actorsInSameMovieMap.put(4, new HashSet<>(Arrays.asList(14,15,16,2,10,17)));

      actorsInSameMovieMap.put(5, new HashSet<>(Arrays.asList(12,14,18,19,20,21)));

      actorsInSameMovieMap.put(6, new HashSet<>(Arrays.asList(22,7,23,24,25,26,27,28)));

      actorsInSameMovieMap.put(7, new HashSet<>(Arrays.asList(22,2,29,30,31,32,33)));

      actorsInSameMovieMap.put(8, new HashSet<>(Arrays.asList(34,30,35,36,37,38,15,39)));

    }

    

    public static void loadMoviesWithSameActorMap() {

      moviesWithSameActorMap.put(1, new HashSet<>(Arrays.asList(1,2)));

      moviesWithSameActorMap.put(2, new HashSet<>(Arrays.asList(1,4,7)));

      moviesWithSameActorMap.put(3, new HashSet<>(Arrays.asList(1)));

      moviesWithSameActorMap.put(4, new HashSet<>(Arrays.asList(1)));

      moviesWithSameActorMap.put(5, new HashSet<>(Arrays.asList(1)));

      moviesWithSameActorMap.put(6, new HashSet<>(Arrays.asList(1,3)));

      moviesWithSameActorMap.put(7, new HashSet<>(Arrays.asList(2,6)));

      moviesWithSameActorMap.put(8, new HashSet<>(Arrays.asList(2)));

      moviesWithSameActorMap.put(9, new HashSet<>(Arrays.asList(2)));

      moviesWithSameActorMap.put(10, new HashSet<>(Arrays.asList(2,3,4)));

      moviesWithSameActorMap.put(11, new HashSet<>(Arrays.asList(3)));

      moviesWithSameActorMap.put(12, new HashSet<>(Arrays.asList(3,5)));

      moviesWithSameActorMap.put(13, new HashSet<>(Arrays.asList(3)));

      moviesWithSameActorMap.put(14, new HashSet<>(Arrays.asList(4,5)));

      moviesWithSameActorMap.put(15, new HashSet<>(Arrays.asList(4,8)));

      moviesWithSameActorMap.put(16, new HashSet<>(Arrays.asList(4)));

      moviesWithSameActorMap.put(17, new HashSet<>(Arrays.asList(4)));

      moviesWithSameActorMap.put(18, new HashSet<>(Arrays.asList(5)));

      moviesWithSameActorMap.put(19, new HashSet<>(Arrays.asList(5)));

      moviesWithSameActorMap.put(20, new HashSet<>(Arrays.asList(5)));

      moviesWithSameActorMap.put(21, new HashSet<>(Arrays.asList(5)));

      moviesWithSameActorMap.put(22, new HashSet<>(Arrays.asList(6,7)));

      moviesWithSameActorMap.put(23, new HashSet<>(Arrays.asList(6)));

      moviesWithSameActorMap.put(24, new HashSet<>(Arrays.asList(6)));

      moviesWithSameActorMap.put(25, new HashSet<>(Arrays.asList(6)));

      moviesWithSameActorMap.put(26, new HashSet<>(Arrays.asList(6)));

      moviesWithSameActorMap.put(27, new HashSet<>(Arrays.asList(6)));

      moviesWithSameActorMap.put(28, new HashSet<>(Arrays.asList(6)));

      moviesWithSameActorMap.put(29, new HashSet<>(Arrays.asList(7)));

      moviesWithSameActorMap.put(30, new HashSet<>(Arrays.asList(7,8)));

      moviesWithSameActorMap.put(31, new HashSet<>(Arrays.asList(7)));

      moviesWithSameActorMap.put(32, new HashSet<>(Arrays.asList(7)));

      moviesWithSameActorMap.put(33, new HashSet<>(Arrays.asList(7)));

      moviesWithSameActorMap.put(34, new HashSet<>(Arrays.asList(8)));

      moviesWithSameActorMap.put(35, new HashSet<>(Arrays.asList(8)));

      moviesWithSameActorMap.put(36, new HashSet<>(Arrays.asList(8)));

      moviesWithSameActorMap.put(37, new HashSet<>(Arrays.asList(8)));

      moviesWithSameActorMap.put(38, new HashSet<>(Arrays.asList(8)));

      moviesWithSameActorMap.put(39, new HashSet<>(Arrays.asList(8)));

    }

    

    public static void loadData() {

      

      loadMoviesMap();

      

      loadActorsMap();

      

      loadActorsInSameMovieMap();

      

      loadMoviesWithSameActorMap();

    }

    

}

class ActorDegreeNode{

  Integer actorId;

  Integer degree;

  List<Integer> path = new LinkedList<>();

  

  public ActorDegreeNode(Integer actorId, Integer degree, List<Integer> path) {

    this.actorId=actorId;

    this.degree=degree;

    this.path=path;

  }

  

}

 

JS Version

 

var Mocha = require('mocha');
var assert = require('assert');
var mocha = new Mocha();

mocha.suite.emit('pre-require', this, 'solution', mocha);

describe('Test Cases', function() {

  it('input data parsed correctly', function() {
    var movies = new MovieData();
    assert.equal(movies.getTitles().length, 8);
  });

  it('Brosnan -> Streep number of degrees', function() {
    var movies = new MovieData();
    var brosnan = "Pierce Brosnan";
    var streep = "Meryl Streep";
    assert.equal(movies.getDegreesBetween(brosnan, streep), 1);
  });

  it('Brosnan -> Streep degrees string', function() {
    var movies = new MovieData();
    var brosnan = "Pierce Brosnan";
    var streep = "Meryl Streep";
    var expected = "Pierce Brosnan was in Mama Mia! with Meryl Streep";
    assert.equal(movies.getDegreesStringBetween(brosnan, streep), expected);
  });

  it('Brosnan -> Swinton number of degrees', function() {
    var movies = new MovieData();
    var brosnan = "Pierce Brosnan";
    var swinton = "Tilda Swinton";
    assert.equal(movies.getDegreesBetween(brosnan, swinton), 2);
  });

  it('Brosnan -> Swinton degrees string', function() {
    var movies = new MovieData();
    var brosnan = "Pierce Brosnan";
    var swinton = "Tilda Swinton";
    var expected = "Pierce Brosnan was in Mama Mia! with Meryl Streep, who was in Adaptation with Tilda Swinton";
    assert.equal(movies.getDegreesStringBetween(brosnan, swinton), expected);
  });
 
  it('Estevez -> Sydow number of degrees', function() {
    var movies = new MovieData();
    var estevez = "Emilio Estevez";
    var sydow = "Max von Sydow";
    assert.equal(movies.getDegreesBetween(estevez, sydow), 3);
  });

  it('Estevez -> Sydow degrees string', function() {
    var movies = new MovieData();
    var estevez = "Emilio Estevez";
    var sydow = "Max von Sydow";
    var expected = "Emilio Estevez was in Mission: Impossible with Jean Reno, who was in Ronin with Robert De Niro, who was in Awakenings with Max von Sydow";
    assert.equal(movies.getDegreesStringBetween(estevez, sydow), expected);
  });
 
  it('Brosnan -> Me number of degrees', function() {
    var movies = new MovieData();
    var brosnan = "Pierce Brosnan";
    var me = "Ryan Ye";
    assert.equal(movies.getDegreesBetween(brosnan, me), -1);
  });

  it('Brosnan -> Me degrees string', function() {
    var movies = new MovieData();
    var brosnan = "Pierce Brosnan";
    var me = "Ryan Ye";
    var expected = "Pierce Brosnan and Ryan Ye are not connected";
    assert.equal(movies.getDegreesStringBetween(brosnan, me), expected);
  });

});



class MovieData {

  data;

  getTitles = function() {
    return this.data.map(x => x.title);
  };

  getDegreesBetween = function(actor1, actor2) {
    var queue = [];
    var actorNode = {actor: actor1, degree:0}
    var connectedActors = new Set();
    queue.push(actorNode);
    while(queue.length > 0){
      actorNode = queue.shift();
      var actor = actorNode.actor;
      var currentDegree = actorNode.degree;
      
      var directConnectedActors = new Set(this.data.filter(x => x.actors.includes(actor)).map(x => x.actors).flat().filter(x => x !== actor));
      
      for (var it = directConnectedActors.values(), val= null; val=it.next().value; ) {
        if( val === actor2){
          return currentDegree+1;
        }
        
        if(!connectedActors.has(val)){
          connectedActors.add(val);
          var newNode = {actor: val, degree: currentDegree + 1};
          queue.push(newNode);
        }
      }
    }
    return -1;
  };
 
  printPath = function(path) {
    var pathElements = path.split("->");
    var outputPath="";
    for(var i = 0, j = pathElements.length; i < j; i=i+2){
      if(i === j-1){
        return `${outputPath}${pathElements[i]}`;
      }
      outputPath = `${outputPath}${pathElements[i]}${i === 0 ? " was in " : ", who was in "}${pathElements[i+1]} with `;
    }
    return outputPath;
  }

  getDegreesStringBetween = function(actor1, actor2) {
    var queue = [];
    var actorPathNode = {actor:actor1, path:actor1}
    var connectedActors = new Set();
    queue.push(actorPathNode);
    while(queue.length > 0){
      actorPathNode = queue.shift();
      var actor = actorPathNode.actor;
      var currentPath = actorPathNode.path;
      var movieDataWithActor = this.data.filter(x => x.actors.includes(actor));
      
      for(var i=0, j=movieDataWithActor.length; i < j; i++){
        var movieData = movieDataWithActor[i];
        var movieTitle = movieData.title;
        var actorList = movieData.actors.filter(x => x !== actor);
        
        for(var l=0, k=actorList.length; l < k; l++){
          var val = actorList[l];
          if( val === actor2){
            return this.printPath(currentPath + "->" + movieTitle + "->" + val);
          }
        
          if(!connectedActors.has(val)){
            connectedActors.add(val);
            var newPathNode = {actor:val, path:currentPath + "->" + movieTitle + "->" + val}
            queue.push(newPathNode);
          }
        }
      }
    }
    return `${actor1} and ${actor2} are not connected`;
  };
 

  constructor() {
    var inputText = getMovieDataInput();
    var inputArray = inputText.split(/\r?\n/);

    var parsedMoviesArray = new Array();

    var MOVIE = "MOVIE";
    var ACTOR = "ACTOR";
    var nextType = MOVIE;
    var currentMovie;

    inputArray.forEach(line => {
      if (line) {
        if (nextType === MOVIE) {
          // movie title -> next line will be an actor's name
          currentMovie = {};
          currentMovie.title = line;
          currentMovie.actors = new Array();
          parsedMoviesArray.push(currentMovie);
          nextType = ACTOR;
        }
        else {
          // actor's name
          currentMovie.actors.push(line);
        }
      }
      else {
        // blank line -> next line will be a movie title
        nextType = MOVIE;
      }
    });
    this.data = parsedMoviesArray;
   
  }
}

function getMovieDataInput() {
return `
GoldenEye
Pierce Brosnan
Sean Bean
Izabella Scorupco
Judi Dench
Desmond Llewelyn
Minnie Driver

Mama Mia!
Meryl Streep
Amanda Seyfried
Pierce Brosnan
Colin Firth
Stellan Skarsgard

Good Will Hunting
Matt Damon
Robin Williams
Ben Affleck
Stellan Skarsgard
Minnie Driver

Ronin
Robert De Niro
Jean Reno
Natascha McElhone
Sean Bean
Stellan Skarsgard
Jonathan Pryce

Awakenings
Robin Williams
Robert De Niro
Julie Kavner
John Heard
Penelope Ann Miller
Max von Sydow

Adaptation
Nicolas Cage
Meryl Streep
Chris Cooper
Cara Seymour
Tilda Swinton
Ron Livingston
Maggie Gyllenhaal
Judy Greer

National Treasure
Nicolas Cage
Sean Bean
Harvey Keitel
Jon Voight
Justin Bartha
Diane Kruger
Christopher Plummer

Mission: Impossible
Tom Cruise
Jon Voight
Emmanuelle Beart
Ving Rhames
Vanessa Redgrave
Henry Czerny
Jean Reno
Emilio Estevez
`;
}

mocha.run();