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

  • Người tạo chủ đề Người tạo chủ đề unknowpc90
  • Ngày bắt đầu Ngày bắt đầu
uytuhgdfr đã nói:
VN mình nhiều người giỏi vãi. Mà sao không vượt biên được nhỉ. Toàn trình Hard thế này.
Nhấp để mở rộng...
Cần nhiều điều kiện khác như :
Tiếng Anh giao tiếp level IELTS 7.0
+ với kinh nghiệm làm việc thực tế nữa
Thực tế nhất là lên Streetjob kiếm việc ở công ty làng nhàng bên Sing rồi đi Sing trước
Sang Sing rồi mới nộp đơn xin việc FAANG chi nhánh bên đó
Muốn phiêu lưu ở nước ngoài trong thời gian thử việc thì trong người anh cũng phải có tối thiểu 200 củ đề phòng bất trắc :(

Chưa kể Việt Nam hay dân da vàng Đông Á thường bị bệnh sợ Tây, đi phượt nước ngoài ở guesthouse rẻ tiền cùng với lũ Tây có duy nhất tôi người bé như con nhái bén, 1m65 nặng 60 ký bụng 0 múi ra bể bơi chơi bóng bia với chúng nó :( Loài người bình đẳng với nhau, sợ đéo gì nhưng bọn Hàn, Tàu, Nhật cũng đéo dám ra chơi :censored:
 
Sửa lần cuối:
Buonnguqua6 đã nói:
Cần nhiều điều kiện khác như :
Tiếng Anh giao tiếp level IELTS 7.0
+ với kinh nghiệm làm việc thực tế nữa
Thực tế nhất là lên Streetjob kiếm việc ở công ty làng nhàng bên Sing rồi đi Sing trước
Sang Sing rồi mới nộp đơn xin việc FAANG chi nhánh bên đó
Muốn phiêu lưu ở nước ngoài trong thời gian thử việc thì trong người anh cũng phải có tối thiểu 200 củ đề phòng bất trắc :(

Chưa kể Việt Nam hay dân da vàng Đông Á thường bị bệnh sợ Tây, đi phượt nước ngoài ở guesthouse rẻ tiền cùng với lũ Tây có duy nhất tôi người bé như con nhái bén 1m65 nặng 60 ký bụng 0 múi ra bể bơi chơi bóng bia với chúng nó :(
Nhấp để mở rộng...
Học thuật toán đến tầm nào thì đủ trình vào FAANG bác? Có case nào ra trường VN phát apply vào FAANG thực tập luôn chưa ạ? Để em phấn đấu :shame:
 
Yêu em Thu Nga CN12 ptit đã nói:
Học thuật toán đến tầm nào thì đủ trình vào FAANG bác? Có case nào ra trường VN phát apply vào FAANG thực tập luôn chưa ạ? Để em phấn đấu :shame:
Nhấp để mở rộng...
FAANG thì anh cứ làm hết Hard Leetcode tầm 45p 1 bài. Có IELTS 7.0 và có 200 củ đi sang Sing ở trọ mấy tháng :rolleyes:

Hoặc anh chăm đi thi Contest như anh này thì FAANG cũng gọi anh đi thực tập
https://youtube.com/c/WilliamLin168
 
Sửa lần cuối:
uytuhgdfr đã nói:
VN mình nhiều người giỏi vãi. Mà sao không vượt biên được nhỉ. Toàn trình Hard thế này.
Nhấp để mở rộng...

KimSoHyunGoddness đã nói:
Đâu phải giỏi thuật toán, trình cao là qua bên Sing, Mỹ hoặc G7 đâu.
Còn tiếng anh, tiền bạc đi kèm nữa chứ.
Nhấp để mở rộng...
T làm mấy bài hard còn chậm lắm. Tự cảm thấy trình độ bản thân vẫn còn bình thường.
Ngoài thuật toán ra thì còn cần nhiều yếu tố khác nữa. Hơn nữa không phải ai cũng đều có chung mục tiêu vào FAANG khi luyện thuật toán.
 
Yêu em Thu Nga CN12 ptit đã nói:
Học thuật toán đến tầm nào thì đủ trình vào FAANG bác? Có case nào ra trường VN phát apply vào FAANG thực tập luôn chưa ạ? Để em phấn đấu :shame:
Nhấp để mở rộng...
Có nha bác. Nhưng cũng thuộc dạng chuyên tin có nền thuật toán sẵn, có giải acm đồ và cũng fail này nọ chứ ko phải làm phát ăn ngay.
Thuật toán thì bác cứ giải gọn đc medium trong tầm 25’ (bao gồm các bước như lúc pv) rồi hẳn tính tới chuyện giải hard.
Mình nghĩ thuật toán cũng chỉ là một phần, một phần khó khăn với người Việt mình là phải giao tiếp và giải thích được suy nghĩ của mình bằng tiếng Anh một cách dễ hiểu và logic nữa


via theNEXTvoz for iPhone
 
Yêu em Thu Nga CN12 ptit đã nói:
Học thuật toán đến tầm nào thì đủ trình vào FAANG bác? Có case nào ra trường VN phát apply vào FAANG thực tập luôn chưa ạ? Để em phấn đấu :shame:
Nhấp để mở rộng...
vào FAANG thì chắc vào chung kết GCJ hay HackerCup rồi tính tiếp
hB8nmx5.png
 
thuyduong2007 đã nói:
T làm mấy bài hard còn chậm lắm. Tự cảm thấy trình độ bản thân vẫn còn bình thường.
Ngoài thuật toán ra thì còn cần nhiều yếu tố khác nữa. Hơn nữa không phải ai cũng đều có chung mục tiêu vào FAANG khi luyện thuật toán.
Nhấp để mở rộng...
Bác lại khiêm tốn rồi. Qua FAANG thì khó chứ qua các nước như Nhật, Hàn, Trung thì dễ hơn không bác. Trình Hard thì đi làm ở đâu chẳng được.
 
Mấy thím cho em hỏi em đang dùng hàm hash trong thư viện hashlib của python để lưu mật khẩu, thế mai mốt python nó ra bản mới hoặc ra python 4 các kiểu thì hàm hash trong thư viện hashlib của nó còn trả về kết quả giống hiện tại ko ạ?
 
uytuhgdfr đã nói:
Bác lại khiêm tốn rồi. Qua FAANG thì khó chứ qua các nước như Nhật, Hàn, Trung thì dễ hơn không bác. Trình Hard thì đi làm ở đâu chẳng được.
Nhấp để mở rộng...
Anh bị dở à
Nhật Hàn Trung nhiều thằng làm hãng nó còn éo nói thạo tiếng Anh, level nói tiếng Anh bập bõm
Tuyển dev Việt Nam qua làm gì, qua để giao tiếp bằng tay chân à :LOL:
Vào topic Việc tìm người của box này mà xem, có mấy anh Tàu bên Campuchia làm gambling online tuyển dụng dev lương khá ngon nhưng đòi biết giao tiếp tiếng Tàu, và tuyển mãi éo có ứng viên Apply
cVL81H2.gif
 
Sửa lần cuối:
Nay cuối tuần ngồi làm mấy bài hard chơi. Thấy bài này khá hay nên share lại cho ae cách giải quyết của mình.
https://leetcode.com/problems/trapping-rain-water-ii/
Input là một matrix chiều cao của các khối. Yêu cầu ouput ra lượng nước mà khối này có thể chứa đc. Ae coi hình bên dưới để hiểu rõ.
trap1-3d.jpg

Ý tưởng ban đầu của mình là dùng cách xử lý giống như morphology trong image processing. Đó là dùng 1 cái kernel để chọn những khối cạnh bên. rồi scan toàn bộ khối này cho đến khi khi không có sự thay đổi về lượng nước chứa được nữa thì dừng lại. Cách này độ phức tạp là O(m*m*n*n). Mặc dù có độ phức tạp cao nhưng cách tiếp cận này mình thấy có thể code nhanh được.

C++: 
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        vector<vector<int>> waterMap(heightMap.size(), vector<int>(heightMap[0].size(), 0));
        for (int i = 1; i < heightMap.size() - 1; i++) {
            for (int j = 1; j < heightMap[0].size() - 1; j++) {
                array<int, 3> neighbours = {heightMap[i][j-1] + waterMap[i][j-1],
                                            heightMap[i][j],
                                            heightMap[i-1][j] + waterMap[i-1][j]};
                waterMap[i][j] = *max_element(neighbours.begin(), neighbours.end()) - heightMap[i][j];
            }   
        }
        bool run = true;
        while(run) {
            run = false;
            for (int i = 1; i < heightMap.size() - 1; i++) {
                for (int j = 1; j < heightMap[0].size() - 1; j++) {
                    array<int, 4> neighbourHeight = {heightMap[i][j+1] + waterMap[i][j+1],
                                                   heightMap[i][j-1] + waterMap[i][j-1],
                                                   heightMap[i+1][j] + waterMap[i+1][j],
                                                   heightMap[i-1][j] + waterMap[i-1][j]};
                    int minHeight = *min_element(neighbourHeight.begin(),
                                                 neighbourHeight.end());
                    int newWater = minHeight > heightMap[i][j] ?
                        minHeight - heightMap[i][j] : 0;
                    run = newWater != waterMap[i][j] ? true : run;
                    waterMap[i][j] = newWater;
                }   
            }
        }
        int result = 0;
        for (auto row : waterMap) {
            for (auto cell : row) {
                result += cell;
            }
        }
        return result;
    }
};

Mặc dù pass được nhưng solution chạy rất chậm :beat_brick:. Mình có tham khảo thì bài này nên dùng bfs kết hợp với minHeap thì độ phức tạp chỉ còn O(m*n). Anh em nào có hứng thú thì có thể coi visualization ở dưới và code lại.
Còn dưới đây là code của mình lấy ý tưởng từ video phía trên :D
C++: 
struct cell{
    cell (int _x, int _y, int _val){
        x = _x;
        y = _y;
        val = _val;
    }
    int x;
    int y;
    int val;
};


bool operator < (const cell &o1, const cell &o2) {
        return o1.val > o2.val;
}

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.size() <= 2 || heightMap[0].size() <= 2) return 0;
        
        vector<vector<bool>> visited(heightMap.size(), vector<bool>(heightMap[0].size(), false));
        priority_queue<cell> minHeap;
        
        // add all cell in boundary into heap
        for (int j = 0; j < heightMap[0].size(); j++){
            minHeap.emplace(0,j,heightMap[0][j]);
            minHeap.emplace(heightMap.size() - 1,j,heightMap.back()[j]);
            visited[0][j] = true;
            visited[heightMap.size() - 1][j] = true;
        }
        for (int i = 1; i < heightMap.size() - 1; i++){
            minHeap.emplace(i,0,heightMap[i][0]);
            minHeap.emplace(i,heightMap[0].size() - 1,heightMap[i].back());
            visited[i][0] = true;
            visited[i][heightMap[0].size() - 1] = true;
        }
        
        
        array<pair<int, int>, 4> offsets = {make_pair(0,-1), make_pair(0,1),
                                            make_pair(-1,0), make_pair(1,0)};
        int curMax = -1;
        int result = 0;
        //bfs
        while (!minHeap.empty()) {
            auto top = minHeap.top();
            curMax = curMax > top.val ? curMax : top.val;
            minHeap.pop();
            for (auto off : offsets){
                int next_x = top.x + off.first;
                int next_y = top.y + off.second;
                if (next_x>=0 && next_x<heightMap.size()
                    && next_y>=0 && next_y<heightMap[0].size()
                    && !visited[next_x][next_y]) {
                    visited[next_x][next_y] = true;
                    if (heightMap[next_x][next_y] < curMax) {
                        result += curMax - heightMap[next_x][next_y];
                        minHeap.emplace(next_x, next_y, curMax);
                    } else{
                        minHeap.emplace(next_x, next_y, heightMap[next_x][next_y]);
                    }
                }
            }
        }
        return result;
    }
};
 
