系統設計題 — 實作範例

# python
# LC 432 - All O`one Data Structure
# IDEA: key -> count map + a doubly linked list of buckets ordered by count;
#       inc / dec move a key to the neighbouring bucket, creating it beside the old one
# time = O(1) per call, space = O(number of keys)
class Bucket:
    def __init__(self, count):
        self.count = count
        self.keys = set()
        self.prev = None
        self.next = None

class AllOne:
    def __init__(self):
        self.count_of = {}          # key -> count
        self.bucket_of = {}         # count -> Bucket
        self.head = Bucket(0)       # sentinel before the smallest count
        self.tail = Bucket(0)       # sentinel after the largest count
        self.head.next = self.tail
        self.tail.prev = self.head

    def _insert_after(self, node, new_node):
        new_node.prev = node
        new_node.next = node.next
        node.next.prev = new_node
        node.next = new_node

    def _remove_if_empty(self, bucket):
        if not bucket.keys:
            bucket.prev.next = bucket.next
            bucket.next.prev = bucket.prev
            del self.bucket_of[bucket.count]

    def inc(self, key):
        count = self.count_of.get(key, 0)
        here = self.bucket_of[count] if count else self.head
        if count + 1 not in self.bucket_of:              # the next bucket goes right after this one
            new_bucket = Bucket(count + 1)
            self.bucket_of[count + 1] = new_bucket
            self._insert_after(here, new_bucket)
        self.bucket_of[count + 1].keys.add(key)
        self.count_of[key] = count + 1
        if count:
            here.keys.remove(key)
            self._remove_if_empty(here)

    def dec(self, key):
        count = self.count_of[key]                      # the problem guarantees key exists
        here = self.bucket_of[count]
        if count == 1:
            del self.count_of[key]
        else:
            if count - 1 not in self.bucket_of:          # the previous bucket goes right before this one
                new_bucket = Bucket(count - 1)
                self.bucket_of[count - 1] = new_bucket
                self._insert_after(here.prev, new_bucket)
            self.bucket_of[count - 1].keys.add(key)
            self.count_of[key] = count - 1
        here.keys.remove(key)
        self._remove_if_empty(here)

    def getMaxKey(self):
        if self.tail.prev is self.head:
            return ""
        return next(iter(self.tail.prev.keys))

    def getMinKey(self):
        if self.head.next is self.tail:
            return ""
        return next(iter(self.head.next.keys))

# python
# LC 355 - Design Twitter
# IDEA: per-user tweet lists in post order + a follow set; getNewsFeed = lazy k-way merge, newest first
# time = O(1) post / follow / unfollow, O(k + 10 log k) getNewsFeed for k followees; space = O(users + tweets)
import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.clock = 0
        self.tweets = defaultdict(list)     # user -> [(time, tweetId)], oldest first
        self.following = defaultdict(set)   # user -> users they follow

    def postTweet(self, userId, tweetId):
        self.tweets[userId].append((self.clock, tweetId))
        self.clock += 1

    def getNewsFeed(self, userId):
        heap = []                                       # (-time, tweetId, user, index in that user's list)
        for user in self.following[userId] | {userId}: # a user always sees their own tweets
            if self.tweets[user]:
                i = len(self.tweets[user]) - 1          # newest tweet of this user
                time, tweet_id = self.tweets[user][i]
                heap.append((-time, tweet_id, user, i))
        heapq.heapify(heap)
        feed = []
        while heap and len(feed) < 10:
            _, tweet_id, user, i = heapq.heappop(heap)
            feed.append(tweet_id)
            if i > 0:                                   # this user's next-newest tweet
                time, next_id = self.tweets[user][i - 1]
                heapq.heappush(heap, (-time, next_id, user, i - 1))
        return feed

    def follow(self, followerId, followeeId):
        self.following[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        self.following[followerId].discard(followeeId)

# python
# LC 642 - Design Search Autocomplete System
# IDEA: each trie node keeps the set of sentences under it; a live cursor follows the typed prefix;
#       '#' records the sentence (count + 1) and resets the cursor
# time = O(m log m) per keystroke for the m sentences under the cursor, space = O(total characters)
from collections import defaultdict

class TrieNode:
    def __init__(self):
        self.children = {}
        self.sentences = set()

class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.root = TrieNode()
        self.count = defaultdict(int)       # sentence -> hot degree
        for sentence, t in zip(sentences, times):
            self.count[sentence] += t
            self._add(sentence)
        self.typed = ""
        self.cursor = self.root

    def _add(self, sentence):
        node = self.root
        for ch in sentence:
            node = node.children.setdefault(ch, TrieNode())
            node.sentences.add(sentence)

    def input(self, c):
        if c == "#":
            self.count[self.typed] += 1
            self._add(self.typed)
            self.typed = ""
            self.cursor = self.root
            return []
        self.typed += c
        if self.cursor is not None:
            self.cursor = self.cursor.children.get(c)
        if self.cursor is None:
            return []
        ranked = sorted(self.cursor.sentences, key=lambda s: (-self.count[s], s))
        return ranked[:3]

# python
# LC 362 - Design Hit Counter
# IDEA: deque of hit timestamps; evict from the left everything at or before timestamp - 300
# time = O(1) amortised per call, space = O(hits in the last 300 s)
from collections import deque

class HitCounter:
    def __init__(self):
        self.hits = deque()

    def hit(self, timestamp):
        self.hits.append(timestamp)

    def getHits(self, timestamp):
        while self.hits and self.hits[0] <= timestamp - 300:
            self.hits.popleft()
        return len(self.hits)

# python
# LC 362 - Design Hit Counter (fixed 300 buckets)
# IDEA: bucket i holds the hits of the last second that mapped to i; a stale bucket is reset on reuse
# time = O(1) hit, O(300) getHits; space = O(300)
class HitCounterBuckets:
    def __init__(self):
        self.times = [0] * 300
        self.counts = [0] * 300

    def hit(self, timestamp):
        i = timestamp % 300
        if self.times[i] != timestamp:      # this bucket still holds an older second
            self.times[i] = timestamp
            self.counts[i] = 0
        self.counts[i] += 1

    def getHits(self, timestamp):
        total = 0
        for i in range(300):
            if timestamp - self.times[i] < 300:
                total += self.counts[i]
        return total

# python
# LC 353 - Design Snake Game
# IDEA: deque body + set of occupied cells; pop the tail unless eating, then test the new head
# time = O(1) per move, space = O(width * height)
from collections import deque

class SnakeGame:
    def __init__(self, width, height, food):
        self.width = width
        self.height = height
        self.food = deque(food)
        self.body = deque([(0, 0)])     # head at index 0
        self.occupied = {(0, 0)}
        self.score = 0

    def move(self, direction):
        dr, dc = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}[direction]
        row, col = self.body[0][0] + dr, self.body[0][1] + dc
        if not (0 <= row < self.height and 0 <= col < self.width):
            return -1
        if self.food and [row, col] == self.food[0]:
            self.food.popleft()             # eat: the tail stays, the snake grows
            self.score += 1
        else:
            tail = self.body.pop()
            self.occupied.remove(tail)
        if (row, col) in self.occupied:
            return -1
        self.body.appendleft((row, col))
        self.occupied.add((row, col))
        return self.score

# python
# LC 1381 - Design a Stack With Increment Operation
# IDEA: inc[i] = pending amount for stack[0..i]; pop adds inc[top] and passes it down to top - 1
# time = O(1) per push / pop / increment, space = O(maxSize)
class CustomStack:
    def __init__(self, maxSize):
        self.max_size = maxSize
        self.stack = []
        self.inc = []           # inc[i] applies to stack[0..i]

    def push(self, x):
        if len(self.stack) < self.max_size:
            self.stack.append(x)
            self.inc.append(0)

    def pop(self):
        if not self.stack:
            return -1
        add = self.inc.pop()
        if self.inc:
            self.inc[-1] += add  # the element below inherits the pending delta
        return self.stack.pop() + add

    def increment(self, k, val):
        i = min(k, len(self.stack)) - 1
        if i >= 0:
            self.inc[i] += val

// java
// LC 1381 - Design a Stack With Increment Operation
// IDEA: inc[i] = amount to add to stack[0..i]; on pop, hand the delta down to i - 1
// time = O(1) per push / pop / increment, space = O(maxSize)
class CustomStack {
    private final int[] stack;
    private final int[] inc;
    private int size = 0;

    public CustomStack(int maxSize) {
        stack = new int[maxSize];
        inc = new int[maxSize];
    }

    public void push(int x) {
        if (size < stack.length) {
            stack[size++] = x;
        }
    }

    public int pop() {
        if (size == 0) {
            return -1;
        }
        size--;
        int result = stack[size] + inc[size];
        if (size > 0) {
            inc[size - 1] += inc[size];   // propagate the pending delta downwards
        }
        inc[size] = 0;                    // the slot will be reused by the next push
        return result;
    }

    public void increment(int k, int val) {
        int i = Math.min(k, size) - 1;    // mark only the k-th element
        if (i >= 0) {
            inc[i] += val;
        }
    }
}

# python
# LC 895 - Maximum Frequency Stack
# IDEA: value -> count, count -> stack of values; pop = top of the max-count stack
# time = O(1) per push / pop, space = O(n)
from collections import defaultdict

class FreqStack:
    def __init__(self):
        self.freq = defaultdict(int)     # value -> count
        self.group = defaultdict(list)   # count -> values that reached it, in push order
        self.max_freq = 0

    def push(self, val):
        self.freq[val] += 1
        f = self.freq[val]
        self.max_freq = max(self.max_freq, f)
        self.group[f].append(val)

    def pop(self):
        val = self.group[self.max_freq].pop()
        self.freq[val] -= 1
        if not self.group[self.max_freq]:
            self.max_freq -= 1
        return val

// java
// LC 895 - Maximum Frequency Stack
// IDEA: bucket values by frequency, each bucket a stack -> pop = top of the maxFreq bucket
// time = O(1) per push / pop, space = O(n)
class FreqStack {
    private final Map<Integer, Integer> freq = new HashMap<>();          // value -> count
    private final Map<Integer, Deque<Integer>> group = new HashMap<>();  // count -> stack of values
    private int maxFreq = 0;

    public void push(int val) {
        int f = freq.merge(val, 1, Integer::sum);
        maxFreq = Math.max(maxFreq, f);
        group.computeIfAbsent(f, x -> new ArrayDeque<>()).push(val);     // keep copies in 1..f
    }

    public int pop() {
        Deque<Integer> top = group.get(maxFreq);
        int val = top.pop();
        freq.merge(val, -1, Integer::sum);
        if (top.isEmpty()) {
            maxFreq--;   // buckets are dense: maxFreq only ever drops by 1
        }
        return val;
    }
}

# python
# LC 981 - Time Based Key-Value Store
# IDEA: key -> parallel lists of times and values (appended in time order); get = floor by bisect
# time = O(1) set, O(log n) get; space = O(n)
import bisect
from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.times = defaultdict(list)    # key -> timestamps, increasing
        self.values = defaultdict(list)   # key -> values, aligned with times

    def set(self, key, value, timestamp):
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key, timestamp):
        i = bisect.bisect_right(self.times[key], timestamp) - 1   # last time <= timestamp
        return self.values[key][i] if i >= 0 else ""

// java
// LC 981 - Time Based Key-Value Store
// IDEA: key -> list of (time, value) appended in time order; get = binary search for the last time <= t
// time = O(1) set, O(log n) get; space = O(n)
class TimeMap {
    private final Map<String, List<Integer>> times = new HashMap<>();
    private final Map<String, List<String>> values = new HashMap<>();

    public void set(String key, String value, int timestamp) {
        times.computeIfAbsent(key, k -> new ArrayList<>()).add(timestamp);
        values.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
    }

