nivir
5/7/2017 - 10:13 PM

Movie rating

Movie rating

using System;
using System.Linq;
using System.Collections.Generic;

namespace MyCollections
{
	public class Movie
	{
		private readonly int movieId;
		private readonly float rating;
		private List<Movie> similarMovies;
		// Similarity is bidirectional

		public Movie (int movieId, float rating)
		{
			this.movieId = movieId;
			this.rating = rating;
			similarMovies = new List<Movie> ();
		}

		public int getId ()
		{
			return movieId;
		}

		public float getRating ()
		{
			return rating;
		}

		/// <summary>
		/// Gets the rating of the movie. I added this property as it's useful in linq expression, and in general in C# we use
		/// properties instead of get/set functions.
		/// </summary>
		/// <value>The movie rating.</value>
		public float Rating {
			get {
				return rating;
			}
		}

		/// <summary>
		/// Gets the movie unique identifier (I assumed it's unique). Same remark as for Rating property.
		/// </summary>
		/// <value>The movie unique identifier.</value>
		public int Id {
			get {
				return movieId;
			}
		}

		public void addSimilarMovie (Movie movie)
		{
			similarMovies.Add (movie);
			movie.similarMovies.Add (this);
		}

		public List<Movie> getSimilarMovies ()
		{
			return similarMovies;
		}

		/*
         * Implement a function to return top rated movies in the network of movies 
         * reachable from the current movie
         * eg:            A(Rating 1.2)
         *               /   \
		*            B(2.4)  C(3.6)
		*              \     /
		*               D(4.8)
         * In the above example edges represent similarity and the number is rating.
         * getMovieRecommendations(A,2)should return C and D (sorting order doesn't matter so it can also return D and C)
         * getMovieRecommendations(A,4) should return A, B, C, D (it can also return these in any order eg: B,C,D,A)
         * getMovieRecommendations(A,1) should return D. Note distance from A to D doesn't matter, 
         *                            return the highest  rated.
         *     
         *     @param movie
         *     @param numTopRatedSimilarMovies 
         *                      number of movies we want to return
         *     @return List of top rated similar movies
         */
		public static IList<Movie> getMovieRecommendations (Movie movie, int numTopRatedSimilarMovies)
		{
			if (movie == null) {
				throw new ArgumentNullException ("movie");
			}

			HashSet<Movie> moviesInNetwork = new HashSet<Movie> (new MovieComparer());

			// Flatten the network in a HashSet<Movie>
			// Two problems with my implementation:
			// 1. It's recursive so it won't work for very large networks (as demonstrated in the sample Program below)
			// 2. It's O(n^2), worst case when every single movie is related to every other movies (n*(n-1)), not so good...
			GetDistinctMovies (movie, moviesInNetwork);

			// Order the movies by rating value (descending) and take the number of movies we want to return.
			// Orderby is a quicksort O(nlog(n))
			// I cannot make any assumption concerning the numTopRatedSimilarMovies range so I didn't try to optimize anything here.
			return (from m in moviesInNetwork orderby m.Rating descending
				select m).Take (numTopRatedSimilarMovies).ToList ();
		}

		private static void GetDistinctMovies (Movie movie, HashSet<Movie> knownMovies)
		{
			// Contains method is O(1) for HashSet<T>
			if (knownMovies.Contains (movie)) return;

			// Add method is O(1) for HashSet<T> 
			knownMovies.Add (movie);

			foreach (var similarMovie in movie.getSimilarMovies()) {
				GetDistinctMovies (similarMovie, knownMovies);
			}
		}

		/// <summary>
		/// Movie comparer, used in the HashSet<Movie> constructor. I assumed movie Ids are unique.
		/// </summary>
		private class MovieComparer : IEqualityComparer<Movie>
		{
			public bool Equals(Movie m1, Movie m2)
			{
				return m1.Id == m2.Id;
			}

			public int GetHashCode(Movie movie)
			{
				return movie.Id;
			}
		}
	}

	public class Program
	{
		public static void Main ()
		{
			try {
				Movie.getMovieRecommendations(null, 10);
			} catch (ArgumentNullException ex) {
				Console.WriteLine (ex.Message);
			}

			var A = new Movie (0, 1.2f);
			var B = new Movie (1, 2.4f);
			var C = new Movie (2, 3.6f);

			A.addSimilarMovie (B);
			A.addSimilarMovie (C);
		
			//B.addSimilarMovie (C);

			var D = new Movie (3, 4.8f);

			D.addSimilarMovie (B);
			D.addSimilarMovie (C);
			//D.addSimilarMovie (A);

			ShowRecommentations (A, 2);
			ShowRecommentations (A, 4);
			ShowRecommentations (A, 1);

			Console.WriteLine ("Now with a very **deep** network");

			Random rating = new Random ();
			var movieId = 0;
			var X = new Movie (movieId, (float)rating.NextDouble () * 5);

			var currentMovie = X;
			while (movieId < 1000000) {
				movieId++;
				var newMovie = new Movie (movieId, (float)rating.NextDouble () * 5);
				currentMovie.addSimilarMovie (newMovie);
				currentMovie = newMovie;
			}

			try {
				ShowRecommentations (X, 20);
			} catch (StackOverflowException e) {
				Console.WriteLine (e.Message);
			}

			Console.ReadLine ();
		}

		public static void ShowRecommentations(Movie movie, int numTopRatedSimilarMovies)
		{
			var recommendations = Movie.getMovieRecommendations (movie, numTopRatedSimilarMovies);

			Console.WriteLine ("If you like movie {0}, we recommend those {1} movies: ", movie.Id, numTopRatedSimilarMovies);

			foreach (var recommendation in recommendations) {
				Console.WriteLine ("Movie {0}, rated {1}", recommendation.Id, recommendation.Rating);
			}
		}
	}
}
using System;
using System.Collections.Generic;
 
namespace MyCollections
{
    public class Movie {
        private readonly int movieId;
        private readonly float rating;
        private List<Movie> similarMovies; // Similarity is bidirectional
 
        public Movie(int movieId, float rating) {
            this.movieId = movieId;
            this.rating = rating;
            similarMovies = new List<Movie>();
        }
 
        public int getId() {
            return movieId;
        }
 
        public float getRating() {
            return rating;
        }
 
        public void addSimilarMovie(Movie movie) {
            similarMovies.Add(movie);
            movie.similarMovies.add(this);
        }
 
        public List<Movie> getSimilarMovies() {
            return similarMovies;
        }
 
        /*
         * Implement a function to return top rated movies in the network of movies 
         * reachable from the current movie
         * eg:            A(Rating 1.2)
         *               /   \
         *            B(2.4)  C(3.6)
         *              \     /
         *               D(4.8)
         * In the above example edges represent similarity and the number is rating.
         * getMovieRecommendations(A,2)should return C and D (sorting order doesn't matter so it can also return D and C)
         * getMovieRecommendations(A,4) should return A, B, C, D (it can also return these in any order eg: B,C,D,A)
         * getMovieRecommendations(A,1) should return D. Note distance from A to D doesn't matter, 
         *                            return the highest  rated.
         *     
         *     @param movie
         *     @param numTopRatedSimilarMovies 
         *                      number of movies we want to return
         *     @return List of top rated similar movies
         */
        public static IList<Movie> getMovieRecommendations(Movie movie, int numTopRatedSimilarMovies) {
            // Implement me
            return null;
        }
    }
}