新鲜G onsite 面经 - 未名空间MITBBS历史存档

S*w2015-05-04 07:05

1 楼

发个新鲜面经，顺便求bless
1. 一块矩形面板上有黑点，白点，红点
给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
时删除一个或多个字符
2. 设计贪吃蛇
怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
3. 设计售票系统，要求
1. 每次返回5张可选最为
2. 保证不会给两个不同user返回同一个可选座位
3. 用户2分钟之内，没有购买，重新开始
moving average
要求，内部用一个固定大小数组
4. letter combination of phone number.
我写了递归的，要求继续写迭代版本的。这个在它提示下，才做出来了，很
tricky ，没练过
5. 一个circle 列表。Circle 有x,y,r
1 ------------------------
0 ----------------------------
判断是否有一条路径可以从负无穷到正无穷。
如果一个活多个circle完全block了通道，就没有路径
除了 letter combination of phone number. 的iterative版本答的不好，其他的都
答的不错
求bless

y*e2015-05-04 07:05

2 楼

bless!

c*n2015-05-04 07:05

3 楼

第五你说得不太清楚，通道是那两条直线 y==1. or y==0 么？

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

S*w2015-05-04 07:05

4 楼

对
路径只能在 0 1 之间

【在 c******n 的大作中提到】

: 第五你说得不太清楚，通道是那两条直线 y==1. or y==0 么？

h*e2015-05-04 07:05

5 楼

thanks
bless

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

c*n2015-05-04 07:05

6 楼

1.2 字典那个，一个个比么？每个O( length_of_dict_word) ,
还是要先build 个suffix tree 什么的？后面的办法就没法写了吧。

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

n*n2015-05-04 07:05

7 楼

不容易。

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

S*w2015-05-04 07:05

8 楼

可能我说的不清楚
假设字典是
Apple orange banana
输入 orange 返回 orange
输入 daxpple 返回 apple

【在 c******n 的大作中提到】

: 1.2 字典那个，一个个比么？每个O( length_of_dict_word) ,
: 还是要先build 个suffix tree 什么的？后面的办法就没法写了吧。

G*m2015-05-04 07:05

9 楼

bless

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

z*c2015-05-04 07:05

10 楼

这道是怎么做的

【在 S***w 的大作中提到】

: 可能我说的不清楚
: 假设字典是
: Apple orange banana
: 输入 orange 返回 orange
: 输入 daxpple 返回 apple

h*32015-05-04 07:05

11 楼

感觉楼主答得很好，应该没问题！
祝好运

r*72015-05-04 07:05

12 楼

bless
5就一题吗？
letter combination of phone number. 的iterative版本我觉得比1的两个题都容易很
多啊。还是说1只需要idea不用coding？

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

c*n2015-05-04 07:05

13 楼

谢谢。我意思确实是不知道怎么做。题目明白。
给一个dictionary word w, 和已知 query string S, 可以O(w + S) 找到 S 是不是
可以退化成w.
但是总的解就是for w in all_words :
if (isDegenerate(S, w)) best = Math.max(w.length()， best)
这样么？
感觉有高级一点快一点的办法吧，尤其如果多次query 的话

【在 S***w 的大作中提到】

: 可能我说的不清楚
: 假设字典是
: Apple orange banana
: 输入 orange 返回 orange
: 输入 daxpple 返回 apple

r*72015-05-04 07:05

14 楼

字典建成trie然后对query的后缀树数组进行query然后track状态。
复杂度是O(|S|*|W|)

【在 c******n 的大作中提到】

: 谢谢。我意思确实是不知道怎么做。题目明白。
: 给一个dictionary word w, 和已知 query string S, 可以O(w + S) 找到 S 是不是
: 可以退化成w.
: 但是总的解就是for w in all_words :
: if (isDegenerate(S, w)) best = Math.max(w.length()， best)
: 这样么？
: 感觉有高级一点快一点的办法吧，尤其如果多次query 的话

c*n2015-05-04 07:05

15 楼

你用query 即使是suffix 它也是连续的，在trie 上walk down 也是连续的。
题目要求可以在query 上任去掉字母。如果用trie 的话，我能想到的就是必须把
query 上每一个字母敲掉的version 都去trie 上试一遍，那就exponential 了

【在 r****7 的大作中提到】

: 字典建成trie然后对query的后缀树数组进行query然后track状态。
: 复杂度是O(|S|*|W|)

r*72015-05-04 07:05

16 楼

