function topRatedSimilarMovies(ratings, similar, start, k) {
if (k === 0) return [];
const n = ratings.length;
const visited = Array(n).fill(false);
const q = [start];
let head = 0;
visited[start] = true;
const candidates = [];
// STEP 1: BFS - Find all reachable movies
while (head < q.length) {
const curr = q[head++];
for (const next of similar[curr]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
candidates.push(next); // Excludes start
}
}
}
// STEP 2: Sort by rating DESC, then movie ID ASC
candidates.sort((a, b) => {
if (ratings[a] !== ratings[b]) {
return ratings[b] - ratings[a];
}
return a - b;
});
// STEP 3: Return top k movies
return candidates.slice(0, k);
}
// ==========================================
// TEST CASES (Ideone-ready)
// ==========================================
const tests = [
{
name: "Normal graph + unreachable highest-rated movie",
ratings: [60, 80, 95, 95, 100],
similar: [[1, 2], [3], [], [1], []],
start: 0,
k: 2,
expected: [2, 3]
},
{
name: "Cycle + duplicate edges + self-loop + rating ties",
ratings: [100, 20, 90, 90],
similar: [[0, 1, 1], [0, 2, 3], [], []],
start: 0,
k: 3,
expected: [2, 3, 1]
},
{
name: "Bidirectional graph + k exceeds reachable movies",
ratings: [10, 90, 70],
similar: [[1], [0, 2], [1]],
start: 0,
k: 5,
expected: [1, 2]
},
{
name: "k = 0",
ratings: [10, 90],
similar: [[1], []],
start: 0,
k: 0,
expected: []
}
];
for (const test of tests) {
const actual = topRatedSimilarMovies(
test.ratings,
test.similar,
test.start,
test.k
);
const passed =
JSON.stringify(actual) === JSON.stringify(test.expected);
console.log(
`${passed ? "PASS" : "FAIL"} - ${test.name}`
);
console.log("Expected:", JSON.stringify(test.expected));
console.log("Actual: ", JSON.stringify(actual));
console.log();
}
CmZ1bmN0aW9uIHRvcFJhdGVkU2ltaWxhck1vdmllcyhyYXRpbmdzLCBzaW1pbGFyLCBzdGFydCwgaykgewogICAgaWYgKGsgPT09IDApIHJldHVybiBbXTsKCiAgICBjb25zdCBuID0gcmF0aW5ncy5sZW5ndGg7CiAgICBjb25zdCB2aXNpdGVkID0gQXJyYXkobikuZmlsbChmYWxzZSk7CiAgICBjb25zdCBxID0gW3N0YXJ0XTsKICAgIGxldCBoZWFkID0gMDsKCiAgICB2aXNpdGVkW3N0YXJ0XSA9IHRydWU7CgogICAgY29uc3QgY2FuZGlkYXRlcyA9IFtdOwoKICAgIC8vIFNURVAgMTogQkZTIC0gRmluZCBhbGwgcmVhY2hhYmxlIG1vdmllcwogICAgd2hpbGUgKGhlYWQgPCBxLmxlbmd0aCkgewogICAgICAgIGNvbnN0IGN1cnIgPSBxW2hlYWQrK107CgogICAgICAgIGZvciAoY29uc3QgbmV4dCBvZiBzaW1pbGFyW2N1cnJdKSB7CiAgICAgICAgICAgIGlmICghdmlzaXRlZFtuZXh0XSkgewogICAgICAgICAgICAgICAgdmlzaXRlZFtuZXh0XSA9IHRydWU7CiAgICAgICAgICAgICAgICBxLnB1c2gobmV4dCk7CiAgICAgICAgICAgICAgICBjYW5kaWRhdGVzLnB1c2gobmV4dCk7IC8vIEV4Y2x1ZGVzIHN0YXJ0CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgLy8gU1RFUCAyOiBTb3J0IGJ5IHJhdGluZyBERVNDLCB0aGVuIG1vdmllIElEIEFTQwogICAgY2FuZGlkYXRlcy5zb3J0KChhLCBiKSA9PiB7CiAgICAgICAgaWYgKHJhdGluZ3NbYV0gIT09IHJhdGluZ3NbYl0pIHsKICAgICAgICAgICAgcmV0dXJuIHJhdGluZ3NbYl0gLSByYXRpbmdzW2FdOwogICAgICAgIH0KICAgICAgICByZXR1cm4gYSAtIGI7CiAgICB9KTsKCiAgICAvLyBTVEVQIDM6IFJldHVybiB0b3AgayBtb3ZpZXMKICAgIHJldHVybiBjYW5kaWRhdGVzLnNsaWNlKDAsIGspOwp9CgovLyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KLy8gVEVTVCBDQVNFUyAoSWRlb25lLXJlYWR5KQovLyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KCmNvbnN0IHRlc3RzID0gWwogICAgewogICAgICAgIG5hbWU6ICJOb3JtYWwgZ3JhcGggKyB1bnJlYWNoYWJsZSBoaWdoZXN0LXJhdGVkIG1vdmllIiwKICAgICAgICByYXRpbmdzOiBbNjAsIDgwLCA5NSwgOTUsIDEwMF0sCiAgICAgICAgc2ltaWxhcjogW1sxLCAyXSwgWzNdLCBbXSwgWzFdLCBbXV0sCiAgICAgICAgc3RhcnQ6IDAsCiAgICAgICAgazogMiwKICAgICAgICBleHBlY3RlZDogWzIsIDNdCiAgICB9LAogICAgewogICAgICAgIG5hbWU6ICJDeWNsZSArIGR1cGxpY2F0ZSBlZGdlcyArIHNlbGYtbG9vcCArIHJhdGluZyB0aWVzIiwKICAgICAgICByYXRpbmdzOiBbMTAwLCAyMCwgOTAsIDkwXSwKICAgICAgICBzaW1pbGFyOiBbWzAsIDEsIDFdLCBbMCwgMiwgM10sIFtdLCBbXV0sCiAgICAgICAgc3RhcnQ6IDAsCiAgICAgICAgazogMywKICAgICAgICBleHBlY3RlZDogWzIsIDMsIDFdCiAgICB9LAogICAgewogICAgICAgIG5hbWU6ICJCaWRpcmVjdGlvbmFsIGdyYXBoICsgayBleGNlZWRzIHJlYWNoYWJsZSBtb3ZpZXMiLAogICAgICAgIHJhdGluZ3M6IFsxMCwgOTAsIDcwXSwKICAgICAgICBzaW1pbGFyOiBbWzFdLCBbMCwgMl0sIFsxXV0sCiAgICAgICAgc3RhcnQ6IDAsCiAgICAgICAgazogNSwKICAgICAgICBleHBlY3RlZDogWzEsIDJdCiAgICB9LAogICAgewogICAgICAgIG5hbWU6ICJrID0gMCIsCiAgICAgICAgcmF0aW5nczogWzEwLCA5MF0sCiAgICAgICAgc2ltaWxhcjogW1sxXSwgW11dLAogICAgICAgIHN0YXJ0OiAwLAogICAgICAgIGs6IDAsCiAgICAgICAgZXhwZWN0ZWQ6IFtdCiAgICB9Cl07Cgpmb3IgKGNvbnN0IHRlc3Qgb2YgdGVzdHMpIHsKICAgIGNvbnN0IGFjdHVhbCA9IHRvcFJhdGVkU2ltaWxhck1vdmllcygKICAgICAgICB0ZXN0LnJhdGluZ3MsCiAgICAgICAgdGVzdC5zaW1pbGFyLAogICAgICAgIHRlc3Quc3RhcnQsCiAgICAgICAgdGVzdC5rCiAgICApOwoKICAgIGNvbnN0IHBhc3NlZCA9CiAgICAgICAgSlNPTi5zdHJpbmdpZnkoYWN0dWFsKSA9PT0gSlNPTi5zdHJpbmdpZnkodGVzdC5leHBlY3RlZCk7CgogICAgY29uc29sZS5sb2coCiAgICAgICAgYCR7cGFzc2VkID8gIlBBU1MiIDogIkZBSUwifSAtICR7dGVzdC5uYW1lfWAKICAgICk7CiAgICBjb25zb2xlLmxvZygiRXhwZWN0ZWQ6IiwgSlNPTi5zdHJpbmdpZnkodGVzdC5leHBlY3RlZCkpOwogICAgY29uc29sZS5sb2coIkFjdHVhbDogICIsIEpTT04uc3RyaW5naWZ5KGFjdHVhbCkpOwogICAgY29uc29sZS5sb2coKTsKfQo=