聊聊我的一次真實 Python 面試經歷頭條網

聊聊我的一次真實 Python 面試經歷

2021-04-08 20:19:15 佚名

優質文章，第一時間送達！

作者：SyntaxError

出處：
segmentfault.com/a/1190000022455160

首先我挺喜歡這家公司的面試風格的，也是比較務實的吧。無奈自己的心理因素和技術水平都不好，導致面試失敗。再接再厲吧

1.一上來就是編程題三連

1.1 大概意思就是：倆列表a b，如果a中的元素在b中，那麼就保存此元素在a中的索引值，最後統一輸出所有索引值。要求：時間複雜度小於O(n)

這個我當時想到的是循環遍歷a，然後判斷是否i in b，但是這個時間複雜度是O(n2)，GG。最後面試官提醒了我一下hashmap，瞬間捶胸頓足……。最後自己想了一下，可以將b先轉成字典，然後再使用in。

<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 如圖，輸入為這樣，輸出為那樣，寫吧……

輸入幾組數據，pid為-1的代表根節點。如果數據為非根節點，那麼就要搜索此節點直至找到根節點。

這個其實我知道考的是樹的遍歷，但是沒見過這種形式的題，要自己構建輸入數據的形式，一下子就懵了，再加上面試官在那一直盯著……唉，承認自己能力不足吧。後續自己寫了一遍，大家可以看一下，有問題直接下面評論就可以。

<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 這個題太經典了。最短路徑和。

要注意是從第一行走到最後一行，而且只能向下或者斜向下走（我當時沒看清就寫，寫成了從左上走到右下……）。我這裡寫的是動態規劃的解法。Leetcode上有原題，解法不唯一。

<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)]
# 遍歷順序是每行內的每列。所以遍歷array中第一行只執行到if，dp中第一行就確定了，然後再確定dp第二行。
# 要注意兩個邊界條件
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
])

# [[1, 8, 5, 2],
# [5, 2, 9, 5],
# [5, 8, 4, 14]]
print(min(dp[-1]))
# 4
/<code>