View profile

#217 - Lỗi hệ thống tại Slack và cách Dropbox chuẩn bị cho thiên tai

Grokking Vietnam
Grokking Vietnam
Trong số này, chúng ta tìm hiểu về:
  • Sự cố xảy ra tại Slack vào ngày 22 tháng 2.
  • DropBox đã kiểm tra hệ thống của mình đối phó với thiên tai như thế nào.
  • Mocker, giả lập hệ thống tại Grab.
  • Lời giải cho góc lập trình tuần trước: Longest String Chain.
  • Đề bài toán góc lập trình tuần này: LRU Cache.

Những bài viết hay
Góc Lập Trình
Đề ra tuần này: LRU Cache
Lời giải đề bài tuần trướcLongest String Chain
Đây là một bài toán mở rộng của bài toán quy hoạch động kinh điển dãy con tăng dài nhất Longest Increasing Subsequence (gọi tắt là LIS).
Gọi L(i) là độ dài dãy con tăng dài nhất ở vị trí i. Công thức đệ quy cho bài toán LIS là:
  • L(1) = 1
  • L(i) = (1, L(j)+1) với mọi j thỏa mãn: 0 < j < iA[j] < A[i]
Nếu bạn đọc đã biết đến bài toán trên, thì sẽ nhận thấy lời giải của bài toán này chỉ khác với bài toán LIS ở bước kiểm tra A[j] < A[i]. Thay bước kiểm tra này bằng bước kiểm tra “word[i] có phải là chuỗi tiền nhiệm (predecessor) của word[j]” hay không, ta sẽ có được lời giải của bài toán. Tuy nhiên lưu ý đối với bài toán này, có thể thay đổi thứ tự của các phần tử trong dãy, nên trước tiên ta phải sắp xếp lại mảng đầu vào theo thứ tự tăng dần. Giải thuật cho lời giải trên như sau: https://pastebin.com/a2J65sW3
Lời giải trên có độ phức tạp là O(S*N^2) với N là độ dài của mảng words, S là độ dài lớn nhất của phần tử trong mảng.
Để ý kỹ hơn, trong bài toán này, ở mỗi bước lặp, ta không bắt buộc phải duyệt tất cả các phần tử từ j = 0 đến i - 1, mà chỉ cần kiểm tra xem có phần tử words[i] nào trước đó là predecessor của words[j] hay không, mà chỉ cần thay mảng L[i] bằng một bảng băm Map<String, Integer>, và thay việc duyệt j từ 0 đến i - 1 bằng việc duyệt tất cả các predecessor của words[j]. Độ phức tạp time complexity của toàn bộ giải thuật là O(NlogN). Mời bạn đọc tham khảo chi tiết cài đặt lời giải trên tại đây: https://pastebin.com/DVm6LrnE
Code & Tools
  • ML For Beginners: Một repo chứa chương trình giáo dục của Azure Cloud Advocates tại Microsoft cho người mới bắt đầu học Machine Learning
  • mongo-rocks: Một repo chứa module cho MongoDB với storage engine từ RocksDB
Góc Sponsors
Là một trong những siêu ứng dụng hàng đầu ở khu vực Đông Nam Á, Grab cung cấp đa dạng dịch vụ cho hơn 187 triệu người dùng tại 428 thành phố ở tám quốc gia. Tại Grab, chúng tôi tin rằng nhân tài chính là trái tim của công ty, vì vậy chúng tôi luôn cố gắng tạo ra một môi trường tuyệt vời để tối ưu hoá tiềm năng của các Grabbers.
Những lý do bạn sẽ thích làm việc ở Grab:
  • Đồng nghiệp thân thiện, chuyên môn cao.
  • Môi trường làm việc đa quốc gia, cân bằng giữa cuộc sống và công việc (work-life balance)
  • Được tham gia giải quyết các bài toán khó (high scale, high traffic), với nhiều impact (vài trăm triệu người dùng)
  • Lương tháng 13 + lương thưởng bonus theo hiệu quả công việc.
  • Rất nhiều khoá học training đào tạo nội bộ cũng như đào tạo được cung cấp bởi các đối tác như Microsoft, Amazon, ..
Hiện văn phòng R&D của Grab đang tuyển nhiều vị trí nhưBackend Developer, Frontend Developer, DevOps Engineer, Lead Software Engineer, ... Bạn có thể tham khảo tại Jobs - Grab Careers để biết thêm chi tiết.
Quotes
“A common fallacy is to assume authors of incomprehensible code will be able to express themselves clearly in comments.”
— Kevlin Henney
Bạn đánh giá nội dung số newsletter này thế nào?
(1 = Rất tệ / 5 = Rất tốt)
👎 1 ——-2 —— 3 —— 4 —— 5 👍
(Việc đánh giá của các bạn là rất quan trọng, sẽ giúp chúng tôi liên tục cải thiện nội dung newsletter tốt hơn)
Đính chính
Trong số trước do sơ xuất trong quá trình biên tập, tại chuyên mục History có một đoạn như sau “Ngoài ra, giao thức reverse-engineering của Tridgell đã phần nào vi phạm quy định sử dụng của BitKeeper”. Chúng tôi xin đính chính lại câu này như sau: “Ngoài ra, việc Tridgell dịch ngược mã nguồn (reverse-engineering) của BitKeeper đã vi phạm quy định sử dụng của BitKeeper”.
Xin cáo lỗi cùng bạn đọc.
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

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.
Viet Nam