View profile

#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"

Grokking Vietnam
Grokking Vietnam
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
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é.
Góc Lập Trình
Đề tuần này: Binary Tree Cameras
Lời giải đề bài tuần trước:
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
Quotes
Much of the essence of building a program is in fact the debugging of the specification.
— Fred Brooks
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