thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

athxzz · 23/8/25

LmaoSuVuong đã nói:
bài này thì brute-force thui mà bác. bên y chỉ lấy substring thì mình cứ phang hết thui2000 *2000

brtue force như nào thế thím tôi chưa tưởng tượng ra? substring ở y chứ x là subsequence mà

aNotHeRNo0b · 23/8/25

LmaoSuVuong đã nói:
bài này thì brute-force thui mà bác. bên y chỉ lấy substring thì mình cứ phang hết thui2000 *2000

Substring lúc check ở bên X vẫn là O(n) nữa, tổng sẽ là O(n**3) mà huynh?

LmaoSuVuong · 23/8/25

athxzz đã nói:
brtue force như nào thế thím tôi chưa tưởng tượng ra? substring ở y chứ x là subsequence mà

với mỗi substring bắt đầu ừ i (0-len y) xem nó trùng dc dài sub sequence x tới đâu thì O(len(y) * len(x)) là ra dc kết quả đúng ko nhỉ.(substring là chuỗi liên tiếp ko ngắt mà đúng ko bác) so len 2 subsequence dài nhất mới xài dp

LmaoSuVuong · 23/8/25

aNotHeRNo0b đã nói:
Substring lúc check ở bên X vẫn là O(n) nữa, tổng sẽ là O(n**3) mà huynh?

hmm theo như e tưởng tượng ra thì cứ match letter là múc thôi bên X cho phép sub sequence mà

aNotHeRNo0b · 23/8/25

LmaoSuVuong đã nói:
hmm theo như e tưởng tượng ra thì cứ match letter là múc thôi bên X cho phép sub sequence mà

Em hiểu ý huynh rồi, for (i,j) ở bên y, lúc j tăng thì tăng bên x luôn đúng không, đúng là O(n^2) rồi

athxzz · 23/8/25

2 thím draft quả solution phát, chẳng nhẽ tôi overthinking dp ngồi debug mãi mới ra

aNotHeRNo0b · 23/8/25

Với mỗi vị trí start i ở Y, for j đến cuối, thím dùng thêm 1 biến nữa để while bên x cho tới khi nó trùng với kí tự Y[j] là được

LmaoSuVuong · 23/8/25

athxzz đã nói:
2 thím draft quả solution phát, chẳng nhẽ tôi overthinking dp ngồi debug mãi mới ra

Java:

        int cnt=0;
        int res =0;
        for(int i =0 ;i <y.length();i++){
            cnt=0;
            for(int j=0;i+cnt<y.length() && j<x.length();j++){
                if(y.charAt(i+cnt)==x.charAt(j)){
                    cnt++;
                }
            }
            res = Math.max(res, cnt)
        }
        return res;

athxzz · 23/8/25

Manmapi · 23/8/25

athxzz đã nói:
tôi cũng thấy lạ, bình thường pv ở mấy công ty Việt chả bao giờ dính thuật.
Btw đề cũng dễ nhớ cho ae quẩy: top down, bottom up chắc chục dòng.
Input: String x and y length < 2000. Find longest common string which is sub sequence of x and is substring of y. Output: Int

Bài long common subsequence mới cần tới DP. Bài này là 1 sub sequence và 1 substring thì dùng 2 pointer là giải được mà nhỉ. TC: O(len(x) + len(y))

Manmapi · 23/8/25

athxzz đã nói:
2 thím draft quả solution phát, chẳng nhẽ tôi overthinking dp ngồi debug mãi mới ra

Python:

def sol(str1, str2):
    m, n, i, j = len(str1), len(str2), 0, 0
    res = 0
    while i < m and j < n:
        if str1[i] == str1[j]:
            res += 1
            i += 1
            j += 1
        else:
            i += 1
    return res

LmaoSuVuong · 23/8/25

Manmapi đã nói:
Bài long common subsequence mới cần tới DP. Bài này là 1 sub sequence và 1 substring thì dùng 2 pointer là giải được mà nhỉ. TC: O(len(x) + len(y))

Manmapi đã nói:

Python:

def sol(str1, str2):
    m, n, i, j = len(str1), len(str2), 0, 0
    res = 0
    while i < m and j < n:
        if str1[i] == str1[j]:
            res += 1
            i += 1
            j += 1
        else:
            i += 1
    return res

x = "bbbbbbbb" y ="abbbb" thì j=0 mãi không lên dc phen

Manmapi · 23/8/25

LmaoSuVuong đã nói:
x = "bbbbbbbb" y ="abbbb" thì j=0 mãi không lên dc phen

À em nhầm với startsWith. Thế quả này thêm 1 loop nữa là O(n^2) à

athxzz · 23/8/25

Manmapi đã nói:
Bài long common subsequence mới cần tới DP. Bài này là 1 sub sequence và 1 substring thì dùng 2 pointer là giải được mà nhỉ. TC: O(len(x) + len(y))

non nớt đấy thím

freedom.9 · 23/8/25

athxzz đã nói:
bỏ bê thuật toán 2 tháng mà đi phỏng vấn FPT có câu về DP cỡ medium ngâm mãi mới ra

Vl thằng nào Fsoft hỏi thuật toán vậy xin cái BU :sweat:

via theNEXTvoz for iPhone

SadboiTMT · 24/8/25

freedom.9 đã nói:
Vl thằng nào Fsoft hỏi thuật toán vậy xin cái BU

via theNEXTvoz for iPhone

Chắc là Meta, đi phá băng dự án khách nhưng khách nói không biết thuật toán thì miễn thương lượng

Husqvarna701SM · 24/8/25

Mình thấy làm thuật toán vẫn vui, dù đi phỏng vấn éo bị hỏi
Đợt này sếp có giao mình 1 task liên quan tới geocoding, về cơ bản có quả xử lý check xem điểm có thuộc polygon hay k. Ngồi tối ưu cũng vui phết

freedom.9 · 24/8/25

SadboiTMT đã nói:
Chắc là Meta, đi phá băng dự án khách nhưng khách nói không biết thuật toán thì miễn thương lượng

Thời của AI, công nghệ càng đi nhanh mà ko biết những cái nền tảng thì đúng là khỏi nên thương lượng thật.
Cơ mà lương trả thì ko cao lại đòi biết thuật toán thì sao mà đủ lương trả cho ứng viên được.

dhl001 · 24/8/25

giải được mỗi Q1:

Java:

class Solution {
    public int gcdOfOddEvenSums(int n) {
        return n;
    }
}

freedom.9 · 24/8/25

Còn Q4

quá phê

thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này