我说了在trie里边track状态啊
没有match上的state保持不变而不是转移到termination。

【在 c******n 的大作中提到】

: 你用query 即使是suffix 它也是连续的，在trie 上walk down 也是连续的。
: 题目要求可以在query 上任去掉字母。如果用trie 的话，我能想到的就是必须把
: query 上每一个字母敲掉的version 都去trie 上试一遍，那就exponential 了

c*n2015-05-04 07:05

17 楼

能不能写个大概的code , 意思明确些。多谢
trie 每一步的branch是query string 上的字符觉定，你字符有可能跳过，那不就成
了 NFA 了么（anyway trie 就是一个DFA )

【在 r****7 的大作中提到】

: 我说了在trie里边track状态啊
: 没有match上的state保持不变而不是转移到termination。

S*w2015-05-04 07:05

18 楼

我太挫了
我觉得 iterative 很难呢

【在 r****7 的大作中提到】

: bless
: 5就一题吗？
: letter combination of phone number. 的iterative版本我觉得比1的两个题都容易很
: 多啊。还是说1只需要idea不用coding？

S*w2015-05-04 07:05

19 楼

bfs阿

【在 z***c 的大作中提到】

: 这道是怎么做的

S*w2015-05-04 07:05

20 楼

我晕我看不懂
不过你想的太复杂了
我是用bfs, 一次删掉1个字符

【在 c******n 的大作中提到】

: 谢谢。我意思确实是不知道怎么做。题目明白。
: 给一个dictionary word w, 和已知 query string S, 可以O(w + S) 找到 S 是不是
: 可以退化成w.
: 但是总的解就是for w in all_words :
: if (isDegenerate(S, w)) best = Math.max(w.length()， best)
: 这样么？
: 感觉有高级一点快一点的办法吧，尤其如果多次query 的话

c*n2015-05-04 07:05

21 楼

ok, 你意思说所有dictionary word 在一个hashmap 里面o(1) time 可以决定是不是
存在？
然后穷举S 的所有enumeration(keep letter order), 看是不是match ?

【在 S***w 的大作中提到】

: 我晕我看不懂
: 不过你想的太复杂了
: 我是用bfs, 一次删掉1个字符

b*o2015-05-04 07:05

22 楼

请问你这个是entry level的面试吗？

S*w2015-05-04 07:05

23 楼

dict 是hashset
也不是穷举
0: 检查去掉0个字符
1：检查去掉1个字符
...

【在 c******n 的大作中提到】

: ok, 你意思说所有dictionary word 在一个hashmap 里面o(1) time 可以决定是不是
: 存在？
: 然后穷举S 的所有enumeration(keep letter order), 看是不是match ?

S*w2015-05-04 07:05

24 楼

应该是吧 google不认其他公司的经验，除了其他实力相当的公司巴？

【在 b****o 的大作中提到】

: 请问你这个是entry level的面试吗？

h*l2015-05-04 07:05

25 楼

bless!

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

e*22015-05-04 07:05

26 楼

cirle那题有O（N）解法吗？只想到O(N^2)的

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

m*32015-05-04 07:05

27 楼

bless, circle那题题意不理解阿，能详细说说，给个例子么？

b*w2015-05-04 07:05

28 楼

LZ第5题你是怎么做的？
能想到的是先建一个connectivity map o(n^2)
然后dfs

b*w2015-05-04 07:05

29 楼

在x-y坐标平面上画两条线y=0 和 y=1，之间的区域就是通道
把所有circle画上去,circle之间可能touch，判断通道最后能否联通

【在 m******3 的大作中提到】

: bless, circle那题题意不理解阿，能详细说说，给个例子么？

h*02015-05-04 07:05

30 楼

楼主售票系统你是怎么答的？

e*22015-05-04 07:05

31 楼

synchorized chooseFive(){}, synchronized putFive(); thread.interrupt() and
ScheduledThreadPool() to implement two minutes timeout. Any other ideas?

【在 h*******0 的大作中提到】

: 楼主售票系统你是怎么答的？

m*32015-05-04 07:05

32 楼

多谢，这道题怎么做呢？

【在 b*****w 的大作中提到】

: 在x-y坐标平面上画两条线y=0 和 y=1，之间的区域就是通道
: 把所有circle画上去,circle之间可能touch，判断通道最后能否联通

e*22015-05-04 07:05

33 楼

他都说了，dfs加connectivity，hint：如果有一条折线把A->B->C->D连起来就行了。
其中A在x=0上，D在x=1上, B, C是圆心，A和B相交，B和C相交，C和D相交，能找出来就
行了。

