《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 8105|回复: 24
收起左侧

Youtube Onsite

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

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

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

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

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

. from: 1point3acres.com/bbs Phone1
讓你完成一個 class 的幾個function

class AvgLatency{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
   AvgLatency(List<String) methods, int window_size)
   double GetAvgLatency(String method)
   AddLatency(String method, int latency). from: 1point3acres.com/bbs
}

window_size , 如果 window = 3 當他要 average 的時候, 只有最近三個有效
每個 method 的 window_size 都設定一樣就可以

ex:
avgLatency({"GET","POST","DELETE"}, 3)
add("GET", 10)
add("GET", 6). visit 1point3acres.com for more.
add("GET", 6)
add("GET", 6)
GetAvgLatency("GET")  = 6

Phone2
findGaps. from: 1point3acres.com/bbs

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


Onsite. from: 1point3acres.com/bbs
Round1 一個英國人,一個國人 shadow. more info on 1point3acres.com
UTF8 validation
http://codereview.stackexchange.com/questions/59428/validating-utf-8-byte-array

0xxxxxxx  single byte
10xxxxxx  continous byte
110xxxxx  2 bytes sequence
1110xxxx  3 bytes sequence
11110xxx  4 bytes sequence
111110xx  5 bytes sequence
1111110x  6 bytes sequence. visit 1point3acres.com for more.
11111110  7 bytes sequence
11111111  8 bytes sequence

Valid    0xxxxxxx
Valid    110xxxxx 10xxxxxx
Valid    1110xxxx 10xxxxxx 10xxxxxx
Valid    0xxxxxxx 110xxxxx 10xxxxxx 0xxxxxxx
invalid  10xxxxxx. 1point 3acres 璁哄潧
invalid  110xxxxx 0xxxxxxx 10xxxxxx
invalid  110xxxxx


Round2 韓國人.鏈枃鍘熷垱鑷1point3acres璁哄潧
pattern 可以跨 strings, 但是必須要是連續的, 注意是 iterable, 所以是不能回頭的
我是 stringBuffer 去保存已經走過的部分, 如果不 match rewind 的時候就從 stringBuffer 裡面的 character 開始 check
不夠再從 iterater 拿

boolean contains(String pattern, Iterable<String> strs). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
ex: .1point3acres缃
pattern: "abc"
strs : "ab", "cd"  -> true 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
strs : "aa", "bcd" -> true
strs : "ab", "ac"  -> false


這一輪寫到最後一秒, 算是寫完了, 也跟他討論了一下複雜度
事後想想有個資料結構用錯, 導致答案會有問題, 估計跪就跪在這輪了

Lunch 也是個 韓國人, 八個月的菜鳥, 是個 Math major 美本
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Round3 美國人-正妹姐姐
Symetric rotation number
boolean checkNum(String num)
ex: 16891 旋轉 180 以後還是 180
確認這個數有沒有符合這個規則. from: 1point3acres.com/bbs

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. 1point 3acres 璁哄潧
ex: int add(int x, int y), the function should return the new count

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


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

评分

1

查看全部评分

