Python Interview Coding Problems: List Index Matching, Tree Traversal, and Minimum Path Sum Solutions

I recently attended an interview with a practical style, but due to personal and technical shortcomings I failed; I share my experience and the coding problems I faced.

1. Programming Question Trio

1.1 List Index Matching

The task: 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²). Using a hashmap for b achieves this.

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

1.2 Tree Traversal Reconstruction

The input consists of node identifiers and parent IDs (with -1 indicating the root). The goal is to reconstruct the path from each node to the root. The solution builds a dictionary of parent relationships and recursively traverses upward.

<code>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)
</code>

1.3 Minimum Path Sum (Dynamic Programming)

The problem requires finding the minimum sum from the top row to the bottom row of a matrix, moving only down or diagonally down. A DP table records the optimal sums.

<code>array = [[1,8,5,2],
         [4,1,7,3],
         [3,6,2,9]]
x = len(array)
y = len(array[0])
dp = [[0 for i in range(y)] for j 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]))
# 4
</code>

2. Other Interview Questions

Additional topics mentioned include transactions, clustered indexes, InnoDB primary key selection, and the relationship between RabbitMQ connections and channels.

Promotion

The article concludes with a QR code invitation to a free Python public course offering extensive learning materials such as e‑books, tutorials, project templates, and source code.