Map giữ thứ tự chèn: foreach trên mảng kết hợp không theo thứ tự bạn nghĩ
Class cần viết: omap · cần máy chấm có SystemVerilog · 6 case (2 mẫu) · giới hạn 4 s/case · ~25 phút
Testbench hay cần một bảng tra cứu nhớ được thứ tự thêm vào: thanh ghi theo thứ tự khai báo, giao dịch theo thứ tự gửi, tham số in ra đúng thứ tự người dùng nhập. Mảng kết hợp tra cứu nhanh nhưng không nhớ thứ tự đó.
Viết class omap, ánh xạ string → int, giữ thứ tự chèn:
| Method | Đặc tả |
|---|---|
void put(string k, int v) |
khoá mới: thêm vào cuối thứ tự. Khoá đã có: chỉ cập nhật giá trị, giữ nguyên vị trí |
bit get(string k, ref int v) |
khoá có: gán v, trả 1. Khoá không có: trả 0 và không đổi v |
bit remove(string k) |
xoá khoá, trả 1; khoá không có thì trả 0. Thêm lại sau khi xoá thì khoá đứng ở cuối |
int size() |
số khoá hiện có |
string key_at(int i) |
khoá thứ i theo thứ tự chèn (từ 0); i ngoài phạm vi trả "" |
void keys(ref string ks[$]) |
gán ks bằng mọi khoá theo thứ tự chèn |
Ví dụ: put("b", 1); put("a", 2); put("10", 3); put("9", 4); thì keys cho {"b", "a", "10", "9"}. Sau put("a", 7), thứ tự không đổi.
Gợi ý cấu trúc: một mảng kết hợp cho giá trị và một queue cho thứ tự. Bạn được tự do chọn cách khác, miễn đúng đặc tả.
Các case
- put và getmẫu
- Thứ tự chèn khác thứ tự sắp xếpmẫu
Cùng 4 case ẩn kiểm các yêu cầu còn lại của đề. Case ẩn chỉ báo đúng/sai, không nói chi tiết: tự tìm chỗ sai từ đề, hoặc mở gợi ý.
Testbench có mô hình tham chiếu riêng, độc lập với lời giải mẫu. Lời giải mẫu đã chạy qua mọi case trên simulator thật, và 4 bản lỗi mẫu đều bị ít nhất một case bắt. Case mẫu sai sẽ cho biết chỗ sai đầu tiên (giá trị mong đợi so với giá trị nhận được); case ẩn chỉ báo đúng/sai.