Đề thi đầu vào của công ty MDC

Công ty cổ phần Tập đoàn MDC (MDC Group) hoạt động trong các lĩnh vực công nghệ thông tin, sản xuất, y tế, phòng cháy – chữa cháy, phân phối & bán lẻ.

Trong các công ty liên kết với viện CNTT&TT của BKHN thì MDC chọn cách phỏng vấn ứng viên bằng một bài test nhỏ. Thường khi các công ty test ứng viên bằng bài test thì sẽ là thuật toán là chủ yếu nha, là những thứ như cấu trúc dữ liệu & thuật toán, thuật toán ứng dụng, những kiến thức về đồ thị,…

Xem thêm KINH NGHIỆM PHỎNG VẤN FLUTTER

Vệ tinh

Tập đoàn viễn thông đa quốc gia UltraCom hiện sở hữu một hệ thống truyền tin gồm N trung tâm truyền nhận dữ liệu (gọi tắt là trung tâm) nằm rải rác khắp địa cầu (các trung tâm này được đánh số từ 1 đến N) và M vệ tinh (gọi tắt là vệ tinh) cũng được phân bố đều khắp trên bầu trời quanh địa cầu (các vệ tinh này được đánh số từ 1 đến M).

Mỗi trung tâm i đều có thể thiết lập kết nối trực tiếp (để khai thác) với mỗi vệ tinh j với chi phí xác định Cij nào đó.

Hai trung tâm được xem là thông băng với nhau nếu chúng cùng được kết nối với một vệ tinh hoặc chúng cùng thông băng với một số trung tâm khác.

Toàn hệ thống của UltraCom đương nhiên vốn là thông băng hoàn toàn, tức là bất kỳ hai trung tâm nào cũng đều thông băng với nhau.

Một sự cố bí ẩn vừa diễn ra trong thời gian gần đây đã khiến một số kết nối bị hư hỏng hoàn toàn và hệ thống của UltraCom bị rơi vào tình trạng không thông băng hoàn toàn được, đặt ra nhiệm vụ cấp bách cho UltraCom phải khẩn trương khắc phục hậu quả này.

Sau sự cố, bộ phận phụ trách kỹ thuật của UltraCom đã tiến hành khảo sát toàn hệ thống và nhận thấy rằng:

1. Mỗi trung tâm đều vẫn còn đang kết nối bình thường với một số các vệ tinh đồng thời mỗi vệ tinh đều còn đang được kết nối bởi một số trung tâm nào đó.
2. Một số kết nối vừa bị hỏng sẽ không thuộc diện xem xét khắc phục nữa, do chi phí quá lớn.
3. Hoàn toàn có phương án khả thi để khắc phục hệ thống thông băng hoàn toàn.

Để tiết kiệm chi phí tại thời điểm nhạy cảm của nền kinh tế toàn cầu, ban lãnh đạo tập đoàn quyết định sẽ chỉ thiết lập lại một số kết nối đã bị hư hỏng sao cho tổng chi phí khắc phục là nhỏ nhất có thể.

Yêu cầu: Xác lập phương án cụ thể và tổng chi phí nhỏ nhất để UltraCom khắc phục sự cố

Dữ liệu vào: Cho trong file văn bản REPAIR.INP, gồm:

• Dòng đầu ghi tuần tự 2 số nguyên dương N, M (2 ≤ M, N ≤ 1000)
  
• Dòng thứ i trong N dòng tiếp theo ghi M số nguyên Ci1, …, CiM (-1 ≤ Cij ≤10000; i = 1, …, N; j = 1, 2,…, M) với ý nghĩa: Cij là chi phí để kết nối trung tâm i với vệ tinh j cùng sự lưu ý đặc biệt: Cij = 0 nếu trung tâm i vẫn đang kết nối bình thường được với vệ tinh j, Cij = -1 nếu bỏ qua việc tái lập sự kết nối giữa trung tâm i với vệ tinh j (do chi phí quá lớn).
• Tất cảc các số nguyên trên cùng dòng đều cách nhau bởi khoảng trống. Dữ liệu luôn đảm bảo tính đúng đắn để có lời giải, tức là luôn có phương án để UltraCom khắc phục sự cố.

Kết quả: Ghi ra file văn bản REPAIR.OUT các thông tin sau:

• Dòng đầu ghi một số nguyên, là tổng chi phí nhỏ nhất tìm được. Thông tin này chiếm 50% số điểm của test.
• Dòng thứ 2 ghi số nguyên dương K, với K là số kết nối cần khắc phục. Thông tin này chiếm 25% số điểm của test.
• K dòng tiếp theo, mỗi dòng ghi hai số nguyên c, s (cách nhau bởi khoảng trống) cho biết cần tái lập kết nối giữa trung tâm c với vệ tinh s. Nếu có nhiều kết quả (phương án), chỉ cần chỉ ra một trong chúng. Thông tin trên K dòng này chiếm 25% số điểm của test.
  

Ví dụ:

REPAIR.INP
4 3
0 -1 5
0 4 4
-1 0 -1
1 2 0

REPAIR.OUT
3 2
4 1
4 2

REPAIR.INP
4 4
0 -1 5 3
-1 4 5 -1
-1 0 -1 0
6 7 0 -1

Ràng buộc:

• 60% số test ứng với 60% số điểm của bài ứng với N, M ≤ 200.
• Giới hạn thời gian cho mỗi test: 01 giây.

Hướng dẫn: Sử dụng thuật toán tham lam, xác định tập lớn nhất các trung tâm đang thông băng (S) , sắp xếp các kết nối theo thứ tự chi phí từ nhỏ đến lớn, sau đó thực hiện kết nối mới (C) vào tập với điều kiện trung tâm X chưa nằm trong tập (S).

Cây và Rừng

Một cấu trúc dạng cây được tổ chức trong CSDL quan hệ dưới dạng các dòng của bảng như sau.

Trong đó, node gốc trong cây sẽ có mã node cha là 0. Có thể có nhiều cây khác nhau trong rừng. Số dòng tối đa có thể lên đến 1.000.000

Yêu cầu:

1. Đọc từ tệp tin tree.txt các node của cây vào bộ nhớ, tệp tin gồm nhiều dòng, mỗi dòng là một node chứa 3 trường thông tin: Mã của node, mã node cha, tên của node.
2. Nhập vào một cặp mã node X và Y, trả lời xem X có phải là node cha (ông, cụ…) của Y hay không. Hiển thị ra màn hình mối quan hệ của X và Y (ví dụ: X=>A=>B=>Y)
3. Nhập vào một mã node X, in ra màn hình tất cả các node con, cháu, chắt….của X (bao gồm mã node, tên node, mỗi cái trên một dòng).
   
4. Hiện thời gian thực hiện thuật toán cho ý 2 và 3, tính theo ms (milisecond)

Đề thi tham khảo từ https://www.tailieubkhn.com/2021/06/de-thi-dau-vao-mdc.html