Re: [心得] 實習面試心得(微軟、BenQ、Dcard)

看板Soft_Job (軟體人)作者banyhong (=_=)時間7年前 (2017/06/01 03:13)推噓3(3推 0噓 7→)

留言10則, 5人參與討論串4/4 (看更多)

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://www.ptt.cc/bbs/Soft_Job/M.1496258013.A.0E4.html