Grokking Newsletter

By Grokking Vietnam

#189 - Pinterest đã mở rộng hệ thống quảng cáo bằng cách nào?

#191・
9.6K

subscribers

200

issues

Grokking Vietnam
Grokking Vietnam
Grokking Newsletter là newsletter hàng tuần của Grokking cho các bạn software engineers người Việt.
Trong số này: Cách Pinterest mở rộng hệ thống quảng cáo, các thói quen giúp tăng năng suất lập trình, bài talk của Rich Hickey về cách xây dựng một hệ thống, v.v…

Những bài viết hay
How we scaled the size of Pinterest
Góc Lập Trình
Đề ra tuần này:
Cho một array số nguyên nums, trả về độ dài của subsequence tăng dần dài nhất.
Một subsequence là một array có thể được dẫn xuất từ một array bằng cách xóa một số hoặc không có phần tử nào mà không thay đổi thứ tự của các phần tử còn lại. Ví dụ, [3,6,2,7] là một subsequence của [0,3,1,6,2,2,7].
Follow-up: giải bài trên với giải thuật có time complexity O(n log(n))
Ví dụ 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: Subsequence tăng dần dài nhất là [2,3,7,101]
Ví dụ 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Ví dụ 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Các bạn có thể thử sức tại đây: https://leetcode.com/problems/longest-increasing-subsequence/
Lời giải tuần trước
Đề bài
Lời giải
Lời giải
Đề bài yêu cầu đếm số cặp nghịch đảo trong mảng, ta có thể dễ dàng giải bài này bằng việc duyệt toàn bộ các cặp trong mảng, và đếm những cặp (a[i], a[j]) thoả mãn điều kiện a[i] > a[j] với i < j. Giải thuật này có độ phức tạp time complexity là O(n2).
Tuy nhiên, có thể nhận thấy việc duyệt và so sánh từng cặp khá tương đồng với các thuật toán sắp xếp, ta có thể tiếp cận theo hướng này để tối ưu thuật toán.
Nếu ta có 2 mảng đã được sắp xếp theo thứ tự giảm dần như sau: arr1 = [5, 3], arr2 = [4,3], ta có arr1[0] > arr2[0] (vì 5 > 4), vậy số lượng cặp đảo nghịch là arr2.length - 0arr1[0] > arr2[i] với tất cả 0 <= i < arr2.length.
Dựa vào hướng tiếp cận trên, ta có thể thực hiện giải thuật merge sort như sau: https://pastebin.com/tJqvjP85
Giải thuật có độ phức tạp time complexity là O(nlogn), space complexity là O(n).
Góc Database
Entropy là một vấn đề hay gặp trong các hệ dữ liệu phân tán. Hiểu một cách nôm na thì entropy ám chỉ việc dữ liệu lưu trữ giữa các node bị mất đồng bộ và trở nên khác biệt, thường là do lỗi mạng (network partition).
Các hệ dữ liệu phân tán khác nhau sẽ có những chiến lược khác nhau để giải quyết bài toán entropy này, lớp lời giải được dùng để giải quyết sẽ được gọi là anti-entropy.
Một trong các kỹ thuật phổ biến trong nhóm lời giải cho anti-entropy là sử dụng Merkle Tree được sử dụng ở Cassandra. Gần đây, một kỹ thuật mới đang được sử dụng nhiều là delta-state-CRDT (Delta State Conflict-Free Replicated Data Types).
Để hiểu thêm về delta-state CRDT, góc DB tuần này mời các bạn cùng xem bài thuyết trình vào năm ngoái của Sailesh Mukil, software engineer làm việc ở Netflix. Trong bài thuyết trình này Sailesh sẽ giới thiệu về Dynomite, một hệ dữ liệu phân tán được phát triển bởi Netflix ban đầu hướng đến xây dựng lớp cache cho Cassandra, nhưng dần dần đã trở thành phương án thay thế Cassandra cho một số lớp bài toán. Một trong các điểm nổi bật của Dynamite đó là sử dụng delta-state-CRDT để giải quyết bài toán entropy.
Mời các bạn cùng tham khảo video bài thuyết trình ở đây.
Code & Tools
Đính chính
Trong số tuần trước, do có một sai sót trong quá trình biên tập, nên đường link trong bài viết “Góc Database” không chính xác.
Chúng tôi xin gửi lại tới bạn đọc đường dẫn chính xác như sau: https://15445.courses.cs.cmu.edu/fall2020/slides/17-twophaselocking.pdf
BTT Grokking Newsletter xin cáo lỗi cùng bạn đọc.
Góc Sponsors
Database documentation tự động với dbdocs.io
[Nội dung tài trợ] dbdocs.io là một công cụ giúp các bạn Dev có thể tự sinh ra nguyên trang document về cấu trúc database của mình chỉ bằng vài dòng lệnh command-line. Nó giúp quá trình planning và design database trong team dev dễ dàng hơn.
Hiện team dbdocs (ở TPHCM) đang tìm thêm 2 bạn fullstack/backend engineers để tham gia phát triển sản phẩm dev tool này. Bạn nào quan tâm có thể xem thêm tại: https://careers.holistics.io/job-openings/open-source-full-stack-engineer
(Team dbdocs cũng là team xây dựng công cụ dbdiagram.io phổ biến mà nhiều bạn dev đang dùng.)
Quotes
“Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.”
— Stan Kelly-Bootle
Did you enjoy this issue? Yes No
Grokking Vietnam
Grokking Vietnam

Cảm ơn bạn đã dành thời gian đọc newsletter kỳ này và chúng tôi hi vọng rằng bạn đã khám phá ra một số điều mới mẻ từ các bài viết trên. Các bạn có thể đọc lại các số cũ tại website newsletter.grokking.org

Ngoài ra các bạn có thể gửi feedback cho Grokking Newsletter team ở https://bit.ly/3k3Jdw5 hoặc đóng góp bài viết tại https://bit.ly/2XaBUtF

In order to unsubscribe, click here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam