Finding N HigestRatedRelatedMovies- Amazon interview coding challenge via HackerRank

Below is a coding question from Amazon interview I had attended in the past. It was through HackerRank which I had to complete within 90 mins. There are now many sites like HackerRank which can be used to screen developers prior to the face to face or telephonic. That saves a lot of time for companies. But there are very less companies using these options including my previous company where I pressed hard to get this into interview process.

I am not copy pasting the question and initial code snippet as is from HackerRank as it may bring this page in case they reuse the question.Instead this version has slight modifications such as using property instead of Java like get methods etc...

Question

• Find highest rated N movies which are related to given movie
• Movie relation is two way
• The result list should not contain the Movie which we start with.
• The highest rated movie can be in any level of relation. 

Basically needs to fill code inside the function below function present in MovieFinder class

getHighestRatedRelatedMovies(Movie root,int numer)

Below is the code snippet. We can have helper methods if required.

---

public class Movie
{
    public int Id { get; private set; }
    public double Rating { get;private set; }
    public IList<Movie> RelatedMovies { get; private set; }
    public Movie(int id,double rating)
    {
        this.Id = id;this.Rating = rating;
        this.RelatedMovies = new List<Movie>();
    }
    public void AddRelatedMovie(Movie movie)
    {
        this.RelatedMovies.Add(movie);
        movie.RelatedMovies.Add(this);
    }
}
public class MovieFinder
{
    public IEnumerable<Movie> getHighestRatedRelatedMovies(Movie root, 

                                                           int numberOfMoviesToSelect)
    {
       //Logic to return appropriate movies
    }
}
class MovieFinderTests
{
    public void Test()
    {
        Movie a = new Movie(1,1.5F);
        Movie b = new Movie(2, 3.5F);
        Movie c = new Movie(3, 2.5F);
        Movie d = new Movie(4, 4.6F);
        a.AddRelatedMovie(b);
        a.AddRelatedMovie(c);
        b.AddRelatedMovie(d);
        c.AddRelatedMovie(d);
 
        Console.WriteLine("getHighestRatedRelatedMovies(a,2) returns Movies 2,4");
        LogMovies(new MovieFinder().getHighestRatedRelatedMovies(a, 2));
        Console.WriteLine("getHighestRatedRelatedMovies(a,1) returns Movie 4");
        LogMovies(new MovieFinder().getHighestRatedRelatedMovies(a, 1));
        Console.WriteLine("getHighestRatedRelatedMovies(a,4) returns Movies 2,3,4");
        LogMovies(new MovieFinder().getHighestRatedRelatedMovies(a, 4));
        Console.WriteLine("getHighestRatedRelatedMovies(c,3) returns Movies 1,2,4");
        LogMovies(new MovieFinder().getHighestRatedRelatedMovies(c, 3));
        Console.WriteLine("getHighestRatedRelatedMovies(b,2) returns Movies 3,4");
        LogMovies(new MovieFinder().getHighestRatedRelatedMovies(b, 2));
    }
 
    private void LogMovies(IEnumerable<Movie> movies)
    {
        foreach(Movie m in movies)
        {
            Console.WriteLine($"Id {m.Id}, Rating {m.Rating}");
        }
    }
}

---

Thoughts on solution

• We have to visit all the related nodes anyway.
• We have to skip visiting previously visited nodes without adding extra flag on Movie class.

Approach 1-Depth first traverse, Sort and take N top movies

One of the method to solve this problem is given below. There are some more ways. May be I can  share later.

---

public IEnumerable<Movie> getHighestRatedRelatedMovies(Movie root, int numberOfMoviesToSelect)
{
        IList<Movie> movies = new List<Movie>();
        FillList(root, movies);
        movies.Remove(root);
        return movies.OrderByDescending(m => m.Rating).Take(numberOfMoviesToSelect);
} 
private void FillList(Movie node, IList<Movie> movies)
{
        if( movies.Contains(node) == false)
        {
            movies.Add(node);
            foreach(Movie m in node.RelatedMovies)
            {
                FillList(m, movies);
            }
        }
}

---

This is plain solution which satisfies the requirements. It may not be the high performing memory efficient logic. In next posts, lets see optimized version of this.