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

Bài LC hôm nay t sử dụng map hoặc set trong C++. Khác với ngôn ngữ khác thì map, set trong C++ nó đã được sorted by key rồi (do được implement bằng red black tree) nên dễ xử lý hơn :big_smile:
Cách 1 dùng set: ý tưởng là lưu hết toàn bộ phần tử vào trong set rồi loop hết cái set và tính số lượng phần tử liên tiếp dài nhất.
C++: 
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> mySet(nums.begin(), nums.end());
        int ret = 0;
        int prev = INT_MIN;
        int curLen = 0;
        for (auto x : mySet){
            if (x == prev + 1) curLen++;
            else curLen = 1;
            ret = max(ret, curLen);
            prev = x;
        }
        return ret;
    }
};
Cách 2 dùng map: có dạng start -> end. Sau đó thêm từng phần tử vào, khi thêm vào thì cần xử lý thêm điều kiện để join các đoạn start->end lại với nhau nữa. Cách này xử lý khó hơn cách dùng set nhưng đỡ tốn memory hơn.
C++: 
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        map<int, int> startToEnd;
        for (auto x : nums) {
            auto it = startToEnd.upper_bound(x);
            if (it != startToEnd.end() && it != startToEnd.begin()
                && prev(it)->second == x && it->first == x + 1) {
                prev(it)->second = it->second;
                startToEnd.erase(it);
            } else if (it != startToEnd.end() && it->first == x + 1) {
                startToEnd[x] = it->second;
                startToEnd.erase(it);
            } else if (it != startToEnd.begin() && prev(it)->second == x) {
                prev(it)->second++;
            } else if (it == startToEnd.begin() || prev(it)->second < x) {
                startToEnd[x] = x+1;
            }
        }
     
        int ret = 0;
        for (auto x : startToEnd){
            ret = max(ret, x.second - x.first);
        }
        return ret;
    }
};
2 cách này đều có TC là O(NlogN).

Edit:
Cách 3 dùng unordered_map: lưu hết toàn bộ nums vào unordered_map, loop hết cái unordered_map rồi visit các phần tử liên tiếp nhau tương ứng để tính kết quả.
C++: 
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, bool> visited;
        for (auto x : nums) visited[x] = false;
        int ret = 0;
        for (auto x : visited){
            if (x.second) continue;
            int e = x.first;
            int curLen = 1;
            while (visited.find(e+1) != visited.end() && !visited[e+1]){
                visited[e+1] = true;
                e++;
                curLen++;
            }
            e = x.first;
            while (visited.find(e-1) != visited.end() && !visited[e-1]){
                visited[e-1] = true;
                e--;
                curLen++;
            }
            visited[e]=true;
            ret = max(ret, curLen);
        }
        return ret;
    }
};
Cách này TC là O(n). Nhưng do input chưa đủ lớn nên khác biệt về tgian chạy so với 2 cách trên là k thấy được. :beat_brick: :beat_brick:
 
Last edited:
ngoctan_95 said:
Bài này quen nên solution của em là Brute force cơ bản + phân tích kiểu dây chun để lấy On:
  • Sort array, streak và maxStreak nên là 1 (dù cỡ nào cũng min là 1, nếu arr empty thì res là 0)
  • Xét từ 1 -> length - 1, kiểm tra x != x[i-1] và x = x[i-1] + 1 hay không, nếu có thì streak tăng 1, còn không thì so sánh Max giữa streak và maxStreak , streak sẽ quay về 1, tương tự xét vòng mảng mới while-xx
    [*]Kết quả sẽ là 1 lần nữa so sánh Max streak và maxStreak


Java: 
public int longestConsecutive(int[] nums) {
        int length = nums.length;
        Arrays.sort(nums);
        if (length == 0) {
            return 0;
        }
        int streak = 1, maxStreak = 1;
        for (int i = 1; i < length; i++) {
            if (nums[i] != nums[i-1]) {
                if (nums[i -1] +1 == nums[i]) {
                    streak += 1;
                } else {
                    maxStreak = Math.max(maxStreak, streak);
                    streak = 1;
                }
            } else {
                    continue;
            }
        }

        return Math.max(maxStreak, streak);
    }
Click to expand...
Đề bài yêu cầu O(n) mà thím
 
Blue Amethyst said:
Bài này giống bài của bác Fire of Heart, constraint không gắt bằng thôi :beauty:

Solution 1:
Time complexity: O(nlogn)
Space complexity: O(1)
  • Sort mảng, sau đó so sánh phần tử hiện tại với phần tử kế tiếp.
  • Với hai phần tử:
- Nếu liền nhau => tiếp tục so sánh theo cặp
- Nếu bằng nhau => tăng vị trí của phần tử kế tiếp lên một đơn vị
- Nếu không bằng => break

Vì con trỏ đến phần tử kế tiếp đã được process nên không cần thiết phải process lại lần nữa, cuối vòng lặp sẽ trỏ con trỏ hiện tại tới con trỏ phần tử kế
Java: 
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length <= 1)
            return nums.length;
        Arrays.sort(nums);
        int max = 1;
        int curPos = 0;
        while (curPos < nums.length)
        {
            int nextPos = curPos + 1;
            int count = 1;
            int curVal = nums[curPos];
            while (nextPos < nums.length)
            {
                if (nums[nextPos] - 1 == curVal)
                {
                    curVal = nums[nextPos];
                    ++count;
                    ++nextPos;
                }
                else if (nums[nextPos] == curVal)
                    ++nextPos;
                else
                    break;
            }
            curPos = nextPos;
            max = Math.max(max, count);
        }
        return max;
    }
}


Solution 2:
Time complexity: O(n)
Space complexity: O(n)
  • Tạo một cái set để add hết tất cả phần tử unique vào set
  • Process từng phần tử trong mảng ban đầu:
- Nếu tồn tại trong set:
- Tạo một biến tạm bằng phần tử hiện tại rồi tăng dần + giảm dần, tổng số phần tử thu được là tổng của hiệu số phần tử - biến tạm (đối với giảm dần) và hiệu số biến tạm - phần tử (đối với tăng dần)
- Với mỗi phần tử tăng/giảm, nếu thỏa mãn, loại khỏi set ban đầu
- Nếu không tồn tại, bỏ qua

Vì phần tử thỏa mãn đã được loại nên không cần phải process đối với phần tử trùng lặp
Java: 
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length <= 1)
            return nums.length;
        Set<Integer> set = new HashSet<>();
        for (int num : nums)
        {
            set.add(num);
        }
 
        int max = 1;
        for (int num : nums)
        {
            if (set.contains(num))
            {
                set.remove(num);
                int cur = num;
                while (set.remove(cur - 1))
                {
                    --cur;
                }
                int count = num - cur;
         
                cur = num;
                while (set.remove(cur + 1))
                {
                    ++cur;
                }
                count += cur - num;
                max = Math.max(count + 1, max);
            }
        }
 
        return max;
    }
}

Vậy mà thời gian chạy của cách 1 toàn nhanh hơn cách 2:beat_brick:
Click to expand...

Lượng thời gian là tổng thời gian của các test case đó. Nên có mấy cái số lượng element nó nhỏ thì built-in sort tối ưu

