Longest Path in a Directed Graph: Python Interview with a Meta Engineer (no-hire signal)

This is an attempted solution to the Longest Path in a Directed Graph problem presented in a mock interview with a Meta/Facebook engineer. The result of the interview was a no-hire signal. The interview is conducted in Python language. You may come across this type of question or similar if you plan to interview with Meta in 2023.

If you like this interviewer, you can book them directly now through our showcase listings.

Timestamps:

00:00 - Introductions
00:41 - Question Starts
11:18 - Coding begins
44:45 - Does the solution support a cyclic structure
48:02 - Feedback snippet

[vincem]

In python I did that:
time complexity = O(number of edges + number of vertexes)
space complexity = O(number of edges + number of vertexes)

def
# key: node id, value: longest path from node
result_dict = {}

# Create parent dict: key: id of node, value: set of parents
partent_dict = { node_id: set() for node_id in range(len(adj_list)) }
for node_id, children_node_ids in enumerate(adj_list):
for children_node_id in children_node_ids:


# key: node id, value: numbre of children without longest path processed of node
remaining_children_count_dict = { node_id: len(children_node_ids) for node_id, children_node_ids in enumerate(adj_list) }

# List of nodes where all childrens have processed longest path (at begining, contains only nodes without children)
to_visist_node_ids = set([node_id for node_id, remaining_children_count in if remaining_children_count == 0])
longest_path = 0

while len(to_visist_node_ids):

# For each node in to_visist_node_ids, set the final result
for node_id in to_visist_node_ids:
result_dict[node_id] = longest_path

# list all parents
all_parent_node_ids = set()
for node_id in to_visist_node_ids:
parent_node_ids = partent_dict[node_id]
for parent_node_id in parent_node_ids:


# for each parent, decrement number of children with unknown longest path
for node_id in all_parent_node_ids:
-= 1

# List next to_visist_node_ids (parents with 0 children with unknown longest path)
to_visist_node_ids = set([node_id for node_id in all_parent_node_ids if == 0])
longest_path += 1

return [result_dict[node_id] for node_id in range(len(adj_list))]