thuyduong2007 đã nói:
Nay cuối tuần ngồi làm mấy bài hard chơi. Thấy bài này khá hay nên share lại cho ae cách giải quyết của mình.
https://leetcode.com/problems/trapping-rain-water-ii/
Input là một matrix chiều cao của các khối. Yêu cầu ouput ra lượng nước mà khối này có thể chứa đc. Ae coi hình bên dưới để hiểu rõ.
trap1-3d.jpg

Ý tưởng ban đầu của mình là dùng cách xử lý giống như morphology trong image processing. Đó là dùng 1 cái kernel để chọn những khối cạnh bên. rồi scan toàn bộ khối này cho đến khi khi không có sự thay đổi về lượng nước chứa được nữa thì dừng lại. Cách này độ phức tạp là O(m*m*n*n). Mặc dù có độ phức tạp cao nhưng cách tiếp cận này mình thấy có thể code nhanh được.

C++: 
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        vector<vector<int>> waterMap(heightMap.size(), vector<int>(heightMap[0].size(), 0));
        for (int i = 1; i < heightMap.size() - 1; i++) {
            for (int j = 1; j < heightMap[0].size() - 1; j++) {
                array<int, 3> neighbours = {heightMap[i][j-1] + waterMap[i][j-1],
                                            heightMap[i][j],
                                            heightMap[i-1][j] + waterMap[i-1][j]};
                waterMap[i][j] = *max_element(neighbours.begin(), neighbours.end()) - heightMap[i][j];
            }  
        }
        bool run = true;
        while(run) {
            run = false;
            for (int i = 1; i < heightMap.size() - 1; i++) {
                for (int j = 1; j < heightMap[0].size() - 1; j++) {
                    array<int, 4> neighbourHeight = {heightMap[i][j+1] + waterMap[i][j+1],
                                                   heightMap[i][j-1] + waterMap[i][j-1],
                                                   heightMap[i+1][j] + waterMap[i+1][j],
                                                   heightMap[i-1][j] + waterMap[i-1][j]};
                    int minHeight = *min_element(neighbourHeight.begin(),
                                                 neighbourHeight.end());
                    int newWater = minHeight > heightMap[i][j] ?
                        minHeight - heightMap[i][j] : 0;
                    run = newWater != waterMap[i][j] ? true : run;
                    waterMap[i][j] = newWater;
                }  
            }
        }
        int result = 0;
        for (auto row : waterMap) {
            for (auto cell : row) {
                result += cell;
            }
        }
        return result;
    }
};

