Created
August 19, 2014 00:53
-
-
Save r-julien-bataille/be492805b3af6a9ac244 to your computer and use it in GitHub Desktop.
Movie rating
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment