ลำดับต่อเนื่องที่ยาวที่สุดและแคช LRU

โจทย์ลำดับจำนวนต่อเนื่องที่ยาวที่สุด

def longestConsecutive(nums):
    num_set = set(nums)
    best    = 0
    for n in num_set:
        if n - 1 not in num_set:   # n is the start of a sequence
            curr_n = n
            length = 1
            while curr_n + 1 in num_set:
                curr_n += 1
                length += 1
            best = max(best, length)
    return best

print(longestConsecutive([100,4,200,1,3,2]))   # 4
print(longestConsecutive([0,3,7,2,5,8,4,6,0,1]))  # 9

เหตุใดการพิสูจน์ O(n) จึงเป็นจริง

# Demonstrate O(n) total inner iterations
nums    = list(range(1000))  # worst case: one long sequence
num_set = set(nums)
inner_iters = 0
for n in num_set:
    if n - 1 not in num_set:
        curr = n
        while curr + 1 in num_set:
            curr += 1
            inner_iters += 1
print('n =', len(nums), '  total inner iterations =', inner_iters)
# inner_iters = n-1 <= n => O(n)

ทางเลือก: แนวทางที่ใช้การเรียงลำดับ

def longestConsecutive_sort(nums):
    if not nums:
        return 0
    nums.sort()
    best = length = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            continue              # skip duplicates
        if nums[i] == nums[i-1] + 1:
            length += 1
            best = max(best, length)
        else:
            length = 1
    return best

print(longestConsecutive_sort([100,4,200,1,3,2]))  # 4

แคช LRU คืออะไร

แคช LRU โดยใช้ OrderedDict

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache    = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)  # mark as recently used
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # evict LRU (first item)

cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
print(cache.get(1))  # 1 (and 1 becomes most recently used)
cache.put(3, 3)      # evict key 2 (LRU)
print(cache.get(2))  # -1
cache.put(4, 4)      # evict key 1 (LRU)
print(cache.get(1))  # -1
print(cache.get(3))  # 3
print(cache.get(4))  # 4

สร้างแคช LRU ตั้งแต่ต้น: ลิงก์ลิสต์เชื่อมสองทิศทางและ HashMap

class DNode:
    def __init__(self, key=0, val=0):
        self.key  = key
        self.val  = val
        self.prev = None
        self.next = None

class LRUCacheDLL:
    def __init__(self, capacity):
        self.cap  = capacity
        self.map  = {}   # key -> DNode
        self.head = DNode()   # dummy LRU end
        self.tail = DNode()   # dummy MRU end
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_tail(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_tail(node)
        return node.val

    def put(self, key, val):
        if key in self.map:
            self._remove(self.map[key])
        node = DNode(key, val)
        self._add_to_tail(node)
        self.map[key] = node
        if len(self.map) > self.cap:
            lru = self.head.next
            self._remove(lru)
            del self.map[lru.key]

cache = LRUCacheDLL(2)
cache.put(1,1); cache.put(2,2)
print(cache.get(1))  # 1
cache.put(3,3)
print(cache.get(2))  # -1 (evicted)

เหตุใดจึงใช้ลิงก์ลิสต์เชื่อมสองทิศทางสำหรับ LRU

# Why not a singly linked list?
# To remove a node you need its predecessor
# With SLL: must traverse from head to find predecessor => O(n)
# With DLL: node.prev IS the predecessor => O(1) removal

print('SLL removal: O(n) — must find predecessor by traversal')
print('DLL removal: O(1) — node.prev is immediately available')
print('Hash map lookup: O(1) — get DNode reference by key')
print('Combined LRU get/put: O(1) average')

แคช LFU (ใช้งานน้อยที่สุด)

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity):
        self.cap   = capacity
        self.min_f = 0
        self.kv    = {}   # key -> val
        self.kf    = {}   # key -> freq
        self.fk    = defaultdict(OrderedDict)  # freq -> {key: None}

    def _touch(self, key):
        f = self.kf[key]
        self.kf[key] = f + 1
        del self.fk[f][key]
        if not self.fk[f] and f == self.min_f:
            self.min_f += 1
        self.fk[f+1][key] = None

    def get(self, key):
        if key not in self.kv:
            return -1
        self._touch(key)
        return self.kv[key]

    def put(self, key, val):
        if self.cap == 0: return
        if key in self.kv:
            self.kv[key] = val
            self._touch(key)
        else:
            if len(self.kv) == self.cap:
                lfu_key, _ = self.fk[self.min_f].popitem(last=False)
                del self.kv[lfu_key]; del self.kf[lfu_key]
            self.kv[key] = val; self.kf[key] = 1
            self.fk[1][key] = None; self.min_f = 1

รูปแบบการออกแบบ: แฮชแมปและลิงก์ลิสต์

ลำดับจำนวนต่อเนื่องในเมทริกซ์

# Simpler: find longest consecutive values in a 2D matrix (no adjacency)
def longestConsecutiveMatrix(matrix):
    all_vals = set()
    for row in matrix:
        for v in row:
            all_vals.add(v)
    best = 0
    for v in all_vals:
        if v - 1 not in all_vals:  # start of sequence
            length = 0
            while v in all_vals:
                v += 1
                length += 1
            best = max(best, length)
    return best

m = [[1, 5, 3], [4, 6, 2], [8, 7, 9]]
print(longestConsecutiveMatrix(m))  # 9 (1..9 all present)

สรุปการสัมภาษณ์: พลังของเซตและ HashMap

แบบทดสอบสั้น ๆ

สรุปบทเรียน