As a speed-coding test, this problem requires you to apply common computer science constructs to a realistic problem, and then challenges you
“How many seconds do you need to build a working directed graph from raw data, and run BFT/DFT on it?”
45 minutes given. Target is to complete first 2 questions with working code. Can some candidates complete all 3 questions? I guess so.
Q: You are given some raw data like
parent_child_pairs = [ (1, 3), (2, 3), (3, 6), (5, 6), (5, 7), (4, 5), (4, 8), (8, 10), (11,2) ]
Suppose we have some input data describing a graph of relationships between parents and children over multiple generations. The data is formatted as a list of (parent, child) pairs, where each individual is assigned a unique integer identifier.
For example, in this diagram, 3 is a child of 1 and 2, and 5 is a child of 4:
1 2 4
\ / / \
3 5 8
\ / \ \
6 7 10
Q1: write a function to output all individuals having no parents(like 1 and 4) in a list, and another list of individuals having a single parent (like 8 and 7)
Q2: write a bool function to determine if two named individuals have any common ancestor. 3 and 6 yes; 3 and 1 no!
I wrote a DFT solution .. https://github.com/tiger40490/repo1/blob/py1/py/tree/commonAncestor_Indeed.py Not very efficient but I really should care less about that since the real challenge is .. timely completion. I was not used to writing DFT on the spot within minutes but I hacked it together under ticking clock, first time in my career !
To find if two sets intersect, I was forced to make a quick judgment call to write my own loop.
- I didn’t know if there’s a
simple and reliable solution online
- i didn’t know how much effort is required to search online and
- i didn’t know how much effort is required to adapt standard solution to suit my needs
- My own loop gives more legwork but more control if requirements turns out to be non-standard.
Q3: (original wording) Write a function that, for a given individual in our dataset, returns their earliest known ancestor — the one at the farthest distance from the input individual. If there is more than one ancestor tied for “earliest”, return any one of them. If the input individual has no parents, the function should return null (or -1).
Sample input and output:
findEarliestAncestor(parentChildPairs, 8) => 4
findEarliestAncestor(parentChildPairs, 7) => 4
findEarliestAncestor(parentChildPairs, 6) => 11
findEarliestAncestor(parentChildPairs, 1) => null or -1