一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1462|回复: 8
收起左侧

Google Technical phone interview 11/9

[复制链接] |试试Instant~ |关注本帖
tyge318 发表于 2015-11-10 04:51:45 | 显示全部楼层 |阅读模式

2016(7-9月) 分析|数据科学类 硕士 实习@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
面試就2關,各45分鐘。第一關,印度人,有點口音,又透過電話,我好幾次忽然不知道他說了啥。
考題是Longest Substring with At Most m Distinct Characters-google 1point3acres
其實這題算有難度!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,大概知道我會緊張,還蠻有耐心在帶我、解說。. from: 1point3acres.com/bbs
他要我implement 一個 moving average的 class,做以下的事:
1. constructor時設定一個window size = k
2. insert(x)
3. avg() 取最後 k 個數的平均
當然要問一下time/space complexity
一開始我直覺的先建一個 array 用來存所有insert的值,avg再用sum(array[-k:])/float(k) 的方式來解,time complexity: insert = O(1), avg = O(k);space complexity = O(n).鐣欏璁哄潧-涓浜-涓夊垎鍦
後來他點我一下,我改成用一個變數記錄最後k個數的sum,在insert的時候就順便算這個值(未滿k個數時,累加即可;超過k時,每加一個值要扣掉最舊的值), avg和insert的time complexity可以達 O(1)
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分鐘又到了,就這樣。.鐣欏璁哄潧-涓浜-涓夊垎鍦

评分

1

查看全部评分

本帖被以下淘专辑推荐:

caffery24 发表于 2015-11-10 06:45:21 | 显示全部楼层
lz面的是software还是data?
回复 支持 反对

使用道具 举报

 楼主| tyge318 发表于 2015-11-10 07:33:26 | 显示全部楼层
caffery24 发表于 2015-11-10 06:45
lz面的是software还是data?

software engineer intern
回复 支持 反对

使用道具 举报

caffery24 发表于 2015-11-10 07:37:19 | 显示全部楼层
tyge318 发表于 2015-11-10 07:33
software engineer intern
.鏈枃鍘熷垱鑷1point3acres璁哄潧
明天中午面。。。好紧张,害怕碰到阿三听不懂题目。想问下lz又问你os的题目吗?我是转专业,基础比较薄弱
回复 支持 反对

使用道具 举报

Jaden 发表于 2015-11-10 07:41:26 | 显示全部楼层
caffery24 发表于 2015-11-10 07:37. 1point3acres.com/bbs
明天中午面。。。好紧张,害怕碰到阿三听不懂题目。想问下lz又问你os的题目吗?我是转专业,基础比较薄弱
-google 1point3acres
同明天中午面,加油!
回复 支持 反对

使用道具 举报

 楼主| tyge318 发表于 2015-11-10 07:49:41 | 显示全部楼层
caffery24 发表于 2015-11-10 07:37
明天中午面。。。好紧张,害怕碰到阿三听不懂题目。想问下lz又问你os的题目吗?我是转专业,基础比较薄弱

OS嗎?講到 concurrent execution 就跟 OS 相關啦!Inter-Process Communication 本來就是 OS最愛考的主題(其實會考也就它了,其它也很難延伸到),Google寄的 Preparation Guide 也有提到像 deadlock, mutex, context switching 這些觀念要熟悉。
回复 支持 反对

使用道具 举报

caffery24 发表于 2015-11-10 08:40:24 | 显示全部楼层
tyge318 发表于 2015-11-10 07:49. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
OS嗎?講到 concurrent execution 就跟 OS 相關啦!Inter-Process Communication 本來就是 OS最愛考的主 ...

只是概念吗?会让你动手写一个什么吗?
回复 支持 反对

使用道具 举报

 楼主| tyge318 发表于 2015-11-10 10:42:28 | 显示全部楼层
caffery24 发表于 2015-11-10 08:40
只是概念吗?会让你动手写一个什么吗?
. 鍥磋鎴戜滑@1point 3 acres
以我的例子,就是你需要lock住data,所以問你 lock 和 unlock 要在code 的哪裡做。
回复 支持 反对

使用道具 举报

caffery24 发表于 2015-11-10 10:48:45 | 显示全部楼层
tyge318 发表于 2015-11-10 10:42.鐣欏璁哄潧-涓浜-涓夊垎鍦
以我的例子,就是你需要lock住data,所以問你 lock 和 unlock 要在code 的哪裡做。

好的,多谢楼主,我抱抱佛脚。转专业好害怕问很基本的东西。。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 01:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表