Interview Coding Questions: List Index Extraction, Tree Path Construction, and Minimum Path Sum Solutions

I enjoyed the company's practical interview style, but my psychological state and technical level caused me to fail.

Problem 1: Given two lists a and b, output the indices of elements in a that also appear in b, with a time complexity better than O(n²).

Solution: Convert b into a hash map and check membership while iterating a:

a = [5,3,1,5,4]
b = [5,3]
d = {}
for i in b:
    d[i] = 0
res = []
for i in range(len(a)):
    if a[i] in d:
        res.append(i)
print(res)

Problem 2: Build a tree from a set of node‑parent pairs where pid = -1 denotes the root, then output the path from each node to the root.

Solution: Store the parent relationships in a dictionary and recursively climb to the root, collecting the path:

d = {
    "A": "-1",
    "A-1": "A",
    "A-2": "A",
    "A-3": "A",
    "A-2-1": "A-2",
    "A-2-2": "A-2",
    "A-2-3": "A-2"
}
res = []

def func(node):
    array.append(node[0])
    if node[1] == "-1":
        return
    func((node[1], d[node[1]]))

for i in d.items():
    array = []
    func(i)
    string = "/".join(array[::-1])
    res.append("/" + string)

for j in res:
    print(j)

Problem 3 (Classic): Find the minimum sum path from the top row to the bottom row of a matrix, moving only down, down‑left, or down‑right.

Solution: Use dynamic programming to accumulate the minimum cost for each cell:

array = [[1,8,5,2],
         [4,1,7,3],
         [3,6,2,9]]
x = len(array)
y = len(array[0])
dp = [[0 for _ in range(y)] for _ in range(x)]
for i in range(x):
    for j in range(y):
        if i == 0:
            dp[i][j] = array[i][j]
        elif j == 0:
            dp[i][j] = array[i][j] + min(dp[i-1][j], dp[i-1][j+1])
        elif j == y-1:
            dp[i][j] = array[i][j] + min(dp[i-1][j-1], dp[i-1][j])
        else:
            dp[i][j] = array[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])
print(min(dp[-1]))  # outputs the minimum path sum

The author reflects on the difficulty of these questions during the interview and shares the solutions for readers to study.