Thư Viện Câu Hỏi Phỏng Vấn

Bản chất vấn đề

Nhiều hệ thống production cấm sử dụng đệ quy quá sâu để tránh lỗi Stack Overflow trên production server. Do đó, việc biết cách triển khai thuật toán Duyệt theo chiều sâu (DFS) sử dụng Stack thủ công kết hợp lưu trữ trạng thái tổng đường đi là kỹ năng bắt buộc đối với lập trình viên hướng tới cấp độ chuyên nghiệp.

Trong máy ảo Ethereum (EVM), các biến được lưu trữ trong các slot có kích thước 32 bytes (256 bits). Khi bạn sử dụng các kiểu dữ liệu nhỏ hơn như uint8, EVM vẫn phải dành ra một slot 32 bytes để lưu trữ giá trị đó. Để thực hiện các phép toán trên các kiểu dữ liệu nhỏ hơn này, EVM phải thực hiện thêm các thao tác chuyển đổi (masking) để đảm bảo dữ liệu nằm trong phạm vi cho phép, điều này tiêu tốn thêm Gas. Do đó, việc sử dụng uint256 giúp tối ưu hóa Gas bằng cách loại bỏ các bước tính toán dư thừa và tận dụng tối đa không gian lưu trữ của một slot.

Cả hai hàm đều được sử dụng để xử lý các tương tác không xác định hoặc nhận Ether trực tiếp: 1. receive(): Được kích hoạt khi một contract nhận Ether mà không kèm theo dữ liệu (data). Hàm này bắt buộc phải có từ khóa external và payable. 2. fallback(): Được kích hoạt khi một lời gọi hàm đến contract không khớp với bất kỳ hàm nào đã định nghĩa, hoặc khi nhận Ether kèm theo dữ liệu nhưng không có hàm receive. Hàm này cũng cần từ khóa external. Lưu ý: fallback có thể thực hiện các logic phức tạp hơn nhưng bị giới hạn về lượng Gas tiêu thụ nếu được gọi thông qua một lời gọi từ bên ngoài.

Mỗi giao dịch trên Ethereum đều có một giới hạn Gas (Gas Limit). Nếu một vòng lặp phụ thuộc vào độ dài của một mảng động (dynamic array) mà mảng này có thể tăng kích thước không giới hạn, thì tại một thời điểm nào đó, chi phí thực thi vòng lặp sẽ vượt quá Gas Limit của block. Điều này dẫn đến lỗi Out of Gas, khiến giao dịch bị revert hoàn toàn. Giải pháp thực chiến là sử dụng mô hình Pull-over-Push, trong đó người dùng tự rút tiền hoặc thực hiện thao tác thay vì ép buộc contract phải lặp qua một danh sách lớn để xử lý cho từng người.

Frontend chỉ là một giao diện tương tác và có thể bị bỏ qua bởi các công cụ như Remix, Ethers.js, hoặc các script tấn công trực tiếp vào địa chỉ contract. Smart Contract là rào cản cuối cùng đảm bảo tính toàn vẹn của dữ liệu. Nếu không kiểm tra (ví dụ: dùng require hoặc revert) ngay tại hàm của contract, kẻ tấn công có thể gửi các giá trị độc hại (như số âm, địa chỉ không hợp lệ) để làm hỏng trạng thái của contract. Luôn tuân thủ nguyên tắc 'Never trust the client' trong phát triển hệ thống phi tập trung.

Việc sử dụng Divide and Conquer cho bài toán tìm cặp điểm gần nhất giúp tối ưu hóa bằng cách chia không gian thành hai nửa. Thay vì so sánh tất cả các cặp điểm, chúng ta chỉ cần tìm khoảng cách nhỏ nhất ở hai nửa trái và phải, sau đó kiểm tra các điểm nằm gần đường biên giữa. Điểm mấu chốt là trong dải biên, mỗi điểm chỉ cần so sánh với tối đa 7 điểm lân cận khác, giúp giảm đáng kể số lượng phép so sánh cần thực hiện.

Bài toán đếm nghịch thế yêu cầu tìm số cặp (i, j) sao cho i < j và A[i] > A[j]. Khi sử dụng Merge Sort, trong quá trình trộn (merge) hai mảng con đã sắp xếp, nếu phần tử ở mảng bên phải nhỏ hơn phần tử ở mảng bên trái, ta biết ngay rằng phần tử đó nhỏ hơn tất cả các phần tử còn lại trong mảng bên trái. Điều này cho phép đếm số lượng nghịch thế trong thời gian O(n log n) thay vì O(n^2) bằng cách duyệt trâu bò.

Đệ quy sâu trong Divide and Conquer tiêu tốn bộ nhớ Stack cho mỗi lời gọi hàm. Nếu kích thước bài toán quá lớn, hệ thống sẽ bị Stack Overflow. Để khắc phục, ta có thể sử dụng kỹ thuật Memoization (lưu trữ kết quả các bài toán con đã giải) hoặc chuyển đổi sang phương pháp lặp (Iterative) kết hợp với cấu trúc dữ liệu Stack thủ công để kiểm soát bộ nhớ tốt hơn trong các hệ thống Enterprise.

Thay vì nhân a liên tiếp n lần (độ phức tạp O(n)), ta chia bài toán thành: nếu n chẵn, a^n = (a^(n/2))^2; nếu n lẻ, a^n = a * (a^((n-1)/2))^2. Việc chia đôi số mũ ở mỗi bước giúp giảm số lượng phép nhân theo hàm logarit. Đây là kỹ thuật nền tảng trong các thư viện mật mã học (Cryptography) để xử lý các số nguyên cực lớn.

Độ phức tạp của Divide and Conquer thường được biểu diễn qua định lý Master Theorem: T(n) = aT(n/b) + f(n). Nếu việc phân chia không cân bằng (ví dụ: b tiến gần về 1), độ sâu của cây đệ quy sẽ tăng lên, dẫn đến hiệu năng suy giảm nghiêm trọng. Trong thực tế, việc đảm bảo bài toán con có kích thước bằng nhau giúp duy trì độ sâu cây ở mức log(n), đảm bảo hệ thống chạy ổn định với dữ liệu lớn.

Cơ chế hoạt động của Accumulator trong reduce

Phương thức Array.prototype.reduce() thực thi một hàm callback trên từng phần tử của mảng, truyền vào kết quả của phép tính từ lần thực thi trước đó. Giá trị này được gọi là accumulator (biến tích lũy).

Bản chất của toán tử Spread (...) trong JavaScript

Toán tử spread (...) thực hiện việc sao chép nông (Shallow Copy). Điều này có nghĩa là nó tạo ra một mảng mới, nhưng các phần tử bên trong mảng đó (nếu là kiểu dữ liệu tham chiếu như Object hoặc một mảng con khác) vẫn chỉ lưu giữ địa chỉ tham chiếu trỏ đến cùng một ô nhớ với mảng gốc.

Phân tích các phương thức kiểm tra mảng

Cả ba phương thức includes(), some(), và every() đều duyệt qua mảng để trả về kết quả kiểu boolean (true hoặc false), nhưng mục đích và cơ chế khác nhau:

Cơ chế hoạt động của Array.prototype.splice()

Mảng trong JavaScript (đặc biệt là Dynamic Array) được cấp phát một vùng nhớ liên tục (Contiguous Memory Allocation) để đảm bảo độ phức tạp truy xuất ngẫu nhiên là $O(1)$.