View profile

#222 - Tìm hiểu về Data Observability

Grokking Vietnam
Grokking Vietnam
Trong số này, chúng ta cùng tìm hiểu về:
  • Bài toán xử lý dữ liệu của Trivago
  • Cloudflare cải thiện tốc độ xây dựng DNS records lên hơn 4.000 lần
  • Tại sao không nên dùng JSON cho Configuration?
  • Data Observability là gì?
Ngoài ra các bạn vẫn có thể tiếp tục đặt mua ấn phẩm Dijkstra tập 2 tại đây nhé.

Những bài viết hay
Góc Data
Góc Lập Trình
Đề ra tuần này: Fraction to Recurring Decimal
Cho hai số nguyên biểu thị tử số và mẫu số của một phân số, hãy trả về phân số ở định dạng chuỗi.
Ví dụ:
Input: numerator = 1, denominator = 2
Output: “0.5”
Lời giải đề bài tuần trướcLinked List Cycle II
(by ndaadn)
Bài toán yêu cầu xác định xem một Linked List cho trước có chu trình (vòng lặp) hay không và trả về phần tử bắt đầu của chu trình đó.
Đọc đề bài, ta có thể nghĩ ngay đến một giải thuật đơn giản đơn giản bằng cách duyệt qua toàn bộ Linked List, với mỗi phần tử, ta đưa phần tử đó vào một HashSet cho đến khi gặp phần tử lặp và trả về kết quả là phần tử đó, hoặc cho đến khi duyệt hết toàn bộ List và trả về kết quả null (List không có chu trình). Giải thuật này có độ phức tạp thời gian O(N), độ phức tạp không gian O(N). Tuy nhiên, đây vốn là một bài toán kinh điển, còn có tên gọi là “Bài toán thỏ và rùa của Floyd” (Floyd’s tortoise and hare). Giải thuật tối ưu cho bài toán này như sau:
  • Chúng ta bắt đầu ở phần tử đầu của Linked List bằng 2 con trỏ. Gọi tên 2 con trỏ này là slow và fast.
  • Di chuyển con trỏ slow qua từng phần tử của list. Di chuyển con trỏ fast nhanh gấp đôi con trỏ slow, tức là sẽ di chuyển qua mỗi 2 phần tử của list.
  • Nếu trong Linked List tồn tại một chu trình, 2 con trỏ này chắc chắn sẽ gặp nhau tại một phần tử nào đó.
  • Sau khi chu trình được phát hiện, tạo một con trỏ (tạm gọi là temp) khác bắt đầu từ phần tử đầu tiên của list.
  • Di chuyển con trỏ temp và con trỏ slow theo từng phần tử một. Phần tử nơi 2 con trỏ này gặp nhau chính là phần tử đầu tiên của chu trình trong Linked List đã cho.
Giải thuật được cài đặt như sau: https://pastebin.com/Vuyn78VL
Giải thuật có độ phức tạp thời gian O(N), không gian O(1). Bạn đọc có thể tham khảo thêm về bài toán, cũng như chứng minh giải thuật ở trang wiki sau: https://en.wikipedia.org/wiki/Cycle_detection
Code & Tools
  • Metriql: Một kho lưu trữ metrics mã nguồn mở cho phép các công ty xác định các metrics của họ dưới dạng code và chia sẻ chúng trên các công cụ dữ liệu và BI của họ một cách dễ dàng
Quotes
“Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning.”
― Rick Cook, The Wizardry Compiled
Feedback
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)
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