一次有趣的面試（上）

前言

春節結束之後就再沒有寫文章了，之前專欄的末尾也提到三月就開始準備實習春招（CV+DL方向）。從三月回到學校開始漫長的刷題，找內推，投遞簡歷，經歷緊張的面試到拿到offer。由於投遞的比較集中，所以大多數公司都集中在三月中下旬就結束了面試。所以那種緊張的氛圍也就維繫了二十來天，之後的四月到五月基本在玩加休息～

不過四五月，一些沒有內推的好公司也發來了面試邀請。由於玩耍了二十來天，幾場面試都表現的很糟糕。這篇文章就是記一個昨天的有趣的面試，主要講解面試過程中的一道題目。

這是一家CV界的王牌公司，因為沒有找到人內推，所以到四月末才預約了五月四號的面試。之前我已經經歷了大大小小十幾場的面試，感覺自己已經駕輕就熟，無論是coding向，還是項目向，都感覺比較熟悉了。但昨天的面試依然給我留下了深刻的印象。

熱身

面試官是一位非常年輕的小哥，上來表明身份後直接詢問有沒有紙筆，沒有讓我所謂自我介紹和寒暄。上來直接一道熱身的題目：

請計算0~6999中含7的數字？

大概1min不到我給了一個錯誤的答案，然後我認真算了一遍，又花了1min給出了正確答案：

（（9+10）×9+100）×7=1897

實際上在計算的過程中我大概意識到要用補集去算，但感覺這個數字也很小就直接遍歷算出來了。面試官聽完來了一句你算的挺快的啊，但是應該是用補集去算：

7000 - 7*9*9*9 = 1897

事後我覺得這兩個演算法寫成程序可能差別有點，但這麼小的範圍，心算真的沒差。其實面試很緊張，又想快又想準確，所以按前一個算也無可厚非，下次小哥可以搞大點，比如70000000以下的hhhh ~

熱身就這樣過去了。

題目1

熱身後馬上下一題：

設計一個演算法等概率取到單位球上的點？

說實話聽到這個題我是有點崩潰的，先表明，我投的都是CV + DL 的 research intern，這道題目給我第一感覺既不是 CV + DL 方向，也不是基礎的數據結構相關的演算法，所以我很懵逼。但我還是強做鎮定，感覺到沒想法還是要說點話，就給了如下的解法：

First try:

def sphere_1(radius): x = random.randint(-radius, radius) r = int(math.sqrt(radius ** 2 - x ** 2)) y = random.randint(-r, r) z = int(math.sqrt(radius ** 2 - x ** 2 - y ** 2)) if random.randint(0, 100) > 50: z = -z return [x, y, z]

小哥直接否定了我的答案，（OK我也知道不對，我是想要點提示啊～）

這裡解釋一下：題目要求是浮點數演算法，我為了畫圖，寫的是int，在上面的演算法中，我們可以看到絕對值越小的y值被選取的概率是明顯大一些的。然後它畫出來的圖是如下的：

左圖我們旋轉了球體可以清楚的看到赤道部分基本概率就很低了，所以也驗證了這個演算法明顯不對。這裡闡述一下如果是等概率均勻分布的，我們應該能夠在截面的任意一個圓環上看到是近似均勻分布的，而即使旋轉球體選擇一個看起來還不錯的截面如右圖，還是能明顯能看到這個截面是存在南北極的。

Second try:

天真的我覺得換一個坐標系可能能拯救我，馬上我又說了下一個：

def sphere_2(radius): theta = random.random()*2*math.pi alpha = random.random()*2*math.pi z = radius*math.sin(alpha) r_2 = radius**2 - z**2 x = math.sqrt(r_2)*math.cos(theta) y = math.sqrt(r_2)*math.sin(theta) return [int(x), int(y), int(z)]

小哥仔細分辨了一下，同樣否定了我的結果。反例：南北極點在所有的theta下都有概率會被取到（alpha=0 or pi）。而alpha的選取中，他們的選取概率和其他點也是等概率的，所以註定了他們的被選取到的概率也會大一些，我們可以得知越靠近南北極概率越大。

好吧我也馬上意識到這個也錯了。

畫一下看一看，不過好像是比上一個強一點把。

