一亩三分地论坛

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

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

Youtube Onsite

[复制链接] |试试Instant~ |关注本帖
jack900001 发表于 2015-6-26 14:16:57 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 Onsite |Otherfresh grad应届毕业生

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

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

x
就要進 HC 了~ 趕緊來發個面經攢個 rp

Phone1
讓你完成一個 class 的幾個function. 鍥磋鎴戜滑@1point 3 acres

class AvgLatency{
   AvgLatency(List<String) methods, int window_size)
   double GetAvgLatency(String method)
   AddLatency(String method, int latency)
}

window_size , 如果 window = 3 當他要 average 的時候, 只有最近三個有效
每個 method 的 window_size 都設定一樣就可以
. 1point 3acres 璁哄潧
ex:
avgLatency({"GET","POST","DELETE"}, 3)
add("GET", 10)
add("GET", 6)
add("GET", 6).1point3acres缃
add("GET", 6)
GetAvgLatency("GET")  = 6
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Phone2
findGaps

[0, 1, 2, 50, 52, 75], n=100
3-49,51,53-74,76-99-google 1point3acres
. 1point 3acres 璁哄潧

Onsite. Waral 鍗氬鏈夋洿澶氭枃绔,
Round1 一個英國人,一個國人 shadow
UTF8 validation
http://codereview.stackexchange.com/questions/59428/validating-utf-8-byte-array. From 1point 3acres bbs

0xxxxxxx  single byte
10xxxxxx  continous byte
110xxxxx  2 bytes sequence
1110xxxx  3 bytes sequence
11110xxx  4 bytes sequence
111110xx  5 bytes sequence.鏈枃鍘熷垱鑷1point3acres璁哄潧
1111110x  6 bytes sequence
11111110  7 bytes sequence
11111111  8 bytes sequence. Waral 鍗氬鏈夋洿澶氭枃绔,

Valid    0xxxxxxx. visit 1point3acres.com for more.
Valid    110xxxxx 10xxxxxx.鐣欏璁哄潧-涓浜-涓夊垎鍦
Valid    1110xxxx 10xxxxxx 10xxxxxx
Valid    0xxxxxxx 110xxxxx 10xxxxxx 0xxxxxxx
invalid  10xxxxxx
invalid  110xxxxx 0xxxxxxx 10xxxxxx
invalid  110xxxxx

-google 1point3acres
Round2 韓國人
pattern 可以跨 strings, 但是必須要是連續的, 注意是 iterable, 所以是不能回頭的
我是 stringBuffer 去保存已經走過的部分, 如果不 match rewind 的時候就從 stringBuffer 裡面的 character 開始 check. from: 1point3acres.com/bbs
不夠再從 iterater 拿

boolean contains(String pattern, Iterable<String> strs)
ex:
pattern: "abc"
strs : "ab", "cd"  -> true
strs : "aa", "bcd" -> true
strs : "ab", "ac"  -> false


這一輪寫到最後一秒, 算是寫完了, 也跟他討論了一下複雜度
事後想想有個資料結構用錯, 導致答案會有問題, 估計跪就跪在這輪了
.鐣欏璁哄潧-涓浜-涓夊垎鍦
Lunch 也是個 韓國人, 八個月的菜鳥, 是個 Math major 美本 . 1point3acres.com/bbs

Round3 美國人-正妹姐姐
Symetric rotation number
boolean checkNum(String num)
ex: 16891 旋轉 180 以後還是 180
確認這個數有沒有符合這個規則

Follow Up: List<String> genNum(int len)

產生所有這個長度以下的所有組合
ex: len=3, {0,1,8,00,11,88,69,96,000,010,080,101,111,181,808,818,888,609,619,689,906,916,986}


Round4 美國人-小帥哥. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Leetcode: count islands

後面的 follow up 都是討論而已, 沒寫 code
Follow up: 如果是大地圖怎麼處理, 要你切 map, 考慮每個 submap 之間的關係
Follow up2: 平行化處理, 這個條件, 可能會讓你前面所想方法要重新思考

