CODEWITHSUNDEEP
algorithm
Jason
Jason

Reputation: 11363

Party rank - Interview Solution

Assume that you are a party consultant, and are hired to prep and host a company party. Every employee in the company is part of a B-tree style hierarchy and are accorded a party rank value. In order to prevent inhibitions of employees in the presence of their direct supervisor, both the supervisor and his direct employees will not be invited. However, either group can be invited.

Design an algorithm to produce a guest list of the largest party rank sum.

My solution is

Execute a bottom-up breadth-first search to access the lowest supervisor sub-tree in the tree. For each supervisor, calculate the differential between the supervisor party rank and the sum of the direct employees. If the employee party rank sum is greater than the supervisor ranking, all affected employees will be added to the guest list.

If the differential between supervisor and employee rankings is less than or equal to zero, move up one level and execute the comparison described above for the next level sub-tree.

Continue up level by level until the head of the company is analyzed, and print out the party rank sum and guest list.

My analysis for the run time is O(n log n -1) due to

log n-1 - time to descend to lowest sub-tree

n - maximum number of comparisons

I came up with this at an interview, but couldn't help but feel I missed something. Am I right on the analysis and steps?

Upvotes: 4

Views: 429

Answers (1)

Keith Randall
Keith Randall

Reputation: 23265

I would compute, for each person in the hierarchy in a bottom-up fashion, two numbers:

  1. If that person DID NOT attend, how many of his transitive subordinates could attend.
  2. If that person DID attend, how many of his transitive subordinates (including himself) could attend.

For each person, this is easy to calculate given the two numbers for each immediate subordinate (in O(B) time where, B is the # of subordinates). Just try both ways for the person and use the appropriate number for each subordinate.

So with a bottom-up walk I think that's O(n) time in total.

Upvotes: 1

Related Questions