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

Coffe_Bên_Lề đã nói:

Em ưng ý kiến của bác này, tiếc là không thể thả tim, em chuẩn bị sang năm 3 rồi, mà thuật toán còn yếu quá, mấy bài từ mức dễ còn giải được lên mức trung bình là phân tích không nổi nữa không biết cải thiện được trình độ giải thuật không nữa chứ cứ mấy bài ngang mức trung bình nhiều lúc loay hoay gần 1 tiếng mà chưa giải được

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

vietdt89 đã nói:

đời còn dài. Hồi xưa mình cũng ngu thuật toán lắm, giờ phải lọ mọ đi học lại. Trên reddit nó liệt kê ra 14 pattern của thuật toán, bạn ôn theo pattern, mỗi pattern luyện đến khi nào chạy ra accepted mà k cần xem đáp án là ok. Khi đi PV đôi khi về ngôn ngữ có thể k quá thành thạo, nhưng nếu thuật toán tốt vẫn có thể pass. Nhất là mấy ông mới ra trường, ngoài thuật toán thì biết hỏi gì.Đồ án các bố trên trời dưới biển chán bỏ mẹ
Có thể nói giỏi thuật toán con đường sự nghiệp sẽ mở rộng hơn rất nhiều, k chỉ ở trong nước mà còn có cơ hội làm việc ở nước ngoài. Tây nó toàn hỏi thuật toán thôi, còn lại là SOLID, rồi domain liên quan

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

vietdt89 đã nói:

k pv cái này thì biết pv cái gì bác, nó phản ánh tư duy của ng lập trình. Còn ngôn ngữ nó bao la lắm. 1 cty có tỷ cái project, mỗi project 1 loại ngôn ngữ nền tảng. Tuyển thằng thuật toán tốt tức là tư duy nó tốt, dễ thích ứng với cty

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

• Cái công việc của 1 dev hằng ngày có liên quan rất ít đến những thuật toán khó vkl trong lúc phỏng vấn.
• Đồng ý là 1 ng giỏi algo thường sẽ có tiềm năng trở thành 1 dev tốt. Nhưng điều ngc lại k đúng, 1 ng k giải được các bài hard trên leetcode k có nghĩa họ là developer kém.
• Cái này tạo ra một khoảng gap giữa việc phỏng vấn và công việc thực tế. Dẫn đến rất nhiều người có thể làm được việc nhưng bị loại => Làm tăng chi phí tuyển dụng và lãng phí tgian, công sức. Nếu bạn nào từng phải dính vào tuyển dụng rồi thì sẽ hiểu chi phí cho recruiment bên mảng IT nó thốn cỡ nào.

_Gia_Cat_Luong_ đã nói:

Uhm, mình hiểu cái này bà con cũng bàn nhiều rồi, và có vẻ kết luận algo là cách tốt nhất để tuyển large scale. Nhưng mình k đồng tình lắm. Về cơ bản:

• Cái công việc của 1 dev hằng ngày có liên quan rất ít đến những thuật toán khó vkl trong lúc phỏng vấn.
• Đồng ý là 1 ng giỏi algo thường sẽ có tiềm năng trở thành 1 dev tốt. Nhưng điều ngc lại k đúng, 1 ng k giải được các bài hard trên leetcode k có nghĩa họ là developer kém.
• Cái này tạo ra một khoảng gap giữa việc phỏng vấn và công việc thực tế. Dẫn đến rất nhiều người có thể làm được việc nhưng bị loại => Làm tăng chi phí tuyển dụng và lãng phí tgian, công sức. Nếu bạn nào từng phải dính vào tuyển dụng rồi thì sẽ hiểu chi phí cho recruiment bên mảng IT nó thốn cỡ nào.

Cuối cùng, để trả lời câu hỏi k phỏng ván algo thì phỏng vấn cái gì. Mình share một clip của 1 dev (từng làm tại FAANG) đồng quan điểm với mình, trong đó nói chi tiết hơn những gì mình viết ở đây.

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

_Gia_Cat_Luong_ đã nói:

Uhm, mình hiểu cái này bà con cũng bàn nhiều rồi, và có vẻ kết luận algo là cách tốt nhất để tuyển large scale. Nhưng mình k đồng tình lắm. Về cơ bản:

• Cái công việc của 1 dev hằng ngày có liên quan rất ít đến những thuật toán khó vkl trong lúc phỏng vấn.
• Đồng ý là 1 ng giỏi algo thường sẽ có tiềm năng trở thành 1 dev tốt. Nhưng điều ngc lại k đúng, 1 ng k giải được các bài hard trên leetcode k có nghĩa họ là developer kém.
• Cái này tạo ra một khoảng gap giữa việc phỏng vấn và công việc thực tế. Dẫn đến rất nhiều người có thể làm được việc nhưng bị loại => Làm tăng chi phí tuyển dụng và lãng phí tgian, công sức. Nếu bạn nào từng phải dính vào tuyển dụng rồi thì sẽ hiểu chi phí cho recruiment bên mảng IT nó thốn cỡ nào.

Cuối cùng, để trả lời câu hỏi k phỏng ván algo thì phỏng vấn cái gì. Mình share một clip của 1 dev (từng làm tại FAANG) đồng quan điểm với mình, trong đó nói chi tiết hơn những gì mình viết ở đây.

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

vietdt89 đã nói:

như mình có nói, khi phỏng vấn trong phạm vi domain mà bạn k xuất sắc hoặc đuối thì thuật toán là cái cứu cánh. Ở VN mình thấy k đặt nặng cái phần thuật toán nên cũng ok. Còn phận làm thuê nghe ngóng ng ta tuyển sao thì ôn vậy thôi chớ hơi đâu phản biện

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

clonemasteruwu đã nói:

Ông này faang nào thế bác

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

vietdt89 đã nói:

k pv cái này thì biết pv cái gì bác, nó phản ánh tư duy của ng lập trình. Còn ngôn ngữ nó bao la lắm. 1 cty có tỷ cái project, mỗi project 1 loại ngôn ngữ nền tảng. Tuyển thằng thuật toán tốt tức là tư duy nó tốt, dễ thích ứng với cty

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

_Gia_Cat_Luong_ đã nói:

Trước có nghe bảo làm cho GG xong nghỉ :v

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

nghiabeopro đã nói:

vậy sao k tuyển mấy cha nội iq cao, loại đó dễ train thành master thuật toán lắm mà?
Nói vậy để thấy cái tư duy tuyển chỉ qua thuật toán nó phiến diện ấy.

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

clonemasteruwu đã nói:

sao thi Đh lại thi toán lý hóa sinh văn sử địa, vào đại học có học mấy môn đó nữa đâu
với iq is a fake measure scale

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

clonemasteruwu đã nói:

GGWP à chưa thấy anh nào xuất thân từ faang mà chửi pv algo cả

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

clonemasteruwu đã nói:

GGWP à chưa thấy anh nào xuất thân từ faang mà chửi pv algo cả

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

tu_do_quan_diem đã nói:

Tôi làm quản lý ở big tech chửi pv algo đây. Mấy lần nói chuyện này ở cty với đồng nghiệp rồi nhưng nghĩ đi nghĩ lại thì pv algo nó vẫn dễ scale nhất và phù hợp với việc đánh giá tư duy các bạn ra trường chưa có kinh nghiệm làm việc với code lớn

Tuyển dụng chính xác nhân lực nhất theo tôi là đến từ thực tập: 3 tháng làm việc production đấy thể hiện bản chất con người nhiều hơn vài tiếng pv, nhưng rất tiếc là ko thể scale mô hình này ra cả triệu người nộp đơn xin việc vào big tech mỗi năm được

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

Buonnguqua6 đã nói:

