一亩三分地论坛

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

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

G家onsite 8/8

[复制链接] |试试Instant~ |关注本帖
low910411 发表于 2016-8-19 01:25:14 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
[size=14.6667px]昨天收到拒信,来贴面筋~. visit 1point3acres.com for more.
1.白人小哥,判断一个matrix是不是这种形式:
从左上到右下的斜线上数字相同,并且matrix要是正方形,比如
1,5,3,4
0,1,5,3
9,0,1,5
2,9,0,1
Follow up: 假如matrix太大了,不能全部存在内存里,一次只能读一部分怎么办

2.白人大哥,有这样的一个List,list里面有好几个item:比如[(1,2,3), (1,2), (2,4), (2)]里面有4个item,每个item有一些数字(无duplicate)
把他partition,并且,分成的份数最少,规则是,他们必须要有相同的元素才能在一份中,比如这个例子可以分成:
[[(1,2,3), (1,2,),(2)], [(2,4)]] 或者[[(1,2,3), (1,2,)], [(2),(2,4)]] 都是分成了两份。

3. 白人大叔,给你一个新的字母顺序规则,比如ole 表示o后面才可以出现l, l后面才可以出现 e.
给你一个string,满足这个字母顺序的的话返回true 否则返回false,不在这个规则顺序中的字母可以忽略. 就是说除了ole其他字母都不用管。
. visit 1point3acres.com for more.
比如如下的string:
Google 返回 true
Elle 返回false(因为l有出现在e的后面)

Follow up 假设现在 这个string特别大,每台机器有一部分这个string,怎么处理

4.国人小哥
题目一:
给你一个 String和一个数字max,比如:
“happy new year new year”           max =2
Max表示最长的可以有几个单词(要是在string中连续的单词)。返回所有的可能单词和次数
这个例子返回:

happy 1
new 2
year 2
happy new 1
new year 2
year new 1


题目2:
两个string,第二个比第一个多一个字母,找出这个字母。
比如 string1: abcd   string2 abecd   得出e

题目不知道解释的清不清楚,如果大家有疑问在楼下问我~ 另外求问各位大神,因为感觉和面试官交流还可以,题目都有给出比较不错的解,hr在拿到面试官的reviews后说looks positive。但是hc没有过。hr也没有说原因。可能是哪些方面还需加强呢?谢谢大家啦~~~


鏉ユ簮涓浜.涓夊垎鍦拌鍧.




补充内容 (2016-8-19 04:16):
我的思路在第三楼~ 欢迎讨论~
-google 1point3acres
补充内容 (2016-8-19 05:08):
.鏈枃鍘熷垱鑷1point3acres璁哄潧第二题没解释清楚,A和B要是包含关系,才可以在一份里。比如(1,2,4)和(1,2)在一份里。(1,2,4)和(1,5)不在一份里。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

randrand1 发表于 2016-8-19 04:58:33 | 显示全部楼层
4.2的思路估计是因为string1和string2比起来只差一个字符,那么string1+string2加起来的字符串里面只有一个字符出现了奇数次,那么XOR出来的就是那个字符
回复 支持 2 反对 0

使用道具 举报

lovelysier613 发表于 2016-8-20 02:10:16 | 显示全部楼层
phantom 发表于 2016-8-20 01:39
两个String没说顺序一样啊。。。你用二分做是要他能保证第一个string和第二个string相同的部分顺序一样才 ...

就算顺序一样,如果这样怎么办:“aaaaa" vs "aaaaba",比中间还是不知道往哪边走
回复 支持 2 反对 0

使用道具 举报

chenzhan171 发表于 2016-8-19 14:32:47 | 显示全部楼层
hyj143 发表于 2016-8-19 07:35
所以4.2 有人想到用二分了么
. 1point 3acres 璁哄潧
正解, 这题确实二分最快
回复 支持 1 反对 1

使用道具 举报

