thảo luận Leetcode mỗi ngày

  • Người tạo chủ đề Người tạo chủ đề _Gia_Cat_Luong_
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
conmalele4 đã nói:
thím có nhận giải bài tập thuê hộ không ạ...
Nhấp để mở rộng...
Không thím ơi.
seastar đã nói:
Thím cày lâu chưa? t cày 2 năm rồi mới đc hơn 7k, :beauty:
Nhấp để mở rộng...
1689609688557.png

Đây thím, cày mới đc có 120 câu khắp các alogrithm rồi :ah:
Mình vừa cày vừa học thôi, đợt này qua US nên quyết tâm nhảy việc vào big tech càng tăng mạnh nên quyết tâm cày lại.
Lúc đầu hơi khó khăn tí chứ giờ mấy bài medium quẩy ok hết rồi. Gặp bài hard vẫn còn lăn tăn tí :mad:
Nhớ mấy ngày đầu linked list còn ko biết cả 2 pointers. Còn ko biết Tree hay Graph là gì khổ vãi :after_boom:
 
freedom.9 đã nói:
Không thím ơi.

Xem tệp đính kèm 1960481
Đây thím, cày mới đc có 120 câu khắp các alogrithm rồi :ah:
Mình vừa cày vừa học thôi, đợt này qua US nên quyết tâm nhảy việc vào big tech càng tăng mạnh nên quyết tâm cày lại.
Lúc đầu hơi khó khăn tí chứ giờ mấy bài medium quẩy ok hết rồi. Gặp bài hard vẫn còn lăn tăn tí :mad:
Nhớ mấy ngày đầu linked list còn ko biết cả 2 pointers. Còn ko biết Tree hay Graph là gì khổ vãi :after_boom:
Nhấp để mở rộng...
Bác sang US dạng gì vậy. Em cũng tính sang năm sang đó (onsite) xong vận may
 