這時剩下15分鐘, 他就說再來個 follow up 好了 = =, 跟大圖無關, 一樣是 count island, 假設已經做了第一次的處理
Follow up3: 如果他現在要新增島到地圖上, 請回傳最新的 count
ex: int add(int x, int y), the function should return the new count

Follow up3.1 這個 function 能不能做到比 O(N*N) 還要好? (N為 map 邊長)



希望這些資訊能幫大家, 讓我自己讚讚人品, 希望明天 HC 有好結果!!!!!. 1point 3acres 璁哄潧

评分

1

查看全部评分

stellari 发表于 2015-6-27 02:50:26 | 显示全部楼层
jack900001 发表于 2015-6-27 01:46-google 1point3acres
Follow up3: 如果他現在要新增島到地圖上, 請回傳最新的 count.1point3acres缃
ex: int add(int x, int y), the function  ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
多谢分享,这个思路挺不错。

我也想了一种解法:

每个island以数字编号。比如地图最初看起来是这个样子的

1 1 0 0 2 2
1 1 1 0 2 2
1 1 0 0 0 2. visit 1point3acres.com for more.
0 0 0 3 0 0. 鍥磋鎴戜滑@1point 3 acres

其中0代表海洋,正整数代表陆地。-google 1point3acres

然后维护一个并查集(union-find set,抱歉这个我不知道这个词台湾是怎么翻译的),也就是一组互不重叠的set的集合:
{{1}, {2}, {3}}
.鏈枃鍘熷垱鑷1point3acres璁哄潧
当一个点被加入时,如果它不和任何一个岛屿相邻,则在并查集中加入一个新岛屿{{1}, {2}, {3}, {4}}

如果新加入的点有至少两个相邻岛屿,且不在同一个set之内,如1,2。这表示因为该点的加入,1,2被连接起来了,所以将1,2所在的set合并起来:{{1,2},{3},{4}}-google 1point3acres

如果这个点周围的相邻岛屿都在同一个set之内,则不做任何事。

任意时刻,并查集中set的个数即为当前的岛屿数。

这里面用到的两个操作:查找岛屿在哪个set中(find),合并两个岛屿(union)恰好是并查集必须支持的两个操作。

根据[url=https://en.wikipedia.org/wiki/Disjoint-set_data_structure
]这里[/url]的说法,查找和合并在极度优化的情况下都只需要O(a(n))时间,其中n是岛屿的数量,而a(n)是个增大非常非常慢的函数(当n = 宇宙中原子数目时, a(n)也不会超过5)。所以运行时间可以看做一个常数。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
.1point3acres缃
每个新插入的点最多只有4个相邻岛屿,每个岛屿的查找/合并都是常数,也就是说我们甚至可以在O(1)时间内完成add操作。


回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-6-26 17:36:08 | 显示全部楼层
谢谢分享,很详细的面经。楼主能否说一下Round 4的Follow up 3.1的思路?
回复 支持 反对

使用道具 举报

 楼主| jack900001 发表于 2015-6-27 01:46:24 | 显示全部楼层
Follow up3: 如果他現在要新增島到地圖上, 請回傳最新的 count
ex: int add(int x, int y), the function should return the new count

Follow up3.1 這個 function 能不能做到比 O(N*N) 還要好? (N為 map 邊長)

這題是最後剩下大概不到三分鐘的時候, 他問的, 這題我也沒想出來
最後結束的時候, 他有跟我說解法, 就是當初在 count islands 的時候把每個 island 都建成一顆 tree
所以再判斷新加上去的 island 周圍的時候, 只要判斷周圍的 island 是不是有 common ancestor O(lgN)
如果是分開的兩個島, 現在被新的島串起來了的話, 就將兩顆 tree 接起來就好
回复 支持 反对

使用道具 举报

tiantiana 发表于 2015-6-27 02:08:05 | 显示全部楼层
jack900001 发表于 2015-6-27 01:46
Follow up3: 如果他現在要新增島到地圖上, 請回傳最新的 count. from: 1point3acres.com/bbs
ex: int add(int x, int y), the function  ...
. from: 1point3acres.com/bbs
谢谢分享,bless!
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-7-5 07:49:20 | 显示全部楼层
谢谢楼主分享!麻烦楼主能不能说下Round2的题目,不是很明白,给定一个pattern,为什么会有以下的结果?谢谢啦!. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