    public String get(String key, int timestamp) {
        List<Integer> ts = times.get(key);
        if (ts == null) return "";
        int lo = 0, hi = ts.size() - 1, found = -1;
        while (lo <= hi) {                      // last index with ts[i] <= timestamp
            int mid = lo + (hi - lo) / 2;
            if (ts.get(mid) <= timestamp) {
                found = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return found == -1 ? "" : values.get(key).get(found);
    }
}

# python
# LC 729 - My Calendar I
# IDEA: sorted starts with aligned ends; check the floor (spills into us?) and the ceiling (we spill into it?)
# time = O(log n) search + O(n) list insert per book, space = O(n)
import bisect

class MyCalendar:
    def __init__(self):
        self.starts = []
        self.ends = []      # aligned with starts

    def book(self, start, end):
        i = bisect.bisect_right(self.starts, start) - 1     # floor: last start <= start
        if i >= 0 and self.ends[i] > start:
            return False
        j = i + 1                                           # ceiling: first start > start
        if j < len(self.starts) and self.starts[j] < end:
            return False
        self.starts.insert(j, start)
        self.ends.insert(j, end)
        return True

// java
// LC 729 - My Calendar I
// IDEA: TreeMap start -> end; a booking is legal iff it fits between its two neighbours
// time = O(log n) per book, space = O(n)
class MyCalendar {
    private final TreeMap<Integer, Integer> booked = new TreeMap<>();   // start -> end

    public boolean book(int start, int end) {
        Integer prev = booked.floorKey(start);     // latest booking starting <= start
        if (prev != null && booked.get(prev) > start) {
            return false;                          // prev spills into us
        }
        Integer next = booked.ceilingKey(start);   // earliest booking starting >= start
        if (next != null && next < end) {
            return false;                          // we spill into next
        }
        booked.put(start, end);
        return true;
    }
}

# python
# LC 731 - My Calendar II
# IDEA: delta map +1 / -1, sweep in key order; reject and roll back if 3 bookings overlap
# time = O(n log n) per book, space = O(n)
from collections import defaultdict

class MyCalendarTwo:
    def __init__(self):
        self.delta = defaultdict(int)

    def book(self, start, end):
        self.delta[start] += 1
        self.delta[end] -= 1
        active = 0
        for t in sorted(self.delta):
            active += self.delta[t]
            if active >= 3:                 # triple booking: undo and refuse
                self.delta[start] -= 1
                self.delta[end] += 1
                return False
        return True

# python
# LC 732 - My Calendar III
# IDEA: delta map +1 / -1; the max prefix sum in key order is the max concurrent bookings
# time = O(n log n) per book, space = O(n)
from collections import defaultdict

class MyCalendarThree:
    def __init__(self):
        self.delta = defaultdict(int)

    def book(self, start, end):
        self.delta[start] += 1
        self.delta[end] -= 1
        active = best = 0
        for t in sorted(self.delta):
            active += self.delta[t]
            best = max(best, active)
        return best

// java
// LC 732 - My Calendar III
// IDEA: TreeMap as a delta array on a sparse timeline; prefix-sum in key order
// time = O(n) per book (n = distinct endpoints), space = O(n)
class MyCalendarThree {
    private final TreeMap<Integer, Integer> delta = new TreeMap<>();

    public int book(int start, int end) {
        delta.merge(start, 1, Integer::sum);
        delta.merge(end, -1, Integer::sum);
        int active = 0;
        int best = 0;
        for (int d : delta.values()) {     // TreeMap iterates keys ascending
            active += d;
            best = Math.max(best, active);
        }
        return best;
    }
}

# python
# LC 715 - Range Module
# IDEA: parallel sorted lists of disjoint [start, end); add/remove replace the touched run by slice assignment
# time = O(log n) search + O(n) slice per call, space = O(n)
import bisect

class RangeModule:
    def __init__(self):
        self.starts = []
        self.ends = []

    def addRange(self, left, right):
        i = bisect.bisect_left(self.ends, left)        # first interval ending at or after left
        j = bisect.bisect_right(self.starts, right)    # first interval starting after right
        if i < j:                                      # intervals i..j-1 touch [left, right): absorb them
            left = min(left, self.starts[i])
            right = max(right, self.ends[j - 1])
        self.starts[i:j] = [left]
        self.ends[i:j] = [right]

    def queryRange(self, left, right):
        i = bisect.bisect_right(self.starts, left) - 1  # the interval that could contain left
        return i >= 0 and self.ends[i] >= right

    def removeRange(self, left, right):
        i = bisect.bisect_right(self.ends, left)       # first interval ending after left
        j = bisect.bisect_left(self.starts, right)     # first interval starting at or after right
        if i >= j:
            return                                     # nothing overlaps [left, right)
        new_starts, new_ends = [], []
        if self.starts[i] < left:                      # keep the head piece [start, left)
            new_starts.append(self.starts[i])
            new_ends.append(left)
        if self.ends[j - 1] > right:                   # keep the tail piece [right, end)
            new_starts.append(right)
            new_ends.append(self.ends[j - 1])
        self.starts[i:j] = new_starts
        self.ends[i:j] = new_ends

// java
// LC 715 - Range Module
// IDEA: TreeMap of merged disjoint [start, end); add absorbs neighbours, remove re-inserts the surviving pieces
// time = O(log n) amortised per call, space = O(n)
class RangeModule {
    private final TreeMap<Integer, Integer> ranges = new TreeMap<>();   // start -> end

    public void addRange(int left, int right) {
        Integer s = ranges.floorKey(left);
        Integer e = ranges.floorKey(right);
        if (s != null && ranges.get(s) >= left) {
            left = s;                                   // touches or overlaps on the left: absorb
        }
        if (e != null && ranges.get(e) > right) {
            right = ranges.get(e);                      // extends past right: absorb
        }
        ranges.subMap(left, true, right, true).clear(); // drop everything swallowed
        ranges.put(left, right);
    }

    public boolean queryRange(int left, int right) {
        Integer s = ranges.floorKey(left);
        return s != null && ranges.get(s) >= right;     // one merged interval must cover it all
    }

    public void removeRange(int left, int right) {
        Integer s = ranges.floorKey(left);
        Integer e = ranges.floorKey(right);
        if (e != null && ranges.get(e) > right) {
            ranges.put(right, ranges.get(e));           // keep the tail piece [right, oldEnd)
        }
        if (s != null && ranges.get(s) > left) {
            ranges.put(s, left);                        // keep the head piece [oldStart, left)
        }
        ranges.subMap(left, true, right, false).clear();
    }
}

add [10, 20)      -> [10,20)
remove [14, 16)   -> [10,14) [16,20)       (one interval split in two)
query [10, 14)    -> True
query [13, 15)    -> False                 (14..16 was removed)
query [16, 17)    -> True

# python
# LC 1166 - Design File System
# IDEA: map full path -> value; a path may be created only if it is new and its parent exists
# time = O(L) per call for a path of length L, space = O(total path length)
class FileSystem:
    def __init__(self):
        self.value_of = {"": -1}             # the root's parent string, so "/a" has a parent

    def createPath(self, path, value):
        if not path or path == "/" or path in self.value_of:
            return False
        parent = path[:path.rfind("/")]
        if parent not in self.value_of:
            return False
        self.value_of[path] = value
        return True

    def get(self, path):
        if path == "":
            return -1
        return self.value_of.get(path, -1)

# python
# LC 635 - Design Log Storage System
# IDEA: keep (timestamp, id); compare the first k characters, where k is set by the granularity
# time = O(1) put, O(n) retrieve; space = O(n)
class LogSystem:
    PREFIX = {"Year": 4, "Month": 7, "Day": 10, "Hour": 13, "Minute": 16, "Second": 19}

    def __init__(self):
        self.logs = []                       # (timestamp, id)

    def put(self, id, timestamp):
        self.logs.append((timestamp, id))

    def retrieve(self, start, end, granularity):
        k = self.PREFIX[granularity]
        low, high = start[:k], end[:k]
        return [log_id for ts, log_id in self.logs if low <= ts[:k] <= high]

# python
# LC 588 - Design In-Memory File System
# IDEA: nested dict trie: each dir is {"dirs": {}, "files": {}}; walk the path's components
# time = O(L) per walk for a path of L components (+ O(k log k) to sort k names in ls), space = O(total content)
class FileSystem:
    def __init__(self):
        self.root = {"dirs": {}, "files": {}}

    def _walk(self, parts):
        """Return the directory at parts, creating missing ones."""
        node = self.root
        for part in parts:
            node = node["dirs"].setdefault(part, {"dirs": {}, "files": {}})
        return node

    def ls(self, path):
        parts = [p for p in path.split("/") if p]
        if parts:
            parent = self._walk(parts[:-1])
            if parts[-1] in parent["files"]:     # a file lists only itself
                return [parts[-1]]
        node = self._walk(parts)
        return sorted(list(node["dirs"]) + list(node["files"]))

    def mkdir(self, path):
        self._walk([p for p in path.split("/") if p])

    def addContentToFile(self, filePath, content):
        parts = [p for p in filePath.split("/") if p]
        directory = self._walk(parts[:-1])
        directory["files"][parts[-1]] = directory["files"].get(parts[-1], "") + content

    def readContentFromFile(self, filePath):
        parts = [p for p in filePath.split("/") if p]
        return self._walk(parts[:-1])["files"][parts[-1]]

# python
# LC 348 - Design Tic-Tac-Toe
# IDEA: one running sum per row, column and both diagonals; +1 for player 1, -1 for player 2
# time = O(1) per move, space = O(n)
class TicTacToe:
    def __init__(self, n):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diagonal = 0
        self.anti_diagonal = 0

    def move(self, row, col, player):
        value = 1 if player == 1 else -1
        self.rows[row] += value
        self.cols[col] += value
        if row == col:
            self.diagonal += value
        if row + col == self.n - 1:
            self.anti_diagonal += value
        if self.n in (abs(self.rows[row]), abs(self.cols[col]), abs(self.diagonal), abs(self.anti_diagonal)):
            return player
        return 0

# python
# LC 1396 - Design Underground System
# IDEA: open trips id -> (station, time); route (start, end) -> [total time, trips]
# time = O(1) per call, space = O(passengers + routes)
from collections import defaultdict

class UndergroundSystem:
    def __init__(self):
        self.open_trip = {}                          # id -> (station, time)
        self.route = defaultdict(lambda: [0, 0])     # (start, end) -> [total time, trips]

    def checkIn(self, id, stationName, t):
        self.open_trip[id] = (stationName, t)

    def checkOut(self, id, stationName, t):
        start_station, start_time = self.open_trip.pop(id)
        totals = self.route[(start_station, stationName)]
        totals[0] += t - start_time
        totals[1] += 1

    def getAverageTime(self, startStation, endStation):
        total, trips = self.route[(startStation, endStation)]
        return total / trips