Mà ở dưới cũng sử dụng kha khá các operations của set nên cũng ngốn thời gian
trinity said:
bài LCS này cần O(n) nên nghĩ đến sử dụng radix sort
C++: 
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
    
        for (int &d : nums) {
            d += 1000000000; // nums[i] in [0...2e9]
        }
    
        vector<vector<int>> buckets(10, vector<int>()); // 10 buckets for sorting [0...9]
        long d1 = 10, d2 = 1;
        for (int i = 0; i < 10; i++) {
            for (int &d : nums) {
                buckets[(d % d1) / d2].push_back(d);
            }
        
            int j = 0;
            for (auto &bucket : buckets) {
                for (int &d : bucket) {
                    nums[j++] = d;
                }
                bucket.clear();
            }
        
            d1 *= 10;
            d2 *= 10;
        }
    
        int ans = 0;
        int c = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1] + 1) {
                c++;
            } else if (nums[i] == nums[i - 1]) {
                continue;
            } else {
                ans = max(ans, c + 1);
                c = 0;
            }
        }
    
        ans = max(ans, c + 1);
    
        return ans;
    }
};
trong related topic có union find nên em cài đặt thử
C++: 
class Solution {
public:
    inline int findParent(vector<int> &p, int i) {
        while (p[i] != -1) {
            i = p[i];
        }
        return i;
    }
 
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> m;
        vector<int> l(nums.size(), 1), p(nums.size(), -1); // l[i] is length of CS from nums[i], p[i] is index of parent of index i
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (m.find(nums[i]) == m.end()) {
                m[nums[i]] = i;
                l[i] = 1;
            
                if (m.find(nums[i] + 1) != m.end()) {
                    p[m[nums[i] + 1]] = i;
                    l[i] += l[m[nums[i] + 1]];
                }
            
                ans = max(ans, l[i]);
            
                if (m.find(nums[i] - 1) != m.end()) {
                    int p0 = findParent(p, m[nums[i] - 1]);
                    p[i] = p0;
                    l[p0] += l[i];
                    ans = max(ans, l[p0]);
                }
            }
        }
    
        return ans;
    }
};
Click to expand...
radix sort là O(N) vậy thím làm được mọi bài cần sort mà chỉ cần O(N) với radix sort à, thế ảo quá nhỉ :sad:
 
Lập Trình Viên Số Khổ said:
Lượng thời gian là tổng thời gian của các test case đó. Nên có mấy cái số lượng element nó nhỏ thì built-in sort tối ưu

Mà ở dưới cũng sử dụng kha khá các operations của set nên cũng ngốn thời gian

radix sort là O(N) vậy thím làm được mọi bài cần sort mà chỉ cần O(N) với radix sort à, thế ảo quá nhỉ :sad:
Click to expand...

Radix/Counting sort cần O(n) space nên nếu mảng quá lớn thì sẽ ko hiệu quả bằng quicksort O(1) space.
 
tdat00 said:
Radix/Counting sort cần O(n) space nên nếu mảng quá lớn thì sẽ ko hiệu quả bằng quicksort O(1) space.
Click to expand...
Hầu hết các sort ngon ngon đều là O(N) còn space của radix là O(N+K) với K là số lượng digits, thì với max của phần tử trong dãy giới hạn 10^18 sẽ có SC là O(N + 18). Thêm có 18, quá ngon rồi bác, hay em sai gì nhỉ @@

1656992817818.png
 
Lập Trình Viên Số Khổ said:
Hầu hết các sort ngon ngon đều là O(N) còn space của radix là O(N+K) với K là số lượng digits, thì với max của phần tử trong dãy giới hạn 10^18 sẽ có SC là O(N + 18). Thêm có 18, quá ngon rồi bác, hay em sai gì nhỉ @@

View attachment 1247386
Click to expand...
Radix và Counting sort chỉ cho non negative integers thôi bác, còn các loại khác là general
 
Lập Trình Viên Số Khổ said:
Lượng thời gian là tổng thời gian của các test case đó. Nên có mấy cái số lượng element nó nhỏ thì built-in sort tối ưu

Mà ở dưới cũng sử dụng kha khá các operations của set nên cũng ngốn thời gian

radix sort là O(N) vậy thím làm được mọi bài cần sort mà chỉ cần O(N) với radix sort à, thế ảo quá nhỉ :sad:
Click to expand...
O(n) < O(nlogn) chỉ đúng khi n đủ lớn. Và trong case sort này thì n đủ lớn chắc phải tầm 10^9 trở lên. Ít khi nào có test case được to vậy, nên dùng radix sort thì chỉ để ăn gian O(n) lý thuyết thôi chứ runtime hầu như là chậm hơn built-in sort.
 
Hỏi thật các bác học thuật toán đã kiếm được việc ngon chưa? Em làm hơn 400 bài leetcode, hơn 500 bài các trang khác mà đi phỏng vấn chả ai hỏi.
Có hỏi cũng toàn lý thuyết.
 
