TradeDesk

01Cloud Storage System (4 Progressive Levels)

Implement a simple cloud storage system. All operations should be supported as listed below. The task consists of several levels; subsequent levels are opened when the current level is correctly solved. The system should be in-memory; you don't need to work with the real filesystem.

It is guaranteed that the given queries will never call operations that result in collisions between file and directory names.

Level 1 — Basic File Manipulation

boolean addFile(String name, int capacity) — add a new file name to the storage. capacity is its size in bytes. The current operation fails if a file with the same name already exists. Returns true if added successfully or false otherwise.
Optional<Integer> getFileSize(String name) — return the size of the file if it exists, or Optional.empty() otherwise.
Optional<Integer> deleteFile(String name) — delete the file. Returns the deleted file's size if successful, or Optional.empty() if the file does not exist.

Level 2 — Prefix Queries

List<String> getNFilesByPrefix(String prefix, int n) — return the list of strings representing names of the top n largest files with names starting with prefix, in the format "name1(size1)", "name2(size2)", ...". Sorted by size descending; tie broken by name ascending. Empty list if no match; fewer than n matches just returns all of them.

Level 3 — Multi-User with Capacity Limits

boolean addUser(String userId, int capacity) — add a new user. Fails if userId exists.
Optional<Integer> addFileBy(String userId, String name, int size) — like addFile but checks user's remaining quota. Returns new remaining capacity on success.
Optional<Integer> mergeUser(String userId1, String userId2) — merge user2 into user1: user2's files become owned by user1, user1's capacity gains user2's remaining capacity. Returns user1's new total capacity. Optional.empty() if either missing or ids equal.

All Level 1 addFile calls are made by user "admin" who has unlimited storage.

Level 4 — Backup and Restore

Optional<Integer> backupUser(String userId) — snapshot all files owned by userId (names + sizes) on a separate store, isolated from later mutations. Overwrites previous backup. Returns the number of backed-up files.
Optional<Integer> restoreUser(String userId) — restore the latest backup. If no backup exists, all of userId's files are deleted. Files whose name was taken by another user after backup are skipped. Returns the number of successfully restored files. mergeUser does not affect userId1's backup; userId2's backup is deleted along with the user.

解法

分四级设计：

Level 1：files: name → (size, owner)，默认 owner 是 admin。
Level 2：线性扫 files 按前缀过滤，按 (-size, name) 排序取前 n。
Level 3：users: id → (capacity, used)。addFileBy 检查剩余配额；mergeUser 把 user2 的文件归到 user1，配额相加，再删除 user2。
Level 4：快照字典 backup: userId → {name: size}。restoreUser 先删该用户当前文件，再回放备份，遇到被别的用户占用的文件名跳过。

复杂度：addFile / getFileSize / deleteFile / addFileBy 为 O(1)；getNFilesByPrefix 为 O(F + matched · log matched)；mergeUser 为 O(F)；backupUser / restoreUser 为 O(F)。