pattern: "abc"
strs : "ab", "cd"  -> true
strs : "aa", "bcd" -> true
strs : "ab", "ac"  -> false
回复 支持 反对

使用道具 举报

 楼主| jack900001 发表于 2015-7-5 07:54:32 | 显示全部楼层
UmassJin 发表于 2015-7-4 15:49 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
谢谢楼主分享!麻烦楼主能不能说下Round2的题目,不是很明白,给定一个pattern,为什么会有以下的结果?谢 ...

The pattern could be across the given set of strings.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
只要他給的 pattern 在連續的 strings 可以組合起來成為 pattern string, return true

ex:
pattern: "horse"
strings: ["ah", "or", "settle"]
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-7-5 08:20:51 | 显示全部楼层
jack900001 发表于 2015-7-5 07:54.鐣欏璁哄潧-涓浜-涓夊垎鍦
The pattern could be across the given set of strings.
只要他給的 pattern 在連續的 strings 可以組 ...

好滴,明白啦,谢谢楼主!
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-5 09:03:26 | 显示全部楼层
感谢分享第一手经历!
想请教一下,一般Google、Facebook这样的顶级公司,是否要在五分钟内给出思路,十分钟内写出bugfree的代码才能让面试官给出满意的评价?
因为我从好些前辈那儿得到的经验,说碰见的面试题不会太难。因此你必须做到毫不费力,才能证明自己足够优秀。请问感受下来是这样吗?
回复 支持 反对

使用道具 举报

 楼主| jack900001 发表于 2015-7-5 09:29:44 | 显示全部楼层
zhuli19901106 发表于 2015-7-4 17:03
感谢分享第一手经历!
想请教一下,一般Google、Facebook这样的顶级公司,是否要在五分钟内给出思路,十分 ...

我分享一下我的個人經驗, 我面試的職位是 University Graduate

第一關的 UTF8 validation
一開始真的很緊張, 我跌跌撞撞地想出一個算法, 我用了 shift 和 counter 不算是什麼 clean code, 但 at least 給出一個解法, 這關表現平平

第二關的 pattern matching. From 1point 3acres bbs
我花了很長的時間跟他解釋我的算法, 到最後寫的時間不太夠, 到最後才發現我的算法有個錯誤, 會導致最後的答案有誤

你前輩的經驗沒錯, 題目都不會算太難, 都是考些基本的算法和解題能力, 我只有真的後兩關才真的算是答得得心應手, 我認為面試的重點不一定要 "豪不費力", 但必須要隨時保持你思路的清晰, 能夠自己分析自己的算法, 自己找出自己算法的盲點, 當你能夠清晰的表達你的算法, 不是胡言亂語的時候, 面試官通常都會給你足夠的提示讓你找出盲點。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
最後的建議 "Be confident", 在解題的時候把你所想清楚的表達出來。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-5 09:52:28 | 显示全部楼层
jack900001 发表于 2015-7-5 09:29
我分享一下我的個人經驗, 我面試的職位是 University Graduate

第一關的 UTF8 validation

非常感谢!
我会好好磨练的,祝前辈前程似锦~
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-5 13:40:33 | 显示全部楼层
data structure 台湾是叫资料结构哦? thanks for sharing!
回复 支持 反对

使用道具 举报

daisywr 发表于 2015-10-19 23:05:32 | 显示全部楼层
如果是大地圖怎麼處理, 要你切 map, 考慮每個 submap 之間的關係. 楼主能讲讲什么意思咩
回复 支持 反对

使用道具 举报

 楼主| jack900001 发表于 2015-10-20 00:52:18 | 显示全部楼层
daisywr 发表于 2015-10-19 07:05
如果是大地圖怎麼處理, 要你切 map, 考慮每個 submap 之間的關係. 楼主能讲讲什么意思咩
. more info on 1point3acres.com
當整張地圖的資訊無法一次處理, 必須要分批處理的時候, 你可以想象就是 google map 這樣的 scale, 你要如何 count islands?
How do you divide the map? How do you optimize your algorithm on memory or time complexity?
回复 支持 反对

