Suppose you are working for a fast-growing startup company, which we will call
“FastCo,” and it is your job to write a software package that can maintain the set,
E, of all the employees working for FastCo. In particular, your software has to
maintain, for each employee, x in E, the vital information about x, such as his
or her name and address, as well as the number of shares of stock in FastCo that
the CEO has promised to x. When an employee first joins FastCo they start out
with 0 shares of stock. Every Friday afternoon, the CEO hosts a party for all the
FastCo employees and kicks things off by promising every employee that they are
getting y more shares of stock, where the value of y tends to be different every
Friday. Describe how to implement this software so that it can simultaneously
achieve the following goals:
- The time to insert or remove an employee in E should be O(log n), where
n is the number of employees in E.
- Your system must be able to list all the employees in E in alphabetical
order in O(n) time, showing, for each x in E, the number of shares of
FastCo the CEO has promised to x.
- Your software must be able to process each Friday promise from the CEO
in O(1) time, to reflect the fact that everyone working for FastCo on that
day is being promised y more shares of stock. (Your system needs to be
this fast so that processing this update doesn’t make you miss too much of
the party.)
