登录
OAmaster

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.

解法

对每个分组，取出对应 similarityScores，排序取前 k 求和。复杂度 O(Σ |group| log |group|)，空间 O(max|group|)。

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;
    }
};

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.

解法

主存 dict: key -> (value, expiresAt)，配套小顶堆 (expiresAt, key)。SET 写 expiresAt = now + ttl 并入堆。GET 时只判断 expiresAt > now(懒删除)。CLEANUP 把堆顶 expiresAt ≤ now 的项弹出并核对当前真实过期时间(避免被覆盖)。复杂度均摊 O(log n)，空间 O(n)。

from typing import List
import heapq

def run_timed_cache(operations: List[str]) -> List[str]:
    cache = {}
    heap = []
    out = []
    for op in operations:
        parts = op.split()
        cmd = parts[0]
        if cmd == "SET":
            key, value = parts[1], parts[2]
            ttl, now = int(parts[3]), int(parts[4])
            exp = now + ttl
            cache[key] = (value, exp)
            heapq.heappush(heap, (exp, key))
        elif cmd == "GET":
            key, now = parts[1], int(parts[2])
            entry = cache.get(key)
            if entry is None or entry[1] <= now:
                out.append("NULL")
            else:
                out.append(entry[0])
        elif cmd == "CLEANUP":
            now = int(parts[1])
            while heap and heap[0][0] <= now:
                exp, key = heapq.heappop(heap)
                entry = cache.get(key)
                if entry is not None and entry[1] == exp:
                    del cache[key]
    return out
import java.util.*;

class Solution {
    static class Entry { String value; long expiresAt; Entry(String v, long e) { value = v; expiresAt = e; } }

    String[] runTimedCache(String[] operations) {
        Map<String, Entry> cache = new HashMap<>();
        PriorityQueue<Object[]> heap = new PriorityQueue<>((a, b) -> Long.compare((long) a[0], (long) b[0]));
        List<String> out = new ArrayList<>();
        for (String op : operations) {
            String[] p = op.split(" ");
            switch (p[0]) {
                case "SET": {
                    long exp = Long.parseLong(p[4]) + Long.parseLong(p[3]);
                    cache.put(p[1], new Entry(p[2], exp));
                    heap.add(new Object[]{exp, p[1]});
                    break;
                }
                case "GET": {
                    long now = Long.parseLong(p[2]);
                    Entry e = cache.get(p[1]);
                    if (e == null || e.expiresAt <= now) out.add("NULL");
                    else out.add(e.value);
                    break;
                }
                case "CLEANUP": {
                    long now = Long.parseLong(p[1]);
                    while (!heap.isEmpty() && (long) heap.peek()[0] <= now) {
                        Object[] top = heap.poll();
                        Entry e = cache.get((String) top[1]);
                        if (e != null && e.expiresAt == (long) top[0]) cache.remove((String) top[1]);
                    }
                    break;
                }
            }
        }
        return out.toArray(new String[0]);
    }
}
class Solution {
public:
    vector<string> runTimedCache(vector<string>& operations) {
        unordered_map<string, pair<string, long long>> cache;
        priority_queue<pair<long long, string>, vector<pair<long long, string>>, greater<>> heap;
        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] == "SET") {
                long long exp = stoll(p[4]) + stoll(p[3]);
                cache[p[1]] = {p[2], exp};
                heap.push({exp, p[1]});
            } else if (p[0] == "GET") {
                long long now = stoll(p[2]);
                auto it = cache.find(p[1]);
                if (it == cache.end() || it->second.second <= now) out.push_back("NULL");
                else out.push_back(it->second.first);
            } else if (p[0] == "CLEANUP") {
                long long now = stoll(p[1]);
                while (!heap.empty() && heap.top().first <= now) {
                    auto [exp, k] = heap.top(); heap.pop();
                    auto it = cache.find(k);
                    if (it != cache.end() && it->second.second == exp) cache.erase(it);
                }
            }
        }
        return out;
    }
};

Microsoft

Microsoft 真实 OA 题库(Codility + HackerRank 平台)，三语题解 (Python / Java / C++)。

Nvidia

Nvidia 真实 OA 题库，三语题解 (Python / Java / C++)。