使用道具 举报

maplain 发表于 2015-10-25 22:15:31 | 显示全部楼层
jack900001 发表于 2015-7-5 07:54
The pattern could be across the given set of strings.
只要他給的 pattern 在連續的 strings 可以組 ...

这个题目把所有iterator里面的string连起来,用一个KMP是不是就可以?
回复 支持 反对

使用道具 举报

 楼主| jack900001 发表于 2015-10-28 08:44:01 | 显示全部楼层
maplain 发表于 2015-10-25 06:15. From 1point 3acres bbs
这个题目把所有iterator里面的string连起来,用一个KMP是不是就可以?

Simple answer, yes.. 1point3acres.com/bbs

但如果不能全部串起來呢?restricted memory
回复 支持 反对

使用道具 举报

maplain 发表于 2015-10-28 09:35:54 | 显示全部楼层
jack900001 发表于 2015-10-28 08:44 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Simple answer, yes.. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

但如果不能全部串起來呢?restricted memory

分段做,比如模板串长度为m,目标长度为分段读入内存,每段长度为n;n远大于m。如果第一段目标串没有匹配,那么滑动到下一段目标串时候做一点小改动。取前一段末尾m-1加上下一段的n-(m-1)组成第二段目标串,这样复杂度是O(m+N/(n-m+1)*n)。因为n>>m,所以约等于O(m+N)。N为目标串总长度。
不知道对不对,上一次看KMP算法了还在本科。。。
回复 支持 反对

使用道具 举报

bensvage1989 发表于 2015-11-7 01:10:53 | 显示全部楼层
弱弱的问一句,Round4的第一次follow up 让你切map,考虑submap之间的关系, LZ是怎么说的,求思路
回复 支持 反对

使用道具 举报

djjkobe 发表于 2015-11-8 07:57:07 | 显示全部楼层
楼主最后拿到offer了吗?
回复 支持 反对

使用道具 举报

richardzrc 发表于 2015-11-15 21:54:44 | 显示全部楼层
  1. class NumIslands2 {
  2. public:
  3.   unordered_map<int, int> fa;
  4.   int cnt;
  5.   int m , n;
  6.   int di[4] = {-1, 1, 0 , 0}, dj[4] = {0,0,-1,1};
  7.   int Find(int x) {
  8.     if(fa[x]==-1) return x;
  9.     return fa[x] = Find(fa[x]);
  10.   }
  11.   vector<int> numIslands2(int m_, int n_, vector<pair<int, int>>& ps) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  12.     m = m_, n = n_;
  13.     fa.clear();
  14.     cnt = 0;
  15.     vector<int> ans;
  16.     for(auto e: ps) {
  17.       int key = e.first * n + e.second;
  18.       fa[key]=-1;
  19.       cnt++;. 1point3acres.com/bbs
  20.       for(int k = 0; k < 4; k++) {
  21.         int ni =di[k] + e.first, nj = dj[k] + e.second;
  22.         if(outrange(ni, nj)) continue;
  23.         int newkey = ni * n + nj;
  24.         if(!fa.count(newkey)) continue;
  25.         int root0 = Find(key), root1 = Find(newkey);
  26.         if(root0!=root1) {.1point3acres缃
  27.           fa[root0]=root1;
  28.           cnt--;. From 1point 3acres bbs
  29.         }
  30.       }
  31.       ans.push_back(cnt);
  32.     }
  33.     return ans;
  34.   }
  35.   bool outrange(int i, int j) {
  36.     return i<0 || i>=m || j< 0 || j>=n;.1point3acres缃
  37.   }
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  38. };
复制代码


4.3Follow up 大概是这样吧。并查集,但是时间复杂度 好难算啊,Find说是当成alpha函数的反函数,基本是常数

话说onsite Prob2,即使不暴力,最坏也要回溯到头,StringBuffer也要存下所有,这个和暴力没啥区别吧,而且暴力好写,确实面试官不让全部append然后kmp么
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 05:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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