f*****u
发帖数: 308 | 1 1. 国男
2sum
数字有重复，比如如果sum是10，{2,2,2,8,8}里面算两个(2,8)pair。求pair总数。
Merge interval
对我的最后solution表示很满意。
2. 国男
stream of strings like this
"1 34 5 6"
"3 4 5 6 3"
"4 5 6 3 3"
...
每行是一个包含数字的string。去除所有数字完全重复的strings.比如这里的第二和第
三行数字完全相同，可以合并成一个。要求合并所有数字完全重复的strings。
最后表示对我的优化结果不满意。
3. 有点像东南亚或者拉美后裔，英文无口音
Reverse linkedlist
不断要求优化。
4. 欧洲人
写一个小游戏。MxN 的格子上有一条蛇，蛇头可以向前，左，右移动，撞到自己身体任
何部位或者撞到边界就算死。
5. 阿三
有N个node,每个都不停的向外发送timestamps,具体发送哪些timestamp是每个node决定
的,从其他node来说是随机的.现在要收集这些node发送的所有timestamp.如果某个
timestamp被发现从超过99%的node上发送出来,记录下来.需要怎么做?这些timestamp很
多,是不能完全放进去内存里面的.如果node非常多,怎么scale?
我给的方案是用HashMap,分布存到多台机器上面。阿三表示数据很
多，每台机器的内存都存不下，让我优化。我的进一步方案是再设定一个时限T，过期
的数据可以丢掉。阿三要求进一步优化。我的再进一步方案是对于这个对于这个时限T
再分割成n个小格。这个n需要通过实验根据具体实际情况来确定。如果在T／n时间里面
，某些Timestamp的count小于某个设定值，比如0.01N，认为这个timestamp被收集到0.
99N的可能性已经趋近于0，可以忽略了，从HashMap里面删除。最后阿三还是表示不满
意，不能完全理解我的方案。
已挂，感觉比较大可能是挂在国男2和那个阿三手上了，当然不排除其他人表面表示满
意，实际有保留。不管怎样，下面接着投简历，接着面。Offer总会来的，祝版上所有
人都拿到理想的offer。
顺便给自己求一下内推：
背景：CS Master一年半工作经验，最近主要用Java开发web，Master期间做过涉及Data
Mining的项目。好几年前有过第一次尝试startup的经历，目前在尝试第二次，希望能
relocate到湾区，因为这里是我一直向往的创业圣地。所以我找工的目标是湾区的
Software Engineer。我同样也很想结交有创业意愿的朋友。非常感谢！ |
f*******w
发帖数: 1243 | 2 顶。
第三题还能怎么优化……
第五题前几天在板上见过，是不是就是你发的……
【在 f*****u 的大作中提到】
: 1. 国男
: 2sum
: 数字有重复，比如如果sum是10，{2,2,2,8,8}里面算两个(2,8)pair。求pair总数。
: Merge interval
: 对我的最后solution表示很满意。
: 2. 国男
: stream of strings like this
: "1 34 5 6"
: "3 4 5 6 3"
: "4 5 6 3 3"
|
f*******w
发帖数: 1243 | 3 第四个人的经典贪食蛇，感觉更像OOD啊。我觉得算法没有任何值得讨论的啊？ |
f*****u
发帖数: 308 | 4 第三题我是从用Stack的解法开始的，所以就有了后面的改进过程。因为据说G注重看你
思维优化的过程。当然也许我理解错了，应该一开始就给优化解法。
第五题就是我上次发的。
【在 f*******w 的大作中提到】
: 顶。
: 第三题还能怎么优化……
: 第五题前几天在板上见过，是不是就是你发的……
|
s**********k
发帖数: 88 | 5 加油，你答得不错了
第二题没看懂，请解释
【在 f*****u 的大作中提到】
: 1. 国男
: 2sum
: 数字有重复，比如如果sum是10，{2,2,2,8,8}里面算两个(2,8)pair。求pair总数。
: Merge interval
: 对我的最后solution表示很满意。
: 2. 国男
: stream of strings like this
: "1 34 5 6"
: "3 4 5 6 3"
: "4 5 6 3 3"
|
f*****u
发帖数: 308 | 6 不好意思，是没表达清楚。更新了一下原帖，现在应该清楚一些了。
【在 s**********k 的大作中提到】
: 加油，你答得不错了
: 第二题没看懂，请解释
|
m****t
发帖数: 555 | 7 看这个面经，说明刷题还是很有用的。不一定是原题，但只要真正理解原题的精髓，这
些题目不难 |
p***y
发帖数: 637 | 8 官方说法是看思考过程。。。但on site感觉可以讨论的时间太少了。不到一小时里要
开场，写两段程序，运行测试，优化讨论，再candidatr问问题。如果再思考摸索，时
间就很急了。
感觉仿佛是在考背题熟练度一样的
【在 f*****u 的大作中提到】
: 第三题我是从用Stack的解法开始的，所以就有了后面的改进过程。因为据说G注重看你
: 思维优化的过程。当然也许我理解错了，应该一开始就给优化解法。
: 第五题就是我上次发的。
|
f*******w
发帖数: 1243 | 9 第二题怎么做？
转化成vector 存到hash里？ |
f******o
发帖数: 1505 | |
|
|
f*****u
发帖数: 308 | 11 确实，我有时感觉又TM回到了高考和背GRE的时代。各类题型都烂熟于心自然就没问题
了。可是觉得那些所谓的优化有些对于现场答题挺扯淡的。就好比你背过茴香豆的回字
写法比别人多，知道比别人漂亮的写法，然后就自然可以装B了。我就TM指望着靠这几
个月刷刷刷搞定一个稍微稳定点的职位，然后就可以抽时间做自己真正想做的事情了。
【在 p***y 的大作中提到】
: 官方说法是看思考过程。。。但on site感觉可以讨论的时间太少了。不到一小时里要
: 开场，写两段程序，运行测试，优化讨论，再candidatr问问题。如果再思考摸索，时
: 间就很急了。
: 感觉仿佛是在考背题熟练度一样的
|
f*****u
发帖数: 308 | 12 就TM因为题水，都会做，所以以为没问题。结果TM还是挂。
【在 f******o 的大作中提到】
: 草，题目好水啊，你男的女的？
|
f*****u
发帖数: 308 | 13 我用的HashMap，他最后跟我说应该用MultiSet，我承认没用过。
【在 f*******w 的大作中提到】
: 第二题怎么做？
: 转化成vector 存到hash里？
|
h*******0
发帖数: 270 | |
p***y
发帖数: 637 | 15 如果我是面试官的话，干脆就不出这些题了。
直接给个算法让实现，看代码质量和思路。
可惜我不是
【在 f*****u 的大作中提到】
: 确实，我有时感觉又TM回到了高考和背GRE的时代。各类题型都烂熟于心自然就没问题
: 了。可是觉得那些所谓的优化有些对于现场答题挺扯淡的。就好比你背过茴香豆的回字
: 写法比别人多，知道比别人漂亮的写法，然后就自然可以装B了。我就TM指望着靠这几
: 个月刷刷刷搞定一个稍微稳定点的职位，然后就可以抽时间做自己真正想做的事情了。
|
y**********a
发帖数: 824 | 16
感觉挂在阿三那里了。就像二爷说的，这些东西都有成熟的解决方案。熟悉轮子的名字
看来很重要啊！
不知道 Storm + Kafka + Cassandra 能不能解决这个问题 -_-
还是请二爷来讲讲好了
【在 f*****u 的大作中提到】
: 1. 国男
: 2sum
: 数字有重复，比如如果sum是10，{2,2,2,8,8}里面算两个(2,8)pair。求pair总数。
: Merge interval
: 对我的最后solution表示很满意。
: 2. 国男
: stream of strings like this
: "1 34 5 6"
: "3 4 5 6 3"
: "4 5 6 3 3"
|
p***y
发帖数: 637 | 17 1 2 3 4 5
1 3 4 5 6
这样两个是完全不合并还是合并3 4 5?
【在 f*****u 的大作中提到】
: 我用的HashMap，他最后跟我说应该用MultiSet，我承认没用过。
|
f*****u
发帖数: 308 | 18 这两个不能合并，因为里面元素不完全相同。必须元素以及个数都一样才能合并。
【在 p***y 的大作中提到】
: 1 2 3 4 5
: 1 3 4 5 6
: 这样两个是完全不合并还是合并3 4 5?
|
f******l
发帖数: 32 | 19 第5题的解法是用range partition吗？
【在 f*****u 的大作中提到】
: 1. 国男
: 2sum
: 数字有重复，比如如果sum是10，{2,2,2,8,8}里面算两个(2,8)pair。求pair总数。
: Merge interval
: 对我的最后solution表示很满意。
: 2. 国男
: stream of strings like this
: "1 34 5 6"
: "3 4 5 6 3"
: "4 5 6 3 3"
|
g**e
发帖数: 6127 | 20 设计题是TSD，常用于monitoring/alarming系统 不需要hash某个timestamp，弄些
bucket，每分钟，每5分钟之类的，循环数组过期persist就行，redis可以
【在 y**********a 的大作中提到】
:
: 感觉挂在阿三那里了。就像二爷说的，这些东西都有成熟的解决方案。熟悉轮子的名字
: 看来很重要啊！
: 不知道 Storm + Kafka + Cassandra 能不能解决这个问题 -_-
: 还是请二爷来讲讲好了
|
|
|
f*****u
发帖数: 308 | 21 这个应该是说到点子上了!多谢大拿点拨!以前还真是没有接触过这种系统,没有这些概
念.学习了.
TSD是指Time Series Database对吧?这里的bucket,你是说对于每个出现的timestamp,
建一个bucket?还是对每小段时间?能再具体点说说怎么实现么?多谢多谢!
【在 g**e 的大作中提到】
: 设计题是TSD，常用于monitoring/alarming系统 不需要hash某个timestamp，弄些
: bucket，每分钟，每5分钟之类的，循环数组过期persist就行，redis可以
|
k**y
发帖数: 12 | 22 用hashmap数count (i.e. map)，难道跟multiset不是一个效果吗？
【在 f*****u 的大作中提到】
: 我用的HashMap，他最后跟我说应该用MultiSet，我承认没用过。
|
k**y
发帖数: 12 | 23 这跟log最近N sec N min N hour内的request个数是差不多的意思么？用一个circular
buffer 做秒级别的，把aggregator存在minute那个数据结构，然后两个分别滚动？
【在 g**e 的大作中提到】
: 设计题是TSD，常用于monitoring/alarming系统 不需要hash某个timestamp，弄些
: bucket，每分钟，每5分钟之类的，循环数组过期persist就行，redis可以
|
r****7
发帖数: 2282 | 24 1的2sum为什么算两个(2,8)pair，而不是一个或者六个？
2个这个我觉得没啥道理
【在 f*****u 的大作中提到】
: 1. 国男
: 2sum
: 数字有重复，比如如果sum是10，{2,2,2,8,8}里面算两个(2,8)pair。求pair总数。
: Merge interval
: 对我的最后solution表示很满意。
: 2. 国男
: stream of strings like this
: "1 34 5 6"
: "3 4 5 6 3"
: "4 5 6 3 3"
|
n*******e
发帖数: 4894 | 25 因为只要用过了，就不能再用了。。。。
【在 r****7 的大作中提到】
: 1的2sum为什么算两个(2,8)pair，而不是一个或者六个？
: 2个这个我觉得没啥道理
|
r****7
发帖数: 2282 | 26 噢。。
【在 n*******e 的大作中提到】
: 因为只要用过了，就不能再用了。。。。
|
p***y
发帖数: 637 | 27 对于这些设计提，有一点疑问。按照G家自己给出的指南，出了数据结构和一门编程语
言，面试不要求其他知识。
感觉G的设计题应该是open end考核思路？、
【在 f*****u 的大作中提到】
: 这个应该是说到点子上了!多谢大拿点拨!以前还真是没有接触过这种系统,没有这些概
: 念.学习了.
: TSD是指Time Series Database对吧?这里的bucket,你是说对于每个出现的timestamp,
: 建一个bucket?还是对每小段时间?能再具体点说说怎么实现么?多谢多谢!
|
p***y
发帖数: 637 | 28 stream of strings like this
"1 3 4 5 6"
"3 4 5 6 3"
"4 5 6 3 3"
...
这个是anagram的变体，用anagram的解法即可。
换言之只需要统计每个字符串里，每个字符出现的次数.这里字符仅限0-9，因此可以建
立一个表int[] statics = new int[10]; 然后保持0-9出现的次数。对每个字符串计算
一次，然后用hashSet来保持这些statics.遇到重复值，即为每个数字完全一样的，可
以遗弃。
如果不是数字，而是unicode字符，那么以上解法无效。必须对字符串按字符排序放进
hashSet。
如果是unicode字符串，每个字符串又很长。。。。大概要变成设计题，套轮子了。 |
p***y
发帖数: 637 | 29 我这statics大概就是面试官说的multiSet
【在 p***y 的大作中提到】
: stream of strings like this
: "1 3 4 5 6"
: "3 4 5 6 3"
: "4 5 6 3 3"
: ...
: 这个是anagram的变体，用anagram的解法即可。
: 换言之只需要统计每个字符串里，每个字符出现的次数.这里字符仅限0-9，因此可以建
: 立一个表int[] statics = new int[10]; 然后保持0-9出现的次数。对每个字符串计算
: 一次，然后用hashSet来保持这些statics.遇到重复值，即为每个数字完全一样的，可
: 以遗弃。
|
p***y
发帖数: 637 | 30 ".如果某个timestamp被发现从超过99%的node上发送出来,记录下来.需要怎么做?这些
timestamp很多,是不能完全放进去内存里面的.如果node非常多,怎么scale?"
有几个疑问：
1. 什么叫“某个timestamp被发现从超过99%的node上发送出来”， timestamp的精度
到小数点后多少位? 假定精确到毫秒，那就是在同一毫秒里99%的nodes都发了个
timestamp?
２. node非常多，还是得有个数量级，ｎｏｄｅｓ的地理分布也影响结果。timestamp
非常多，也得有数量级。数量级不同，思路也不同。如果４个节点在一分钟内产生的ｔ
ｉｍｅｓｔａｍｐｓ能吃掉１ＴＢ空间，那估计只能依赖外存。又比如，如果有一万个
全球分布的节点，那搞分布式内存的额外开销也够呛。
假定节点数量大约数千个，在同一数据中心（或同一个云计算系统）。产生的数据量，
每台节点的ｔｉｍｅｓｔａｍｐｓ在１０分钟内把自己的内存吃光。
３. timestamps从源节点抵达目标节点的时间延迟多大？如果我们只关心是否某个ｔ
ｉｍｅｓｔａｍｐｅ来自９９％的机器，完全可以不保持这些ｔｉｍｅｓｔａｍｐｓ，
只关注是否同一个timestamp来自９９％的机器。理想情况下只需要保持一个ｋｅｙ／
ｖａｌｕｅ ｐａｉｒ，即ｔｉｍｅｓｔａｍｐｅ／ｃｏｕｎｔ．但ｔｉｍｅｓｔａｍ
ｐ抵达可能有延迟，计算机计算也需要时间，因此得有个宽容度。
４. 假定代表同一个时刻的ｔｉｍｅｓｔａｍｐ会在无限长的区间内到达，为了使问
题能够解决，我们也人为设定只观察５分钟区间，隔开太久的，小概率事件，像ｇａｔ
ｅ说的，ｋｅｙ／ｖａｌｕｅ ｐａｉｒｓ存到外存里了，万一遇到，可以读取外存的
数据来解决。
５. 如果节点越来越多，内存也会越来越多。因此适当选择观察区间后，应该可以达
到动态平衡。直到最终节点太多，通信开销扛不住为止。这时唯一的办法大概是用ＳＳ
Ｄ存储阵列（开个玩笑的，不合题意）
【在 g**e 的大作中提到】
: 设计题是TSD，常用于monitoring/alarming系统 不需要hash某个timestamp，弄些
: bucket，每分钟，每5分钟之类的，循环数组过期persist就行，redis可以
|
|
|
k**y
发帖数: 12 | 31 没有特别明白。
然后保持0-9出现的次数
--> 这整个int[10] 存到 hashset里面吗？
这跟multiset有什么关系？难道不是会看到同样的就更新一下counter就好了，不需要
把重复的set存进去？我觉得能用set的东西一定可以用map呀，map的value是0/1就够表
达set了，value是count就能表达multiset了
【在 p***y 的大作中提到】
: stream of strings like this
: "1 3 4 5 6"
: "3 4 5 6 3"
: "4 5 6 3 3"
: ...
: 这个是anagram的变体，用anagram的解法即可。
: 换言之只需要统计每个字符串里，每个字符出现的次数.这里字符仅限0-9，因此可以建
: 立一个表int[] statics = new int[10]; 然后保持0-9出现的次数。对每个字符串计算
: 一次，然后用hashSet来保持这些statics.遇到重复值，即为每个数字完全一样的，可
: 以遗弃。
|
p***y
发帖数: 637 | 32 我也不知道为啥会提mult set，
int[10]
就是个简单的map，整个map放hashset里。
有时候面试官死心眼等着某个概念吧也许？
我试过面a家让分析logs,面试官看见不是用unix命令行马上黑脸不耐烦了。
【在 k**y 的大作中提到】
: 没有特别明白。
: 然后保持0-9出现的次数
: --> 这整个int[10] 存到 hashset里面吗？
: 这跟multiset有什么关系？难道不是会看到同样的就更新一下counter就好了，不需要
: 把重复的set存进去？我觉得能用set的东西一定可以用map呀，map的value是0/1就够表
: 达set了，value是count就能表达multiset了
|
b****t
发帖数: 112 | 33 #2.
Sort, remove space, make new string, add to HashMap
3 4 5 6 3 -> 3 3 4 5 6 --> make String 33456, add to HashMap
"33456" -> "3 4 5 6 3"
4 5 6 3 3 -> 3 3 4 5 6 --> "33456", check HashMap
【在 f*****u 的大作中提到】
: 1. 国男
: 2sum
: 数字有重复，比如如果sum是10，{2,2,2,8,8}里面算两个(2,8)pair。求pair总数。
: Merge interval
: 对我的最后solution表示很满意。
: 2. 国男
: stream of strings like this
: "1 34 5 6"
: "3 4 5 6 3"
: "4 5 6 3 3"
|
c****l
发帖数: 1280 | |
p***y
发帖数: 637 | 35 如果字符串每个都很长，排序会比map慢
反之，如果字符集很大而非0-9则排序佳
string="">
【在 b****t 的大作中提到】
: #2.
: Sort, remove space, make new string, add to HashMap
: 3 4 5 6 3 -> 3 3 4 5 6 --> make String 33456, add to HashMap
: "33456" -> "3 4 5 6 3"
: 4 5 6 3 3 -> 3 3 4 5 6 --> "33456", check HashMap
|
b****t
发帖数: 112 | 36 优化：假设字符串中只含数字0-9
Map s: digit --> digit count
0:5(count), 1:100, 2:9999, 3:..., 9:111111
Make string:
05_1100_29999_3..._9111111
【在 p***y 的大作中提到】
: 如果字符串每个都很长，排序会比map慢
: 反之，如果字符集很大而非0-9则排序佳
:
: string="">
:
|
p***y
发帖数: 637 | 37 字符串生成hash code比int[10]要慢吧
intt[10]也是个map只是lightweight一点
【在 b****t 的大作中提到】
: 优化：假设字符串中只含数字0-9
: Map s: digit --> digit count
: 0:5(count), 1:100, 2:9999, 3:..., 9:111111
: Make string:
: 05_1100_29999_3..._9111111
|
T*****u
发帖数: 7103 | |
s**********k
发帖数: 88 | 39 multiset比hashmap省空间
【在 p***y 的大作中提到】
: 我也不知道为啥会提mult set，
: int[10]
: 就是个简单的map，整个map放hashset里。
: 有时候面试官死心眼等着某个概念吧也许？
: 我试过面a家让分析logs,面试官看见不是用unix命令行马上黑脸不耐烦了。
|