Java: 
class LRUCache {
    
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
    }
    
    private void addNode(DLinkedNode node) {
        // add node after head;
        node.prev = head;
        node.next = head.next;
        
        head.next.prev = node;
        head.next = node;
    }
    
    private void removeNode(DLinkedNode node) {
        // Remove the node from the linked list
        
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;
        
        prev.next = next;
        next.prev = prev;
    }
    
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addNode(node);
    }
    
    private DLinkedNode popTail() {
        DLinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }
    
    
    private Map<Integer, DLinkedNode> map;
    private int currentSize;
    private DLinkedNode head;
    private DLinkedNode tail;
    private int capacity;
    

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.currentSize = 0;
        this.map = new HashMap<>();
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        DLinkedNode node = map.get(key);
        
        // cache miss
        if (node == null) return -1;
        
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DLinkedNode node = map.get(key);
        
        // cache miss
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;
            map.put(key, newNode);
            addNode(newNode);
            currentSize++;
            
            if (currentSize > capacity) {
                // evict the last node
                DLinkedNode tail = popTail();
                map.remove(tail.key);
                currentSize--;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
 
Debug oải vãi :tire:
Python: 
class ListNode:
    def __init__(self, key, val, prev=None, next=None):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class DoubleLinkedList:
    def __init__(self):
        self.head = ListNode(0, 0)
        self.tail = ListNode(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
   
    def remove(self, node):
        if node is None or self.size == 0:
            return

        self.size -= 1
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
   
    def push_right(self, node):
        prev_tail = self.tail.prev
        prev_tail.next = node
        node.prev = prev_tail
        node.next = self.tail
        self.tail.prev = node
        self.size += 1
   
    def pop_left(self):
        if self.size == 0:
            return

        removed_node = self.head.next
        self.remove(removed_node)
        return (removed_node.key, removed_node.val)


class LRUCache:
    def __init__(self, capacity: int):
        self.node_dict = dict()
        self.recent_used_list = DoubleLinkedList()
        self.capacity = capacity


    def use_key(self, key):
        node = self.node_dict[key]
        self.recent_used_list.remove(node)
        self.recent_used_list.push_right(node)
        return node


    def get(self, key: int) -> int:
        if key not in self.node_dict:
            return -1

        node = self.use_key(key)
        return node.val


    def put(self, key: int, value: int) -> None:
        if key in self.node_dict:
            node = self.use_key(key)
            node.val = value
            return
       
        if len(self.node_dict) == self.capacity:
            remove_key, remove_val = self.recent_used_list.pop_left()
            self.node_dict.pop(remove_key)
       
        new_node = ListNode(key, value)
        self.node_dict[key] = new_node
        self.recent_used_list.push_right(new_node)
 
NahSama đã nói:
Truoc nghe ban keu, mot so cho hoi coding LRU cache, xong hoi them concurrency control, roi co cach nao lock-free khong? :mad:
Nhấp để mở rộng...
Xưa thấy có ông nào phỏng vấn bytedance đó fence
Violet_7 đã nói:
Debug oải vãi :tire:
Python: 
class ListNode:
    def __init__(self, key, val, prev=None, next=None):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class DoubleLinkedList:
    def __init__(self):
        self.head = ListNode(0, 0)
        self.tail = ListNode(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
 
    def remove(self, node):
        if node is None or self.size == 0:
            return

        self.size -= 1
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
 
    def push_right(self, node):
        prev_tail = self.tail.prev
        prev_tail.next = node
        node.prev = prev_tail
        node.next = self.tail
        self.tail.prev = node
        self.size += 1
 
    def pop_left(self):
        if self.size == 0:
            return

        removed_node = self.head.next
        self.remove(removed_node)
        return (removed_node.key, removed_node.val)


class LRUCache:
    def __init__(self, capacity: int):
        self.node_dict = dict()
        self.recent_used_list = DoubleLinkedList()
        self.capacity = capacity


    def use_key(self, key):
        node = self.node_dict[key]
        self.recent_used_list.remove(node)
        self.recent_used_list.push_right(node)
        return node


    def get(self, key: int) -> int:
        if key not in self.node_dict:
            return -1

        node = self.use_key(key)
        return node.val


    def put(self, key: int, value: int) -> None:
        if key in self.node_dict:
            node = self.use_key(key)
            node.val = value
            return
     
        if len(self.node_dict) == self.capacity:
            remove_key, remove_val = self.recent_used_list.pop_left()
            self.node_dict.pop(remove_key)
     
        new_node = ListNode(key, value)
        self.node_dict[key] = new_node
        self.recent_used_list.push_right(new_node)
Nhấp để mở rộng...
Fence debug oải là do ko add 1 node head 1 node tail default vô cái LinkedList. Fence add 2 node đó vô là có thể simplify nó lại thành 1 hàm Add 1 hàm Remove node thôi o_O .
Kinh nghiệm làm mấy thằng LinkedList này là lúc nào cũng phải add 1 cái dummyNode ở đầu để tránh edge case mấy chỗ Add với remove haha
 
Ý tưởng bài hôm nay khá trực quan như tên gọi Least Recently Used, ta tìm cách để giữ thứ tự truy cập vào key trên trục thời gian, nếu vượt quá capacity thì xoá thằng có thời điểm truy cập xa nhất.

Cách dùng Double Linked Lít thì mấy bác trên có đề cập, chủ yếu là mỗi lần truy cập "key", ta đẩy node có "key" lên đầu (hoặc cuối) DLL, nghiễm nhiên thằng nào ở cuối (hoặc đầu) sẽ là thằng bị evict.

Em lười code lại DLL nên dùng queue thay thế, ý tưởng là sẽ lưu lại thời gian truy cập cho mỗi "key", và mỗi lần truy cập "key" thì lại append vào queue để đảm bảo thứ tự truy cập trên trục thời gian.

Hoặc xài thằng dict thôi cũng được vì từ 3.7 Python đảm bảo thứ tự phần tử của dict luôn theo thứ tự chèn vào (không khuyến khích mang đi phỏng vấn)

Python: 
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.queue = deque()
        self.storage = {}
        self.__access_time__ = 0

    def __push_top__(self, key):
        self.__access_time__ += 1
        self.queue.append((key, self.__access_time__))
        self.storage[key] = (self.storage[key][0], self.__access_time__)

    def get(self, key: int) -> int:
        if key not in self.storage:
            return -1
        self.__push_top__(key)
        return self.storage[key][0]

    def put(self, key: int, value: int) -> None:
        self.storage[key] = (value, 0)
        self.__push_top__(key)
        if len(self.storage) > self.capacity:
            while self.queue:
                prior_key, prior_time = self.queue.popleft()
                if self.storage[prior_key][1] != prior_time: continue
                del self.storage[prior_key]
                break
 
Bài hôm nay code C++ có DLL rồi nên code sướng vkl, :p
btw, đây là một trong những bài t rất hay hỏi ứng viên khi phỏng vấn.
Kiểu như sẽ bắt đầu là design 1 system. Sau đó kiểu gì cũng có layer cần cache, rồi hỏi 1 hồi kiểu gì cũng đến LRU, LFU,... Lúc đó t sẽ yêu cầu implement. :matrix:
C++: 
class LRUCache {
public:
    LRUCache(int capacity) :
    capacity_(capacity) {
        key_to_it_.reserve(capacity);
    }
   
    int get(int key) {
        auto it = key_to_it_.find(key);
        if (it == key_to_it_.end()) return -1;
        int value = it->second->second;
        data_.erase(it->second);
        key_to_it_[key] = data_.emplace(data_.end(), key, value);
        return value;
    }
   
    void put(int key, int value) {
        auto it = key_to_it_.find(key);
        if (it != key_to_it_.end()) {
            data_.erase(it->second);
        } else if (key_to_it_.size() == capacity_) {
            key_to_it_.erase(data_.begin()->first);
            data_.pop_front();
        }
        key_to_it_[key] = data_.emplace(data_.end(), key, value);
    }
private:
    unordered_map<int, list<pair<int,int>>::iterator> key_to_it_;
    list<pair<int,int>> data_;
    int capacity_;
};
 
Sửa lần cuối:
freedom.9 đã nói:
Xưa thấy có ông nào phỏng vấn bytedance đó fence

Fence debug oải là do ko add 1 node head 1 node tail default vô cái LinkedList. Fence add 2 node đó vô là có thể simplify nó lại thành 1 hàm Add 1 hàm Remove node thôi o_O .
Kinh nghiệm làm mấy thằng LinkedList này là lúc nào cũng phải add 1 cái dummyNode ở đầu để tránh edge case mấy chỗ Add với remove haha
Nhấp để mở rộng...
Có add mà fency :ops:
 
seastar đã nói:
Bài hôm nay code C++ có DLL rồi nên code sướng vkl, :p
btw, đây là một trong những bài t rất hay hỏi ứng viên khi phỏng vấn.
Kiểu như sẽ bắt đầu là design 1 system. Sau đó kiểu gì cũng có layer cần cache, rồi hỏi 1 hồi kiểu gì cũng đến LRU, LFU,... Lúc đó t sẽ yêu cầu implement. :matrix:
C++: 
class LRUCache {
public:
    LRUCache(int capacity) :
    capacity_(capacity) {
        key_to_it_.reserve(capacity);
    }
 
    int get(int key) {
        auto it = key_to_it_.find(key);
        if (it == key_to_it_.end()) return -1;
        int value = it->second->second;
        data_.erase(it->second);
        key_to_it_[key] = data_.emplace(data_.end(), key, value);
        return value;
    }
 
    void put(int key, int value) {
        auto it = key_to_it_.find(key);
        if (it != key_to_it_.end()) {
            data_.erase(it->second);
        } else if (key_to_it_.size() == capacity_) {
            key_to_it_.erase(data_.begin()->first);
            data_.pop_front();
        }
        key_to_it_[key] = data_.emplace(data_.end(), key, value);
    }
private:
    unordered_map<int, list<pair<int,int>>::iterator> key_to_it_;
    list<pair<int,int>> data_;
    int capacity_;
};
Nhấp để mở rộng...
Bác đang làm ở đâu vậy, em áp lai cty bác thì đừng hỏi bài khác nhé :love:
 
Map trong JS/TS là ordered nên làm đơn giản
qZV215Z.png
, mỗi tội ko phải O(1). Nhưng lười quá ngại ko implement Double LinkedList :burn_joss_stick:
JavaScript: 
class LRUCache {
    map: Map<number, number>;
    capacity: number;
    constructor(capacity: number) {
        this.map = new Map();
        this.capacity = capacity
    }

    get(key: number) {
        if (!this.map.has(key)) return -1;

        const v = this.map.get(key);
        this.map.delete(key);
        this.map.set(key, v);
        return this.map.get(key);
    };

    put(key: number, value: number) {
        this.map.delete(key);
        this.map.set(key, value);
        if (this.map.size > this.capacity) {
            this.map.delete(this.map.keys().next().value);
        }
    };
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
 
Mã: 
class LLNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = this.next = null;
  }
}
class LRUCache {
  constructor(cap) {
    this.map = new Map();
    this.cap = cap;
    this.head = new LLNode();
    this.tail = new LLNode();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  #attach(node) {
    node.prev = this.tail.prev;
    node.next = this.tail;
    node.prev.next = node;
    node.next.prev = node;
  }
  #detach(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = node.next = null;
  }
  get(key) {
    const node = this.map.get(key);
    if (!node) {
      return -1;
    }
    const { value } = node;
    this.#detach(node);
    this.#attach(node);
    return value;
  }
  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.value = value;
      this.#detach(node);
      this.#attach(node);
    } else {
      if (this.map.size === this.cap) {
        const node = this.head.next;
        this.#detach(node);
        this.map.delete(node.key);
      }
      const node = new LLNode(key, value);
      this.#attach(node);
      this.map.set(key, node);
    }
  }
}
 