class CloudStorage:
    ADMIN = "admin"

    def __init__(self):
        self.files = {}
        self.users = {self.ADMIN: {"cap": float('inf'), "used": 0}}
        self.backups = {}

    def addFile(self, name, capacity):
        if name in self.files:
            return False
        self.files[name] = {"size": capacity, "owner": self.ADMIN}
        self.users[self.ADMIN]["used"] += capacity
        return True

    def getFileSize(self, name):
        return self.files[name]["size"] if name in self.files else None

    def deleteFile(self, name):
        if name not in self.files:
            return None
        size = self.files[name]["size"]
        owner = self.files[name]["owner"]
        self.users[owner]["used"] -= size
        del self.files[name]
        return size

    def getNFilesByPrefix(self, prefix, n):
        matched = [(name, info["size"]) for name, info in self.files.items() if name.startswith(prefix)]
        matched.sort(key=lambda x: (-x[1], x[0]))
        return [f"{name}({size})" for name, size in matched[:n]]

    def addUser(self, userId, capacity):
        if userId in self.users:
            return False
        self.users[userId] = {"cap": capacity, "used": 0}
        return True

    def addFileBy(self, userId, name, size):
        if userId not in self.users or name in self.files:
            return None
        u = self.users[userId]
        if u["used"] + size > u["cap"]:
            return None
        self.files[name] = {"size": size, "owner": userId}
        u["used"] += size
        return u["cap"] - u["used"]

    def mergeUser(self, u1, u2):
        if u1 == u2 or u1 not in self.users or u2 not in self.users:
            return None
        for name, info in self.files.items():
            if info["owner"] == u2:
                info["owner"] = u1
        self.users[u1]["cap"] += self.users[u2]["cap"] - self.users[u2]["used"]
        self.users[u1]["used"] += self.users[u2]["used"]
        del self.users[u2]
        self.backups.pop(u2, None)
        return self.users[u1]["cap"]

    def backupUser(self, userId):
        if userId not in self.users:
            return None
        snap = {name: info["size"] for name, info in self.files.items() if info["owner"] == userId}
        self.backups[userId] = snap
        return len(snap)

    def restoreUser(self, userId):
        if userId not in self.users:
            return None
        to_del = [n for n, info in self.files.items() if info["owner"] == userId]
        for n in to_del:
            self.users[userId]["used"] -= self.files[n]["size"]
            del self.files[n]
        snap = self.backups.get(userId)
        if snap is None:
            return 0
        restored = 0
        u = self.users[userId]
        for n, size in snap.items():
            if n in self.files:
                continue
            if u["used"] + size > u["cap"]:
                continue
            self.files[n] = {"size": size, "owner": userId}
            u["used"] += size
            restored += 1
        return restored

import java.util.*;

class CloudStorage {
    static final String ADMIN = "admin";

    static class FileInfo { int size; String owner; FileInfo(int s, String o){ size=s; owner=o; } }
    static class User { long cap; long used; User(long c){ cap=c; used=0; } }

    Map<String, FileInfo> files = new HashMap<>();
    Map<String, User> users = new HashMap<>();
    Map<String, Map<String, Integer>> backups = new HashMap<>();

    CloudStorage() { users.put(ADMIN, new User(Long.MAX_VALUE)); }

    public boolean addFile(String name, int capacity) {
        if (files.containsKey(name)) return false;
        files.put(name, new FileInfo(capacity, ADMIN));
        users.get(ADMIN).used += capacity;
        return true;
    }
    public Optional<Integer> getFileSize(String name) {
        return files.containsKey(name) ? Optional.of(files.get(name).size) : Optional.empty();
    }
    public Optional<Integer> deleteFile(String name) {
        FileInfo f = files.remove(name);
        if (f == null) return Optional.empty();
        users.get(f.owner).used -= f.size;
        return Optional.of(f.size);
    }
    public List<String> getNFilesByPrefix(String prefix, int n) {
        List<Map.Entry<String, FileInfo>> matched = new ArrayList<>();
        for (var e : files.entrySet()) if (e.getKey().startsWith(prefix)) matched.add(e);
        matched.sort((a, b) -> a.getValue().size != b.getValue().size
                ? Integer.compare(b.getValue().size, a.getValue().size)
                : a.getKey().compareTo(b.getKey()));
        List<String> out = new ArrayList<>();
        for (int i = 0; i < Math.min(n, matched.size()); i++)
            out.add(matched.get(i).getKey() + "(" + matched.get(i).getValue().size + ")");
        return out;
    }
    public boolean addUser(String userId, int capacity) {
        if (users.containsKey(userId)) return false;
        users.put(userId, new User(capacity));
        return true;
    }
    public Optional<Long> addFileBy(String userId, String name, int size) {
        if (!users.containsKey(userId) || files.containsKey(name)) return Optional.empty();
        User u = users.get(userId);
        if (u.used + size > u.cap) return Optional.empty();
        files.put(name, new FileInfo(size, userId));
        u.used += size;
        return Optional.of(u.cap - u.used);
    }
    public Optional<Long> mergeUser(String u1, String u2) {
        if (u1.equals(u2) || !users.containsKey(u1) || !users.containsKey(u2)) return Optional.empty();
        for (FileInfo f : files.values()) if (f.owner.equals(u2)) f.owner = u1;
        users.get(u1).cap += users.get(u2).cap - users.get(u2).used;
        users.get(u1).used += users.get(u2).used;
        users.remove(u2);
        backups.remove(u2);
        return Optional.of(users.get(u1).cap);
    }
    public Optional<Integer> backupUser(String userId) {
        if (!users.containsKey(userId)) return Optional.empty();
        Map<String, Integer> snap = new HashMap<>();
        for (var e : files.entrySet())
            if (e.getValue().owner.equals(userId)) snap.put(e.getKey(), e.getValue().size);
        backups.put(userId, snap);
        return Optional.of(snap.size());
    }
    public Optional<Integer> restoreUser(String userId) {
        if (!users.containsKey(userId)) return Optional.empty();
        List<String> toDel = new ArrayList<>();
        for (var e : files.entrySet()) if (e.getValue().owner.equals(userId)) toDel.add(e.getKey());
        for (String n : toDel) { users.get(userId).used -= files.get(n).size; files.remove(n); }
        Map<String, Integer> snap = backups.get(userId);
        if (snap == null) return Optional.of(0);
        int restored = 0;
        User u = users.get(userId);
        for (var e : snap.entrySet()) {
            if (files.containsKey(e.getKey())) continue;
            if (u.used + e.getValue() > u.cap) continue;
            files.put(e.getKey(), new FileInfo(e.getValue(), userId));
            u.used += e.getValue();
            restored++;
        }
        return Optional.of(restored);
    }
}

