c*****n
发帖数: 95 | 1 两轮编程，两轮设计，一个演讲， 一个经验＋编程
编程一：三姐
寒暄5分钟
1.在一个字典中找一个给定的单词，单词中可以有＊，＊可以和任意字符匹配。字典自
己定义 （我用的前缀树 ＋ 深搜）
2. 给一个数组，全为正数，找是否有一个连续子数组，和为一个给定的值 （由于没考
虑正数
条件，给了几个做法，三姐都不高兴，最后给提示，强调是正数，才想起来用sliding
window, 可惜时间不够把代码做到完整无bug。）
最后5分钟问问题。
三姐没有照相，感觉有黑我的倾向。。。
编程二：东欧小哥
寒暄5分钟
正则表达试匹配。
lc第10题
没有一上来就动态规划。用了递归做法。然后分析时间复杂度。然后优化成记忆搜索，
然后讨论DP。问了下各个方法的优缺点。最后拍照，又寒暄了几分钟。
设计一：比较专业相关就不透露了
设计二：常见题：板上有
答的还算比较顺
最后一轮：谈了30分钟，最后一道：最小覆盖子窜变种，比lc上的原题简单些。拍照后
，继续聊了10分钟。
感觉最差的一轮就是三姐那轮了，而且她还没拍照，感觉随便怎么黑我都行啊。 |
n******n
发帖数: 12088 | 2 一轮多久？一个小时？怎么最后一轮聊了40分钟还能做题？
sliding
【在 c*****n 的大作中提到】
: 两轮编程，两轮设计，一个演讲， 一个经验＋编程
: 编程一：三姐
: 寒暄5分钟
: 1.在一个字典中找一个给定的单词，单词中可以有＊，＊可以和任意字符匹配。字典自
: 己定义 （我用的前缀树 ＋ 深搜）
: 2. 给一个数组，全为正数，找是否有一个连续子数组，和为一个给定的值 （由于没考
: 虑正数
: 条件，给了几个做法，三姐都不高兴，最后给提示，强调是正数，才想起来用sliding
: window, 可惜时间不够把代码做到完整无bug。）
: 最后5分钟问问题。
|
c*****n
发帖数: 95 | 3 最后一轮 一个小时。其他设计和编程 45 分钟
【在 n******n 的大作中提到】
: 一轮多久？一个小时？怎么最后一轮聊了40分钟还能做题？
:
: sliding
|
y*****e
发帖数: 712 | 4 lz, trie + dfs那题你能再解释一下吗？ *是不是不用放到字典里， 比如说abc*de，
在trie里记录abc，然后skip一个character,再在后面找de? 不是太清楚具体怎么实现
的。。。
另外就是regex那题，DP的complexity是 n^2 + n^2; recursion + backtracking的复
杂度怎么考虑？最坏是2^n吧，怎么说服recursion是更优的办法呢？
另外感觉lz答得不错，phd应该有很高的级别吧，羡慕。。。
sliding
【在 c*****n 的大作中提到】
: 两轮编程，两轮设计，一个演讲， 一个经验＋编程
: 编程一：三姐
: 寒暄5分钟
: 1.在一个字典中找一个给定的单词，单词中可以有＊，＊可以和任意字符匹配。字典自
: 己定义 （我用的前缀树 ＋ 深搜）
: 2. 给一个数组，全为正数，找是否有一个连续子数组，和为一个给定的值 （由于没考
: 虑正数
: 条件，给了几个做法，三姐都不高兴，最后给提示，强调是正数，才想起来用sliding
: window, 可惜时间不够把代码做到完整无bug。）
: 最后5分钟问问题。
|
S**********t
发帖数: 71 | 5 suppose the given array is a[0], a[1], ..., a[n-1]
Define a new array z[0] = 0,z[1] = a[0], ..., z[n] = a[0]+...+a[n-1]
Then it should be very easy!
sliding
【在 c*****n 的大作中提到】
: 最后一轮 一个小时。其他设计和编程 45 分钟
|
c*****n
发帖数: 95 | 6 要求constant space
【在 S**********t 的大作中提到】
: suppose the given array is a[0], a[1], ..., a[n-1]
: Define a new array z[0] = 0,z[1] = a[0], ..., z[n] = a[0]+...+a[n-1]
: Then it should be very easy!
:
: sliding
|
c*****n
发帖数: 95 | 7 ＊可以和任意非空字符匹配 e.g. a - z
DP 复杂度应该是 m * n
recursion + backtracking 是 2^n. recursion好处是，如果没有很多＊时，可能结束
的更早。
，
【在 y*****e 的大作中提到】
: lz, trie + dfs那题你能再解释一下吗？ *是不是不用放到字典里， 比如说abc*de，
: 在trie里记录abc，然后skip一个character,再在后面找de? 不是太清楚具体怎么实现
: 的。。。
: 另外就是regex那题，DP的complexity是 n^2 + n^2; recursion + backtracking的复
: 杂度怎么考虑？最坏是2^n吧，怎么说服recursion是更优的办法呢？
: 另外感觉lz答得不错，phd应该有很高的级别吧，羡慕。。。
:
: sliding
|
y*****e
发帖数: 712 | 8 谢谢回复，我说n^2 + n^2的意思是，space是n square, time也是n square, 不过感觉
面试官只care time, m * n更准确些。我去写写trie那题，挺有意思的感觉。
【在 c*****n 的大作中提到】
: ＊可以和任意非空字符匹配 e.g. a - z
: DP 复杂度应该是 m * n
: recursion + backtracking 是 2^n. recursion好处是，如果没有很多＊时，可能结束
: 的更早。
:
: ，
|
p*u
发帖数: 2454 | 9 they want O(n), urs is O(n^2) w/ lots of extra memory
【在 S**********t 的大作中提到】
: suppose the given array is a[0], a[1], ..., a[n-1]
: Define a new array z[0] = 0,z[1] = a[0], ..., z[n] = a[0]+...+a[n-1]
: Then it should be very easy!
:
: sliding
|
m******3
发帖数: 346 | 10 多谢分享，楼主能讲讲三姐的第二题用sliding window怎么做么？ |
|
|
S**********t
发帖数: 71 | 11 Isn't the problem just a variant of two-sum?
: Define a new array z[0] = 0,z[1] = a[0], ..., z[n] = a[0]+...+a[n-1]
: Then it should be very easy!
: sliding
【在 p*u 的大作中提到】
: they want O(n), urs is O(n^2) w/ lots of extra memory
|
p*u
发帖数: 2454 | 12 pay attention to "contiguous subarray"
【在 S**********t 的大作中提到】
: Isn't the problem just a variant of two-sum?
:
: : Define a new array z[0] = 0,z[1] = a[0], ..., z[n] = a[0]+...+a[n-1]
: : Then it should be very easy!
: : sliding
|
c*****n
发帖数: 95 | 13 不难，直接上代码啦
可惜当时没能完成, 做完一题后头有点晕。
bool search(vector& num, int target) {
int sum = 0;
int i = 0;
int j = 0;
while(j < num.size()) {
sum += num[j];
if(sum == target) return true;
else if(sum > target) {
while(sum > target && i < j) {
sum -= num[i];
i++;
}
}
j++;
}
return false;
}
【在 m******3 的大作中提到】
: 多谢分享，楼主能讲讲三姐的第二题用sliding window怎么做么？
|
m******3
发帖数: 346 | |
z***b
发帖数: 127 | 15 祝楼主好运。不过楼主这道题好像写的有bug吧？ 你减去一个数的时候就不和target比
较了嘛？
while(sum > target && i < j) {
sum -= num[i];
i++;
}
【在 c*****n 的大作中提到】
: 不难，直接上代码啦
: 可惜当时没能完成, 做完一题后头有点晕。
: bool search(vector& num, int target) {
: int sum = 0;
: int i = 0;
: int j = 0;
: while(j < num.size()) {
: sum += num[j];
: if(sum == target) return true;
: else if(sum > target) {
|
c*****n
发帖数: 95 | 16 的确是啊。在while loop 结束后，还要额外check一下。
【在 z***b 的大作中提到】
: 祝楼主好运。不过楼主这道题好像写的有bug吧？ 你减去一个数的时候就不和target比
: 较了嘛？
: while(sum > target && i < j) {
: sum -= num[i];
: i++;
: }
|
n******n
发帖数: 12088 | 17 那相当于？啊。*应该是0个或多个。
【在 c*****n 的大作中提到】
: ＊可以和任意非空字符匹配 e.g. a - z
: DP 复杂度应该是 m * n
: recursion + backtracking 是 2^n. recursion好处是，如果没有很多＊时，可能结束
: 的更早。
:
: ，
|
y*****e
发帖数: 712 | 18 lz, 我刚才写了写trie这题，感觉代码量不小啊，得写trienode再写trie class里的
match words， 你这轮2题，难道15分钟这题就得写出来？无bug? 这要求也太高了吧
【在 c*****n 的大作中提到】
: ＊可以和任意非空字符匹配 e.g. a - z
: DP 复杂度应该是 m * n
: recursion + backtracking 是 2^n. recursion好处是，如果没有很多＊时，可能结束
: 的更早。
:
: ，
|
b**********5
发帖数: 7881 | 19 我也觉得这种题， 即使你一刻不停的写， 也要15分钟。。。
【在 y*****e 的大作中提到】
: lz, 我刚才写了写trie这题，感觉代码量不小啊，得写trienode再写trie class里的
: match words， 你这轮2题，难道15分钟这题就得写出来？无bug? 这要求也太高了吧
|
c*****n
发帖数: 95 | 20 这题不用实现trie。可以假设你有一个。
【在 y*****e 的大作中提到】
: lz, 我刚才写了写trie这题，感觉代码量不小啊，得写trienode再写trie class里的
: match words， 你这轮2题，难道15分钟这题就得写出来？无bug? 这要求也太高了吧
|
|
|
p*********g
发帖数: 2998 | 21 除了设计题外, 题还满正常的, 三姐应该不算友好, 而且没有提醒你有bug, 你把sum>
target放在前面, 下面在写sum==target就行了 |
m******s
发帖数: 1469 | 22 Zan!
sliding
【在 c*****n 的大作中提到】
: 两轮编程，两轮设计，一个演讲， 一个经验＋编程
: 编程一：三姐
: 寒暄5分钟
: 1.在一个字典中找一个给定的单词，单词中可以有＊，＊可以和任意字符匹配。字典自
: 己定义 （我用的前缀树 ＋ 深搜）
: 2. 给一个数组，全为正数，找是否有一个连续子数组，和为一个给定的值 （由于没考
: 虑正数
: 条件，给了几个做法，三姐都不高兴，最后给提示，强调是正数，才想起来用sliding
: window, 可惜时间不够把代码做到完整无bug。）
: 最后5分钟问问题。
|
d**********6
发帖数: 4434 | 23 你这第二条是我前两个月面过的改良
我的不是全正数
sliding
【在 c*****n 的大作中提到】
: 两轮编程，两轮设计，一个演讲， 一个经验＋编程
: 编程一：三姐
: 寒暄5分钟
: 1.在一个字典中找一个给定的单词，单词中可以有＊，＊可以和任意字符匹配。字典自
: 己定义 （我用的前缀树 ＋ 深搜）
: 2. 给一个数组，全为正数，找是否有一个连续子数组，和为一个给定的值 （由于没考
: 虑正数
: 条件，给了几个做法，三姐都不高兴，最后给提示，强调是正数，才想起来用sliding
: window, 可惜时间不够把代码做到完整无bug。）
: 最后5分钟问问题。
|
c*******5
发帖数: 4 | 24 拍照是面的好还是不好，有什么说法依据么？
sliding
【在 c*****n 的大作中提到】
: 两轮编程，两轮设计，一个演讲， 一个经验＋编程
: 编程一：三姐
: 寒暄5分钟
: 1.在一个字典中找一个给定的单词，单词中可以有＊，＊可以和任意字符匹配。字典自
: 己定义 （我用的前缀树 ＋ 深搜）
: 2. 给一个数组，全为正数，找是否有一个连续子数组，和为一个给定的值 （由于没考
: 虑正数
: 条件，给了几个做法，三姐都不高兴，最后给提示，强调是正数，才想起来用sliding
: window, 可惜时间不够把代码做到完整无bug。）
: 最后5分钟问问题。
|
c*****n
发帖数: 95 | 25 更新：
由于最后一轮experience不positive，被加面一轮。
所以面试感觉根本不准。。。
加面一轮的简单算法题是：
把一棵树的叶子节点连起来。
答的不错，recruiter说已经送到final hiring committee。求bless啊
手上已有个MSR的offer，要是FB也给了，去哪呢？ |
y*****e
发帖数: 712 | 26 bless!
lz再说说加面那题行吗？是lc上的吗，right pointer那题？ |
c*****n
发帖数: 95 | 27 不是leetcode上的。但有类似，例如把每层的node连起来。
比如
A
/ \
B C
/ \
D E
把D，E，C 连起来
【在 y*****e 的大作中提到】
: bless!
: lz再说说加面那题行吗？是lc上的吗，right pointer那题？
|
b**********5
发帖数: 7881 | 28 ah, ok, got it. just connect the leaves....
did u just use BFS? and just remember the prev leaf node?
【在 c*****n 的大作中提到】
: 不是leetcode上的。但有类似，例如把每层的node连起来。
: 比如
: A
: / \
: B C
: / \
: D E
: 把D，E，C 连起来
|
c*****n
发帖数: 95 | 29 是。这题不难。用的DFS
【在 b**********5 的大作中提到】
: ah, ok, got it. just connect the leaves....
: did u just use BFS? and just remember the prev leaf node?
|
b**********5
发帖数: 7881 | 30 用BFS也可以吧？ 是要connect成doubly linked list么？ 还是singly linked list？
【在 c*****n 的大作中提到】
: 是。这题不难。用的DFS
|