bobzhang2004 发表于 2015-12-7 13:06:23 | 显示全部楼层
写了下找pattern的代码,每次只保存以前str的pattern - 1个字母,欢迎指教
  1.         static boolean contains(String pattern, Iterable<String> strs) {
  2.                 StringBuilder sb = new StringBuilder();
  3.                 while (strs.iterator().hasNext()) {
  4.                         String str = strs.iterator().next();
  5.                         sb.append(str);. more info on 1point3acres.com
  6.                         if (sb.length() >= pattern.length()) {
  7.                                 if (containsHelper(sb.toString(), pattern)) {
  8.                                         return true;
  9.                                 }
  10.                                 int end = sb.length() - pattern.length() + 1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.                                 sb.delete(0, end);
  12.                         }
  13.                 }
  14.                 return false;
  15.         }

  16.         private static boolean containsHelper(String haystack, String needle) {

  17.                 if (haystack == null || needle == null) {
  18.                         return false;
  19.                 }
  20.                 int m = haystack.length();
  21.                 int n = needle.length();
  22.                 for (int i = 0; i < m - n + 1; i++) {
  23.                         int j = 0;
  24.                         for (; j < needle.length(); j++) {-google 1point3acres
  25.                                 if (haystack.charAt(i + j) != needle.charAt(j)) {
  26.                                         break; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  27.                                 }
  28.                         }
  29.                         if (j == needle.length()) {
  30.                                 return true;
  31.                         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  32.                 }

  33.                 return false;
  34.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-6-27 02:50:26 | 显示全部楼层
jack900001 发表于 2015-6-27 01:46
Follow up3: 如果他現在要新增島到地圖上, 請回傳最新的 count
ex: int add(int x, int y), the function  ...
. 鍥磋鎴戜滑@1point 3 acres
多谢分享,这个思路挺不错。
. Waral 鍗氬鏈夋洿澶氭枃绔,
我也想了一种解法:

每个island以数字编号。比如地图最初看起来是这个样子的
. From 1point 3acres bbs
1 1 0 0 2 2
1 1 1 0 2 2
1 1 0 0 0 2
0 0 0 3 0 0

其中0代表海洋,正整数代表陆地。

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

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

如果这个点周围的相邻岛屿都在同一个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)。所以运行时间可以看做一个常数。

每个新插入的点最多只有4个相邻岛屿,每个岛屿的查找/合并都是常数,也就是说我们甚至可以在O(1)时间内完成add操作。

. Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 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 邊長). 1point 3acres 璁哄潧

這題是最後剩下大概不到三分鐘的時候, 他問的, 這題我也沒想出來
最後結束的時候, 他有跟我說解法, 就是當初在 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. more info on 1point3acres.com
ex: int add(int x, int y), the function  ...
-google 1point3acres
谢谢分享,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. Waral 鍗氬鏈夋洿澶氭枃绔,

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
感谢分享第一手经历!.1point3acres缃
想请教一下,一般Google、Facebook这样的顶级公司,是否要在五分钟内给出思路,十分 ...
. visit 1point3acres.com for more.
我分享一下我的個人經驗, 我面試的職位是 University Graduate

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

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

你前輩的經驗沒錯, 題目都不會算太難, 都是考些基本的算法和解題能力, 我只有真的後兩關才真的算是答得得心應手, 我認為面試的重點不一定要 "豪不費力", 但必須要隨時保持你思路的清晰, 能夠自己分析自己的算法, 自己找出自己算法的盲點, 當你能夠清晰的表達你的算法, 不是胡言亂語的時候, 面試官通常都會給你足夠的提示讓你找出盲點。. 1point 3acres 璁哄潧

最後的建議 "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 之間的關係. 楼主能讲讲什么意思咩

當整張地圖的資訊無法一次處理, 必須要分批處理的時候, 你可以想象就是 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 可以組 ...
. 1point3acres.com/bbs
这个题目把所有iterator里面的string连起来,用一个KMP是不是就可以?
回复 支持 反对

使用道具 举报

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

Simple answer, yes.. from: 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 {. 1point3acres.com/bbs
  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();. 1point3acres.com/bbs
  14.     cnt = 0;
  15.     vector<int> ans;
    . 1point3acres.com/bbs
  16.     for(auto e: ps) {
  17.       int key = e.first * n + e.second;
  18.       fa[key]=-1;
  19.       cnt++;
  20.       for(int k = 0; k < 4; k++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  21.         int ni =di[k] + e.first, nj = dj[k] + e.second;. more info on 1point3acres.com
  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) {
  27.           fa[root0]=root1;
  28.           cnt--;
  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;. 鍥磋鎴戜滑@1point 3 acres
  37.   }
  38. };
复制代码

鏉ユ簮涓浜.涓夊垎鍦拌鍧.
4.3Follow up 大概是这样吧。并查集,但是时间复杂度 好难算啊,Find说是当成alpha函数的反函数,基本是常数

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-25 10:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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