lovelysier613 发表于 2016-8-19 14:08:27 | 显示全部楼层
1.2 不需要hashmap,记住上一行的结果,当循环array用,挪一位跟下一行直接比就好;
2. 感觉答案很漂亮,不需要unionfind
3. 回答的也很好. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
4.2. 这是leetcode所有数出现两次except一个数只出现一次那题几乎原题呀。把所有数异或一次,异或结果就是你要的结果。
回复 支持 1 反对 0

使用道具 举报

pushazhiniao 发表于 2016-8-19 05:11:10 | 显示全部楼层
感觉楼主的题第二题我不是很明白额。求讲解。
我说一说另外几题。
1.第一题就是bfs,感觉并不需要hashmap。起始[(0,0)]然后每一轮比较(i,j)和(i+1,j+1)并放入两端的[(i,j+1),(i+1,j)]。也就是斜着走的bfs。
2.比较不明白的是1)那个例子每个set都有2,为啥要分成两份,一份不可以吗?2)这题要求最优解,楼主的方法像greedy,不过能保证最优吗?还是需要dp?
3.楼主的把char序列转成整数来比较很好呢,followup里类似bucket sort,每个机器跑一遍自己的substring,算出最小最大index然后跟隔壁bucket比较。
4.第四轮国人小哥好给力。第一题是类似combination sum之类的,dfs跑出小于等于n的长度的list就存入返回值。第二题就是lc的one edit distance吧。

求问楼主第二题的题意。

补充内容 (2016-8-19 05:18):
谢谢楼主解释,如果是包含关系的话,应该类似lc的这题https://leetcode.com/problems/largest-divisible-subset/ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这题dp做法.1point3acres缃

补充内容 (2016-8-19 05:22):.1point3acres缃
不过楼主的这题还是要greedy
回复 支持 1 反对 0

使用道具 举报

 楼主| low910411 发表于 2016-8-19 04:15:11 | 显示全部楼层
第一题:
判断第一行和第一列的数字,坐标为(i,j),然后每次判断(i+1, j+1)的数字(不越界的话)是不是和(i, j)一样。
鏉ユ簮涓浜.涓夊垎鍦拌鍧. follow up 我用了一个HashMap, key是坐标pair, value是值。按行读取,每次读到一个(i, j)判断(i-1, j-1)在不在hashmap中。需要override pair class 的 equal 和 hash 函数,来不及写override只写了主要部分,但是跟面试官说了。

第二题:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
函数要这么写: public  List<List<Set<>>> getAnswer(List<Set<>> input)。 (面试官提示我的= =).鏈枃鍘熷垱鑷1point3acres璁哄潧
开始时把input 按照Set的size排序,size大的在前面。然后一遍for循环。尝试把每个item加入output中(output也要走一遍循环),如果output走到结束也没加入到output,说明这个item要自立门户,加入output中。

第三题:
以帖子里面例子为例,先把ole建立一个hashmap, value是他们的index,key-value则是: o-0, l-1, e-2
for循环一遍这个string,每次遇到一个在hashmap里面的字母,check一下这个index是不是比之前遇到的那个index小。

followup:有N台机器,每台有1/N的片断(substring)。 同时开始计算,首先每台机器内部这个substring要是合法的。 每台机器有一个start_index, end_index,记录的是本机器中这个substring,在hashmap中的, 第一个字母,最后一个字母的index。 吧所有的start_index. end_index放在一起,看是不是in order。
这里要注意 start_index end_index 初始值, 我设置成了(-1, -1)。 因为 如果你设置成(0,0)该substring不含有ole、比如这个substring是xyz,会出问题。(这个地方面试官提示我的). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


第四题
第一小题:
这题我就是暴力解答的。每遇到一个新的词放入hashmap. 写完了讨论下复杂度,面试官就问了下能不能优化,也没让我想,也没提示,就说那下一题。
第二小题:
先问了下是不是这两个string 除了多出来的一位, 其他字母顺序是不是一样的。 如果一样的话,因为有一个string多一位,那一旦遇到字母不同,返回长一点那个string的当前字母就可以了。. from: 1point3acres.com/bbs
如果不是顺序的,就把短一点的放入hashmap. value是该字幕出现的个数。 然后for循环一遍长一点string。每次把这个字母value-1。 遇到不在hashmap或者 value <0 说明就是要找的那个string。



大概就是这样~~~求交流~~
回复 支持 1 反对 0

使用道具 举报

phantom 发表于 2016-8-20 01:39:11 | 显示全部楼层
chenzhan171 发表于 2016-8-20 01:06
二分就是找两个string中第一个不一样的char, 以第一个string为基准, st = 0 , ed = s1.length() - 1;. Waral 鍗氬鏈夋洿澶氭枃绔,
...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
两个String没说顺序一样啊。。。你用二分做是要他能保证第一个string和第二个string相同的部分顺序一样才行
回复 支持 1 反对 0

使用道具 举报

taobingxue 发表于 2016-8-20 04:25:13 | 显示全部楼层
lovelysier613 发表于 2016-8-20 03:28
感觉时间和空间复杂度都是一样的?还是我没有理解sliding windows。能不能给个详细点儿的过程?

我就mark一下,我也觉得sliding windows复杂度是一样的 @.@?
难道sliding windows不是像扫描线一样移动嘛 还是每一块都要暴力一下的?

默默觉得,N非常大,可以把每个单词当字符,然后做后缀数组……的样子?

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

mdyuki1016 发表于 2016-8-19 03:36:59 | 显示全部楼层
能简单讲讲楼主都怎么做的吗?  也可以让大家分析下是不是还有更好的解法
回复 支持 反对

使用道具 举报

 楼主| low910411 发表于 2016-8-19 04:15:34 | 显示全部楼层
mdyuki1016 发表于 2016-8-19 03:36.鏈枃鍘熷垱鑷1point3acres璁哄潧
能简单讲讲楼主都怎么做的吗?  也可以让大家分析下是不是还有更好的解法
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我写在第三楼了~~~
回复 支持 反对

使用道具 举报

chenzhan171 发表于 2016-8-19 04:24:08 | 显示全部楼层
和你同一天onsite的, 前两天催了下hr说还有个feedback没收到。。。
回复 支持 反对

使用道具 举报

 楼主| low910411 发表于 2016-8-19 04:26:55 | 显示全部楼层
chenzhan171 发表于 2016-8-19 04:24
和你同一天onsite的, 前两天催了下hr说还有个feedback没收到。。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那可能面试官有事情吧,祝好运,拿到offer~
回复 支持 反对

使用道具 举报

mdyuki1016 发表于 2016-8-19 04:28:06 | 显示全部楼层
我感觉有几个地方也许能改进, 有理解错的地方,楼主指正哈.
#1, 可以用斜着走的方法 iterate 2d array . 这样只需要O1 space,
#2, 是不是 union find 更高效一点?
#3, 感觉楼主答得挺好的
#4.1 典型的 n-gram 问题, 可以用 sliding window
回复 支持 反对

使用道具 举报

 楼主| low910411 发表于 2016-8-19 04:40:05 | 显示全部楼层
mdyuki1016 发表于 2016-8-19 04:28. 鍥磋鎴戜滑@1point 3 acres
我感觉有几个地方也许能改进, 有理解错的地方,楼主指正哈.
#1, 可以用斜着走的方法 iterate 2d array . 这 ...
. visit 1point3acres.com for more.
谢谢你的回答哈~
#1 你说的是大数据的情况下O(1)嘛?因为大数据是按行存储的,面试官的意思是大数据时候一行一行读取。
#2 这道题其实面试官提示了我挺多的,他的意思似乎这是最优解了。
union find应该不可行。因为比如(1,2,4)和(1,2)是一组的,但是(1,2,4)和(2,5)不是一组的。一组是有并集,不是交集。
#4.1 谢谢提醒!好像确实可以用sliding window!在生成一个新的词组的时候。
回复 支持 反对