longvatrong111 said:
Hỏi thật các bác học thuật toán đã kiếm được việc ngon chưa? Em làm hơn 400 bài leetcode, hơn 500 bài các trang khác mà đi phỏng vấn chả ai hỏi.
Có hỏi cũng toàn lý thuyết.
Click to expand...
Việc ngon thì đầy rồi. Nhưng không phải nhờ thuật toán hay cày LC.

Thuật toán chỉ là bước screening, đánh giá đầu vào thôi. Chiếm không đến 30% kết quả phỏng vấn chung. Nó là điều kiện cần chứ không phải là điều kiện đủ.

Để hôm nào rảnh tạo thêm topic cho ae bàn về phỏng vấn. Interviewer care cái gì, với mỗi level thì mình cần tập trung phần nào.
 
longvatrong111 said:
Hỏi thật các bác học thuật toán đã kiếm được việc ngon chưa? Em làm hơn 400 bài leetcode, hơn 500 bài các trang khác mà đi phỏng vấn chả ai hỏi.
Có hỏi cũng toàn lý thuyết.
Click to expand...

3 công ty gần nhất tôi làm đều bắt làm codility/hackerrank ở round đầu tiên. Đề cũng tầm medium thôi không quá khó đâu (tiên sư thằng codility giấu test cases chứ không trưng ra hết như leetcode/hackerrank).

Thường thì chỉ cần pass 60% các tests, hoặc ngồi code đến hết giờ không bỏ ngang giữa chừng là công ty mời pv vòng 2 :shame:
 
longvatrong111 said:
Hỏi thật các bác học thuật toán đã kiếm được việc ngon chưa? Em làm hơn 400 bài leetcode, hơn 500 bài các trang khác mà đi phỏng vấn chả ai hỏi.
Có hỏi cũng toàn lý thuyết.
Click to expand...

Bác làm 400 bài Leetcode. Vậy chắc qua Google làm được rồi còn gì.
 
longvatrong111 said:
Hỏi thật các bác học thuật toán đã kiếm được việc ngon chưa? Em làm hơn 400 bài leetcode, hơn 500 bài các trang khác mà đi phỏng vấn chả ai hỏi.
Có hỏi cũng toàn lý thuyết.
Click to expand...
Cũng có thể là do bạn apply chưa đúng chỗ. K phải chỗ nào cũng yêu cầu phải strong về DSA. Nên lần sau apply vào đâu thì nhớ đọc kỹ JD.
 
_Gia_Cat_Luong_ said:
Việc ngon thì đầy rồi. Nhưng không phải nhờ thuật toán hay cày LC.

Thuật toán chỉ là bước screening, đánh giá đầu vào thôi. Chiếm không đến 30% kết quả phỏng vấn chung. Nó là điều kiện cần chứ không phải là điều kiện đủ.

Để hôm nào rảnh tạo thêm topic cho ae bàn về phỏng vấn. Interviewer care cái gì, với mỗi level thì mình cần tập trung phần nà
Click to expand...
30% thì nhiều quá, mình thấy đếm trên đầu ngón tay các công ty có 1 vòng thuật toán.

Như big tech thì là 50% đến 75% vòng cuối, trước đấy có 1 vòng nữa cũng thuật toán. Tất cả để kiểm tra tư duy của 1 engineer
 
Last edited:

Similar threads

4 More Years
Nhiều người mất sạch bài đăng trên Facebook
Replies
0
Views
192
4 More Years
4 More Years
4 More Years
Elon Musk có kế hoạch tính phí người dùng X mới để cho phép đăng bài
2 3
Replies
48
Views
3K
bimatcuasoi5
bimatcuasoi5
Lenh Ho Dai Ca
Giám đốc Nhã Nam xin lỗi
2 3 4
Replies
68
Views
8K
clonebymeeeee
clonebymeeeee
buiduchanh1995
thắc mắc Cách thiết kế database cho hệ thống lớn
2
Replies
37
Views
3K
khonganhit19
khonganhit19
meekoo
thắc mắc [Hỏi AI] Cách làm sao để train AI hiểu một task nào đấy?
Replies
9
Views
1K
weed_bông
weed_bông

Share this page

Back
Top