LeetCode: Cho hai linked list không rỗng biểu diễn hai số nguyên không âm. Các chữ số được lưu theo thứ tự ngược; mỗi node chỉ lưu một chữ số. Hãy cộng hai số và trả về một linked list mới.
Bạn có thể giả định rằng ngoài số 0, hai số này đều không bắt đầu bằng 0.
Tác giả: wwwxmu
Địa chỉ bài viết gốc: https://www.weiweiblog.cn/13string/
Khi nói đến các bài toán chuỗi, không thể không nhắc đến thuật toán KMP. Thuật toán này dùng để giải quyết bài toán tìm kiếm chuỗi, tức là tìm vị trí xuất hiện của một chuỗi con W trong một chuỗi S. KMP giảm độ phức tạp thời gian của việc matching ký tự xuống O(m+n), còn độ phức tạp không gian chỉ là O(m). Phương pháp “tìm kiếm brute force” liên tục quay lui trong chuỗi chính, dẫn đến hiệu suất thấp. Trong khi đó, KMP tận dụng thông tin đã matching một phần, giữ con trỏ trên chuỗi chính không quay lui, đồng thời điều chỉnh con trỏ của chuỗi con để dịch chuỗi mẫu đến vị trí phù hợp nhất.
LRU là viết tắt của Least Recently Used, nghĩa là ít được sử dụng gần đây nhất. Khi cache đầy, dữ liệu lâu nhất chưa được truy cập sẽ bị loại bỏ.
Trong các buổi phỏng vấn, tự viết LRU là câu hỏi rất thường gặp vì nó kết hợp hash table và doubly linked list: hash table chịu trách nhiệm tìm node trong O(1), còn doubly linked list chịu trách nhiệm di chuyển node và xóa node cuối trong O(1).
Cách trực quan nhất để viết một interface lưu file là: nhận path, open một file, write dữ liệu vào đó, cuối cùng close. Khi số lượng file ít, concurrency thấp và máy không gặp sự cố, quy trình này có vẻ không khó.
Nhưng khi phỏng vấn hỏi sâu hơn, vấn đề sẽ xuất hiện. fd mà open() trả về thực sự trỏ tới đâu? Tên file có nằm trong inode không? Vì sao hai hard link có thể nhìn thấy cùng một nội dung? write() trả về thành công có nghĩa là dữ liệu đã được ghi xuống disk chưa? File log đã bị xóa, vì sao df -h vẫn hiển thị disk đầy?
Hai thread đồng thời cộng 1 vào cùng một counter, nhìn thì chỉ là một việc rất nhỏ nhưng kết quả cuối cùng lại có thể bị thiếu một lần tăng.
Nguyên nhân thực ra khá đơn giản. Trong source code, count++ chỉ là một dòng, nhưng khi máy thực thi thường phải trải qua các bước đọc, tính toán và ghi trở lại. Thread A vừa đọc được giá trị cũ nhưng chưa ghi trở lại; thread B cũng đọc được đúng giá trị cũ đó. Mỗi bên tự tính ra giá trị mới, nhưng cuối cùng lại ghi cùng một kết quả.
Sau khi nhập domain name vào thanh địa chỉ của trình duyệt, trước khi thực hiện HTTP request, trình duyệt thường phải phân giải DNS.
DNS giải quyết bài toán ánh xạ giữa domain name và địa chỉ IP. Thoạt nhìn, nó chỉ là “dịch domain name thành IP”, nhưng phía sau liên quan đến cả một hệ thống cơ chế gồm cache cục bộ, truy vấn đệ quy, truy vấn lặp, authoritative server, root server và chuyển đổi giữa UDP/TCP.
