Throne Inheritance

MediumTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A kingdom tracks its royal family starting from a single king. Implement ThroneInheritance(kingName): - birth(parentName, childName) records that the living-or-dead person parentName had a child childName. Children of the same parent are ordered by birth. - death(name) marks name as dead. Death does not remove anyone from the family tree. - getInheritanceOrder() returns the line of succession with dead people omitted. The line of succession is a **pre-order traversal** of the family tree: the king first, then the king's first-born child followed by that child's entire line, then the king's second child and their line, and so on. All names are distinct.

Examples

Input: ["ThroneInheritance","birth","birth","birth","getInheritanceOrder","death","birth","getInheritanceOrder","death","getInheritanceOrder"] [["ann"],["ann","bo"],["ann","cy"],["bo","dee"],[],["bo"],["cy","eve"],[],["ann"],[]]
Output: [null,null,null,null,["ann","bo","dee","cy"],null,null,["ann","dee","cy","eve"],null,["dee","cy","eve"]]
The tree is ann -> (bo -> dee), (cy). Pre-order gives ann, bo, dee, cy. After bo dies and cy has eve, bo is skipped but dee keeps her place. Once ann dies she is dropped too.
Input: ["ThroneInheritance","getInheritanceOrder","death","getInheritanceOrder","birth","getInheritanceOrder"] [["k"],[],["k"],[],["k","a"],[]]
Output: [null,["k"],null,[],null,["a"]]
A dead king leaves an empty line until a child is born; a dead parent can still have children recorded.

Constraints

  • 1 <= kingName.length, parentName.length, childName.length, name.length <= 15
  • Names consist of lowercase letters and digits; all names are distinct
  • `parentName` and `name` always refer to existing people
  • At most 10^5 calls to `birth` and `death`
  • At most 10 calls to `getInheritanceOrder`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems