thảo luận Leetcode mỗi ngày

thay vì hỏi ứng viên "bạn đã đọc về LSM chưa?" thì hãy hỏi "cho một file 200GB chứa nhiều dòng chuỗi ký tự, mỗi chuỗi dài không quá 1KB..."
 
maskup said:
Bài đó dùng LSM tree được à bác?:surrender:
Click to expand...
trong quá trình nghĩ ra lời giải thì dính tới mấy thứ có xài trong LSM: sorted strings table chứa dữ liệu sort theo key, bloomfilter để biết coi là trong SST có key hay không, quá trình compaction để merge hai sorted strings table, etc., mấy cái này chương 3 của DIDA có nói qua
 
rock_o0o said:
Cho mình hỏi cày leetcode thì có cách nào thể hiện khả năng của mình vào CV k? Kiểu mình cày hackerrank thì có hẳn bài thi chứng chỉ riêng. Cơ mà kể cả vậy mình thấy vd như ghi chứng chỉ sql trên hackerrank vào mục chứng chỉ trong cv cx cứ kiểu gì á.
Click to expand...
HR nhìn resume chắc chỉ scan keyword thôi chứ không quan tâm LC đâu
 
small-lambda said:
trong quá trình nghĩ ra lời giải thì dính tới mấy thứ có xài trong LSM: sorted strings table chứa dữ liệu sort theo key, bloomfilter để biết coi là trong SST có key hay không, quá trình compaction để merge hai sorted strings table, etc., mấy cái này chương 3 của DIDA có nói qua
Click to expand...
Hợp lý, nhưng theo em chỉ dùng bloomfilter là đủ, không cần tới LSM
Có 2 lần scan disk, cả 2 lần đều là sequential read
  • Lần 1: scan từng line, check trùng key bằng bloomfilter, nếu bloomfilter detect trùng => lưu dòng này (hoặc hash của dòng này) vào ram (có thể dùng hashset)
  • Lần 2: scan từng line check xem nó có tồn tại trong hashset trên hay ko, nếu có thì chắc chắn nó là dòng dup.
Edit: à chưa đào sâu cái false positive rate của bloomfilter, nếu nó cao tới mức 16GB ram ko gánh được thì phải partition file.
 
Last edited:
maskup said:
Hợp lý, nhưng theo em chỉ dùng bloomfilter là đủ, không cần tới LSM
Có 2 lần scan disk, cả 2 lần đều là sequential read
  • Lần 1: scan từng line, check trùng key bằng bloomfilter, nếu bloomfilter detect trùng => lưu dòng này (hoặc hash của dòng này) vào ram (có thể dùng hashset)
  • Lần 2: scan từng line check xem nó có tồn tại trong hashset trên hay ko, nếu có thì chắc chắn nó là dòng dup.
Click to expand...
đề bài đảm bảo là chỉ có duy nhất một string trùng rồi, nên trước khi insert vào bf kiểm tra coi trong bf có string đó hay chưa là kiếm được kết quả

xài bf thì phải đảm bảo là memory đủ chứa bf cho lượng item cần scan, tức là phải ước lượng trong cái file đó có bao nhiêu item, tương ứng với amortized memory usage là bao nhiêu, ví dụ implement cái bf ntn đó mà có amortized storage cost là 10 bit cho mỗi item đi thì bf chỉ chứa được tối đa 8 * 16 * 1024.pow(3) / 10 xấp xỉ bẳng 13.7 tỉ string, có thể lợi dụng chuyện đề chỉ có một string trùng lặp để ước lượng gì đó và biết là chỉ cần xài bf chẳng hạn, mà lười quá không làm, v/v

trong trường hợp biết là xài bf mà không đủ mem, bằng cách đếm hay ước lượng gì đó, thì buộc phải đi làm chuyện external sort thôi

nhưng mấy solution này phức tạp quá, thông thường câu trả lời cho mấy câu hỏi này là "lụi", khác nhau là lụi đứa nào thôi,

ví dụ như cần lấy thông tin từ cái laptop nào đó mà thông tin bị mã hóa với thuật toán tân tiến xyz gì đó thì lụi chủ laptop

theo như đề bài thì lụi đứa ra đề

edit:

nhiều khả năng là người ra đề muốn bạn chí ít phải chỉ ra được mấy cái vớ vẩn trong LSM, nếu chỉ xài bf thì hỏi vặn coi lỡ như đề cho không đủ mem thì làm ntn, chẳng hạn
 
Last edited:
C#: 
public class Solution {
    public int MinPatches(int[] nums, int n) {
        int count = 0;
        int index = 0;
        long minMis = 1;
        
        while(minMis <=n){
            if(index < nums.Length && minMis >= nums[index]){
                minMis += nums[index];
                index++;
            }else{
                minMis *=2;
                count++;
            }
        }
        return count;
    }
}
 
