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

Bản chất vấn đề

Việc đảo ngược dữ liệu là thao tác cơ bản trong xử lý tín hiệu và phân tích log. Cấu trúc dữ liệu Stack hoạt động theo nguyên tắc LIFO (Last-In, First-Out), điều này khiến nó trở thành công cụ tự nhiên nhất để đảo ngược thứ tự.

Bản chất vấn đề

Các tệp cấu hình XML có cấu trúc phân cấp (Hierarchical Structure). Một thẻ mở phải được đóng bởi thẻ tương ứng theo đúng thứ tự ngược lại với lúc mở. Stack phản ánh chính xác cơ chế lồng nhau này.

Bản chất vấn đề

Việc kiểm tra tính cân bằng của dấu ngoặc ((), [], {}) là bài toán kinh điển trong biên dịch mã nguồn. Stack giúp lưu trữ các dấu ngoặc mở chưa được đóng để đối chiếu với dấu ngoặc đóng xuất hiện sau đó.

Bản chất vấn đề

Call Stack là cơ chế của môi trường thực thi (Runtime) để theo dõi vị trí của chương trình đang chạy. Mỗi khi một hàm được gọi, một Stack Frame được đẩy vào Stack.

Bản chất vấn đề

Cách tiếp cận thông thường là dùng hai vòng lặp lồng nhau (O(n^2)), điều này không khả thi với tập dữ liệu lớn trong các hệ thống tài chính. Stack cho phép lưu trữ các chỉ số (indices) của các phần tử chưa tìm được phần tử lớn hơn tiếp theo.

Cơ chế hoạt động

• Full Table Scan: Cơ sở dữ liệu phải đọc từng dòng (row) từ đĩa cứng lên bộ nhớ để kiểm tra điều kiện. Đây là thao tác I/O rất tốn kém.
• B-Tree Index: Tạo ra một cấu trúc cây cân bằng, nơi các giá trị được sắp xếp theo thứ tự. Khi tìm kiếm, hệ thống chỉ cần đi từ gốc xuống lá theo các nhánh, giảm số lượng block dữ liệu cần đọc từ đĩa.

Ví dụ thực tế

Với 1 triệu bản ghi, Full Table Scan cần đọc 1 triệu dòng. Với B-Tree, độ cao của cây thường chỉ từ 3-4 tầng, nghĩa là chỉ cần tối đa 4 lần truy xuất đĩa để tìm ra bản ghi chính xác.

So sánh cơ bản

Hiện tượng Collision

Collision xảy ra khi hàm băm (hash function) tạo ra cùng một vị trí (index) cho hai giá trị đầu vào khác nhau. Khi đó, Hash Table phải lưu trữ nhiều giá trị tại cùng một vị trí.

Tại sao chọn Trie?

• Hash Table: Chỉ hỗ trợ tìm kiếm chính xác (exact match). Để tìm kiếm theo tiền tố (prefix), Hash Table không có khả năng hỗ trợ trực tiếp.
• Trie: Được thiết kế đặc biệt để lưu trữ chuỗi ký tự theo dạng phân cấp. Mỗi nút đại diện cho một ký tự.

Ưu điểm của Trie

1. Tìm kiếm tiền tố cực nhanh: Độ phức tạp là O(m) với m là độ dài của từ khóa, không phụ thuộc vào số lượng từ trong tập dữ liệu.
2. Tiết kiệm không gian: Các từ có chung tiền tố sẽ được lưu trữ chung các nút, giúp giảm trùng lặp bộ nhớ.

Ứng dụng thực chiến

Tính năng gợi ý từ khóa (Autocomplete) hoặc kiểm tra chính tả (Spell Checker) luôn ưu tiên dùng Trie vì khả năng duyệt nhanh các nhánh cây dựa trên ký tự người dùng vừa nhập.

Bản chất cơ chế

Binary Search hoạt động dựa trên nguyên lý chia để trị (Divide and Conquer). Bằng cách so sánh giá trị cần tìm với phần tử ở giữa (mid), thuật toán có thể loại bỏ ngay lập tức một nửa không gian tìm kiếm trong mỗi bước lặp.

Bản chất của Mapping

Mapping trong Solidity hoạt động như một bảng băm (hash table) ảo. Các khóa (key) không được lưu trữ trực tiếp mà được sử dụng để tính toán vị trí lưu trữ thông qua hàm băm Keccak-256. Do đó, không có danh sách các khóa tồn tại trong bộ nhớ, khiến việc duyệt qua (iteration) là không thể.

Phân tích kỹ thuật

• Memory: Là vùng nhớ tạm thời, dữ liệu có thể thay đổi được (mutable). Khi truyền tham số vào hàm, dữ liệu được copy từ nguồn vào vùng nhớ memory.
• Calldata: Là vùng nhớ chỉ đọc (read-only), chứa dữ liệu đầu vào của giao dịch. Dữ liệu này không thể thay đổi và không tốn chi phí copy vào memory.

Tại sao ưu tiên calldata?

• Tiết kiệm Gas: Sử dụng calldata giúp tránh việc copy dữ liệu tốn kém vào memory.
• An toàn: Vì là read-only, nó đảm bảo dữ liệu đầu vào không bị thay đổi ngoài ý muốn trong quá trình thực thi hàm.

Ví dụ

function processData(string calldata input) external pure {
    // Sử dụng calldata cho tham số đầu vào không thay đổi
}

Lưu ý

Chỉ sử dụng calldata cho các tham số đầu vào của hàm (external/public). Nếu bạn cần sửa đổi dữ liệu bên trong hàm, bạn buộc phải copy nó sang memory hoặc storage.

Nguyên nhân

Các hàm transfer() và send() có giới hạn cố định là 2300 gas. Giới hạn này được thiết kế để ngăn chặn Reentrancy Attack trong quá khứ. Tuy nhiên, với các bản cập nhật của Ethereum (như EIP-1884), chi phí của các opcode có thể thay đổi, khiến 2300 gas không còn đủ để thực hiện các logic cần thiết (ví dụ: ghi vào storage hoặc gọi hàm khác).

Định nghĩa

• Gas Limit: Là số lượng gas tối đa mà người dùng sẵn sàng chi trả cho việc thực thi giao dịch. Nó đóng vai trò như một cơ chế an toàn để ngăn chặn các vòng lặp vô tận.
• Gas Price: Là số tiền (tính bằng Gwei) mà người dùng trả cho mỗi đơn vị gas để các validator ưu tiên xử lý giao dịch.

Khi vượt quá Gas Limit

Nếu giao dịch tiêu tốn nhiều gas hơn mức Gas Limit đã thiết lập, máy ảo Ethereum (EVM) sẽ dừng thực thi giao dịch ngay lập tức. Trạng thái của Smart Contract sẽ được hoàn tác (revert) về trạng thái ban đầu, nhưng toàn bộ lượng gas đã sử dụng cho đến thời điểm đó sẽ bị mất và không được hoàn lại cho người gửi.

Phân biệt

• view: Hàm được phép đọc dữ liệu từ trạng thái (storage) của contract nhưng không được phép thay đổi trạng thái đó.
• pure: Hàm không được phép đọc cũng như không được phép thay đổi trạng thái của contract. Nó chỉ thực hiện tính toán dựa trên các tham số đầu vào.

Tầm quan trọng đối với hiệu năng

• Khi gọi các hàm này từ bên ngoài (off-chain) thông qua các node, chúng không tốn gas vì không cần tạo giao dịch trên mạng lưới.
• Việc khai báo đúng giúp trình biên dịch tối ưu hóa mã bytecode và giúp các công cụ phân tích bảo mật hiểu rõ hành vi của hàm.

Ví dụ

uint256 public value;
function getValue() public view returns (uint256) { return value; } // Đọc storage
function add(uint256 a, uint256 b) public pure returns (uint256) { return a + b; } // Chỉ tính toán

Lưu ý

Nếu bạn khai báo hàm là view hoặc pure nhưng lại thực hiện ghi dữ liệu (ví dụ: thay đổi giá trị biến state), trình biên dịch sẽ báo lỗi.