第一輪ABC小姊姊跟華人小姊姊
一上來輪流問了簡歷還有 why bb
第一題就是簡單的DFS
就是給你兩個機場 要從機場A飛到機場B 還有一堆不同機場間的班機 要print出機場A飛到機場B的所有路徑
題目不難 但花了巨多的間在跑test case LZ用電腦打扣 但他們不要電腦run用手動run code 導致第一題寫完根本沒剩多少時間
第二題是裡扣妻散舅
LZ一開始忘了怎麼寫 只給出個O(n^2)暴力解 小姊姊叫我打暴力解的扣後突然想了起來 就用白板解釋一下算法就草草結束了
第二輪一個美國大叔跟歐洲小哥
也是輪流問了簡歷還有why bb 美國大叔還說我認識有人在你實習工作的公司 你這產品我沒聽過 是新的嗎？
第一題是shuffle linked list
給你一個linkedlist 先把他切成兩半 然後再把兩個merge成一個linkedlist merge時要random從第一個拿或從第二個拿 但merge後在原本在同個linkedlist的元素順序不變
寫扣期間大叔不斷的打斷我 光一開始把linkedlist切一半這段就問了五六個問題 具體忘了 一直說這段扣需要嗎我們是不是可以優化
或是表達對shuffle的定義的質疑 隨機從兩個linkedlist拿是對的嗎 是不是要按照剩餘多少元素的比例去求機率 不否認大叔提出的點都很精確 只是體驗不是很好
最後問了我一個致命的問題 說要shuffle幾次我們才可以保證所有元素是隨機的 LZ就隨口答了log n次 說我也不知道為什麼 有沒有人可以跟我說答案是什麼？
test case:
1 -> 2-> 3 -> 4 -> 5 -> 6
可以變成 1 -> 2 -> 3 -> 4 -> 5 -> 6 或 1 -> 2 -> 4 -> 3 -> 5 -> 6 或 4 -> 5 -> 6 -> 1 -> 2 -> 3 但就是不能變成 1 -> 3 -> 2 -> 4 -> 5 -> 6
第二題是bank hours and transaction hours
給定一堆銀行開門的interval 數字都在0-24之間代表hour 問給定的trasaction interval可不可以被執行 可以被執行的定義就是在這transacion裡面任意時間都要有銀行開門
解法就是先sort and merge bank hours interval 然後在這interval binary search到小於等於transaction開始時間 然後確定interval結束時間是否cover transaction結束時間
最後小哥問了兩個follow up
第一個是如果interval開始時間大於結束時間怎麼處理 也就是說這間銀行開門時間或是transaction時間跨過了半夜
第二個是怎麼設計class 假設bank hours變動很少但query次數很多要怎麼讓這個query更快 也就是這個查詢不用每次都merge bank hours interval
test case:
bank hours: [4, 7] [21, 3] [8, 11] [10, 15] transaction: [6, 9] return false, [9, 13] return true, [22, 1] return true, [20, 1] return false
最後等了十幾分鐘被hr送下樓 下樓前還帶我去拿了零食水果
隔天中午在機場收了拒信
因為學校地點關係要當天要回到學校最晚的飛機是五點 我就稍微提一下說是不是太趕 後來BB就提供LZ兩晚飯店
不過五點對於兩輪遊倒是綽綽有餘了呢hhhhhh
anyway move on