_Gia_Cat_Luong_ said:
Gặp bài hard là phải trồi lên

Python: 
class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        expect = 1
        nums.reverse()
        count = 0
       
        while expect <= n:
            if nums and expect >= nums[-1]:
                expect += nums[-1]
                nums.pop()
            else:
                expect *= 2
                count += 1
            # print(expect)
               
        return count
Click to expand...
Bác giải thích giúp em cách tiếp cận bài này được không ạ, em đọc mãi mà không hiểu 😕
 
Python: 
class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        current_range, result = 0, 0
        i, m = 0, len(nums)
        while current_range < n:
            new_range = current_range + 1
            if i < m and nums[i] <= new_range:
                current_range += nums[i]
                i += 1
            else:
                current_range += new_range
                result += 1
        return result
 
phuctienn said:
Bác giải thích giúp em cách tiếp cận bài này được không ạ, em đọc mãi mà không hiểu 😕
Click to expand...
Cũng không biết người khác ra sao, mình tiếp cận theo hướng phân tích các case cơ bản rồi suy ra pattern. Kiểu vầy:
  • Đầu tiên dễ thấy, tổng n = 1 chắc chắn phải được tạo ra từ mảng [1], nếu trong mảng chưa có số 1 thì bắt buộc phải patch vào
  • Tổng n = 2 thì sao ? Vì chắc chắn mảng đã tạo được tổng n = 1 rồi, nên:
    • Nếu mảng có 1 số 1 nữa thì khỏi cần làm gì
    • Nếu mảng chỉ có đúng một số 1 (đã dùng để tạo tổng n = 1 trước đó) thì:
      • Mảng có số 2 không ? Nếu có thì ok
      • Nếu không có thì lại có 2 hướng:
        • Hoặc là patch thêm 1 số 1 vào
        • Hoặc là patch thêm 1 số 2 vào
      • => Chỗ này phân tích thì thấy patch số 2 lợi hơn vì khi đó auto tạo được số 3 luôn (chỗ này quan trọng)
    • Lại nghĩ rộng ra, nếu mình đang tìm tổng bằng số n mà không cách nào tạo được với mảng hiện tại thì best solution là patch đúng số n đó vào
  • Lại suy rộng ra tiếp:
    • Nếu mình patch số n vào, mình sẽ tạo thêm được nhiều tổng khác lớn hơn n chứ không chỉ là tổng = n (từ chỗ in đậm)
    • Ngẫm lại, nếu mình đang xét tới số n, nghĩa là trước đó mình đã xét xong các số từ 1 -> n - 1. Vậy h thêm số n thì chắc chắn sẽ tạo được thêm các tổng từ n -> 2 * n - 1
    • Vậy nếu đang xét số n, mà phải patch, thì sau đó mình xét tiếp số 2 * n luôn (vì có thể skip đoạn n -> 2 * n - 1
  • Ở trên toàn là trường hợp nếu phải patch, vậy nếu không cần patch thì sao ?
    • Dễ thấy, trong case đơn giản, cũng tương tự như trên, nếu đang xét đến số n mà số đó có trong mảng thì auto skip luôn đến số 2*n
  • Nhưng skip vậy thì các số ở trong mảng mà từ n -> 2*n - 1 không dùng nữa à ?
    • Đương nhiên vẫn phải dùng để tối ưu, nếu đang xét đến tổng = n rồi, thì các số trong mảng nhỏ hơn n sẽ không có tác dụng gì trong tương lai nữa
    • Giả sử đang xét đến tổng = n, bây giờ dùng thêm số x vào thì dễ thấy sẽ tạo được thêm các tổng từ n + 1 -> n + x - 1.
    • Hay nói cách khác, nếu đang xét số n mà trong mảng có số x <= n chưa dùng thì dùng luôn và skip đến số n + x
Done, vậy tổng kết các kết luận trên, ta có thuật toán đại loại vầy:
  • Mình sẽ xét các tổng s từ 1 -> n, đến khi s > n thì ngưng
  • Nếu đang xét và thấy trong mảng có số x nhỏ hơn s, thì skip s = s + x. Bỏ số x này ra khỏi mảng
  • Ngược lại, nếu trong mảng có đúng số s => Skip s = 2*s. Bỏ số s này khỏi mảng.
  • Ngược lại, phải patch số s này => Skip s = 2*s. Tăng biến đếm số lượng patch
  • Đến khi s > n thì done => return số lượt patch
 
_Gia_Cat_Luong_ said:
Cũng không biết người khác ra sao, mình tiếp cận theo hướng phân tích các case cơ bản rồi suy ra pattern. Kiểu vầy:
  • Đầu tiên dễ thấy, tổng n = 1 chắc chắn phải được tạo ra từ mảng [1], nếu trong mảng chưa có số 1 thì bắt buộc phải patch vào
  • Tổng n = 2 thì sao ? Vì chắc chắn mảng đã tạo được tổng n = 1 rồi, nên:
    • Nếu mảng có 1 số 1 nữa thì khỏi cần làm gì
    • Nếu mảng chỉ có đúng một số 1 (đã dùng để tạo tổng n = 1 trước đó) thì:
      • Mảng có số 2 không ? Nếu có thì ok
      • Nếu không có thì lại có 2 hướng:
        • Hoặc là patch thêm 1 số 1 vào
        • Hoặc là patch thêm 1 số 2 vào
      • => Chỗ này phân tích thì thấy patch số 2 lợi hơn vì khi đó auto tạo được số 3 luôn (chỗ này quan trọng)
    • Lại nghĩ rộng ra, nếu mình đang tìm tổng bằng số n mà không cách nào tạo được với mảng hiện tại thì best solution là patch đúng số n đó vào
  • Lại suy rộng ra tiếp:
    • Nếu mình patch số n vào, mình sẽ tạo thêm được nhiều tổng khác lớn hơn n chứ không chỉ là tổng = n (từ chỗ in đậm)
    • Ngẫm lại, nếu mình đang xét tới số n, nghĩa là trước đó mình đã xét xong các số từ 1 -> n - 1. Vậy h thêm số n thì chắc chắn sẽ tạo được thêm các tổng từ n -> 2 * n - 1
    • Vậy nếu đang xét số n, mà phải patch, thì sau đó mình xét tiếp số 2 * n luôn (vì có thể skip đoạn n -> 2 * n - 1
  • Ở trên toàn là trường hợp nếu phải patch, vậy nếu không cần patchthì sao ?
    • Dễ thấy, trong case đơn giản, cũng tương tự như trên, nếu đang xét đến số n mà số đó có trong mảng thì auto skip luôn đến số 2*n
  • Nhưng skip vậy thì các số ở trong mảng mà từ n -> 2*n - 1không dùng nữa à ?
    • Đương nhiên vẫn phải dùng để tối ưu, nếu đang xét đến tổng = n rồi, thì các số trong mảng nhỏ hơn n sẽ không có tác dụng gì trong tương lai nữa
    • Giả sử đang xét đến tổng = n, bây giờ dùng thêm số x vào thì dễ thấy sẽ tạo được thêm các tổng từ n + 1 -> n + x - 1.
    • Hay nói cách khác, nếu đang xét số n mà trong mảng có số x <= n chưa dùng thì dùng luôn và skip đến số n + x
Done, vậy tổng kết các kết luận trên, ta có thuật toán đại loại vầy:
  • Mình sẽ xét các tổng s từ 1 -> n, đến khi s > n thì ngưng
  • Nếu đang xét và thấy trong mảng có số x nhỏ hơn s, thì skip s = s + x. Bỏ số x này ra khỏi mảng
  • Ngược lại, nếu trong mảng có đúng số s => Skip s = 2*s. Bỏ số s này khỏi mảng.
  • Ngược lại, phải patch số s này => Skip s = 2*s. Tăng biến đếm số lượng patch
  • Đến khi s > n thì done => return số lượt patch
Click to expand...
Đội ơn bác 🙏 , em đọc giải trên leetcode mãi k hiểu.
 
Diệp Vô Ưu said:
leetcode toàn bài dynamic programing với BFS DFS thế nhỉ
mù màu quá
Click to expand...
là do những thuật toán này giúp giải bài toán với performence tốt đó chứ, có phải ngta cố tình ra đề để xài dp, bfs, dfs đâu
zFNuZTA.png
 
làm sao để bản thân toxic hơn 🤔


khó quá thì copy solution thôi

Code: 
impl Solution {
    pub fn min_patches(nums: Vec<i32>, n: i32) -> i32 {
        let mut missing = 1i64;
        let mut count = 0;
        let mut i = 0;

        while missing <= n as i64 {
            if i < nums.len() && nums[i] as i64 <= missing {
                missing += nums[i] as i64;
                i += 1;
            } else {
                missing += missing;
                count += 1;
            }
        }

        count
    }
}

edit: làm bài #1789 trước dễ thấy pattern hơn
 
Last edited:

Similar threads

Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
595
heocon0123
heocon0123
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
143
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
15
Views
394
truonggiang!
T
@_shin
kiến thức PIXELVERSE kèo hot - inbox tele để lấy extension chạy auto đánh boss
Replies
0
Views
115
@_shin
@_shin
D
kiến thức Lộ trình tự học phát triển Website Fullstack - Fullstack Web Development
Replies
15
Views
2K
HarryNam
HarryNam

Share this page

Back
Top