Solving My Google Phone Interview Question

This video explains and solves a problem given in a real Google phone interview.

#keeponcoding #tech #programming

DISCLAIMER: Links included in this description might be affiliate links. If you purchase a product or service with the links that I provide I may receive a small commission. There is no additional charge to you! Thank you for supporting so I can continue to provide you with free content!

[edwardnjoroge]

This is the most ideal way one imagines the interview would go...

The interview? An entirely different story :)

[josephwong]

Thanks a lot Keep on Coding!!! your walkthroughs are so helpful, especially your thought process when you talk

[MaheshKulkarni-el]

This is the most subtle explanation ever, thanks for the question, I learned a lot, looking to more videos like this, you earned a subscriber here !

[jocalvo]

You can also find the root by using a DS to check if you have an element in the adj list while building the graph and that will remove the for loop … thanks for sharing !!

[pathapac]

Good video. I think I have a solution for avoiding an extra loop to filter our root nodes. Below are the steps.
1) create an empty set to store root nodes.
2) During first iterarion where you iterate through Relationship list, keep checking if the child is present in the root node set. If so remove it from the set. If not then store the parent to root nodes set. End of this iteration the set would have just the root nodes. Hope this reduces the complexity to 2N

[Garensonic]

I have my Google phone screen next week and am very scared. I had one phone screen five years ago and could not get the optimal solution

[luckabuse]

You might have a forest which has several roots.
Write them all out and loop over.

[research]

Topological sort problem. Seems interesting.

[jahedurrahman]

I solved it using a custom class Node (int depth, string nodename, List<Node> childs) and recursive method.

[ak]

If u use the child as the key and parent as value in the hashmap u could approach this as a topological sort which means the roots find themselves

[mohamedabdul]

This problem gave new perspective of given problem.

[VictorNascimentoo]

In javascript:

const input = []

input.push(['animal', 'mammal']);
input.push(['animal', 'bird']);
input.push(['lifeform', 'animal']);
input.push(['cat', 'lion']);
input.push(['mammal', 'cat']);
input.push(['animal', 'fish']);

printTree(input);

function printTree(input) {
const tree = getTree(input);
const root = findRoot(tree);
dfs({ root, tree, depth: 0});
}

function getTree(input) {
const tree = new Map();

// build graph
input.forEach(relation => {
if(!tree.has(relation[0]))
tree.set(relation[0], new Set());


});

return tree;
}

function findRoot(tree) {
const parents = new Set(tree.keys());

for (let children of tree.values()) {
for(let child of children)
parents.delete(child);
}

return [...parents][0];
}

function dfs({ root, depth, tree }) {
+ root);

if (!tree.get(root)) {
return;
}

for(let child of tree.get(root)) {
dfs({ root: child, depth: depth+1, tree });
}
}

[codestorywithMIK]

Another way to find root :
Any node having 0 indegree will be the root.

[unstoppablehumour]

Idea for finding roots: have a hashset of root candidates: rootCandidates.
For each relation: (line 16)

if the rs.parent is not in children set then add it to rootCandidates
attempt to remove rs.child from rootCandidates

[potatocoder]

I think union find would be useful to find the highest level parent (root)

[rishabh]

Why not just keep the record of topmost-parent, i.e root while traversing through inputs, as soon as we encounter the input relation where the current recorded topmost-parent/root is the child, we update the root to the parent of the current root as per the input relation.
When we do DFS, we will traverse all the way till the last related child node of the root. Nodes at the level same as that of root can be traversed during backtracking, as those and their subsequent children will be one that hasn't been visited till now when we backtrack to root node and check whether any other nodes are still unvisited.

[treyquattro]

it strikes me this is pretty much a B-tree solution. I probably would have struggled through a minimal implementation rather than go the set / map route, but it would have been non-optimal (search / add). BTW, when using e.g. a set, don't you have to account for the underlying complexity: sets are typically implemented as balanced trees, so you would have a search complexity of nlogn. Your channel is extremely good & your solutions are super-clear. Only nit is the YT ads occurring at inopportune moments (any moment is inopportune for YT ad IMHO!)

[krystaljinluma]

Wouldn’t it be better to analyze complexity in terms of V+E?

[shengmingxu]

For finding root node, we can just update root on the run while doing the first loop. Initially just set root as first parent node we have. When the root acts as a child node in another relation, we just update root as the new parent node, and so forth...

[amfalek]

For finding the root without creating the children set, you can create a variable root initially set to null.
Then, for the first relation, you set root as the parent (since it was null initially). Then, for every new relation, if the child in that relation is your current root, then the root becomes the parent in the relation.
If the graph is connected and therefore you always have a single root, and if of course, I'm not missing some critical detail, you should always end up with the correct root.
What do you think of this approach?

EDIT: It seems I did indeed miss a critical detail, as you mentioned in another comment if you add a new relation fish -> shark initially then this approach breaks.