#include <unordered_map>
#include <string>
#include <vector>
#include <optional>
#include <algorithm>
#include <climits>
using namespace std;

class CloudStorage {
    struct FileInfo { long long size; string owner; };
    struct User { long long cap; long long used; };
    unordered_map<string, FileInfo> files;
    unordered_map<string, User> users;
    unordered_map<string, unordered_map<string, long long>> backups;
    static constexpr long long INF = LLONG_MAX / 4;
public:
    CloudStorage() { users["admin"] = {INF, 0}; }

    bool addFile(const string& name, long long cap) {
        if (files.count(name)) return false;
        files[name] = {cap, "admin"};
        users["admin"].used += cap;
        return true;
    }
    optional<long long> getFileSize(const string& name) {
        auto it = files.find(name);
        return it == files.end() ? nullopt : optional<long long>(it->second.size);
    }
    optional<long long> deleteFile(const string& name) {
        auto it = files.find(name);
        if (it == files.end()) return nullopt;
        long long s = it->second.size;
        users[it->second.owner].used -= s;
        files.erase(it);
        return s;
    }
    vector<string> getNFilesByPrefix(const string& prefix, int n) {
        vector<pair<string, long long>> matched;
        for (auto& [k, v] : files)
            if (k.rfind(prefix, 0) == 0) matched.push_back({k, v.size});
        sort(matched.begin(), matched.end(), [](auto& a, auto& b){
            return a.second != b.second ? a.second > b.second : a.first < b.first;
        });
        vector<string> out;
        for (int i = 0; i < (int)min<size_t>(n, matched.size()); i++)
            out.push_back(matched[i].first + "(" + to_string(matched[i].second) + ")");
        return out;
    }
    bool addUser(const string& id, long long cap) {
        if (users.count(id)) return false;
        users[id] = {cap, 0};
        return true;
    }
    optional<long long> addFileBy(const string& id, const string& name, long long size) {
        if (!users.count(id) || files.count(name)) return nullopt;
        auto& u = users[id];
        if (u.used + size > u.cap) return nullopt;
        files[name] = {size, id};
        u.used += size;
        return u.cap - u.used;
    }
    optional<long long> mergeUser(const string& a, const string& b) {
        if (a == b || !users.count(a) || !users.count(b)) return nullopt;
        for (auto& [_, f] : files) if (f.owner == b) f.owner = a;
        users[a].cap += users[b].cap - users[b].used;
        users[a].used += users[b].used;
        users.erase(b);
        backups.erase(b);
        return users[a].cap;
    }
    optional<long long> backupUser(const string& id) {
        if (!users.count(id)) return nullopt;
        unordered_map<string, long long> snap;
        for (auto& [k, v] : files) if (v.owner == id) snap[k] = v.size;
        backups[id] = snap;
        return (long long)snap.size();
    }
    optional<long long> restoreUser(const string& id) {
        if (!users.count(id)) return nullopt;
        vector<string> del;
        for (auto& [k, v] : files) if (v.owner == id) del.push_back(k);
        for (auto& k : del) { users[id].used -= files[k].size; files.erase(k); }
        auto it = backups.find(id);
        if (it == backups.end()) return 0LL;
        long long restored = 0;
        auto& u = users[id];
        for (auto& [k, sz] : it->second) {
            if (files.count(k)) continue;
            if (u.used + sz > u.cap) continue;
            files[k] = {sz, id};
            u.used += sz;
            restored++;
        }
        return restored;
    }
};

