HCM, 19/3/2025

Background: Nguyễn Văn Biên (Ben), có kinh nghiệm gần 4 năm lập trình Mobile bằng Flutter & nửa năm code Backend CRUD cơ bản với Go. Đang kiếm sống bằng Flutter.

1. Luyện giả thuật: HackerRank - Minimum Operations

URL: https://www.hackerrank.com/challenges/minimum-operations

Tóm tắt

Có n hộp, mỗi hộp i chứa số lượng bóng màu đỏ (r[i]) , màu xanh lá (g[i]) và xanh dương (b[i]). Mục tiêu là tách các bóng sao cho mỗi hộp chỉ chứa duy nhất 1 màu. Tìm số lần di chuyển tối thiểu để đạt được điều đó.

Đây là một bài DEBUG, nghĩa là phải sửa đổi tối đa 6 dòng code (chỉ được sửa, không được thêm) để hàm chạy ra kết quả chính xác

Cách giải

int min_operations(vector <int> red, vector <int> green, vector <int> blue) { int n = (int)red.size(), i, j; for (i = 0; i < n; i++) { for (j = 0; j < 7; j++) { dp[i][j] = 1<<30; } } dp[0][0] = 0; for (i = 0; i < n; i++){ for (j = 0; j < 7; j++){ dp[i + 1][j | 1] = min(dp[i + 1][j | 1], dp[i][j] + green[i] + blue[i]); dp[i + 1][j | 2] = min(dp[i + 1][j | 2], dp[i][j] + red[i] + blue[i]); dp[i + 1][j | 4] = min(dp[i + 1][j | 4], dp[i][j] + blue[i] + green[i]); } } j = 0; for (i = 0; i < n; i++){ if (green[i]) j |= 1; if (red[i]) j |= 2; if (blue[i]) j |= 4; } if (dp[n][j] >= (1<<30)) dp[n][j] = -1; return dp[n][j];
}

Nhìn vào phép toán bitwise OR (|), có thể suy đoán rằng cách giải này có liên quan gì đó tới dãy nhị phân. Để ý con số 7 và có 3 màu RGB, dãy nhị phân có thể là tượng trưng cho các trạng thái màu sắc:

• 000 (0) = không có màu nào được chọn.
• 001 (1) = Red.
• 010 (2) = Green.
• 100 (4) = Blue.
• 011 (3) = Red + Green.
• 101 (5) = Blue + Rred.
• 110 (6) = Blue + Green.
• 111 (7) = RGB.

Có tất cả 8 trạng thái ==> Sửa những chỗ có số 7 thành 8.

Sửa lại tất cả những thứ tự kết hợp R/G/B bị sai. Kết quả:

int min_operations(vector <int> red, vector <int> green, vector <int> blue) { int n = (int)red.size(), i, j; for (i = 0; i <= n; i++) { for (j = 0; j < 8; j++) { dp[i][j] = 1<<30; } } dp[0][0] = 0; for (i = 0; i < n; i++){ for (j = 0; j < 8; j++){ dp[i + 1][j | 1] = min(dp[i + 1][j | 1], dp[i][j] + green[i] + blue[i]); dp[i + 1][j | 2] = min(dp[i + 1][j | 2], dp[i][j] + red[i] + blue[i]); dp[i + 1][j | 4] = min(dp[i + 1][j | 4], dp[i][j] + red[i] + green[i]); } } j = 0; for (i = 0; i < n; i++){ if (green[i]) j |= 2; if (red[i]) j |= 1; if (blue[i]) j |= 4; } if (dp[n][j] >= (1<<30)) dp[n][j] = -1; return dp[n][j];
}

Giờ mình vẫn chưa biết thuật toán này hoạt động như nào nữa :v Nói chung là cũng fix bug theo bản năng.

2. Authentication để làm gì?

Để xác minh danh tính của người đang yêu cầu request.

Authen có tác dụng:

• Bảo mật: Chỉ những người hợp lệ mới được phép truy cập tài nguyên.
• Phân quyền: Sau khi xác thực, xác định xem người đó có thể làm được những hành động gì (athorization - đến sau authentication).
• Cá nhân hoá: Vì biết bạn là người nào, có thể phân tích dữ liệu của bạn và đề xuất những nội dung được cá nhân hoá.
• Theo dõi và giám sát.

Một số cách để authenticate:

• Username / password
• Token
• Sinh trắc học
• Xác thực đa yếu tố MFA: Kết hợp nhiều phương pháp. VD: Username / password + OTP

3. JWT là gì?

JWT, JSON Web Token, là một tiêu chuẩn rất phổ biến trong việc authentication. Nó chứa các thông tin được mã hoá dưới dạng JSON, giúp xác minh danh tính của người dùng.

Cấu trúc JWT

Gòm 3 phần được phân tách bới dẩu (.) và được mã hoá dưới dạng Base64.

1. Header: Chưa thông tin về loại token (thường là "JWT") và thuật toán mã hoá (VD: HS256).
   • Ví dụ: {"alg": "HS256", "typ": "JWT"}
2. Payload: Chứa một số dữ liệu thực tế của user, VD: {"sub": "1234567890", "name": "John Doe", "exp": 1516239022}
3. Signature: Mã hoá header & payload bằng một khoá bí mật secret key.

JWT được xác minh tính hợp lệ như thế nào?

1. Kiểm tra xem có đủ 3 thành phần header, payload & signature chưa.
2. Giải mã header & payload
   • Header: Xem thuật toán alg có được hỗ trợ không.
   • Payload: Xem có đủ các field cần thiết không.
3. Kiếm tra chữ ký
   • Lấy chuỗi Base64 của header & payload, nối chúng lại với nhau bằng dấu (.): header.payload
   • Dùng secret key (đối với HS256) và thuật toán từ header để mã hoá chuỗi trên lại.
   • So với signature lấy từ JWT, nếu không giống nhau --> token không hợp lệ.
4. Kiểm tra thời gian hết hạn
5. Kiểm tra thời gian phát hành (issued at - iat) xem nó có phải đến từ tương lai không.
6. Kiểm tra các claims khác nếu cần. VD:
   • iss (issuer): Nếu token đến từ nguồn đáng tin cậy
   • aud (audience): Nếu token dành cho đúng đối tượng.
   • sub(subject): Xác mình ID người dùng or something.
7. Kiểm tra blacklist nếu có.

Ưu điểm của JWT

• Không cần lưu dưới server, chỉ cần kiểm tra tính hợp lệ của token.
• Đa nền tảng: Web, mobile, RESTful API.
• Tự chứa một số thông tin cần thiết từ claims, VD: username, user ID...