View profile

#187 - Điều ta không thể nghĩ trong lập trình

Grokking Vietnam
Grokking Vietnam
Những bài viết hay
Building a dynamic and responsive Pinterest
Góc Distributed System
Enabling Seamless Kafka Async Queuing with Consumer Proxy
Góc Lập Trình
Đề ra tuần này:
Cho hai mảng số nguyên inorderpostorder lần lượt là inorder traversal và  postorder traversal của một binary tree. Hãy xây dựng và trả về binary tree nói trên.
Ví dụ 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Ví dụ 2:
Input: inorder = [-1], postorder = [-1]
Output: [-1]
Lời giải tuần trước
Đề bài
Lời giải
Đề bài yêu cầu gộp `k` linked-list đã được sắp xếp lại thành một linked-list, linked-list sau khi gộp cũng phải được sắp xếp. Có rất nhiều phương pháp để giải bài này, mình xin được giới thiệu 2 hướng tiếp cận sau đây:
1. Chọn lần lượt node có giá trị nhỏ nhất từ `k` linked-list
Ý tưởng của hướng tiếp cận này là ta lần lượt chọn node có giá trị nhỏ nhất từ `k` linked-list, thêm vào list kết quả, sau đó tăng con trỏ của node được chọn tới node tiếp theo.
Lặp lại bước trên cho tới khi tất cả các node đều đã được chọn.
Độ phức tạp của giải thuật time complexity là O(kN) với k là số lượng linked-list, N là tổng số node, bởi tại mỗi bước ta cần so sánh `k` node để chọn node có giá trị nhỏ nhất. Space complexity là O(1).Với thuật toán trên ta có thể tối ưu bước chọn phần tử nhỏ nhất bằng min heap có size là k. time complexity sẽ là O(logk * N), space complexity là O(k).2. Gộp từng cặp 2 linked-list cho tới khi có kết quả cuối cùng
Hướng tiếp cận này mượn ý tưởng của hàm gộp trong merge sort. Ta lần lượt gộp 2 cặp list lại thành 1, và lặp lại quá trình cho tới khi chỉ còn 1 list duy nhất. Thuật toán được thực hiện như sau:<TODO: paste link to code>Độ phức tạp của giải thuật trên có time complexity là O(logk * N), space complexity là O(N) cho mảng `tmp`.
Ta có thể tối ưu space complexity xuống O(1) bằng cách sử dụng mảng đầu vào `ListNode[] lists` để lưu trữ kết quả gộp tạm thời. Bạn đọc hãy thử tối ưu nhé.
Code & Tools
This Week Sponsors
Database documentation tự động với dbdocs.io
[Nội dung tài trợ] dbdocs.io là một công cụ giúp các bạn Dev có thể tự sinh ra nguyên trang document về cấu trúc database của mình chỉ bằng vài dòng lệnh command-line. Nó giúp quá trình planning và design database trong team dev dễ dàng hơn.
Hiện team dbdocs (ở TPHCM) đang tìm thêm 2 bạn fullstack/backend engineers để tham gia phát triển sản phẩm dev tool này. Bạn nào quan tâm có thể xem thêm tại: https://careers.holistics.io/job-openings/open-source-full-stack-engineer
(Team dbdocs cũng là team xây dựng công cụ dbdiagram.io phổ biến mà nhiều bạn dev đang dùng.)
Quotes
“I very frequently get the question: “What’s going to change in the next 10 years?” That’s a very interesting question.
I almost never get the question: “What’s not going to change in the next 10 years?” And I submit to you that that second question is actually the more important of the two.
You can build a business strategy around the things that are stable in time. In our retail business, we know that customers want low prices, and I know that’s going to be true 10 years from now. They want fast delivery; they want vast selection. It’s impossible to imagine a future 10 years from now where a customer comes up and says, “Jeff I love Amazon, I just wish the prices were a little higher.” Or, “I love Amazon, I just wish you’d deliver a little slower.” Impossible.
So we know the energy we put into these things today will still be paying off dividends for our customers 10 years from now. When you have something that you know is true, even over the long term, you can afford to put a lot of energy into it.”
— Jeff Bezos
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

Ngoài ra các bạn có thể gửi feedback cho Grokking Newsletter team ở https://bit.ly/3k3Jdw5 hoặc đóng góp bài viết tại https://bit.ly/2XaBUtF

If you don't want these updates anymore, please unsubscribe here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam