#207 - Lời giải mới cho trường hợp tổng quát của bài toán "Tám quân hậu"

Feb 10, 2022

Chào các bạn,

Hi vọng mọi người đã có một kì nghỉ Tết vui vẻ. Trong kì Grokking Newsletter đầu tiên của năm Nhâm Dần 2022, chúng tôi giới thiệu với bạn đọc các nội dung sau:

Lời giải mới cho trường hợp tổng quát của bài toán "Tám quân hậu";
Cách Netflix xây dựng hệ thống phát hiện workload thất bại và tự khắc phục trong thời gian thực;
Quá trình và kinh nghiệm đúc rút từ ba năm Github migrate dữ liệu;
Cơ chế scan và biến đổi source code thành dạng database có thể truy vấn được;
Lời giải Đề bài tuần trước: "Number of Subarrays with Bounded Maximum".

Những bài viết hay

Harvard Mathematician Answers 150-year-old Chess Problem

Bài toán Tám quân hậu (Eight queens puzzle) chắc hẳn không còn xa lạ với những bạn chơi cờ vua. Xuất hiện lần đầu tiên vào năm 1848, câu đố này nhanh chóng trở nên nổi tiếng và hấp dẫn nhiều nhà toán học. Trên bàn cờ vua kích thước 8x8, ta chỉ có 92 lời giải - nhưng khi tổng quát hoá bài toán với bàn cờ kích thước nxn và n quân hậu, việc tìm đáp án lại khó hơn rất nhiều (VD: với bàn cờ 25x25 và 25 quân hậu, ta đã có hàng triệu tỉ lời giải!).

Mãi tới gần đây, nhà toán học Michael Simkin đã đưa ra lời giải gần đúng cho bài toán tổng quát. Theo tính toán của Simkin, có xấp xỉ (0.143n)^n cách để đặt n quân hậu trên một bàn cờ nxn, sao cho không có quân hậu nào tấn công lẫn nhau. Để tạo ra phương trình này, tác giả đã nắm được mẫu (pattern) để đặt các quân hậu trên bàn cờ lớn (tập trung ở giữa bàn cờ hay đặt ở cạnh), sau đó áp dụng các kỹ thuật toán học và thuật toán.

Trên lý thuyết, vẫn có thể tìm ra phương trình cho kết quả chính xác hơn nữa, nhưng Simkin sẽ để dành nó cho những người tiếp theo khám phá.

Auto-Diagnosis and Remediation in Netflix Data Platform

Với lượng người dùng đang tăng nhanh, đội Data Platform của Netflix đang vận hành một nền tảng dữ liệu phức tạp trên cloud. Nền tảng dữ liệu này gồm những luồng batch và streaming workload, được xây dựng bên trên một số hệ thống phân tán có chức năng truy xuất dữ liệu theo nhu cầu của người dùng. Do bản chất vốn có của các hệ thống này, không thể tránh khỏi xảy ra sự cố liên tục và lặp đi lặp lại. Việc phát hiện và xử lý những sự cố như thế mất khá nhiều thời gian, công sức và tất nhiên còn ảnh hưởng tới năng suất của cả người dùng cũng như của đội Data Platform.

Vì vậy, đội Data Platform của Netflix đã quyết định xây dựng Pensive: một hệ thống có thể phát hiện, chẩn đoán các workload thất bại và tự động khắc phục trong thời gian thực.

Pensive bao gồm hai thành phần chính là Batch và Streaming.
Ngoài ra, Pensive còn có rule set để phân loại lỗi. Ban đầu, mỗi khi component owner và người dùng hệ thống yêu cầu thì rule set sẽ được bổ sung rule mới. Hiện nay, Netflix đang áp dụng Machine Learning nhằm giúp component owner phân loại lỗi.

Ngoài việc phân loại lỗi trong workflow và pipeline, Pensive cũng có thể nhanh chóng nhận diện được các issue ở quy mô platform ảnh hưởng đến nhiều workflow - bằng cách phân tích dữ liệu trong thời gian thực bằng Apache Kafka và Apache Druid. Đội Data Platform có thể dễ dàng nắm bắt tình hình và thông báo cho các bên liên quan.

Tóm tại, Pensive đã có tác động đáng kể đến nền tảng dữ liệu ở Netflix, giúp giảm bớt gánh nặng của việc vận hành, cho họ thời gian để giải quyết các vấn đề quan trọng và khó khăn hơn. Để biết thêm chi tiết về quá trình xây dựng, triển khai và những tính năng tiếp theo của Pensive, mời các bạn đọc bài viết chi tiết tại đây.

Partitioning GitHub’s Relational Databases to Handle Scale

Vào năm 2019, Github đã bắt đầu thực hiện vertical partition cho cụm dữ liệu MySQL nhằm scale hệ thống tốt hơn. Để quá trình vertical partition diễn ra hiệu quả mà không ảnh hưởng quá nhiều đến người dùng cũng như đến các lập trình viên của chính mình, Github đã dùng ý tưởng virtual partition để gộp các bảng dữ liệu lại với nhau.

Các bảng dữ liệu này sẽ được dời qua một cluster khác sau khi quá trình migration hoàn tất.
Việc chuyển code ứng dụng có thể diễn ra luôn mà không cần chờ chuyển dữ liệu sang cluster khác.

Ngoài ra, để tránh bỏ sót các trường hợp đặc biệt, các kỹ sư Github đã xây dựng linter cho lệnh truy vấn và giao dịch SQL. Với các linter này, lập trình viên sẽ được thông báo khi có câu lệnh và giao dịch SQL không đúng với vertical virtual partitions đã định sẵn.

Bài viết sau đây được các kỹ sư ở Github viết vào cuối năm 2021 sau 3 năm migrate dữ liệu và partition dữ liệu sang nhiều cluster khác nhau. Mời bạn đọc học hỏi quá trình và kinh nghiệm đúc rút từ việc partition cơ sở dữ liệu MySQL của Github.

Code scanning and Ruby: turning source code into a queryable database

Nếu bạn có sử dụng Github nhiều, hẳn bạn sẽ thấy Github đã release nhiều tính năng khá hữu ích gần đây như: phân tích lỗi bảo mật từ mã nguồn, tự động nhận diện và đề xuất bản nâng cấp các dependencies, copilot, ...

Để xây dựng những tính năng này, bài toán đầu tiên cần giải quyết là phải có cơ chế để parse và diễn giải mã nguồn thành một loại cấu trúc dữ liệu nào đó đủ tổng quát để có thể phân tích sâu hơn. Cấu trúc dữ liệu nào là phù hợp?

Nếu bạn nghĩ đến Abstract Syntax Tree (AST) thì bạn đã suy nghĩ đúng hướng nhưng nếu vậy thì chưa đủ. Giải pháp của team Github đó là trước hết sẽ parse mã nguồn thành dạng AST, tuy nhiên tiếp theo sẽ là chuyển đổi AST này thành cấu trúc dạng bảng có thể truy vấn được bằng CodeQL (một ngôn ngữ truy vấn tương tự SQL được phát triển riêng bởi Github). Nhờ quá trình chuyển đổi này mà các tính năng phân tích mã nguồn chuyên sâu có thể được xây dựng dễ dàng hơn.

Mời các bạn đọc bài blog sau để hiểu thêm về cách team Github chuyển đổi mã nguồn thành dạng database truy vấn được nhé.

Góc Database

Làm việc với các relational database thì index là một công đoạn hầu như không thể thiếu. Tuy nhiên, nếu chỉ áp dụng index một các máy móc mà không hiểu cách nó vận hành có thể dẫn đến câu hỏi phổ biến "câu query này đã có index rồi mà, sao vẫn không chạy nhanh?".

Trong góc Database kỳ này chúng ta sẽ thử khảo sát một ví dụ khá kinh điển cho các bài toán IoT. Ví dụ chúng ta có 2 table: table Truck lưu thông tin của xe tải được đăng ký, table TruckStatus lưu trạng thái và vị trí của xe tải. Hai table có cấu trúc như bên dưới. Câu hỏi là nếu yêu cầu bạn viết câu query để lấy trạng thái cuối cùng của một hoặc vài chiếc xe tải bất kỳ, bạn sẽ cần index như thế nào để câu query này chạy nhanh hơn? Mời bạn đọc thử dành vài phút suy nghĩ về câu trả lời, sau đó thử tham khảo bài blog bên dưới để xem cách tiếp cận của mình có phải là đã tối ưu chưa nhé.

Link bài báo

Góc Lập Trình

Đề tuần này: Binary Tree Cameras

Lời giải đề bài tuần trước:

Đề bài: Number of Subarrays with Bounded Maximum

Lời giải:

Đề bài yêu cầu đếm số lượng mảng con với phần tử lớn nhất trong mảng con thuộc khoảng [left, right]. Nói cách khác, left <= max(subarray) <= right.

Cách tiếp cận đầu tiên ta có thể nghĩ tới là duyệt tất cả mảng con, và đếm những mảng con thoả mãn điều kiện đề bài.

Ta có n * (n + 1) / 2 mảng con.
Việc kiểm tra mỗi mảng con thoả mãn điều kiện đề bài có độ phức tạp Time Complexity là O(n).
Vì vậy, giải thuật này có độ phức tạp Time Complexity O(n^3)

Để tối ưu bài này:

Nếu ta có thể đếm được số mảng con với phần tử lớn nhất nhỏ hơn hoặc bằng một số cho trước, kết quả của bài toán sẽ là: atMost(right) - atMost(left - 1).
Trong đó, atMost(given value) là hàm đếm số mảng con với phần tử lớn nhất nhỏ hơn hoặc bằng một số cho trước.
Giải thuật có độ phức tạp thời gian Time Complexity là O(n) và được thực hiện như sau: https://pastebin.com/yCCc9DvU

Có rất nhiều bài có thể được giải với công thức atMost(upper) - atMost(lower), mời bạn đọc tham khảo tại: Binary Subarrays With Sum, Subarrays with K Different Integers

Code & Tools

Góc Sponsors

Fossil Việt Nam, tiền thân là Misfit, giữ vị thế là Trung tâm Nghiên cứu và Phát triển Công nghệ Thiết bị đeo thông minh trực thuộc Fossil Group. Từ những ngày đầu thành lập, đội ngũ kỹ sư Việt đã thiết kế và xây dựng hệ sinh thái thiết bị đeo thông minh phục vụ cuộc sống của hàng triệu người toàn cầu. Chúng tôi tự hào là những nhà đổi mới luôn bứt phá giới hạn của công nghệ và thời trang, tập trung phát triển 3 nhóm sản phẩm chủ lực: thiết bị, ứng dụng, và dữ liệu trên đám mây.

ĐIỀU FOSSIL TỰ TIN MANG ĐẾN CHO BẠN?

Tham gia nghiên cứu và phát triển Thiết bị đeo thông minh hàng triệu người dùng trên toàn thế giới. Với Fossil, mỗi việc bạn làm đều có thể mang lại thay đổi cho cuộc sống của rất nhiều người.
Lộ trình nghề nghiệp đa dạng, bất kể bạn muốn quản lý đội ngũ hay tập trung phát triển chuyên môn kỹ thuật.
Cơ hội làm việc và học hỏi từ các kỹ sư Google, Qualcomm, Citizen, v.v.
Bảo hiểm sức khỏe cao cấp, thu nhập và phúc lợi cạnh tranh mang đến trải nghiệm làm việc toàn diện nhất.
Môi trường làm việc linh hoạt để bạn thỏa sức học hỏi, phát triển và tạo ra tác động tích cực!

Fossil Việt Nam đang mở ra cơ hội với hàng loạt vị trí hấp dẫn

(Cloud Engineer, Android Engineer, Software Architect), mời bạn tham khảo chi tiết công việc tại ĐÂY.

Kết nối với Fossil Việt Nam

Email tuyển dụng: people@fossil.com
Facebook: https://www.facebook.com/FossilVietnamCareers
Linkedin: https://www.linkedin.com/company/fossilvietnamcareers

Quotes

Much of the essence of building a program is in fact the debugging of the specification.

— Fred Brooks