Python cho người Việt

Python cho người Việt

Phỏng vấn: Số nhân viên cấp dưới

written by Nguyễn Thành Nam, on Apr 10, 2015 11:56:00 AM.

Câu hỏi

Cho một từ điển từ chuỗi sang chuỗi, khoá là tên nhân viên, và giá trị là tên của người quản lý. Nhân viên cấp cao nhất báo cáo cho chính họ. Tìm số nhân viên cấp dưới của một nhân viên nào đó.

Ví dụ: Trong từ điển sau, A và B cùng báo cáo cho C, C và E báo cáo cho F, D báo cáo cho E, và F là nhân viên cấp cao nhất.

{
    "A": "C",
    "B": "C",
    "C": "F",
    "D": "E",
    "E": "F",
    "F": "F",
}

Số lượng nhân viên cấp dưới của A là 0, B là 0, C là 2, D là 0, E là 1, và F là 5.

Phân tích

Giả sử A là nhân viên cấp dưới của B, và B là nhân viên cấp dưới của C.

Cách nhìn trực tiếp từ trên xuống theo câu hỏi này là C có 2 nhân viên cấp dưới, và B có một nhân viên cấp dưới. Nếu nhìn ngược lại, ta sẽ nói rằng A "đội" B lên 1, đội tiếp C lên 1, và B đội C lên thêm 1. Tức là mỗi nhân viên sẽ đội tất cả các nhân viên cấp trên của họ lên 1 (A đội B và C, B đội C).

Do đó, cách giải câu hỏi này là duyệt hết các phần tử trong danh sách, với mỗi phần tử, lần lượt đội (cộng 1) vào kết quả của các nhân viên cấp trên của phần tử đấy.

Độ phức tạp thực thi là O(n^2) và tốn O(n) bộ nhớ.

Nếu bạn có cách giải tốt hơn xin hãy cùng chia sẻ tại diễn đàn.

Cài đặt

def solve(employees):
    subordinate_count = {}
    for emp, boss in employees.iteritems():
        if emp not in subordinate_count:
            subordinate_count[emp] = 0
        while emp != boss:
            try:
                subordinate_count[boss] += 1
            except KeyError:
                subordinate_count[boss] = 1
            emp, boss = boss, employees[boss]
    return subordinate_count

inp = {"A": "C", "B": "C", "C": "F", "D": "E", "E": "F", "F": "F"}
exp = {"A": 0, "B": 0, "C": 2, "D": 0, "E": 1, "F": 5}
assert(solve(inp) == exp)