FastPrepTransitive Employee Referral Counts

Transitive Employee Referral Counts

Robinhood logoRobinhood● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Each string in referrals is referrer referredEmployee. The relationships form a forest: an employee has at most one direct referrer and no cycles occur.

For every employee mentioned in the input, count all direct and indirect referred descendants. Return employee=count strings sorted by employee id.

Function

referralCounts(referrals: String[]) → String[]

Examples

Example 1

referrals = ["A B","A C","B D"]return = ["A=3","B=1","C=0","D=0"]

A refers B and C directly and D through B.

Example 2

referrals = ["x y"]return = ["x=1","y=0"]

A leaf has no referred descendants.

Example 3

referrals = ["m n","p q"]return = ["m=1","n=0","p=1","q=0"]

Independent referral trees are both reported.

Constraints

  • 1 <= referrals.length <= 10^5.
  • Employee ids contain no spaces.
  • The directed relationships form a forest with no duplicate edges.

More Robinhood problems

See Robinhood hiring insights
public String[] referralCounts(String[] referrals) {
    // Write your solution here.
}
referrals["A B","A C","B D"]
expected["A=3", "B=1", "C=0", "D=0"]
Checking account…