5 posts tagged with "Design"

from typing import Optional


class Node:
    def __init__(
        self,
        value=0,
        key=0,  # for eviction
        left: Optional['Node'] = None,
        right: Optional['Node'] = None,
    ):
        self.key = key
        self.value = value
        self.left = left
        self.right = right

    def append(self, node: 'Node'):
        node.left = self
        node.right = self.right
        if self.right:
            self.right.left = node
        self.right = node

    def isolate(self):
        if self.left:
            self.left.right = self.right
        if self.right:
            self.right.left = self.left


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.dict: dict[int, Node] = {}
        self.fresh = Node()
        self.stale = Node()
        self.fresh.right = self.stale
        self.stale.left = self.fresh
        self.amount = 0

    def get(self, key: int) -> int:
        node = self.dict.get(key, Node(-1))
        if key in self.dict:
            node.isolate()
            self.fresh.append(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.dict:
            self.dict[key].isolate()
        else:
            if self.amount == self.capacity:
                evicted = self.stale.left
                if evicted:
                    evicted.isolate()
                    self.dict.pop(evicted.key)
            else:
                self.amount += 1
        node = self.dict.setdefault(key, Node(key=key))
        self.fresh.append(node)
        node.value = value

class SnapshotArray:
    def __init__(self, length: int):
        self._array: list[list[tuple[int, int]]] = [[(-1, 0)] for _ in range(length)]
        self._snap_id = -1

    def set(self, index: int, val: int) -> None:
        self._array[index].append((self._snap_id, val))

    def snap(self) -> int:
        self._snap_id += 1
        return self._snap_id

    @staticmethod
    def bs_r(a, t):
        l, r = 0, len(a)
        while l < r:
            m = (l + r) // 2
            if a[m] > t:
                r = m
            else:
                l = m + 1
        return l

    def get(self, index: int, snap_id: int) -> int:
        low = self.bs_r(self._array[index], (snap_id,))
        return self._array[index][low - 1][1]

from collections import defaultdict


class UndergroundSystem:
    def __init__(self):
        checkInStationNameT = checkOutStationNameT = str
        checkInTimeT = travelTimeT = int
        idT = countT = int
        self.check_in: dict[idT, tuple[checkInTimeT, checkInStationNameT]] = {}
        self.time: defaultdict[
            tuple[checkInStationNameT, checkOutStationNameT], tuple[travelTimeT, countT]
        ] = defaultdict(lambda: (0, 0))

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.check_in[id] = (t, stationName)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        check_in_time, check_in_station_name = self.check_in.pop(id)
        _key = check_in_station_name, stationName
        _travel_time, _count = self.time[_key]
        self.time[_key] = _travel_time + (t - check_in_time), _count + 1

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        _key = startStation, endStation
        travel_time, count = self.time[_key]
        return travel_time / count

import heapq


class SmallestInfiniteSet:
    def __init__(self):
        self.i = 0
        self.q = []

    def popSmallest(self) -> int:
        if self.q:
            return heapq.heappop(self.q)
        self.i += 1
        return self.i

    def addBack(self, num: int) -> None:
        if num <= self.i and num not in self.q:
            heapq.heappush(self.q, num)

from typing import Optional


class Node:
    def __init__(self, is_end: bool = False):
        self.is_end = is_end
        self.children: dict[str, Node] = {}

    def __repr__(self):
        return f'''{'! ' if self.is_end else ''}{self.children}'''


class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            node.children[c] = node.children.get(c, Node())
            node = node.children[c]
        node.is_end = True

    def _last_node_same_with(self, word: str) -> Optional[Node]:
        node = self.root
        for c in word:
            if c not in node.children:
                return
            node = node.children[c]
        return node

    def search(self, word: str) -> bool:
        node = self._last_node_same_with(word)
        return bool(node) and node.is_end

    def startsWith(self, word: str) -> bool:
        node = self._last_node_same_with(word)
        return bool(node)