Mặc dù pass được nhưng solution chạy rất chậm :beat_brick:. Mình có tham khảo thì bài này nên dùng bfs kết hợp với minHeap thì độ phức tạp chỉ còn O(m*n). Anh em nào có hứng thú thì có thể coi visualization ở dưới và code lại.
Còn dưới đây là code của mình lấy ý tưởng từ video phía trên :D
C++: 
struct cell{
    cell (int _x, int _y, int _val){
        x = _x;
        y = _y;
        val = _val;
    }
    int x;
    int y;
    int val;
};


bool operator < (const cell &o1, const cell &o2) {
        return o1.val > o2.val;
}

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.size() <= 2 || heightMap[0].size() <= 2) return 0;
       
        vector<vector<bool>> visited(heightMap.size(), vector<bool>(heightMap[0].size(), false));
        priority_queue<cell> minHeap;
       
        // add all cell in boundary into heap
        for (int j = 0; j < heightMap[0].size(); j++){
            minHeap.emplace(0,j,heightMap[0][j]);
            minHeap.emplace(heightMap.size() - 1,j,heightMap.back()[j]);
            visited[0][j] = true;
            visited[heightMap.size() - 1][j] = true;
        }
        for (int i = 1; i < heightMap.size() - 1; i++){
            minHeap.emplace(i,0,heightMap[i][0]);
            minHeap.emplace(i,heightMap[0].size() - 1,heightMap[i].back());
            visited[i][0] = true;
            visited[i][heightMap[0].size() - 1] = true;
        }
       
       
        array<pair<int, int>, 4> offsets = {make_pair(0,-1), make_pair(0,1),
                                            make_pair(-1,0), make_pair(1,0)};
        int curMax = -1;
        int result = 0;
        //bfs
        while (!minHeap.empty()) {
            auto top = minHeap.top();
            curMax = curMax > top.val ? curMax : top.val;
            minHeap.pop();
            for (auto off : offsets){
                int next_x = top.x + off.first;
                int next_y = top.y + off.second;
                if (next_x>=0 && next_x<heightMap.size()
                    && next_y>=0 && next_y<heightMap[0].size()
                    && !visited[next_x][next_y]) {
                    visited[next_x][next_y] = true;
                    if (heightMap[next_x][next_y] < curMax) {
                        result += curMax - heightMap[next_x][next_y];
                        minHeap.emplace(next_x, next_y, curMax);
                    } else{
                        minHeap.emplace(next_x, next_y, heightMap[next_x][next_y]);
                    }
                }
            }
        }
        return result;
    }
};
Nhấp để mở rộng...
có heap thì thêm cái log mới đúng, đpt là O(mnlog(mn)), cái này cũng có thể giải dùng Dijkstra, đpt tương tự. ý tưởng là với mỗi ô ở trong, tìm đường để nước chảy ra biên.