02Light Sources

In the expanse of a linear coordinate line, a celestial spectacle unfolds as numerous luminous orbs, each possessing its unique radiance, are strategically placed. The intricate details of these radiant spheres are cataloged within a two-dimensional array, dubbed "celestialArrangements." Each entry in this array encapsulates the essence of a single orb, revealing both its position and the extent of its luminosity. Within the realm of "celestialArrangements":

The ethereal coordinates of the ith orb are encapsulated in celestialArrangements[i][0].
Manifesting its brilliance, the positive radius of the ith orb's radiance is manifested through celestialArrangements[i][1]. As the night unfolds, each orb casts its enchanting glow, spanning from celestialArrangements[i][0] - celestialArrangements[i][1] to celestialArrangements[i][0] + celestialArrangements[i][1], inclusively. Yet, amidst this celestial ballet, a quest awaits. Adventurers must discern the mystical allure of those coordinates touched by the singular radiance of exactly one orb. For original prompt, pls refer to source images ˚₊‧꒰ა໒꒱ ‧₊˚

Constraints

1 ≤ celestialArrangements.length ≤ 10^5
-10^9 ≤ celestialArrangements[i][0] ≤ 10^9
1 ≤ celestialArrangements[i][1] ≤ 10^9

Example 1

Input:

lightSources = [[-2, 3], [2, 3], [2, 1]]

Output:

Explanation: For a set of luminous orbs with their respective radii, represented as [[-2, 3], [2, 3], [2, 1]], the resulting illumination yields 6 distinct sections. In the visual depiction, both overlapping and separate illuminated areas are observed, extending along the coordinate line from -6 to 6.

解法

扫描线：每盏灯产生区间 [c−r, c+r]，每段端点事件 +1/-1。把所有事件按坐标排序，扫描时维护当前覆盖数 cnt；累加 cnt==1 段的总长度。注意坐标范围可能为负。时间 O(n log n)。

from typing import List

def count_single_coverage(light_sources: List[List[int]]) -> int:
    events = []
    for c, r in light_sources:
        events.append((c - r, 1))
        events.append((c + r + 1, -1))
    events.sort()
    cnt = 0
    total = 0
    prev = None
    for x, delta in events:
        if prev is not None and cnt == 1:
            total += x - prev
        cnt += delta
        prev = x
    return total

import java.util.*;

class Solution {
    public long countSingleCoverage(int[][] lightSources) {
        List<int[]> events = new ArrayList<>();
        for (int[] s : lightSources) {
            events.add(new int[]{s[0] - s[1], 1});
            events.add(new int[]{s[0] + s[1] + 1, -1});
        }
        events.sort((a, b) -> a[0] - b[0]);
        long total = 0;
        int cnt = 0;
        Integer prev = null;
        for (int[] e : events) {
            if (prev != null && cnt == 1) total += e[0] - prev;
            cnt += e[1];
            prev = e[0];
        }
        return total;
    }
}

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

class Solution {
public:
    long long countSingleCoverage(vector<vector<int>>& lightSources) {
        vector<pair<int, int>> events;
        for (auto& s : lightSources) {
            events.push_back({s[0] - s[1], 1});
            events.push_back({s[0] + s[1] + 1, -1});
        }
        sort(events.begin(), events.end());
        long long total = 0;
        int cnt = 0;
        bool first = true;
        int prev = 0;
        for (auto& [x, d] : events) {
            if (!first && cnt == 1) total += x - prev;
            cnt += d;
            prev = x;
            first = false;
        }
        return total;
    }
};

03Earn the Most

Let's delve into the art of crafting an algorithm , tailor-made for the exhilarating realm of currency trading. Picture a bustling marketplace where fortunes are won and lost with each passing day. Our algorithm, honed to perfection, is poised to navigate this volatile landscape with finesse. Our journey begins with two essential components: "prices" and "strategy." The former, a tapestry of daily currency prices, while the latter serves as our guiding light, indicating whether to buy, sell, or hold our precious assets. But here's where it gets intriguing. We're granted the power to tweak our strategy, to optimize our trading performance. How, you ask? By strategically selecting a range of consecutive days, precisely Mr."mrk" in length, and orchestrating a symphony of buying and selling within that span. Imagine it as a conductor wielding a baton, shaping the melody of our trades. The first half of our chosen range, we keep in a state of anticipation, a silent hold, while in the latter half, we unleash the power of our convictions, executing sell orders with precision. And what's our goal amidst this dance of numbers? It's simple yet profound: to maximize our total profit. We aim to strike a chord of prosperity, where the sum of our selling rates eclipses the sum of our buying rates, paving the way for wealth and prosperity. But remember, in this realm of uncertainty, where fortunes can shift in the blink of an eye, one must tread carefully. Yet armed with strategy and insight, we embark on this odyssey, ready to seize the opportunities that lie ahead. For original prompt, pls refer to source images ₍ᐢ. .ᐢ₎

Constraints

1 ≤ prices.length ≤ 10^5
1 ≤ prices[i] ≤ 10^4
strategy[i] ∈ {'B', 'S', 'H'}
1 ≤ mrk ≤ prices.length，且 mrk 为偶数

解法

strategy 中 B=买、S=卖、H=持有。基础利润 = Σ (prices[i] if S else −prices[i] if B else 0)。允许选一个长度 mrk 的连续区间，前 mrk/2 天强制 H、后 mrk/2 天强制 S。求最大化新利润。对每个起点 i，新增 = − 原区间贡献 + 强制区间贡献。滑动窗口预计算每个长度 mrk 的区间的"基础贡献"和"被覆盖时新贡献"。时间 O(n)。

from typing import List

def earn_the_most(prices: List[int], strategy: List[str], mrk: int) -> int:
    n = len(prices)
    base = 0
    for i in range(n):
        if strategy[i] == 'S': base += prices[i]
        elif strategy[i] == 'B': base -= prices[i]

    # contribution if window [i, i+mrk-1] is replaced: first mrk/2 H, last mrk/2 S
    h = mrk // 2
    best = base
    for i in range(n - mrk + 1):
        old = 0
        for j in range(mrk):
            if strategy[i + j] == 'S': old += prices[i + j]
            elif strategy[i + j] == 'B': old -= prices[i + j]
        new = sum(prices[i + h: i + mrk])
        best = max(best, base - old + new)
    return best

import java.util.*;

class Solution {
    public long earnTheMost(int[] prices, char[] strategy, int mrk) {
        int n = prices.length;
        long base = 0;
        for (int i = 0; i < n; i++) {
            if (strategy[i] == 'S') base += prices[i];
            else if (strategy[i] == 'B') base -= prices[i];
        }
        int h = mrk / 2;
        long best = base;
        for (int i = 0; i + mrk <= n; i++) {
            long old = 0, neu = 0;
            for (int j = 0; j < mrk; j++) {
                if (strategy[i + j] == 'S') old += prices[i + j];
                else if (strategy[i + j] == 'B') old -= prices[i + j];
                if (j >= h) neu += prices[i + j];
            }
            best = Math.max(best, base - old + neu);
        }
        return best;
    }
}

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

class Solution {
public:
    long long earnTheMost(vector<int>& prices, string strategy, int mrk) {
        int n = prices.size();
        long long base = 0;
        for (int i = 0; i < n; i++) {
            if (strategy[i] == 'S') base += prices[i];
            else if (strategy[i] == 'B') base -= prices[i];
        }
        int h = mrk / 2;
        long long best = base;
        for (int i = 0; i + mrk <= n; i++) {
            long long old = 0, neu = 0;
            for (int j = 0; j < mrk; j++) {
                if (strategy[i + j] == 'S') old += prices[i + j];
                else if (strategy[i + j] == 'B') old -= prices[i + j];
                if (j >= h) neu += prices[i + j];
            }
            best = max(best, base - old + neu);
        }
        return best;
    }
};

Pro 会员

解锁剩余 5 道 OA 真题

开通后立即解锁完整题面 + Python / Java / C++ 三语题解。全站 165 家公司 · 1000+ 道 OA · 月度更新。

开通会员已是会员，去登录