View profile

#235 - Một cái nhìn sâu về Idempotence

Grokking Vietnam
Grokking Vietnam
Trong số này, chúng ta cùng tìm hiểu về:
  • Concurrency chưa chắc luôn luôn là nhanh nhất ở Go
  • So sánh giữa REST vs GraphQL vs gRPC
  • Một cái nhìn sâu về Idempotence
  • Lời giải bài Last Stone Weight II
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.

News
Những bài viết hay
Góc Lập Trình
Đề ra tuần này: Add Bold Tag in String
(by phucnh)
Cho một string s và một array chứa strings words. Ta cần phải viết thêm bold tag <b> và </b> cho các substrings words chứa trong s. Nếu 2 substrings chồng lên nhau thì ta cần phải bọc chúng với chỉ một cặp bold tag. Nếu 2 substrings được bọc bởi các bold tags liền kề với nhau, ta cần phải kết hợp chúng lại.
Hãy trả lại s với bold tags. Ví dụ:
Input: s = “abcxyz123”, words = [“abc”, “123”]
Output: “<b>abc</b>xyz<b>123</b>”
Lời giải đề bài tuần trước: Last Stone Weight II
(by phucnh)
Cách tiếp cận đầu tiên ta có thể nghĩ tới là lần lượt đập hai hòn đá bất kì, tuy nhiên giải thuật này sẽ có độ phức tạp về thời gian là 2^n, với n là số lượng hòn đá.
Để giải bài này một cách tối ưu hơn, ta cần có quan sát như sau: Giả sử ta có 4 hòn đá a, b, c, d, với khối lượng lần lượt là wa >= wb >= wc >= wd, ta lần lượt đập 2 hòn đá vào nhau như đề bài, ta có thể thu được những kết quả sau:
  1. (a - b) - (c - d)
  2. (a - c) - (b - d)
  3. (a - d) - (b - c)
Ta triển khai các kết quả lần lượt như sau:
  1. (a - b) - (c - d) =  a - b - c + d =  (a + d) - (b + c)
  2. (a - c) - (b - d) =  a - c - b + d = (a + d) - (b + c)
  3. (a - d) - (b - c) =  a - d - b + c = (a + c) - (b + d)
Ta thấy rằng, ta luôn luôn có thể chia những hòn đá thành 2 nhóm, và kết quả cuối cùng là hiệu của tổng khối lượng đá ở mỗi nhóm. Và đề bài yêu cầu tìm hiệu nhỏ nhất.
Đây là một ứng dụng của bài toán tìm tập con trong mảng số nguyên dương có tổng cho trước, được giải bằng cách áp dụng lời giải của 0/1 Knapsack.
Thuật toán được thực hiện như sau: https://pastebin.com/v3nLYqmH
Giải thuật có độ phức tạp là O(n*total), với n là số lượng hòn đá, total là tổng khối lượng của tất cả các hòn đá.
Code & Tools
  • Media-To-Ascii - Một tool viết bằng Rust để chuyển đổi media files sang ASCII output.
  • pandas-gbg - Một python package chứa interface tới Google BigQuery API từ pandas
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)
Grokking mang lại cho các bạn những kiến thức mới mẻ và hữu ích thông qua:
  • Tech Talk: Là một hoạt động thường xuyên của Grokking từ những ngày đầu thành lập. Tại đây các diễn giả chia sẻ kiến thức xoay quanh Computer Science và Software Engineer. Các buổi Tech Talk đều được record và upload lên kênh youtube của Grokking.
  • Grokking Knowledge Graph: Tập hợp những nguồn kiến thức phong phú với hơn 1000 bài viết chọn lọc, các đầu sách, khóa học, v.v… Các bài viết đều được gán nhãn để giúp bạn đọc dễ dàng tìm kiếm.
  • Webinar: Là chương trình kết nối các kỹ sư Việt Nam và các kỹ sư đang làm việc tại các công ty công nghệ hàng đầu thế giới.
  • Dijkstra: Một ấn phẩm được xuất bản bởi các thành viên của Grokking. Với những bài viết đào sâu vào kỹ thuật và kiến thức khoa học máy tính.
  • Kipalog: Nền tảng chia sẻ kiến thức dành cho các lập trình viên.
  • Newsletter: Những bài viết hay về công nghệ sẽ được gửi tới bạn hàng tuần qua email.
Chúc các bạn sẽ tìm được nhiều điều mới mẻ khi đến với Grokking và xin hẹn gặp lại các bạn vào tuần sau.
Quotes
Every programmer is an author.
- Sercan Leylek
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