Thanh niên nào éo biết bất cứ tí gì về algo thì đúng nghĩa code monkey. Than vãn gì
Cho vào làm 3 tháng production để biết thực lực thì ai trả lương 3 tháng này cho, các ông chủ tư nhân bao giờ chả tiếc tiền

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

_Gia_Cat_Luong_ đã nói:

Uhm, mình hiểu cái này bà con cũng bàn nhiều rồi, và có vẻ kết luận algo là cách tốt nhất để tuyển large scale. Nhưng mình k đồng tình lắm. Về cơ bản:

• Cái công việc của 1 dev hằng ngày có liên quan rất ít đến những thuật toán khó vkl trong lúc phỏng vấn.
• Đồng ý là 1 ng giỏi algo thường sẽ có tiềm năng trở thành 1 dev tốt. Nhưng điều ngc lại k đúng, 1 ng k giải được các bài hard trên leetcode k có nghĩa họ là developer kém.
• Cái này tạo ra một khoảng gap giữa việc phỏng vấn và công việc thực tế. Dẫn đến rất nhiều người có thể làm được việc nhưng bị loại => Làm tăng chi phí tuyển dụng và lãng phí tgian, công sức. Nếu bạn nào từng phải dính vào tuyển dụng rồi thì sẽ hiểu chi phí cho recruiment bên mảng IT nó thốn cỡ nào.

Cuối cùng, để trả lời câu hỏi k phỏng ván algo thì phỏng vấn cái gì. Mình share một clip của 1 dev (từng làm tại FAANG) đồng quan điểm với mình, trong đó nói chi tiết hơn những gì mình viết ở đây.

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

trungpham90 đã nói:

Halo effect à? Cha này làm Faang bao h? https://www.linkedin.com/in/benawad/

Tôi Google engineer đây, làm tech ở FAANG thì tech stack hầu như khác hẳn vs bên ngoài, chỉ có programming language là chung, nên việc tập trung vào algo vs problem solving skill cũng dễ hiểu thôi.

SWE là công việc đòi hỏi phải có tư duy + sáng tạo, ko phải công nhân nhà máy, khi mà công việc chỉ mang tính rập khuôn, lặp lại; nên nếu nói chỉ phỏng vấn những gì sẽ làm thì tôi thấy khá khó. Đương nhiên tuỳ bản chất công ty nữa, ví dụ như FAANG, thì việc cho nhân viên 1 năm để làm quen với tech stack là điều chấp nhận đc, thì việc tuyển dụng chỉ cần vững lập trình + problem solving skill là hợp lý. Ở chiều ngược lại, start up thì ko có thời gian như vậy, nên tập trung tuyển những người có background để giảm thời gian training lại là điều nên làm.

There is no silver bullet.

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

_Gia_Cat_Luong_ đã nói:

Halo effect thật . Chắc đọc đâu đó r nhớ nhầm.
Tui chưa làm ở FAANG nên chắc góc nhìn phiến diện. Chỉ đánh giá bên ngoài thì thấy nó k cần thiết lắm.

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

. 2^31 => Tối ưu là O(1) hoặc O(logn)
. 10^6 => 10^8 => O(n)
. 10^4 => 10^5 => O(nlogn)
. 2000 => 10^4 => O(nlogn) hoặc O(n^2)
. 300 - 5000 => O(n^2)
. Nhỏ hơn nữa thì thường là O(2^n) hoặc O(n!)

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

. (1) Sort lại: O(nlogn)
. (2) For với mỗi element: O(n)
. (3) Giải bài toán nhỏ cho element đó: O(logn) vì dữ liệu đã sắp xếp

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

• 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).

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)

• 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:

. Mỗi layer có thể lưu minWidth và minHeight để hạn chế loop vào trong từng layer để kiểm tra
. Dữ liệu trong từng layer cũng có thể có thứ tự và dùng binary search để improve

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

• 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.

_Gia_Cat_Luong_ đã nói:

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).

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