thảo luận [Học Tập] Topic thuật toán

Yoo Si Jin đã nói:

Tư duy em nói ở đây là tư duy giải quyết bài toán đó thím, kiểu trong đầu mình phân tích làm các bước a -> b được kết quả c

Em thấy cái đó em hơi chậm

Nhấp để mở rộng...

canh_1412 đã nói:

Thím cho hỏi, khi phỏng vấn google xong, pass rồi, thím đã biết vào mình làm gì, assign team nào chưa. Hay vào chính thức vào rồi mới biết.

Nhấp để mở rộng...

trungpham90 đã nói:

Qua đc vòng hiring committee (HC) rồi thì sẽ vào team matching, lúc đó hiring manager của các team sẽ xem profile của cậu và nói chuyện vs cậu để xem có phù hợp vs team họ ko. Nếu thấy cậu phù hợp thì họ sẽ offer cho cậu. Trong trường hợp có nhiều hơn 1 team thích cậu thì cậu sẽ đc chọn team. Cậu cũng có thể reject team đó để đợi team khác, vì khi đã qua đc vòng HC thì kết quả đó sẽ đc bảo lưu trong 1 năm, nên trong vòng 1 năm đó cậu có thể đợi team phù hợp rồi mới vào.

Khi có team rồi thì mới nhận đc offer chính thức, bao gồm cả mức lương, thưởng, stock ....

Cậu đã pv chưa? đến vòng nào rồi?

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Tiếp tục chuyên mục mỗi ngày một leetcode. Ba bài mình làm ngày hôm nay:

#354. (Hard) https://leetcode.com/problems/russian-doll-envelopes/
#355. (Medium) https://leetcode.com/problems/design-twitter/
#357. (Medium) https://leetcode.com/problems/count-numbers-with-unique-digits/

Mình sẽ share về bài Russian Doll Envelopes:
#354. (Hard) https://leetcode.com/problems/russian-doll-envelopes/

Bài này Hard và mình thấy khá chua, mất khoảng 2h để giải. Mình chọn share bài này vì 2 bài kia 1 cái quá phức tạp, 1 cái quá simple.

Phân tích bài toán:
- 1 <= envelopes.length <= 5000: Độ phức tạp tối ưu có vẻ là O(nlogn). Cái này làm nhiều sẽ có kinh nghiệm, đề thường cho khoảng dữ liệu đủ lớn để timedout các solution không tối ưu:


- Thấy O(nlogn) thì thường sẽ dính đến việc sắp xếp hoặc tổ chức dữ liệu trước khi xử lý. Thường sẽ là:


- Điểm khó của bài này chính là dữ liệu 2 chiều nên khó sắp xếp hợp lý, nếu chỉ sắp xếp theo 1 chiều thì bước 3 sẽ fallback về O(n) và bị timed-out.

Solution:

• Nhận thấy nếu sort dữ liệu theo diện tích của bao thư thì sẽ đảm bảo được nếu bao thư a bọc được bao thư b, thì diện tích của a chắc chắn lớn hơn b.
• Sau khi sort xong thì bài toán trở thành tìm mảng con các bao thư bọc nhau, sao cho mảng con này có chiều dài lớn nhất.
• Đây là biến thể của bài toán kinh điển của QHĐ: Tìm mảng con tăng dài nhất (https://leetcode.com/problems/longest-increasing-subsequence/). Mà bài này có thể được giải đơn giản với đpt O(nlogn).

Python:

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes:
            return 0
   

        envelopes.sort(key=lambda envl: envl[0] * envl[1]) # Sắp xếp theo diện tích tăng dần
   
        # Ý tưởng tương tự như bài mảng con tăng dài nhất
        # Mảng layers là số lượng lớp bao thư lớn nhất, đến hiện tại
        # Mỗi phần tử thứ i trong mảng layer lại là một list chứa các bao thư nằm ở lớp thứ i
        # Bao thư nằm ở lớp 0 nghĩa là bên trong nó không chứa được thêm bao thư nào
        # Bao thư nằm ở lớp i nghĩa là bên trong nó có thể chứa được i - 1 bao thư nằm ở các lớp trước đó
        layers = []
        for envl in envelopes:
            # với mỗi bao thư, tìm layer thứ i sao cho ở layer này có ít nhất 1 bao thư mà có thể chứa trong bao thư này
            # => bao thư hiện tại sẽ nằm ở thứ i + 1
            i = len(layers) - 1
            while i >= 0:
                if any(envl2 for envl2 in layers[i] if envl[0] > envl2[0] and envl[1] > envl2[1]):
                    break
                i -= 1
           
            # Nếu i == -1 => bao thư không chứa được ai cả, cho vào layer 0
            # i == len(layers) - 1: Bao thư này chứa được bao thư lớn nhất => Tạo thêm 1 layer mới
            if i == len(layers) - 1:
                layers.append([])
           
            # set bao thư vào layer thứ i + 1
            layers[i + 1].append(envl)
       
        # Số lượng layer chính là kết quả cần tìm
        return len(layers)

Note:

• Solution ở trên thật ra có độ phức tạp trong trường hợp xấu nhất là O(n^2). Khi tất cả các bao thư không cái nào chứa được trong cái nào (Tất cả bằng nhau chẳng hạn).
• Về trung bình thì số layer sẽ bằng log(n) so với số bao thư. Nên độ phức tạp trong trường hợp trung bình là O(nlogn)
• Mình chỉ faster than 22% thôi. Còn có nhiều điểm có thể tối ưu, nhưng pass là vui rồi, bạn nào hứng thú có thể improve thêm:

• Giải pháp ban đầu của mình là tổ chức dạng graph và quy về bài toán tìm đường đi dài nhất trong đồ thị => mất hơn 1 tiếng trước khi đập hết và nghĩ ra giải pháp trên.
• Việc có một hướng tiếp cận đúng đắn sẽ giúp tiết kiệm rất rất nhiều thời gian. Trong pv thực tế các bạn nên communicate liên tục với interviewer để họ sửa ngay khi mình đi sai đường.

Welcome mọi người thảo luận và đưa ra solution tốt hơn nữa.

Nhấp để mở rộng...

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        envelopes.sort(key = lambda e: e[0] + e[1])
        res = 1
        farfromnow = [1]*n
       
        for i in range(1,n):
            for j in range(i):
                if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]:
                    farfromnow[i] = max(farfromnow[j]+1, farfromnow[i])
                res = max(res, farfromnow[i])
                   
        return res

[IamNormal] đã nói:

constraint 5000 thì O(n^2) thừa sức giải, mà tđn bị TLE ạ

phần sort thìm em chỉ sort theo tổng vì x1 < x2 and y1 < y2 => x1 + y1 < x2 + y2
Ý tưởng đơn giản là tìm dãy con tăng chặt dài nhất, kết quả là độ dài của dãy con tăng chặt dài nhất đó. Phương pháp DP như thường

Python:

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        envelopes.sort(key = lambda e: e[0] + e[1])
        res = 1
        farfromnow = [1]*n
     
        for i in range(1,n):
            for j in range(i):
                if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]:
                    farfromnow[i] = max(farfromnow[j]+1, farfromnow[i])
                res = max(res, farfromnow[i])
                 
        return res

Nhấp để mở rộng...

clonemasteruwu đã nói:

LIS pair có thể làm nlogn được đấy.
sort theo phần tử đầu (nếu strictly LIS thì break tie bằng sort decresase thằng thứ 2, còn loosely LIS thì increase thằng thứ 2), sau đó làm LIS trên thằng thứ 2

C++:

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        auto n = envelopes.size();
        vector<pair<int,int>> v;
        v.reserve(n);
        for(auto& env:envelopes){
            v.emplace_back(env[0],env[1]);
        }
        sort(v.begin(),v.end(),[](const pair<int,int>& a,const pair<int,int>& b){
            return a.first == b.first ? a.second > b.second : a.first < b.first;
        });
        vector<int> lis;
        for(auto p:v){
            auto insert_pos = lower_bound(lis.begin(),lis.end(),p.second);
            if(insert_pos == lis.end()) lis.push_back(p.second);
            else *insert_pos = p.second;
        }
        return (int)lis.size();
    }

Nhấp để mở rộng...

[IamNormal] đã nói:

constraint 5000 thì O(n^2) thừa sức giải, mà tđn bị TLE ạ

phần sort thìm em chỉ sort theo tổng vì x1 < x2 and y1 < y2 => x1 + y1 < x2 + y2
Ý tưởng đơn giản là tìm dãy con tăng chặt dài nhất, kết quả là độ dài của dãy con tăng chặt dài nhất đó. Phương pháp DP như thường

Python:

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        envelopes.sort(key = lambda e: e[0] + e[1])
        res = 1
        farfromnow = [1]*n
      
        for i in range(1,n):
            for j in range(i):
                if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]:
                    farfromnow[i] = max(farfromnow[j]+1, farfromnow[i])
                res = max(res, farfromnow[i])
                  
        return res

Nhấp để mở rộng...

Lập Trình Viên Số Khổ đã nói:

fen siêu vậy CF 1975, tui học nửa năm rồi mà vẫn 1300

Nhấp để mở rộng...

clonemasteruwu đã nói:

anh CEO cứ trêu e, VN rank tím nhiều như lợn con

Nhấp để mở rộng...

clonemasteruwu đã nói:

anh CEO cứ trêu e, VN rank tím nhiều như lợn con

Nhấp để mở rộng...

Lập Trình Viên Số Khổ đã nói:

Đấy là học sinh chuyên tin mới được chứ ng trái ngành, già não chậm ko bik luyện mấy năm mới đc

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

2 cái số đấy là gì thế fen ?

Nhấp để mở rộng...

thenaodaynho đã nói:

Thấy mấy thread thuật toán xôm quá. Hnay vào leetcode giải thử thì nguyên buổi được 2 vài easy, tới bài thứ 3 thì bí. Khốn nạn thiệt mà

Nhấp để mở rộng...

thenaodaynho đã nói:

Thấy mấy thread thuật toán xôm quá. Hnay vào leetcode giải thử thì nguyên buổi được 2 vài easy, tới bài thứ 3 thì bí. Khốn nạn thiệt mà

Nhấp để mở rộng...

• 1 <= nums.length <= 1000: Độ phức tạp kì vọng có lẽ là O(n^2)
• Thông thường khi estimate độ phức tạp từ O(nlogn) trở lên thì ta nên thử nghĩ đến việc sort lại dữ liệu trước. Vì độ phức tạp của việc sort chỉ là O(nlogn) nên nó như kiểu free juice, không làm ảnh hưởng đến kết quả chung. Và hầu hết các bài toán được giải dễ hơn nhiều trên dữ liệu đã sắp xếp.
• Đề bài gây rối khi yêu cầu mỗi cặp số trong kết quả đều phải thỏa mãn điều kiện trông có vẻ phức tạp:

answer % answer[j] == 0, or
answer[j] % answer == 0

Nhấp để mở rộng...

• Đồng thời yêu cầu trả về kết quả tốt nhất có thể => Tạo cảm giác khó khăn vì bài toán tối ưu thường khó hơn nhiều so với bài toán chỉ cần trả về một kết quả phù hợp.
• Phân tích kĩ thì yêu cầu bài toán là các cặp số trong mảng kết quả phải là bội số của nhau, tức là cứ lấy 2 số a và b bất kì, thì hoặc a là bội số của b, hoặc b là bội số của a

Ví dụ: [2,1,4,8,32] => Tất cả các cặp số đều là bội hoặc ước số của nhau

Nhấp để mở rộng...

• Điều này nghe có vẻ phức tạp, nhưng nếu nhìn bài toán trong điều kiện đã sắp xếp, thì nhận thấy nó chỉ đơn giản là số đứng sau phải chia hết cho các số đứng trước.

Ví dụ: [1,2,4,8,32] hoặc [3,27,81,729]

Nhấp để mở rộng...

• Tiếp tục suy diễn, thì ta thấy thật ra số đứng sau chỉ cần chia hết cho số liền trước nó là được, không cần phải kiểm tra toàn bộ các số đứng trước, vì tính chất bắc cầu.
• Ta nhận thấy từ một mảng input có thể có nhiều mảng con thỏa mãn điều kiện trên, và kết quả cần tìm là mảng có length lớn nhất.

Ví dụ: [1,2,3,4,5,6,7,8,9]. Có 2 mảng con thỏa mãn điều kiện là [1,2,4,8] và [1,3,9]. Kết quả sẽ là [1,2,4,8] vì nó dài hơn.

Nhấp để mở rộng...

• Vì độ phức tạp kì vọng là O(n^2), nên ta đơn giản có thể loop và kiểm tra từng cặp số trong mảng input, nếu số b chia hết cho số a thì b sẽ được thêm vào trong mảng kết quả tương ứng, đứng sau a.
• Để trả về mảng có chiều dài lớn nhất, ta chỉ cần keep track chiều dài của các mảng kết quả và trả về mảng lớn nhất

