Am working on a coding exercise which I am somewhat confused on how to implement a solution. 

According to the JavaDoc, I have to implement this EmployeeManager interface.

Presume that employee data arrives in a separate thread from other requests.

Note that getSalary() execute in constant time O(n).

Execution time must not vary with number of employees or departments.

import java.util.List;
    
    /**
     * Manage departments and employees to easily query aggregate data.
     * All methods should be thread-safe.
     */
    public interface EmployeeManager {
    
        /**
         * Create a new department with the given name and the given parentId. 
         * The department name need not be unique.
         * 
         * @param departmentName
         *            the name of the new department.
         * @param parentId
         *            the parent department or null if no parent
         * @return the ID of the newly created department
         * @throws RuntimeException
         *             if the parent department (if not null) does not exist
         */
        public int newDepartment(String departmentName, Integer parentDepartmentId);
    
        /**
         * Create a new employee with the given ID 
         * and given parent department (if any).
         * 
         * @param employeeId
         *            the new employee's ID
         * @param parentdepartmentId
         *            the parent department or null if no parent
         * @throws RuntimeException
         *             if the employee or parent department (if not null) does not exist
         */
        public void newEmployee(int employeeId, Integer parentdepartmentId);
    
        /**
         * Return a list of department IDs that are 
         * direct children of the given parent. 
         * 
         * Null is a valid value for parent.
         * 
         * @param departmentId
         *            the parent department ID
         * @return a list of child department IDs
         * @throws RuntimeException
         *             if the department does not exist
         */
        public List<Integer> getDepartments(Integer departmentId);
    
        /**
         * Return a list of employee IDs that are direct children of the given parent. 
         * Null is a valid value for parent.
         * 
         * @param departmentId
         *            the parent department ID
         * @return a list of child employee IDs
         * @throws RuntimeException
         *             if the department does not exist
         */
        public List<Integer> getEmployees(Integer departmentId);
    
        /**
         * Move the given department to the new parent.
         * 
         * @param departmentId
         *            the ID of the department to move
         * @param parentDepartmentId
         *            the new parent. The new parent department 
         *            -- if the id is not null -- must exist, and
         *            must not create a cyclic graph.
         * @throws RuntimeException
         *             if a cyclic graph would be created or
         *             the department or parent department does not exist
         */
        public void moveDepartment(int departmentId, Integer parentDepartmentId);
    
        /**
         * Move the given employee to the new parent.
         * 
         * @param employeeId
         *            the ID of the employee to move
         * @param parentDepartmentId
         *            the new parent. The new parent department 
         *            -- if the id is not null -- must exist.
         * @throws RuntimeException
         *             if the employee or parent department 
         *             (if not null) does not exist
         */
        public void moveEmployee(int employeeId, Integer parentDepartmentId);
    
        /**
         * Return the name of the given department.
         * 
         * @param departmentId
         *            the department ID
         * @return the department name
         * @throws RuntimeException
         *             if the department does not exist
         */
        public String getName(int departmentId);
    
        /**
         * Return the current aggregate salaries of 
         * all employees in the given department
         * 
         * (including all employees in all child departments).
         * 
         * Must execute in constant time O(n).
         * 
         * @param departmentId
         *            the department ID
         * @return the aggregate salary or return null if no employees
         * @throws RuntimeException
         *             if the department does not exist
         */
        public Double getSalary(int departmentId);
    
        /**
         * New data has arrived from the given employee. 
         * If new data arrives for an unknown employee, then
         * create this employee with parent department null.
         * 
         * @param employeeId
         *            the employee ID
         * @param salary
         *            the new salary
         * @throws RuntimeException
         *             if the employee does not exist
         */
        public void newEmployeeData(int employeeId, double salary);
    }

Question(s):

1. What type of problem is this? 

2. Should I create Employee and Department classes as POJOs and what would be inside? Will they have to implement runnable in order to be thread-safe?

3. What type of data structure(s) does this need?

Am really rusty with my data structures and CS stuff so would greatly appreciate any feedback.

P.S. When I highlight my source inline and click on the <> Source button from above, it puts in html tags over the entire content and doesn't really change the source code (in terms of syntax coloring for Java)?