Hi there amazing people. I gave the screening round for google in March 2025. Waiting for the feedback.
Question.
You have movies with the movie name and rating. For example:
"Movie A , rating 6",
"Movie B , rating 7",
"Movie C , rating 8",
"Movie D , rating 9",
"Movie E , rating 5",
You are also given transitive relation (bi-directional), for example:
Movie A is similar to Movie B,
Movie B is similar to Movie C.
Movie C is similar to Movie D.
Movie A is similar to Movie E.
keep in mind it's bi-directional(means B is similar to A as well)
We can safely assume from above relation that :
Movie A is similar to Movie C as well
That being said you will be given input as (movieName, N), you have to find out N movies similar to the movieName with highest rating.
In this case,
A->6
B->7
C->8
D->9
E->5
input=(A,2) -> means find 2 movies with highest rating similar to movie A.
output= D,C -> as A is similar to B and B is similar to C and C is similar to D and A is similar to E means A,B,C,D,E are similar movies and among them D and C have highest rating , hence the above answer.
my solution:
class Movie:
def __init__(self, title, rating):
self.title = title
self.rating = rating
#list to store similar movies
self.similarMovies = []
def addSimilarMovie(self, movie):
self.similarMovies.append(movie)
#ensuring bidirectional similarity
movie.similarMovies.append(self)
def getTopSimilarMovies(movie, N):
visited = set()
queue = [movie]
#list to store all connected movies
similar_movies = []
while queue:
current = queue.pop(0)
if current in visited:
continue
visited.add(current)
similarMovies.append(current)
for neighbor in current.similarMovies:
if neighbor not in visited:
queue.append(neighbor)
#sort the movies in desscending to find top N movies
similarMovies.sort(key=lambda x: x.rating, reverse=True)
#return the top N movies excluding the initial given movie
return [m.title for m in similarMovies if m != movie][:N]
#creating movies
A = Movie("A", 6)
B = Movie("B", 7)
C = Movie("C", 8)
D = Movie("D", 9)
E = Movie("E", 5)
#similarity relationships
A.addSimilarMovie(B)
B.addSimilarMovie(C)
C.addSimilarMovie(D)
A.addSimilarMovie(E)
#get top 2 recommended movies similar to A
result = getTopSimilarMovies(A, 2)
print(result) #["D", "C"]