10/23 gougou面经

10/23 gougou MTV onsite，记得签了NDA所以就大概回忆一下四轮题目吧，总体不难，但是follow up把题目抬升了一点就没有答好，所以拒了也是意料之中的。

您好！
本帖隐藏的内容需要积分高于 25 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 25 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

总体感受：注重交流和分析，如果能找到最优解当然perfect啦，题目灵活有抬升，全能做出来感觉就可以pass，狗家对new grad最看重algorithm了，拒的理由绝大多数就是algorithm不够好。

祝大家好运～！


补充内容 (2017-11-13 00:15):
修正：第二轮是问array里找subarray的最长长度，要和为0的subarray。sum最大就简单了。。不知道为什么写成了sum最大。。


补充内容 (2017-11-13 12:09):
gou家题目很灵活的，大家看看练练脑子就好啦，要有人遇到重复饿还请告诉我哈

quingogo 发表于 2017-11-13 11:55
你看楼主后来加的描述信息 并不是伍伞 但好像有印象有见过类似的

那感觉应该是hashmap存一下0到i的和。是0就返回index加1，不是0就在hashmap里找。找得到就返回差值，找不到就存index？

这样可以 average O(n)

quingogo 发表于 2017-11-13 04:24
谢谢楼主分享 请问第二题怎么解？

补充内容 (2017-11-13 04:25):

嗯嗯对的～

请问楼主第三轮rectangles uniformly generate 坐标是怎么做的？是吧重叠的长方形分割成多个小长方形？但是分割的方法好像没有trivial的算法啊

同问第三轮的rectangle怎么处理啊？如果找到了overlapping areas，如何使得坐标uniformly distributed呢？
已加米~

所以第一题的follow up是类似Word break吗

desperatelife 发表于 2017-11-12 04:44
所以第一题的follow up是类似Word break吗

差不多吧，有对应关系所以建个2d array，然后在之前发生过的true‘s的基础上看是否在新位置匹配到。

tiatia123456 发表于 2017-11-12 04:06
请问楼主第三轮rectangles uniformly generate 坐标是怎么做的？是吧重叠的长方形分割成多个小长方形？但是 ...

可以不割 用个大方框把他们全匡进去～

shenqi77 发表于 2017-11-12 06:26
可以不割 用个大方框把他们全匡进去～

生成一个uniformly distributed的坐标 ,这个到底是要干什么呢？感谢！

570468837 发表于 2017-11-12 04:19
同问第三轮的rectangle怎么处理啊？如果找到了overlapping areas，如何使得坐标uniformly distributed呢？
...

用个大方框把它们全匡进去～谢谢～overlap算一次或者多次问题不大，看她的意思算一次都可以～

shenqi77 发表于 2017-11-12 06:29
用个大方框把它们全匡进去～谢谢～overlap算一次或者多次问题不大，看她的意思算一次都可以～

全框进去的话，如何使得get random point呢？
感觉写起代码来好麻烦啊。。。

570468837 发表于 2017-11-12 10:11
全框进去的话，如何使得get random point呢？
感觉写起代码来好麻烦啊。。。

匡进去了就是一个大rectangle， randomly生成一个点 check一下在不在原来那些小方形里，不在就再randomly生成一个点酱紫