fork download
  1.  
  2. /*
  3. PROBLEM:
  4. Given:
  5. - ratings[i]: Rating of movie i
  6. - titles[i]: Title of movie i
  7. - similar[i]: List of movies similar to movie i
  8. - start: Starting movie
  9. - k: Number of recommendations
  10.  
  11. Return up to K highest-rated reachable movies.
  12.  
  13. RULES:
  14. 1. Exclude the starting movie.
  15. 2. Higher rating comes first.
  16. 3. If ratings tie, lexicographically smaller title comes first.
  17. 4. If titles also tie, smaller movie ID comes first.
  18. 5. Avoid duplicate movies and handle cycles.
  19.  
  20. APPROACH: BFS + SORTING
  21.  
  22. 1. Start BFS from the starting movie.
  23. 2. Use visited to avoid processing movies multiple times.
  24. 3. Collect all reachable movies except start.
  25. 4. Sort candidates:
  26.   - Rating descending
  27.   - Title ascending (using custom compareTitles)
  28.   - Movie ID ascending if both rating and title match
  29. 5. Return the first K movie IDs.
  30.  
  31. CUSTOM STRING COMPARISON:
  32. 1. Compare both titles character by character.
  33. 2. At the first different character:
  34.   - Smaller character comes first.
  35. 3. If all compared characters match:
  36.   - Shorter title comes first.
  37. 4. Return 0 if both titles are identical.
  38.  
  39. TIME COMPLEXITY:
  40. O(V + E + R * log(R) * L)
  41.  
  42. V = number of movies
  43. E = number of similarity edges
  44. R = number of reachable movies excluding start
  45. L = maximum movie title length
  46.  
  47. - BFS: O(V + E)
  48. - compareTitles: O(L)
  49. - Sorting: O(R log R * L)
  50.  
  51. SPACE COMPLEXITY:
  52. O(V + R) auxiliary space, excluding sort internals.
  53.  
  54. - visited: O(V)
  55. - BFS queue: O(V)
  56. - candidates: O(R)
  57. - compareTitles: O(1)
  58. - Sorting may use additional implementation-dependent space.
  59. */
  60.  
  61. // ==========================================
  62. // CUSTOM LEXICOGRAPHICAL COMPARISON
  63. // ==========================================
  64.  
  65. function compareTitles(str1, str2) {
  66. const minLen = Math.min(str1.length, str2.length);
  67.  
  68. // Compare characters one by one
  69. for (let i = 0; i < minLen; i++) {
  70. if (str1[i] < str2[i]) return -1;
  71. if (str1[i] > str2[i]) return 1;
  72. }
  73.  
  74. // If one title is a prefix of the other,
  75. // the shorter title comes first.
  76. if (str1.length < str2.length) return -1;
  77. if (str1.length > str2.length) return 1;
  78.  
  79. // Both titles are identical
  80. return 0;
  81. }
  82.  
  83. // ==========================================
  84. // SOLUTION: BFS + SORTING
  85. // ==========================================
  86.  
  87. function topRatedSimilarMovies(
  88. ratings, titles, similar, start, k
  89. ) {
  90. if (k === 0) return [];
  91.  
  92. const visited = Array(ratings.length).fill(false);
  93. const q = [start];
  94. let head = 0;
  95. const candidates = [];
  96.  
  97. visited[start] = true;
  98.  
  99. // STEP 1: BFS to find all reachable movies
  100. while (head < q.length) {
  101. const curr = q[head++];
  102.  
  103. // STEP 2: Explore neighboring movies
  104. for (const next of similar[curr]) {
  105. if (!visited[next]) {
  106. visited[next] = true;
  107. q.push(next);
  108.  
  109. // Exclude start (already marked visited)
  110. candidates.push(next);
  111. }
  112. }
  113. }
  114.  
  115. // STEP 3: Sort by rating, title, then ID
  116. candidates.sort((a, b) => {
  117. // Higher rating first
  118. if (ratings[a] !== ratings[b]) {
  119. return ratings[b] - ratings[a];
  120. }
  121.  
  122. // Alphabetical title order
  123. const titleComparison = compareTitles(
  124. titles[a], titles[b]
  125. );
  126.  
  127. if (titleComparison !== 0) {
  128. return titleComparison;
  129. }
  130.  
  131. // Same rating and same title:
  132. // Smaller movie ID first
  133. return a - b;
  134. });
  135.  
  136. // STEP 4: Return top K movie IDs
  137. return candidates.slice(0, k);
  138. }
  139.  
  140. // ==========================================
  141. // TEST CASES (IDEONE-READY)
  142. // ==========================================
  143.  
  144. const tests = [
  145. {
  146. name: "Normal + alphabetical rating ties",
  147. ratings: [80, 95, 95, 90],
  148. titles: [
  149. "Avatar",
  150. "Titanic",
  151. "Inception",
  152. "Interstellar"
  153. ],
  154. similar: [[1, 2, 3], [], [], []],
  155. start: 0,
  156. k: 2,
  157. expected: [2, 1]
  158. },
  159. {
  160. name: "Same rating and same title - smaller ID",
  161. ratings: [50, 90, 90, 90],
  162. titles: ["Start", "Avatar", "Avatar", "Batman"],
  163. similar: [[2, 3, 1], [], [], []],
  164. start: 0,
  165. k: 3,
  166. expected: [1, 2, 3]
  167. },
  168. {
  169. name: "Cycles + duplicate edges + prefix titles",
  170. ratings: [100, 95, 95, 95, 999],
  171. titles: ["Start", "Avatar", "Av", "Avengers", "Other"],
  172. similar: [
  173. [1, 1, 2],
  174. [0, 3],
  175. [1],
  176. [3],
  177. []
  178. ],
  179. start: 0,
  180. k: 3,
  181. expected: [2, 1, 3]
  182. },
  183. {
  184. name: "No reachable movies",
  185. ratings: [100, 90],
  186. titles: ["Start", "Avatar"],
  187. similar: [[], []],
  188. start: 0,
  189. k: 1,
  190. expected: []
  191. }
  192. ];
  193.  
  194. for (const test of tests) {
  195. const actual = topRatedSimilarMovies(
  196. test.ratings,
  197. test.titles,
  198. test.similar,
  199. test.start,
  200. test.k
  201. );
  202.  
  203. const passed =
  204. JSON.stringify(actual) === JSON.stringify(test.expected);
  205.  
  206. console.log(
  207. `${passed ? "PASS" : "FAIL"} - ${test.name}`
  208. );
  209. console.log("Expected:", JSON.stringify(test.expected));
  210. console.log("Actual: ", JSON.stringify(actual));
  211. console.log();
  212. }
  213.  
Success #stdin #stdout 0.03s 5656KB
stdin
Standard input is empty
stdout
PASS - Normal + alphabetical rating ties
Expected: [2,1]
Actual:   [2,1]

PASS - Same rating and same title - smaller ID
Expected: [1,2,3]
Actual:   [1,2,3]

PASS - Cycles + duplicate edges + prefix titles
Expected: [2,1,3]
Actual:   [2,1,3]

PASS - No reachable movies
Expected: []
Actual:   []