Google Technical phone interview 11/9

面試就2關，各45分鐘。第一關，印度人，有點口音，又透過電話，我好幾次忽然不知道他說了啥。
考題是Longest Substring with At Most m Distinct Characters
其實這題算有難度！Leetcode上有類似的題目，就叫"Longest Substring with At Most Two Distinct Characters"，難度被列為Hard
基本上一開始想到就是用 sliding window 法，用兩個 pointers 去記錄 substring 的 begin 和 end indices；可惜最後還是有小bug 因為緊張得腦袋空白而沒de出來。
他還建議我variable name不要取太 general，邊coding時要邊告訴對方自己現在在寫的是什麼功能，他才有辦法follow (如果心中有解的話我可以，但現在是連解都還在想，我真的也不知道能講什麼)
不過他倒是有說我approach 的方向是對的。
第一關就這麼鳥的結束了，有bug，不知道會被扣多少分。
第二關，白人，很nice，大概知道我會緊張，還蠻有耐心在帶我、解說。
他要我implement 一個 moving average的 class，做以下的事：
1. constructor時設定一個window size = k
2. insert(x)
3. avg() 取最後 k 個數的平均
當然要問一下time/space complexity
一開始我直覺的先建一個

您好！
本帖隐藏的内容需要积分高于 133 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 133 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

space complexity我只想到是 O(n)，因為我認為所有data都要留；不過後來結束後再想，如果沒有delete operation，其實根本只需要 O(k) 的空間記錄最後k個值就夠了；反正太舊的值也不會再用到。
接著開始考follow up：
1. testing，有哪些cases是我們可以test驗證code正確的？我想到的有，negative values, k <= 0, overflow；negative values基本上不會有問題，k<=0 可以用exception解，overflow在python下也不會是問題
2. concurrent execution, 如果多個 threads同時run這個code，會有race condition嗎？(會) 可以用什麼解? (mutex或 semaphore) 所以要lock哪個部分? (insert 算總和的部分要lock住，確保它是 atomic)
45分鐘又到了，就這樣。

lz面的是software还是data？

caffery24 发表于 2015-11-10 06:45
lz面的是software还是data？

software engineer intern

tyge318 发表于 2015-11-10 07:33
software engineer intern

明天中午面。。。好紧张，害怕碰到阿三听不懂题目。想问下lz又问你os的题目吗？我是转专业，基础比较薄弱

caffery24 发表于 2015-11-10 07:37
明天中午面。。。好紧张，害怕碰到阿三听不懂题目。想问下lz又问你os的题目吗？我是转专业，基础比较薄弱

同明天中午面，加油！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

tyge318 发表于 2015-11-10 07:49
OS嗎？講到 concurrent execution 就跟 OS 相關啦！Inter-Process Communication 本來就是 OS最愛考的主 ...

只是概念吗？会让你动手写一个什么吗？

caffery24 发表于 2015-11-10 08:40
只是概念吗？会让你动手写一个什么吗？

以我的例子，就是你需要lock住data，所以問你 lock 和 unlock 要在code 的哪裡做。

tyge318 发表于 2015-11-10 10:42
以我的例子，就是你需要lock住data，所以問你 lock 和 unlock 要在code 的哪裡做。

好的，多谢楼主，我抱抱佛脚。转专业好害怕问很基本的东西。。。