c**w
发帖数: 1024 | 1 刚才HR来信，已挂。背景： fresh 100+烂校 master， GPA 3.6+。
特上面经：
1. 一个2d的黑白棋盘，黑色的格子都是连在一起的，现在给一个黑色的格子的坐标，
请找出最小的矩形，包含所有的黑色格子
2. Implement Iterator接口，但是增加一个功能，peek()返回next()的值，但是不能
移动pointer。 constructor已经指定，就是 PeekIterator(Iterator iter)
这题有个special case需要考虑
然后就是原题，maxSubArr()
3. 一个特殊的binary tree，叫full tree，定义是每个节点要么有2个children，要么
没有。现在我们要copy一个给定full tree的形状，请写encode和decode方法
4. 检查()序列对是否正确；
follow up 1： 如果有三种 ()[]{}怎么办
follow up 2: "()()(" double quote里面的ignore，如何判断
总结，当天晚上差不多12：00到酒店，大概2点才上床，早上起床眼睛全是血丝。。去g
面试做题完全没状态，maxSubArr就5行代码都一个bug。 不过居然还是让进了HC，虽然
毫无悬念的挂了。总体来看，题目有新题，但是仔细想还是能想到的，不过google对
coding速度要求很高，HR建议我继续好好练习coding，12-18个月再来。
希望能帮到大家，也祝大家好运。 |
h*****a
发帖数: 1718 | 2 第一题其实挺tricky的。worst case复杂度最好的算法不容易想。
【在 c**w 的大作中提到】
: 刚才HR来信，已挂。背景： fresh 100+烂校 master， GPA 3.6+。
: 特上面经：
: 1. 一个2d的黑白棋盘，黑色的格子都是连在一起的，现在给一个黑色的格子的坐标，
: 请找出最小的矩形，包含所有的黑色格子
: 2. Implement Iterator接口，但是增加一个功能，peek()返回next()的值，但是不能
: 移动pointer。 constructor已经指定，就是 PeekIterator(Iterator iter)
: 这题有个special case需要考虑
: 然后就是原题，maxSubArr()
: 3. 一个特殊的binary tree，叫full tree，定义是每个节点要么有2个children，要么
: 没有。现在我们要copy一个给定full tree的形状，请写encode和decode方法
|
f*****e
发帖数: 2992 | 3 斜的长方形，算吗？
【在 h*****a 的大作中提到】
: 第一题其实挺tricky的。worst case复杂度最好的算法不容易想。
|
g*****g
发帖数: 212 | 4 看来我想简单了，
如果矩形不是斜的，
难道不是DFS同时记录 up，down， left， right 的最大值吗？
【在 h*****a 的大作中提到】
: 第一题其实挺tricky的。worst case复杂度最好的算法不容易想。
|
c**w
发帖数: 1024 | 5 对，不过好好想，还是能想到。
其实第二题写iterator也很不容易bug free，虽然看起来简单。
【在 h*****a 的大作中提到】
: 第一题其实挺tricky的。worst case复杂度最好的算法不容易想。
|
g*****g
发帖数: 212 | 6 3题，似乎有印象，copy形状而非树本身（不带value）
所以：I表示中间节点，L表示叶子节点
encode，可以前序遍历，顺序输出I和L的序列
反之，也很容易decode。 |
g*****g
发帖数: 212 | 7 第二题，似乎就是用一个private变量 cur 保存一个当前value就好了。
每次call next的时候，替换当前 cur，直到 null
call peek 返回 cur
hasnext 返回 cur ！= null
第四题 没看到follow up 2。。。 |
c**w
发帖数: 1024 | 8 第二题不要太小看G的面试题了。
第四题直接ignore好了，我25分钟全部搞完，其余时间都是扯淡。
【在 g*****g 的大作中提到】
: 第二题，似乎就是用一个private变量 cur 保存一个当前value就好了。
: 每次call next的时候，替换当前 cur，直到 null
: call peek 返回 cur
: hasnext 返回 cur ！= null
: 第四题 没看到follow up 2。。。
|
n*******s
发帖数: 482 | 9 worst case, all black?
DFS with predefined direction? maintain DFS trace to avoid revist any
unvisitd node inside circle?
【在 h*****a 的大作中提到】
: 第一题其实挺tricky的。worst case复杂度最好的算法不容易想。
|
h*****a
发帖数: 1718 | 10 这样worst case 复杂度是n^2, 有更好的算法。
【在 g*****g 的大作中提到】
: 看来我想简单了，
: 如果矩形不是斜的，
: 难道不是DFS同时记录 up，down， left， right 的最大值吗？
|
|
|
h*****a
发帖数: 1718 | 11 第二题是很老的题了。主要考察细心。
【在 c**w 的大作中提到】
: 对，不过好好想，还是能想到。
: 其实第二题写iterator也很不容易bug free，虽然看起来简单。
|
h*****a
发帖数: 1718 | 12 no.
【在 n*******s 的大作中提到】
: worst case, all black?
: DFS with predefined direction? maintain DFS trace to avoid revist any
: unvisitd node inside circle?
|
c**w
发帖数: 1024 | 13 对。我潜意识有意识到问题，所以我一开始用了定义2个iterator variable的解，写完
才发现iterator不能clone，是个问题。然后用一个iterator variable的解，然后定义
nextCalled，擦掉，又写上，反复三次。。最后还是擦掉了。。。
准备面试，我几乎不看面经。。还是吃亏了。。1，2，3我都没见过，硬想。。
【在 h*****a 的大作中提到】
: 第二题是很老的题了。主要考察细心。
|
f*****e
发帖数: 2992 | 14 对呀，最好能边沿走一圈就知道了。
【在 h*****a 的大作中提到】
: 这样worst case 复杂度是n^2, 有更好的算法。
|
h*****a
发帖数: 1718 | 15 还是不行啊，考虑最坏情况，一样复杂度。
【在 f*****e 的大作中提到】
: 对呀，最好能边沿走一圈就知道了。
|
h*****a
发帖数: 1718 | 16 这样比较吃亏了，多做点真题很重要。
【在 c**w 的大作中提到】
: 对。我潜意识有意识到问题，所以我一开始用了定义2个iterator variable的解，写完
: 才发现iterator不能clone，是个问题。然后用一个iterator variable的解，然后定义
: nextCalled，擦掉，又写上，反复三次。。最后还是擦掉了。。。
: 准备面试，我几乎不看面经。。还是吃亏了。。1，2，3我都没见过，硬想。。
|
p*******2
发帖数: 50 | 17 赞！
第一题是在4个方向上binary search找到黑白临界点？
大牛能展开说说吗 |
s*******z
发帖数: 83 | 18 感觉是四个角找最大的和黑子不香蕉的白色正方形, 抛开这四个正方形就是黑的地盘了
. |
p*g
发帖数: 141 | 19 第一题谁解释一下
如果黑色都连在一起，那就只有一个最大的矩形覆盖，对任意取的小格子
【在 c**w 的大作中提到】
: 刚才HR来信，已挂。背景： fresh 100+烂校 master， GPA 3.6+。
: 特上面经：
: 1. 一个2d的黑白棋盘，黑色的格子都是连在一起的，现在给一个黑色的格子的坐标，
: 请找出最小的矩形，包含所有的黑色格子
: 2. Implement Iterator接口，但是增加一个功能，peek()返回next()的值，但是不能
: 移动pointer。 constructor已经指定，就是 PeekIterator(Iterator iter)
: 这题有个special case需要考虑
: 然后就是原题，maxSubArr()
: 3. 一个特殊的binary tree，叫full tree，定义是每个节点要么有2个children，要么
: 没有。现在我们要copy一个给定full tree的形状，请写encode和decode方法
|
h*****a
发帖数: 1718 | 20 你的思路是正确的。
提示一下，这个矩阵是2D的case，同样的问题如果退化到1维应该怎么描述？算法是什
么？
【在 p*******2 的大作中提到】
: 赞！
: 第一题是在4个方向上binary search找到黑白临界点？
: 大牛能展开说说吗
|
|
|
f*****e
发帖数: 2992 | 21 2D还分多联通吧，不知道怎么用binary search.比如一个环。
【在 h*****a 的大作中提到】
: 你的思路是正确的。
: 提示一下，这个矩阵是2D的case，同样的问题如果退化到1维应该怎么描述？算法是什
: 么？
|
m****n
发帖数: 25 | 22 binary search对环状似乎不work？如下*是黑的，还请大牛解惑
*******
* * *
* * *
* *
*******
【在 h*****a 的大作中提到】
: 你的思路是正确的。
: 提示一下，这个矩阵是2D的case，同样的问题如果退化到1维应该怎么描述？算法是什
: 么？
|
h*****a
发帖数: 1718 | 23 你期待的复杂度是多少？为什么你觉得这个例子不行？
【在 m****n 的大作中提到】
: binary search对环状似乎不work？如下*是黑的，还请大牛解惑
: *******
: * * *
: * * *
: * *
: *******
|
m****n
发帖数: 25 | 24 四个方向dfs的话就需要traverse所有黑格吧
binary search是对边界做？比如我从(x,y)黑出发对边界(0,y) binary search，
那我考察(x/2, y)，
但如果是环的话，(x/2,y)如果是白，那么(x/2-1,y)也可能是黑啊
似乎感觉能构造一个worst case．．
使得每次binary search踩中白点．．．那样binary search的优势就没法体现了．．．
【在 h*****a 的大作中提到】
: 你期待的复杂度是多少？为什么你觉得这个例子不行？
|
g****1
发帖数: 89 | 25 可以这样么？
起始点(x,y),先二分(0，x)找左边界,每次扫描整列，如果遇到黑点继续向0二分，否则
向x二分。顺便记住最小的Ymin(小优化)。然后对（0，Ymin)找到上边界。继续找到右
边界和下
边界。复杂度 O(NlgN) N是边长
【在 m****n 的大作中提到】
: 四个方向dfs的话就需要traverse所有黑格吧
: binary search是对边界做？比如我从(x,y)黑出发对边界(0,y) binary search，
: 那我考察(x/2, y)，
: 但如果是环的话，(x/2,y)如果是白，那么(x/2-1,y)也可能是黑啊
: 似乎感觉能构造一个worst case．．
: 使得每次binary search踩中白点．．．那样binary search的优势就没法体现了．．．
|
h*****a
发帖数: 1718 | 26 Close. 哈哈
再给一个提示，如果某一行没有一个黑的，那向上（或者向下）就肯定没有黑的了。:)
【在 g****1 的大作中提到】
: 可以这样么？
: 起始点(x,y),先二分(0，x)找左边界,每次扫描整列，如果遇到黑点继续向0二分，否则
: 向x二分。顺便记住最小的Ymin(小优化)。然后对（0，Ymin)找到上边界。继续找到右
: 边界和下
: 边界。复杂度 O(NlgN) N是边长
|
s*****i
发帖数: 32 | 27 不是说G不要求bug free吗。最主要的是速度。见前面某贴。但你这个是常见题的bug，
不知道有没有关系。
我想主要还是第一个人的和第三个人的，楼主做出来（或经提示做出来了吗），完整
code了吗？
楼主是用java吗？
【在 c**w 的大作中提到】
: 刚才HR来信，已挂。背景： fresh 100+烂校 master， GPA 3.6+。
: 特上面经：
: 1. 一个2d的黑白棋盘，黑色的格子都是连在一起的，现在给一个黑色的格子的坐标，
: 请找出最小的矩形，包含所有的黑色格子
: 2. Implement Iterator接口，但是增加一个功能，peek()返回next()的值，但是不能
: 移动pointer。 constructor已经指定，就是 PeekIterator(Iterator iter)
: 这题有个special case需要考虑
: 然后就是原题，maxSubArr()
: 3. 一个特殊的binary tree，叫full tree，定义是每个节点要么有2个children，要么
: 没有。现在我们要copy一个给定full tree的形状，请写encode和decode方法
|
P*****f
发帖数: 2272 | 28 divide and conquer.
Scan 中间列,如果有黑点， F(n) = F(left) + F(right), //递归返回后，需要左右高
度对齐一下
否则 F(n) = max (F(left). F (right));
在递归的时候，竖切和横切是alternative的，保证了子问题规模half.
【在 g****1 的大作中提到】
: 可以这样么？
: 起始点(x,y),先二分(0，x)找左边界,每次扫描整列，如果遇到黑点继续向0二分，否则
: 向x二分。顺便记住最小的Ymin(小优化)。然后对（0，Ymin)找到上边界。继续找到右
: 边界和下
: 边界。复杂度 O(NlgN) N是边长
|
s*******z
发帖数: 83 | 29 果然tricky, 给一个黑子只是为了确定搜索边界.
黑白子那个二分搜索~~, NLog(N)对吗? |
c**w
发帖数: 1024 | 30 第一题提示了一下，其余所有都是自己想的。我能进hc应该是看中我的反应能力，但是
bug实在太多了，没发挥出水平。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 s*****i 的大作中提到】
: 不是说G不要求bug free吗。最主要的是速度。见前面某贴。但你这个是常见题的bug，
: 不知道有没有关系。
: 我想主要还是第一个人的和第三个人的，楼主做出来（或经提示做出来了吗），完整
: code了吗？
: 楼主是用java吗？
|
|
|
c**w
发帖数: 1024 | 31 其实第一题面试的时候题目描述更隐晦，开始没说知道一个黑子地址。只是我说，这个
题是search problem,要想快，肯定是二分法，然后面试官问怎么搞，之后才把条件改
了，开始就给定一个黑子的地址
★ 发自iPhone App: ChineseWeb 8.2.2
【在 c**w 的大作中提到】
: 刚才HR来信，已挂。背景： fresh 100+烂校 master， GPA 3.6+。
: 特上面经：
: 1. 一个2d的黑白棋盘，黑色的格子都是连在一起的，现在给一个黑色的格子的坐标，
: 请找出最小的矩形，包含所有的黑色格子
: 2. Implement Iterator接口，但是增加一个功能，peek()返回next()的值，但是不能
: 移动pointer。 constructor已经指定，就是 PeekIterator(Iterator iter)
: 这题有个special case需要考虑
: 然后就是原题，maxSubArr()
: 3. 一个特殊的binary tree，叫full tree，定义是每个节点要么有2个children，要么
: 没有。现在我们要copy一个给定full tree的形状，请写encode和decode方法
|
s*******z
发帖数: 83 | 32 peek iterator那个有什么陷阱吗?
太弱了吗, 怎么觉得楼上几位说的就可以做了~~~ |
c**w
发帖数: 1024 | 33 还没看到有对的解
★ 发自iPhone App: ChineseWeb 8.2.2
【在 s*******z 的大作中提到】
: peek iterator那个有什么陷阱吗?
: 太弱了吗, 怎么觉得楼上几位说的就可以做了~~~
|
t**********h
发帖数: 2273 | 34 24k哥，不屌google
【在 c**w 的大作中提到】
: 刚才HR来信，已挂。背景： fresh 100+烂校 master， GPA 3.6+。
: 特上面经：
: 1. 一个2d的黑白棋盘，黑色的格子都是连在一起的，现在给一个黑色的格子的坐标，
: 请找出最小的矩形，包含所有的黑色格子
: 2. Implement Iterator接口，但是增加一个功能，peek()返回next()的值，但是不能
: 移动pointer。 constructor已经指定，就是 PeekIterator(Iterator iter)
: 这题有个special case需要考虑
: 然后就是原题，maxSubArr()
: 3. 一个特殊的binary tree，叫full tree，定义是每个节点要么有2个children，要么
: 没有。现在我们要copy一个给定full tree的形状，请写encode和decode方法
|
g****1
发帖数: 89 | 35 是啊，已经考虑了啊--扫描整列（行）。大牛赶快公布答案吧 :)
【在 h*****a 的大作中提到】
: Close. 哈哈
: 再给一个提示，如果某一行没有一个黑的，那向上（或者向下）就肯定没有黑的了。:)
|
g*****g
发帖数: 212 | 36 如果每一行二分,每一列二分找边界
nlogm + mlogn
不过
看来大牛还有更优解
【在 g****1 的大作中提到】
: 是啊，已经考虑了啊--扫描整列（行）。大牛赶快公布答案吧 :)
|
g*****g
发帖数: 212 | 37 求答案
【在 c**w 的大作中提到】
: 还没看到有对的解
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
c**w
发帖数: 1024 | 38 第一题是对的，第二题考虑iterator里面有元素为null
★ 发自iPhone App: ChineseWeb 8.2.2
【在 g*****g 的大作中提到】
: 如果每一行二分,每一列二分找边界
: nlogm + mlogn
: 不过
: 看来大牛还有更优解
|
g*****g
发帖数: 212 | 39 多谢多谢，得到了。这个null确实没考虑。
【在 c**w 的大作中提到】
: 第一题是对的，第二题考虑iterator里面有元素为null
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
d********e
发帖数: 239 | 40 请问你说的是 list 的list么，复合list?
【在 c**w 的大作中提到】
: 第一题是对的，第二题考虑iterator里面有元素为null
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
|
|
d********e
发帖数: 239 | 41 没明白
上面给的思想不就是利用了这个条件么？
【在 h*****a 的大作中提到】
: Close. 哈哈
: 再给一个提示，如果某一行没有一个黑的，那向上（或者向下）就肯定没有黑的了。:)
|
g*****g
发帖数: 212 | 42 因该说只要 nlogm或者mlogn
比如遍历行，在找列边界的过程中，如果没有列边界（都是白色），我们可以记录其中
行的最大和最小。
【在 g*****g 的大作中提到】
: 多谢多谢，得到了。这个null确实没考虑。
|
h*****a
发帖数: 1718 | 43 复杂度是对的。不过不需要起始给一个黑子的位置。
【在 s*******z 的大作中提到】
: 果然tricky, 给一个黑子只是为了确定搜索边界.
: 黑白子那个二分搜索~~, NLog(N)对吗?
|
h*****a
发帖数: 1718 | 44 好像是不需要起始黑子的位置的
【在 c**w 的大作中提到】
: 其实第一题面试的时候题目描述更隐晦，开始没说知道一个黑子地址。只是我说，这个
: 题是search problem,要想快，肯定是二分法，然后面试官问怎么搞，之后才把条件改
: 了，开始就给定一个黑子的地址
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
s*****i
发帖数: 32 | 45 如果黑子只有一个，在右下角，找到这个黑子就需要o(n^2)。大牛能给个提示怎么有效
找一个黑子吗？
【在 h*****a 的大作中提到】
: 好像是不需要起始黑子的位置的
|
h*****a
发帖数: 1718 | 46 其实前面的人都给了算法，就是binary search。N*log(N)
【在 s*****i 的大作中提到】
: 如果黑子只有一个，在右下角，找到这个黑子就需要o(n^2)。大牛能给个提示怎么有效
: 找一个黑子吗？
|
s****u
发帖数: 1433 | 47 搜索列肯定错。因为行列都可能是无限的。黑色可以拐弯。
估计是跟具当前黑子上下左右颜色决定策略然后 spawn |
s****u
发帖数: 1433 | |
r****c
发帖数: 2585 | 49 怎么不需要啊，我就是告诉你有一个黑的，不给你位置你哪里找得出位置如果你linear
search
【在 h*****a 的大作中提到】
: 好像是不需要起始黑子的位置的
|
g*****g
发帖数: 212 | 50 可以的，复杂度一样
linear
【在 r****c 的大作中提到】
: 怎么不需要啊，我就是告诉你有一个黑的，不给你位置你哪里找得出位置如果你linear
: search
|
|
|
P*****f
发帖数: 2272 | 51 你看我的帖子没？
linear
【在 r****c 的大作中提到】
: 怎么不需要啊，我就是告诉你有一个黑的，不给你位置你哪里找得出位置如果你linear
: search
|
e*****i
发帖数: 182 | 52 还是没有懂。。。元素是null怎么了- -求详细讲解 多谢了！
【在 g*****g 的大作中提到】
: 多谢多谢，得到了。这个null确实没考虑。
|
r****c
发帖数: 2585 | 53 怎么一样 先算算一维 不给你黑点位置你怎么知道
【在 g*****g 的大作中提到】
: 可以的，复杂度一样
:
: linear
|
r****c
发帖数: 2585 | 54 没看你帖子 没给你初始位置你怎么知道做binary search
你怎么都上当
【在 P*****f 的大作中提到】
: 你看我的帖子没？
:
: linear
|
g*****g
发帖数: 212 | 55 我是针对我之前贴的算法（在下面）说的
如果有null 会失败，
其实考虑这个case，除了保存一个cur之外，保存一个bool的hasnext就好了
----
第二题，似乎就是用一个private变量 cur 保存一个当前value就好了。
每次call next的时候，替换当前 cur，直到 null
call peek 返回 cur
hasnext 返回 cur ！= null
---
【在 e*****i 的大作中提到】
: 还是没有懂。。。元素是null怎么了- -求详细讲解 多谢了！
|
P*****f
发帖数: 2272 | 56 这题难点就是找初始位置。我还没想到nlogn的。刚开始的想法master theorem
算错了
【在 r****c 的大作中提到】
: 没看你帖子 没给你初始位置你怎么知道做binary search
: 你怎么都上当
|
e*****i
发帖数: 182 | 57 哦哦 多谢！但是不是不知道泛型的类型是什么么？
【在 g*****g 的大作中提到】
: 我是针对我之前贴的算法（在下面）说的
: 如果有null 会失败，
: 其实考虑这个case，除了保存一个cur之外，保存一个bool的hasnext就好了
: ----
: 第二题，似乎就是用一个private变量 cur 保存一个当前value就好了。
: 每次call next的时候，替换当前 cur，直到 null
: call peek 返回 cur
: hasnext 返回 cur ！= null
: ---
|
g****1
发帖数: 89 | 58 找初始位置最坏情况是O(N^2)，正如楼上大侠举的例子 -- 仅有一个黑子的情况。
【在 P*****f 的大作中提到】
: 这题难点就是找初始位置。我还没想到nlogn的。刚开始的想法master theorem
: 算错了
|
s****u
发帖数: 1433 | 59 复杂度的N应该代表黑子个数，而不是Matrix的边长。
Matrix边长可以是无限的，而总搜索次数仍然有限。 |
a****n
发帖数: 1887 | |
|
|
f*******w
发帖数: 1243 | |