C++: 
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#define pb push_back
#define rep(i,a,b) for (int i = (a);i<(b);i++)
 
using namespace std;
 
typedef long long ll;
 
const int maxh = 1e6 + 3;
const int maxn = 1e3 + 3;
 
struct TCell
{
    int x,y,val;
    TCell() : x(0),y(0),val(0) {};
    TCell(int x_,int y_,int val_) : x(x_),y(y_),val(val_) {};
};
 
struct cmp
{
    bool operator() (const TCell &a,const TCell &b)
    {
        return a.val > b.val;
    }
};
 
int a[maxn][maxn],h[maxn][maxn];
priority_queue<TCell,vector<TCell>,cmp> q;
int m,n;
 
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
 
bool inside(int x,int y)
{
    return !(x == m || y == n || x == 0-1 || y == 0-1);
}
 
void dijkstra()
{
    rep(i,0,m) rep(j,0,n) h[i][j] = maxh;
    rep(i,0,m)
    {
        h[i][0] = a[i][0];
        h[i][n-1] = a[i][n-1];
        q.push(TCell(i,0,h[i][0]));
        q.push(TCell(i,n-1,h[i][n-1]));
    }
    rep(i,1,n-1)
    {
        h[0][i] = a[0][i];
        h[m-1][i] = a[m-1][i];
        q.push(TCell(0,i,a[0][i]));
        q.push(TCell(m-1,i,a[m-1][i]));
    }
    while (! q.empty())
    {
        int x = q.top().x;
        int y = q.top().y;
        int d = q.top().val;
        q.pop();
        if (h[x][y] != d) continue;
        rep(i,0,4)
        {
            int xk = x+dx[i];
            int yk = y+dy[i];
            if (inside(xk,yk))
            {
                int nprio = max(a[xk][yk],d);
                if (h[xk][yk] > nprio)
                {
                    h[xk][yk] = nprio;
                    q.push(TCell(xk,yk,nprio));
                }
            }
        }
    }
}
 
