狗狗4月 Cambridge onsite

在Cambridge 面的

第一轮: 印度大叔 人很好
定义 n-straight 指连续的n个数字, 输入是一个integer array 和n , 要求返回array 满不满足 n-straight 的要求:
eg 3-straight  [1,2,3,5,6,7]返回true, [1,2,3,4,5] 返回False
follow up:

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

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

up: 如果字符串特别大, 怎么办?

感觉会不会是最简单的面试了...
求过, 求大米



补充内容 (2018-6-15 10:15):
offer

楼主你好，请问你现在送hc了吗？如果送了的话，大概的timeline是怎么样的呀？谢谢！

kid1314 发表于 2018-5-10 00:51
恩, 第四问, 输入是两个祖父穿, 这也能XOR 吗> 那和遍历一遍比较野没有啥差别吧
感觉我挂在第四问 上了

可以XOR啊，字母都是ASCII码存的嘛，都是数字，说到底都是01串，当然可以XOR啊，XOR是O（1）空间啊，最后的follow up就显示出空间重要性了，不管你再大，我处理完的中间结果就一个数字而已，到最后总是可以得到结果，然后要存cnt可能就要知道字符集的大小了，字符集太大而内存小cnt就慢了

第三轮 给一个integer array, 表示每辆车在路上的速度, 假设他们都往同一个方向开, 开的快的会被开的慢的卡住,  问你最后整个路上的车, 会被分成几组 ,每组有几辆车
应该开车有个前后顺序吧, 要不然不存在被卡住的情况了, 我的思路大概这样，先开的车，先建一个queue, 然后后面一辆车比top快，呢就是加入这个queue, 因为被卡住了, 如果再来一辆比第一辆慢，呢就再建一个queue。
举个例子，[60, 70, 40, 60, 80, 100, 30, 20]
最后的结果应该是[60, 70], [40, 60, 80, 100], [30], [20]

第四轮, 两个字符串, 一个字符串比另一个多一个字母, 其余出现顺序相同,返回那个字母,
为什么不能用map reduce, 然后一个一个的数？总共256个bucket, 每次读几个到memory里面比数字就好了。

第一轮题意不是很清楚，楼主大神可以clarify一下么？

定义 n-straight 指连续的n个数字, 输入是一个integer array 和n , 要求返回array 满不满足 n-straight 的要求:
eg 3-straight  [1,2,3,5,6,7]返回true, [1,2,3,4,5] 返回False
follow up: 如果n-straight 指至少n个连续的数字, 应该怎么写函数

第二个为什么是False？n-staight是说数组中的每一个数都要在一个n-straight集合里么？

第二轮 不知道哪里的大叔

给一个integer array 表示不同符号的个数, 和输入n, 返回所有可能的n个符号的组合(不在乎顺序)
follow up: 返回这些组合的个数, 优化时间空间复杂度

第二轮是不是假设integer array是【2， 1， 1】 n=3
可能的组合有（0， 0， 1）， （0， 0， 2）， （0， 1， 2）对吧（括号里面对应的是array的index，比如（0，0，1）表示第一个字符取两次，第二个字符取一次）

idatascience 发表于 2018-5-9 07:18
第一轮题意不是很清楚，楼主大神可以clarify一下么？

定义 n-straight 指连续的n个数字, 输入是一个inte ...

比如 3-straight 就是, 1,2,3 是一个, 4,5,6 是一个所以返回True'  但是1,2,3,4,5 就不能被安排成x个3-straight,
这样说的清楚吗? 相当于是规定了长度是n的

idatascience 发表于 2018-5-9 07:24
第二轮 不知道哪里的大叔

给一个integer array 表示不同符号的个数, 和输入n, 返回所有可能的n个符号的 ...

非常正确

第四轮是不是统计一下每个字母的数量就行了。

darkscope 发表于 2018-5-9 23:09
第四轮是不是统计一下每个字母的数量就行了。

我认为是的, 但是面试官一直在问我说是字符串非常大应该怎么办?我不知道他到底想要啥....

kid1314 发表于 2018-5-9 22:51
比如 3-straight 就是, 1,2,3 是一个, 4,5,6 是一个所以返回True'  但是1,2,3,4,5 就不能被安排成x个3-st ...

如果允许一个数字出现在不同的3 straight里，[1，2，3，4，5]也是True的，即[1，2，3]， [3， 4，5] 符合要求。但是看起来题目是要求每个数字要出现在一个且仅允许出现在一个straight里。即[1，2，3，4，5]，3重复出现在两个组合里，这个是False的。[1， 2， 3， 4， 6， 7， 8]也是false的，4不属于任何一个straight里。这样理解题意对么？

但这样的话，这个题就太简单了阿。这样就是说数组的长度首先要是3的倍数，然后就每三个每三个的判断是否符合连续性....是不是我误解了，题不可能这么简单吧？

idatascience 发表于 2018-5-9 23:29
如果允许一个数字出现在不同的3 straight里，[1，2，3，4，5]也是True的，即[1，2，3]， [3， 4，5] 符合 ...

完全正确!

kid1314 发表于 2018-5-9 23:37
完全正确!

哇，那这道题真的好简单....不是吧！！！楼主真是好命！