使用道具 举报

chenzhan171 发表于 2016-8-19 04:42:04 | 显示全部楼层
low910411 发表于 2016-8-19 04:26
那可能面试官有事情吧,祝好运,拿到offer~
. 鍥磋鎴戜滑@1point 3 acres
我觉得第二题和第4题可以改进下,
#2, UnionFind好一些
#4.2  A^A  = 0, A^0 = A, 两次for循环可以Space O(1)找出来。
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-8-19 04:45:34 | 显示全部楼层
第2题, 四个list都可以放在一份中吧? 因为都有2
回复 支持 反对

使用道具 举报

randrand1 发表于 2016-8-19 04:46:24 | 显示全部楼层
第二题的例子为什么不可以分成一份?每个list里面都有2,那么不是他们都可以分到一起吗?
回复 支持 反对

使用道具 举报

 楼主| low910411 发表于 2016-8-19 04:48:01 | 显示全部楼层
hyj143 发表于 2016-8-19 04:45
第2题, 四个list都可以放在一份中吧? 因为都有2

要A是B的并集,A和B才可以在一份里。
回复 支持 反对

使用道具 举报

 楼主| low910411 发表于 2016-8-19 04:48:17 | 显示全部楼层
randrand1 发表于 2016-8-19 04:46
. 鍥磋鎴戜滑@1point 3 acres第二题的例子为什么不可以分成一份?每个list里面都有2,那么不是他们都可以分到一起吗?

要A是B的并集,A和B才可以在一份里。
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-8-19 04:52:30 | 显示全部楼层
chenzhan171 发表于 2016-8-19 04:42
我觉得第二题和第4题可以改进下,
#2, UnionFind好一些
#4.2  A^A  = 0, A^0 = A, 两次for循环可以Sp ...

求具体的4.2方法
回复 支持 反对

使用道具 举报

 楼主| low910411 发表于 2016-8-19 04:53:12 | 显示全部楼层
chenzhan171 发表于 2016-8-19 04:42.鏈枃鍘熷垱鑷1point3acres璁哄潧
我觉得第二题和第4题可以改进下,
#2, UnionFind好一些
#4.2  A^A  = 0, A^0 = A, 两次for循环可以Sp ...

. Waral 鍗氬鏈夋洿澶氭枃绔,#2 要A是B的并集,A和B才可以在一份里。
#4.2 这种方法是不是bit manipulation? 如果没有duplicate可以用! 有duplicate好像不行?
回复 支持 反对

使用道具 举报

chenzhan171 发表于 2016-8-19 04:56:59 | 显示全部楼层
low910411 发表于 2016-8-19 04:53 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
#2 要A是B的并集,A和B才可以在一份里。. from: 1point3acres.com/bbs
#4.2 这种方法是不是bit manipulation? 如果没有duplicate可以 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
有duplicate当然可以, a^a^a = a
回复 支持 反对

使用道具 举报

 楼主| low910411 发表于 2016-8-19 05:03:43 | 显示全部楼层
randrand1 发表于 2016-8-19 04:58
4.2的思路估计是因为string1和string2比起来只差一个字符,那么string1+string2加起来的字符串里面只有一个 ...

明白了~~~好办法,赞~
回复 支持 反对

使用道具 举报

 楼主| low910411 发表于 2016-8-19 05:05:52 | 显示全部楼层
chenzhan171 发表于 2016-8-19 04:56
有duplicate当然可以, a^a^a = a

楼下有人解释了下,大概懂了你的思路,膜拜一下大神。。
回复 支持 反对

使用道具 举报

 楼主| low910411 发表于 2016-8-19 05:06:48 | 显示全部楼层
第二题没解释清楚,A和B要是并集,才可以在一份里。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 10:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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