int main()
{
    scanf("%d%d",&m,&n);
    rep(i,0,m) rep(j,0,n) scanf("%d",&a[i][j]);
    dijkstra();
    ll ans = 0;
    rep(i,0,m) rep(j,0,n) ans += h[i][j] - a[i][j];
    printf("%lld",ans);
    return 0;
}
 
Độ cao max là 20000 nên không cần dùng heap làm gì. Độ phức tạp tối ưu là O(mn + 20000) thôi.
 
Bạn phải đăng nhập hoặc đăng ký để trả lời tại đây.

Chủ đề tương tự

atomwaffen
7 lý do khiến TPHCM ngày càng ngập nặng
2
Trả lời
30
Lượt xem
3K
SpaceXAI
SpaceXAI
Địa Ngục
Mưa lớn là đường Tô Ngọc Vân, chợ Thủ Đức thành sông: Ngóng dự án hơn 5.000 tỉ
Trả lời
15
Lượt xem
664
betappt
betappt
ChatGPT AI
(Trung Quốc) Singapore và Trung Quốc dẫn đầu thế giới về kết quả học tập
Trả lời
0
Lượt xem
200
ChatGPT AI
ChatGPT AI
Ma trận
[Dịch] Kết quả PISA 2025: Điểm đọc và toán giảm mạnh trên toàn thế giới
2 3 4
Trả lời
66
Lượt xem
5K
đừng nghe hãy nhìn27
đừng nghe hãy nhìn27
manoao
Khi sự không hoàn hảo làm nên bản sắc của phin cà phê Việt
Trả lời
1
Lượt xem
178
chocoboxx
chocoboxx

Thống kê chủ đề

Ngày tạo
unknowpc90,
Người trả lời cuối
Spaghetti Code,
Trả lời
1.460
Lượt xem
154.147

Chia sẻ trang này

Quay lại
Lên đầu trang