Google 第一題應該是 Graph 的概念 共有1000個點 (0 ~ 999) 每個點的 neighbor 是相差一個 distance 的其他數字 目標是要找出 Hamilton Circuit def gen_neighbor(n, num): '''得到一個list包含num的鄰點。 例如 num=111 時，傳回值為 [110, 112, 101, 121, 11, 211] ''' neighbor = [] for digit in range(n): factor = 10 ** digit d = (num // factor) % 10 if d > 0: neighbor.append(num - factor) if d < 9: neighbor.append(num + factor) return neighbor def find_path(start, visited, n): '''從起點start開始，找鄰點加入visited，直到全部點都加入為止。 ''' visited_set = set(visited) max_size = 10 ** n while True: for n in adjlist[start]: if n not in visited_set: visited.append(n) visited_set.add(n) start = n break if len(visited) == max_size: break return visited n = 3 adjlist = [gen_neighbor(n, i) for i in range(10 ** n)] path = find_path(0, [0], n) 完整的 Hamilton Circuit 要考慮當 find_path 無法加入全部點時，要如何處理。 但在這個例子中，總是可以加入全部點，所以不需要處理。 ※ 引述《changyuheng (Henry)》之銘言： : 我也是中央在學，貢獻 Google 第一題：http://bit.ly/2qn4iHE : 第二題我會說每一個二分點都測 m 次，最後再實際測試比對結果。 : O(mn) : θ(m log n) : ※ 引述《william45682 (QQQQQQ)》之銘言： : : --- : : Google : : 有投一個google 履歷不過連面試都沒面試就被reject了 = =…(難過QQ : : 不過我強者同學的第一階段心得 : : 假設現在給你一個n 代表有幾位數 : : 然後 說 假設n為3好了 代表有000~999這1000個數字 : : 然後現在要把這1000個數字排序 : : 排序規則是 兩個數字之前 的distance差1 : : 兩個數字的distance是指 兩個數字拿起來比對 不一樣的那幾位數相差的總和 譬如說 111 跟 222 distance 是3 111 113 distance 是 2 111 011 distance是1 : : 給出一組合法的排序 : : 然後第二題是 用git的時候會有很多commit 假設現在的code是壞的 前面有n個commit你需要找出哪個commit後面壞掉了 你可以選擇詢問任一個commit 他會回答你是好的還是壞的 這個很簡單 二分搜就好 但是現在題目是 如果你問他 他是好的他就會回答你是好的 他是壞的 有50%機率回是好的 50%機率回是壞的 : : 電話面試， 他叫我打code在 google雲端上 : : 整個過程大概45分鐘 : : 因為是工程師面所以比較多問的是技術問題 像是前面問我有沒有遇過甚麼有趣的題目之類的 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.127.245.66 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Soft_Job/M.1496258013.A.0E4.html