Netflix

— / 3已做

01Command Undo Data Structure

Design a command system that mutates a state and supports undo. Redo is optional. For this problem, the state is a single integer that starts at 0. Supported commands are:

ADD x: add x to the state
MUL x: multiply the state by x
UNDO: undo the most recent command that has not already been undone
PRINT: output the current state Return the output lines produced by the command batch. Function Description Complete the function runCommandUndo in the editor below. runCommandUndo has the following parameter:
String[] operations: the commands to execute in order Returns String[]: the lines printed by PRINT operations.

Constraints

Each undo should revert exactly one previously executed mutating command.
Explain or implement the command history so that undo stays efficient.

Example 1

Input:

operations = ["ADD 5", "MUL 3", "UNDO", "PRINT"]

Output:

["5"]

Explanation: After adding 5 and multiplying by 3, the state becomes 15. Undo reverts the multiplication, so PRINT outputs 5.

解法

每次执行 mutating 命令前，先把当前 state 压入历史栈；UNDO 时弹栈恢复。PRINT 收集输出。复杂度每操作 O(1)，空间 O(操作数)。

from typing import List

def run_command_undo(operations: List[str]) -> List[str]:
    state = 0
    history = []
    out = []
    for op in operations:
        parts = op.split()
        if parts[0] == "ADD":
            history.append(state)
            state += int(parts[1])
        elif parts[0] == "MUL":
            history.append(state)
            state *= int(parts[1])
        elif parts[0] == "UNDO":
            if history:
                state = history.pop()
        elif parts[0] == "PRINT":
            out.append(str(state))
    return out

import java.util.*;

class Solution {
    String[] runCommandUndo(String[] operations) {
        long state = 0;
        Deque<Long> history = new ArrayDeque<>();
        List<String> out = new ArrayList<>();
        for (String op : operations) {
            String[] p = op.split(" ");
            switch (p[0]) {
                case "ADD": history.push(state); state += Long.parseLong(p[1]); break;
                case "MUL": history.push(state); state *= Long.parseLong(p[1]); break;
                case "UNDO": if (!history.isEmpty()) state = history.pop(); break;
                case "PRINT": out.add(Long.toString(state)); break;
            }
        }
        return out.toArray(new String[0]);
    }
}

class Solution {
public:
    vector<string> runCommandUndo(vector<string>& operations) {
        long long state = 0;
        vector<long long> history;
        vector<string> out;
        for (auto& op : operations) {
            vector<string> p;
            string cur;
            for (char c : op) { if (c == ' ') { p.push_back(cur); cur.clear(); } else cur += c; }
            if (!cur.empty()) p.push_back(cur);
            if (p[0] == "ADD") { history.push_back(state); state += stoll(p[1]); }
            else if (p[0] == "MUL") { history.push_back(state); state *= stoll(p[1]); }
            else if (p[0] == "UNDO") { if (!history.empty()) { state = history.back(); history.pop_back(); } }
            else if (p[0] == "PRINT") out.push_back(to_string(state));
        }
        return out;
    }
};

02Rank Movies by Similarity Score (FrontEnd :)

In this problem, we will implement a solution where given a single source movie that a user has liked in the past, we return groups of target movies. Given a source movie, you have access to a similarity score of the source movie with all target movies. You also have the groups of target movies that you need to rank. Using this information, you can generate a score for each group given the source movie by taking the top k similar movies in each group, and using them to compute a score for the group using the following formula: ∑_(i=1)^k score_i. For example, if the similarity scores for the target movies are [0.3, 0.2, 0.1, 0.4, 0.5], where the array index is the id of the movie; and a group has movies [1, 2, 4], the corresponding scores are [0.2, 0.1, 0.5]. For a value of k = 2, the score of this collection would be 0.5 + 0.2 = 0.7.

Example 1

Input:

similarityScores = [0.3, 0.2, 0.1, 0.4, 0.5]
movieGroups = [[1, 2, 4], [0, 3, 4]]
k = 2

Output:

[0.7, 0.9]

Explanation: For the first group [1, 2, 4], the top 2 similarity scores are [0.5, 0.2], so the score is 0.5 + 0.2 = 0.7. For the second group [0, 3, 4], the top 2 similarity scores are [0.5, 0.4], so the score is 0.5 + 0.4 = 0.9.

解法

from typing import List
import heapq

def rank_movies_by_similarity(similarity_scores: List[float],
                                 movie_groups: List[List[int]], k: int) -> List[float]:
    res = []
    for group in movie_groups:
        scores = [similarity_scores[i] for i in group]
        top = heapq.nlargest(k, scores)
        res.append(sum(top))
    return res

import java.util.*;

class Solution {
    double[] rankMoviesBySimilarity(double[] similarityScores, int[][] movieGroups, int k) {
        double[] res = new double[movieGroups.length];
        for (int g = 0; g < movieGroups.length; g++) {
            int[] group = movieGroups[g];
            double[] scores = new double[group.length];
            for (int i = 0; i < group.length; i++) scores[i] = similarityScores[group[i]];
            Arrays.sort(scores);
            double s = 0;
            for (int i = scores.length - 1; i >= Math.max(0, scores.length - k); i--) s += scores[i];
            res[g] = s;
        }
        return res;
    }
}

class Solution {
public:
    vector<double> rankMoviesBySimilarity(vector<double>& similarityScores,
                                           vector<vector<int>>& movieGroups, int k) {
        vector<double> res;
        for (auto& group : movieGroups) {
            vector<double> scores;
            for (int i : group) scores.push_back(similarityScores[i]);
            sort(scores.begin(), scores.end(), greater<double>());
            double s = 0;
            for (int i = 0; i < min((int) scores.size(), k); i++) s += scores[i];
            res.push_back(s);
        }
        return res;
    }
};

03Timed Cache with Sidecar Cleanup

Implement a key-value cache where each entry has its own TTL. Support the following operations:

SET <key> <value> <ttlSeconds> <now>
GET <key> <now>
CLEANUP <now> GET is the hot path, so it should not scan the whole cache to remove expired entries. A separate sidecar or background process may perform proactive cleanup. Return the output lines produced by the operation batch. GET should print the current value or NULL if the key is missing or expired. Function Description Complete the function runTimedCache in the editor below. runTimedCache has the following parameter:
String[] operations: cache operations executed in order Returns String[]: the output lines produced by the batch.

Constraints

GET should stay cheap even when the cache is large.
Each key has a per-item TTL.
A cleanup help

Example 1

Input:

operations = ["SET a 1 5 0", "GET a 3", "GET a 6"]

Output:

["1", "NULL"]

Explanation: Key a expires at time 5. It is still valid at time 3 and expired by time 6.

Example 2

Input:

operations = ["SET a 1 5 0", "SET b 2 2 0", "CLEANUP 3", "GET a 3", "GET b 3"]

Output:

["1", "NULL"]

Explanation: By time 3, key b has expired and may be removed during cleanup. Key a is still alive.

Pro解法 · 三语代码 · 复杂度分析

边界讨论 + 面试官追问 · $98 / 一年解锁

Pro 会员

解锁全部 1 道题的解法

题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.

Pro 解锁全部

📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
📊个人 dashboard + 进度可视化 + 14 天活跃图
📝题目笔记跨设备同步 + 个人复盘库
🔓随时取消下次续费, Stripe Customer Portal 自助管理

$12/月($98/年, 一次付清省 32%)

≈ 北美 SWE 工资 10 分钟 · LeetCode Premium $35/月的 23%

立即解锁 $98/年已是会员, 去登录