fork download
  1.  
  2. function topRatedSimilarMovies(ratings, similar, start, k) {
  3. if (k === 0) return [];
  4.  
  5. const n = ratings.length;
  6. const visited = Array(n).fill(false);
  7. const q = [start];
  8. let head = 0;
  9.  
  10. visited[start] = true;
  11.  
  12. const candidates = [];
  13.  
  14. // STEP 1: BFS - Find all reachable movies
  15. while (head < q.length) {
  16. const curr = q[head++];
  17.  
  18. for (const next of similar[curr]) {
  19. if (!visited[next]) {
  20. visited[next] = true;
  21. q.push(next);
  22. candidates.push(next); // Excludes start
  23. }
  24. }
  25. }
  26.  
  27. // STEP 2: Sort by rating DESC, then movie ID ASC
  28. candidates.sort((a, b) => {
  29. if (ratings[a] !== ratings[b]) {
  30. return ratings[b] - ratings[a];
  31. }
  32. return a - b;
  33. });
  34.  
  35. // STEP 3: Return top k movies
  36. return candidates.slice(0, k);
  37. }
  38.  
  39. // ==========================================
  40. // TEST CASES (Ideone-ready)
  41. // ==========================================
  42.  
  43. const tests = [
  44. {
  45. name: "Normal graph + unreachable highest-rated movie",
  46. ratings: [60, 80, 95, 95, 100],
  47. similar: [[1, 2], [3], [], [1], []],
  48. start: 0,
  49. k: 2,
  50. expected: [2, 3]
  51. },
  52. {
  53. name: "Cycle + duplicate edges + self-loop + rating ties",
  54. ratings: [100, 20, 90, 90],
  55. similar: [[0, 1, 1], [0, 2, 3], [], []],
  56. start: 0,
  57. k: 3,
  58. expected: [2, 3, 1]
  59. },
  60. {
  61. name: "Bidirectional graph + k exceeds reachable movies",
  62. ratings: [10, 90, 70],
  63. similar: [[1], [0, 2], [1]],
  64. start: 0,
  65. k: 5,
  66. expected: [1, 2]
  67. },
  68. {
  69. name: "k = 0",
  70. ratings: [10, 90],
  71. similar: [[1], []],
  72. start: 0,
  73. k: 0,
  74. expected: []
  75. }
  76. ];
  77.  
  78. for (const test of tests) {
  79. const actual = topRatedSimilarMovies(
  80. test.ratings,
  81. test.similar,
  82. test.start,
  83. test.k
  84. );
  85.  
  86. const passed =
  87. JSON.stringify(actual) === JSON.stringify(test.expected);
  88.  
  89. console.log(
  90. `${passed ? "PASS" : "FAIL"} - ${test.name}`
  91. );
  92. console.log("Expected:", JSON.stringify(test.expected));
  93. console.log("Actual: ", JSON.stringify(actual));
  94. console.log();
  95. }
  96.  
Success #stdin #stdout 0.03s 5564KB
stdin
Standard input is empty
stdout
PASS - Normal graph + unreachable highest-rated movie
Expected: [2,3]
Actual:   [2,3]

PASS - Cycle + duplicate edges + self-loop + rating ties
Expected: [2,3,1]
Actual:   [2,3,1]

PASS - Bidirectional graph + k exceeds reachable movies
Expected: [1,2]
Actual:   [1,2]

PASS - k = 0
Expected: []
Actual:   []