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

[banyhong (=_=)]

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
推 FRAXIS: 為什麼要把一個簡單問題 reduce 到一個 NPC 問題？
推 lNishan: 同上 ...
→ banyhong: 因為執行速度快、而且好理解(對我而言)
推 changyuheng: 請問執行速度快是跟什麼做比較？可以麻煩說明時間複
→ changyuheng: 雜度嗎？
→ wendly777: 感覺要是隨機找鄰居的話，可能沒辦法一刀劃，很可能會
→ wendly777: 自己卡自己，還是需要處理，你能跑完應該是在genAdjace
→ wendly777: ncyList時, 剛好用到了某個會跑完的規則
→ wendly777: 我分析這題，從最低維度的先找，找不到鄰居，再依次提
→ wendly777: 高維度找，剛好是一個能解決問題的貪婪法