• Đầu tiên đương nhiên là sort lại mảng input
• Tạo mảng truy vết. Với mỗi phần tử ta cần truy vết lại phần tử đứng trước nó trong mảng kết quả, và kích thước của mảng kết quả đến hiện tại
• Ta cũng cần truy vết index của phần tử có mảng kết quả lớn nhất
• Lặp với từng cặp số trong mảng input
• Nếu nums chia hết cho nums[j] và kích thước tại i < kích thước tại j + 1 => Cập nhật lại mảng truy vết của i
• Nếu kích thước tại i > maxSize => cập nhật lại maxSize mà maxIndex = i
• Từ maxIndex truy ngược lại mảng kết quả có chiều dài lớn nhất
• Trả về kết quả

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        divs = [] # Mảng truy vết
        maxSize = 0 # Chiều dài lớn nhất của các mảng kết quả
        maxIndex = -1 # Index của phần tử cuối cùng
        for i, n in enumerate(nums):
            divs.append([-1, 1])
            for j in range(i):
                if n % nums[j] == 0 and divs[j][1] + 1 > divs[-1][1]:
                    divs[-1][0] = j
                    divs[-1][1] = divs[j][1] + 1
            if divs[-1][1] > maxSize:
                maxSize = divs[-1][1]
                maxIndex = i
               

        # Truy vết lại từ maxIndex
        res = []
        while maxIndex >= 0:
            res.append(nums[maxIndex])
            maxIndex = divs[maxIndex][0]
           
        res.reverse()
        return res

• 1 <= nums1.length, nums2.length <= 10^4: Độ phức tạp kì vọng có lẽ là O(nlogn)
• Dữ liệu đã sắp xếp sẵn nên không cần sắp xếp lại
• Đề bài yêu cầu lấy ra k cặp số có tổng nhỏ nhất, từ 2 mảng
• Dễ thấy cặp số nhỏ nhất chắc chắn là 2 phần tử đầu tiên của 2 mảng (nums1[0], nums2[0])
• Với cặp số thứ 2, đó có thể là (nums1[1], nums2[0]) hoặc (nums1[0], nums2[1]). Tùy theo cái nào nhỏ hơn.
• Với cặp số thứ 3, nó phụ thuộc vào cách ta chọn cặp số thứ 2, các khả năng có thể là
  • (nums1[1], nums2[1]) và (nums1[0], nums2[2]). Nếu lần trước ta chọn cặp (nums1[0], nums2[1])
  • (nums1[1], nums2[1]) và (nums1[2], nums2[0]). Nếu lần trước ta chọn cặp (nums1[1], nums2[0])
• Đến đây ta rút ra 2 kết luận:
  • Nếu lần trước ta chọn cặp số thứ (nums1, nums1[j]). Thì tiếp theo sẽ phát sinh thêm 2 khả năng (nums1, nums2[j + 1]) hoặc (nums1[i + 1], nums2[j])
  • Pattern ở đây là có một mảng các số (là tổng của cặp số), và ta liên tục lấy ra các số số nhỏ nhất, không quan tâm các số còn lại => Phù hợp với cấu trúc dữ liệu heap

• Khởi tạp heap với cặp đầu tiên là (0, 0)
• Lặp cho đến khi lấy được k kết quả, hoặc hết heap
  • Lấy kết quả nhỏ nhất ra, cho và mảng output
  • Thay thế nó bằng 2 khả năng mới là (i + 1, j) và (i, j + 1)
• Return về mảng output

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        j = [0] * len(nums1)
        h = [(nums1[0] + nums2[0], 0, 0)]
      
        visited = set()
        res = []
        while h and len(res) < k:
            val, i, j = heappop(h)
            res.append([nums1[i], nums2[j]])
          
            if i < len(nums1) - 1 and (i + 1, j) not in visited:
                heappush(h, (nums1[i + 1] + nums2[j], i + 1, j))
                visited.add((i + 1, j))
              
            if j < len(nums2) - 1 and (i, j + 1) not in visited:
                heappush(h, (nums1[i] + nums2[j + 1], i, j + 1))
                visited.add((i, j + 1))
              
        return res

bibooboo đã nói:

^ bác siêng thế, mình làm 8 tiếng cty xong ở nhà phải phụ bạn gái nấu ăn, rửa chén, dọn dẹp nhà cửa, thành ra buổi tối rảnh có 1-2 tiếng. Đang cố cày thuật toán mà hơi rối.
bác cho mình cái roadmap dc ko, hay cứ lên leetcode quất đại?

Nhấp để mở rộng...

• Muốn target vào FAANG: Phải luyện all level. Bài hard cũng phải làm trôi được 80%.
• Muốn vào EU & US: Luyện đến medium thôi chắc cũng đủ rồi. Làm hard hao não lắm mà ng ta cũng k phỏng vấn đến đó
• Luyện cho market VN: Chẹp, chắc là lên mạng gg các bài code thường gặp khi phỏng vấn thì tốt hơn. VN k pv leetcode.
• Luyện để cải thiện khả năng tư duy & code thực tế: Làm mấy bài easy là đủ