Applied Intuition

01Compilation Order with Topological Sort

You are given a list of module names and a list of dependency pairs. Each dependency [a, b] means module a depends on module b, so b must be compiled before a. Return one valid compilation order that includes every module exactly once. If multiple modules are currently available to compile, choose the lexicographically smallest available module first so the result is deterministic. If the dependency graph contains a cycle, return a single-element array ["IMPOSSIBLE"]. Function Description Complete the function compilationOrder in the editor below. compilationOrder has the following parameters:

String[] modules: all module names
String[][] dependencies: dependency pairs [module, prerequisite] Returns String[]: a valid compilation order, or ["IMPOSSIBLE"] if the dependencies contain a cycle.

Constraints

1 ≤ modules.length ≤ 2 * 10⁵
0 ≤ dependencies.length ≤ 2 * 10⁵
All module names are distinct.

解法

Kahn 拓扑排序 + 字典序最小堆：把 b -> a 视为边。计算入度，将入度为 0 的模块放入最小堆，每次取出最小名字、加入答案，删边、入度归零的入堆。若最终未覆盖所有模块说明有环，返回 ["IMPOSSIBLE"]。时间 O((V+E) log V)。

import heapq
from collections import defaultdict
from typing import List

def compilation_order(modules: List[str], dependencies: List[List[str]]) -> List[str]:
    graph = defaultdict(list)
    indeg = {m: 0 for m in modules}
    for a, b in dependencies:
        graph[b].append(a)
        indeg[a] = indeg.get(a, 0) + 1
        indeg.setdefault(b, indeg.get(b, 0))
    heap = [m for m, d in indeg.items() if d == 0]
    heapq.heapify(heap)
    out = []
    while heap:
        m = heapq.heappop(heap)
        out.append(m)
        for nxt in graph[m]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                heapq.heappush(heap, nxt)
    if len(out) != len(indeg):
        return ["IMPOSSIBLE"]
    return out

import java.util.*;

class Solution {
    public String[] compilationOrder(String[] modules, String[][] dependencies) {
        Map<String, List<String>> g = new HashMap<>();
        Map<String, Integer> indeg = new HashMap<>();
        for (String m : modules) indeg.put(m, 0);
        for (String[] d : dependencies) {
            g.computeIfAbsent(d[1], k -> new ArrayList<>()).add(d[0]);
            indeg.merge(d[0], 1, Integer::sum);
        }
        PriorityQueue<String> pq = new PriorityQueue<>();
        for (var e : indeg.entrySet()) if (e.getValue() == 0) pq.add(e.getKey());
        List<String> out = new ArrayList<>();
        while (!pq.isEmpty()) {
            String m = pq.poll();
            out.add(m);
            for (String nxt : g.getOrDefault(m, List.of())) {
                indeg.merge(nxt, -1, Integer::sum);
                if (indeg.get(nxt) == 0) pq.add(nxt);
            }
        }
        if (out.size() != indeg.size()) return new String[]{"IMPOSSIBLE"};
        return out.toArray(new String[0]);
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> compilationOrder(vector<string>& modules, vector<vector<string>>& dependencies) {
        unordered_map<string, vector<string>> g;
        unordered_map<string, int> indeg;
        for (auto& m : modules) indeg[m] = 0;
        for (auto& d : dependencies) {
            g[d[1]].push_back(d[0]);
            indeg[d[0]]++;
        }
        priority_queue<string, vector<string>, greater<string>> pq;
        for (auto& [k, v] : indeg) if (v == 0) pq.push(k);
        vector<string> out;
        while (!pq.empty()) {
            string m = pq.top(); pq.pop();
            out.push_back(m);
            for (auto& nxt : g[m]) if (--indeg[nxt] == 0) pq.push(nxt);
        }
        if ((int)out.size() != (int)indeg.size()) return {"IMPOSSIBLE"};
        return out;
    }
};

02KV Store with Nested Transactions

Implement an in-memory key-value store that supports nested transactions. Commands are executed in order, one command per line. Supported commands are:

SET <key> <value>
GET <key>
DELETE <key>
BEGIN
ROLLBACK
COMMIT GET returns the current value of a key, or NULL if it does not exist. ROLLBACK and COMMIT print NO TRANSACTION when there is no active transaction. Return the lines that would be printed while processing the command batch. Function Description Complete the function runNestedTransactions in the editor below. runNestedTransactions has the following parameter:
String[] commands: the command batch, one command per element Returns String[]: the output lines produced by the batch in order.

Constraints

1 ≤ commands.length ≤ 200000
Keys and values are non-empty strings without spaces.
Transactions may be nested arbitrarily deeply.
A near-linear total runtime is expected for large command batches.

解法

维护栈 txs：每个元素是一个 dict 记录该层 transaction 内对 key 的覆盖(值或哨兵 DELETED)。GET 时从栈顶到栈底依次查找，若遇到 DELETED 返回 NULL，遇到值返回；SET/DELETE 写入栈顶 dict(若无 transaction 则栈底有一个 base dict)。BEGIN push 空 dict；ROLLBACK pop(无 transaction 时输出 NO TRANSACTION)；COMMIT 把栈顶 merge 到下层(同样校验)。约定 base 层永远存在，transaction 层在 base 之上。所有操作均摊 O(1)(COMMIT O(层大小)，总和 O(N))。

from typing import List

DELETED = object()

def run_nested_transactions(commands: List[str]) -> List[str]:
    stack: list = [{}]  # base layer
    in_tx = 0
    out: List[str] = []

    def get(key):
        for layer in reversed(stack):
            if key in layer:
                v = layer[key]
                return None if v is DELETED else v
        return None

    for cmd in commands:
        parts = cmd.split()
        op = parts[0]
        if op == "SET":
            stack[-1][parts[1]] = parts[2]
        elif op == "DELETE":
            stack[-1][parts[1]] = DELETED
        elif op == "GET":
            v = get(parts[1])
            out.append("NULL" if v is None else v)
        elif op == "BEGIN":
            stack.append({})
            in_tx += 1
        elif op == "ROLLBACK":
            if in_tx == 0:
                out.append("NO TRANSACTION")
            else:
                stack.pop()
                in_tx -= 1
        elif op == "COMMIT":
            if in_tx == 0:
                out.append("NO TRANSACTION")
            else:
                top = stack.pop()
                stack[-1].update(top)
                in_tx -= 1
    return out

import java.util.*;

class Solution {
    static final String DELETED = "\0DEL\0";
    public String[] runNestedTransactions(String[] commands) {
        Deque<Map<String, String>> stack = new ArrayDeque<>();
        stack.push(new HashMap<>());
        int inTx = 0;
        List<String> out = new ArrayList<>();
        for (String cmd : commands) {
            String[] p = cmd.split("\\s+");
            switch (p[0]) {
                case "SET": stack.peek().put(p[1], p[2]); break;
                case "DELETE": stack.peek().put(p[1], DELETED); break;
                case "GET": {
                    String v = null;
                    for (Map<String, String> layer : stack) {
                        if (layer.containsKey(p[1])) { v = layer.get(p[1]); break; }
                    }
                    out.add(v == null || v.equals(DELETED) ? "NULL" : v);
                    break;
                }
                case "BEGIN": stack.push(new HashMap<>()); inTx++; break;
                case "ROLLBACK":
                    if (inTx == 0) out.add("NO TRANSACTION"); else { stack.pop(); inTx--; }
                    break;
                case "COMMIT":
                    if (inTx == 0) out.add("NO TRANSACTION");
                    else { Map<String, String> top = stack.pop(); stack.peek().putAll(top); inTx--; }
                    break;
            }
        }
        return out.toArray(new String[0]);
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
    const string DEL = "\0DEL\0";
public:
    vector<string> runNestedTransactions(vector<string>& commands) {
        vector<unordered_map<string,string>> stack(1);
        int inTx = 0;
        vector<string> out;
        for (auto& cmd : commands) {
            stringstream ss(cmd); vector<string> p; string t;
            while (ss >> t) p.push_back(t);
            if (p[0] == "SET") stack.back()[p[1]] = p[2];
            else if (p[0] == "DELETE") stack.back()[p[1]] = DEL;
            else if (p[0] == "GET") {
                string v; bool found = false;
                for (auto it = stack.rbegin(); it != stack.rend(); ++it) {
                    auto f = it->find(p[1]);
                    if (f != it->end()) { v = f->second; found = true; break; }
                }
                out.push_back(!found || v == DEL ? "NULL" : v);
            } else if (p[0] == "BEGIN") { stack.emplace_back(); inTx++; }
            else if (p[0] == "ROLLBACK") {
                if (inTx == 0) out.push_back("NO TRANSACTION");
                else { stack.pop_back(); inTx--; }
            } else if (p[0] == "COMMIT") {
                if (inTx == 0) out.push_back("NO TRANSACTION");
                else { auto top = stack.back(); stack.pop_back(); for (auto& kv : top) stack.back()[kv.first] = kv.second; inTx--; }
            }
        }
        return out;
    }
};