【在 m******3 的大作中提到】

: 多谢，这道题怎么做呢？

e*22015-05-04 07:05

34 楼

把圆们分成2 sets，两个sets，第一个set的圆可以reach x=0（might via some
circles），第二个set的圆可以reach x＝1（might via some circles），如果两个
set的交非空，就block了。

【在 e********2 的大作中提到】

: 他都说了，dfs加connectivity，hint：如果有一条折线把A->B->C->D连起来就行了。
: 其中A在x=0上，D在x=1上, B, C是圆心，A和B相交，B和C相交，C和D相交，能找出来就
: 行了。

l*u2015-05-04 07:05

35 楼

bless

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

s*42015-05-04 07:05

36 楼

先Mark一下

m*s2015-05-04 07:05

37 楼

Bless

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

l*k2015-05-04 07:05

38 楼

第5题有比n squared 好的方法没有？
n-squared:
1. cluster cycles. If two cycles have overlap, put them into one cluster.
2. If the max y and min y of cycles in any cluster exceed y=0, y=1, then no
path.

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

c*n2015-05-04 07:05

39 楼

没有吧，连起来只不过给你一个connected component, 比如说这个图是一个star 形
状，你还得找哪个点跟横线的距离最近

【在 e********2 的大作中提到】

: 他都说了，dfs加connectivity，hint：如果有一条折线把A->B->C->D连起来就行了。
: 其中A在x=0上，D在x=1上, B, C是圆心，A和B相交，B和C相交，C和D相交，能找出来就
: 行了。

n*n2015-05-04 07:05

40 楼

一块矩形面板上有黑点，白点，红点。给一个起点，找出和这个点颜色相同，且相连
的点组。
没看懂。
给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作删除
一个或多个字符
删多个不就是多次删，每次删一个吗？

【在 S***w 的大作中提到】

: 发个新鲜面经，顺便求bless
: 1. 一块矩形面板上有黑点，白点，红点
: 给一个起点，找出和这个点颜色相同，且相连的点组。求这个点组的周长
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作
: 时删除一个或多个字符
: 2. 设计贪吃蛇
: 怎么定义蛇，怎么移动，怎么吃，怎么判断时候活着，怎么定义游戏版
: 3. 设计售票系统，要求
: 1. 每次返回5张可选最为
: 2. 保证不会给两个不同user返回同一个可选座位

S*w2015-05-04 07:05

41 楼

第一个，求相同颜色块的边的长度。画个图就更清楚了
第二个，对

【在 n******n 的大作中提到】

: 一块矩形面板上有黑点，白点，红点。给一个起点，找出和这个点颜色相同，且相连
: 的点组。
: 没看懂。
: 给一个字典，一个字符串，找出可以由这个字串合法转成的最长单词。转换操作删除
: 一个或多个字符
: 删多个不就是多次删，每次删一个吗？

S*w2015-05-04 07:05

42 楼

对的

【在 e********2 的大作中提到】

: 他都说了，dfs加connectivity，hint：如果有一条折线把A->B->C->D连起来就行了。
: 其中A在x=0上，D在x=1上, B, C是圆心，A和B相交，B和C相交，C和D相交，能找出来就
: 行了。

M*T2015-05-04 07:05

43 楼

第一题白点黑点的是啥意思？没看懂

S*w2015-05-04 07:05

44 楼

换个图就知道
求一团同色点的边界

【在 M**********T 的大作中提到】

: 第一题白点黑点的是啥意思？没看懂

g*c2015-05-04 07:05

45 楼

第一题比如连红色的点可以有不同的连法导致周长不同？
弱问一下每一题都是要当场把code写全吗？有没有是说说想法就可以的？

g*c2015-05-04 07:05

46 楼

求回复～

【在 g*****c 的大作中提到】

: 第一题比如连红色的点可以有不同的连法导致周长不同？
: 弱问一下每一题都是要当场把code写全吗？有没有是说说想法就可以的？

S*w2015-05-04 07:05

47 楼

1. 不会阿周长固定阿
2. 当然写code

【在 g*****c 的大作中提到】

: 第一题比如连红色的点可以有不同的连法导致周长不同？
: 弱问一下每一题都是要当场把code写全吗？有没有是说说想法就可以的？

s*n2015-05-04 07:05

48 楼

第一题看不懂，怎么算相连？

c*42015-05-04 07:05

49 楼

加油！