Trạng thái
Không mở để trả lời thêm.

Chủ đề tương tự

Thach Sanh Mat Riu
Điều gì xảy ra nếu bạn uống nước chè xanh mỗi ngày?
2
Trả lời
22
Lượt xem
1K
dattenmoi
D
megume
thảo luận Hôm nay, buổi bình minh của AI robot đã đến
Trả lời
4
Lượt xem
1K
Toc Hong
Toc Hong
Lộc Tục
(Dịch) Cuộc điều tra của CBC/Radio-Canada tiết lộ công ty Việt Nam nhắm vào người Canada bằng tin giả AI để kiếm lời
2
Trả lời
30
Lượt xem
5K
dukeng995
dukeng995
Ti Amo
[Dịch] Công ty Việt Nam dùng tin giả do AI tạo ra để kiếm tiền — nhắm vào độc giả Canada
Trả lời
0
Lượt xem
1K
Ti Amo
Ti Amo
Gấu Ted
Độc giả ngày càng tin nhà báo hơn thương hiệu báo chí
Trả lời
10
Lượt xem
838
giayasics
giayasics

Thống kê chủ đề

Ngày tạo
_Gia_Cat_Luong_,
Người trả lời cuối
Vipluckystar,
Trả lời
17.755
Lượt xem
1.212.727

Chia sẻ trang này

Quay lại
Lên đầu trang