可以在左圖看到，如面試官小哥所說的，存在明顯的南北極。同時右圖可以看到，赤道的概率沒有上一個演算法那麼不堪，以致於出現明顯的鏤空。

Final Try:

我能感覺到小哥真的不打算給我提示，所以我只能硬著頭皮寫下去。思考了一陣子之後（我覺得可能5~10分鐘），我表示，我有一個明顯的不對的演算法，但我表示這是我能給出最接近的了，小哥表示讓我說說看。

def sphere_3_bad(radius): x = (random.random() - 0.5) * 2 * radius y = (random.random() - 0.5) * 2 * radius z = (random.random() - 0.5) * 2 * radius scale = math.sqrt((radius ** 2) / (x ** 2 + y ** 2 + z ** 2)) return [int(scale * x), int(scale * y), int(scale * z)]

小哥表示既然你也知道不對，可以再想想，整個面試大概已經持續了半小時了。其實這個的效果已經很好了，我也感覺就差一點。（恕我這個本碩EE的渣渣緊張的真的沒想起來蒙卡模擬，如果小哥說一句如何算複雜圖形面積，我可能馬上就能改出來了）。

最後我選擇了放棄，小哥表示有點可惜，告訴我只需要判斷一下選取的點是否在圓內，不在重新選一下就好了，效率也相對很高。（這個時候我已經想起了蒙卡模擬,好氣～）

看一下效果好了，左圖是bad的演算法，右圖是正確的演算法：

可以看到左圖bad的演算法在圓環是是存在明顯的不均勻的，對角線會密集，而與立方體的切線處則少一些，這個可以想像。而右圖正確的演算法在任意旋轉的截面下的任意選取的圓環都是很均勻的。

NEXT

之後時間還有剩餘小哥又出了一道更難的題目，可惜我真的玩的太久了加上自己太菜，也沒怎麼答出來。可以說是那種可能感覺到要用什麼方法然後結合提示已經確定了，但我完全沒信心自己能講清楚，最後時間到了也就結束了，下一題有機會再介紹把。所以我感覺這一面應該是掛掉了～之後有其他部門的面試官進行了一場比較細緻的項目面試，才感覺找回了一點場子。

補充

1. 如果面試官看到，覺得不合適透露題目，可以私信聯繫我刪除文章。之前面試記錄有很多很多但我都沒有發文，這個單純是因為覺得面試過程有趣～第二天就coding了一下～試驗了一下這次交流的成果，就算掛了也是有所收穫hhhhh。
2. 上面的畫圖工具是之前做肺結節比賽的時候用作可視化的工具，自己寫的一個python的介面，可以拖動旋轉圖像，下面是包含介面的正確答案全部源代碼有需求的可以自取。

from skimage import measurefrom mpl_toolkits.mplot3d.art3d import Poly3DCollectionimport matplotlib.pyplot as pltimport numpy as npimport randomimport mathdef plot_3d(image, threshold=-300): p = image.transpose(2, 1, 0) verts, faces = measure.marching_cubes(p, threshold) fig = plt.figure(figsize=(10, 10)) ax = fig.add_subplot(111, projection=3d) mesh = Poly3DCollection(verts[faces], alpha=0.70) face_color = [0.45, 0.45, 0.75] mesh.set_facecolor(face_color) ax.add_collection3d(mesh) ax.set_xlim(0, p.shape[0]) ax.set_ylim(0, p.shape[1]) ax.set_zlim(0, p.shape[2]) plt.show()def sphere_3(radius): x = radius y = radius z = radius while (x ** 2 + y ** 2 + z ** 2) > radius ** 2: x = (random.random() - 0.5) * 2 * radius y = (random.random() - 0.5) * 2 * radius z = (random.random() - 0.5) * 2 * radius scale = math.sqrt((radius ** 2) / (x ** 2 + y ** 2 + z ** 2)) return [int(scale * x), int(scale * y), int(scale * z)]if __name__ == "__main__": render_shape = 300 a = np.zeros([render_shape, render_shape, render_shape]) for i in range(5000): p = sphere_3(130) a[p[0]+render_shape/2, p[1]+render_shape/2, p[2]+render_shape/2] = 10 plot_3d(a, 0)

祝大家都能找到自己理想的工作 & 都能在工作里玩的開心 & 都能開心！

我輩不忘初心，方得始終，送大家一張我十年前的墨寶！（新的結尾圖片）