C******w
发帖数: 23 | 1 10月17日，第一轮电面：
第一题：上海的电话isTree(vector >& edges); (离散化+dfs判环
判联通)
第二题，
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
y2)
inclusive, and there is an infinite stream of such 2 types of
operations which have to supported. How would you store the values for
efficient updates and retrievals ? （二维线段树 说算法+分析复杂度）
第一轮答得还可以。
10月30日，第二轮电面：(挂)
美国的电话，面试官很nice：
第一题。一个二叉树，节点值有正有负，求树中的任意路径的最大值。路径的值就
是路径经过点的值的和。然后我说dfs，面试官就让写代码 。 写代码一开始dfs的接
口声明有问题，期间停下来修改了一下，然后写完。被面试官查出1个bug。面试官提示
了，一开始找出了另外个bug；面试官又提示了一下，才找出了面试官想要我fix的bug
。杯具。
第二题。给三个字符串，a，b，c。问a 和b 能不能组成c，且保证c 中a b 的字母
顺序不变。 一开始我给了一个没验证贪心的想法。然后面试官让我验证或举个反例。
我想贪心多数没戏，就又说了种dp的思路。面试官让我写下来。我写完之后，让我解释
了解释。然后突然悲催地发现我的解法是O(2^n)的。。面试后想想如果我的解法状态去
重后，就和普通的dp无异了。。 杯具 。。 然后就挂了。
哎，悲伤，简单题目答成这样，白白浪费了这次机会。
背景：国内渣本科毕业一年，有ACM竞赛经验。平常做算法题还可以，leetcode上
刷题也从没看过其他人的题解。还是把google电面想的太easy了，所以心态上有松懈。
而且加之早上起早有些困。。。 总之这些都是次要原因，主要还是因为太他妈挫了。
好好努力，来年再战！ | a***m
发帖数: 5037 | 2 谢分享 二叉树最大路径 好像是leetcode 原题啊 | j*******t
发帖数: 223 | 3 貌似第一题不是leetcode原题。其他还好。至少第二面都是原题。 | l*n
发帖数: 529 | 4 第三个的最大路径用dfs怎么做的？感觉是recursion的问题啊。
【在 C******w 的大作中提到】
: 10月17日，第一轮电面：
: 第一题：上海的电话isTree(vector >& edges); (离散化+dfs判环
: 判联通)
: 第二题，
: Given a 2D space of maximum size NxN which supports two operations :
: [1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
: [2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
: y2)
: inclusive, and there is an infinite stream of such 2 types of
: operations which have to supported. How would you store the values for
| P*******r
发帖数: 210 | 5 最大路径不是也是leetcode上的吗，一般都考虑用recursion.
请问第二题怎么解？能展开一下吗？
【在 l*n 的大作中提到】
: 第三个的最大路径用dfs怎么做的？感觉是recursion的问题啊。
| f********4
发帖数: 988 | 6 第二面都是leetcode原题吧感觉，怎么会挂呢。。 | s****n
发帖数: 147 | | C******w
发帖数: 23 | 8 刚刚看了下，确实是leetcode原题。leetcode没刷全，只刷了100道。这两道题没做。
凄惨。 | f**x
发帖数: 21 | | n****e
发帖数: 678 | 10 楼主能说说第一轮店面的第二题吗？
能展开说说如何用二维线段树来做吗？
【在 C******w 的大作中提到】
: 10月17日，第一轮电面：
: 第一题：上海的电话isTree(vector >& edges); (离散化+dfs判环
: 判联通)
: 第二题，
: Given a 2D space of maximum size NxN which supports two operations :
: [1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
: [2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
: y2)
: inclusive, and there is an infinite stream of such 2 types of
: operations which have to supported. How would you store the values for
| | | z****s
发帖数: 409 | 11 一面题一没看懂，什么叫isTree，判断是不是树？怎么还用离散化了？
二面题一直接树链剖分。
二面题二也没看懂，什么叫用a，b构成c，怎么构？ | e***s
发帖数: 799 | | n***t
发帖数: 8357 | 13 no disrespect at all.
but, with this kind of effort, people should try to make much bigger money
from market, instead of trying to find an opp to work for other people. | c********p
发帖数: 1969 | | n*****f
发帖数: 17 | 15 楼主ACM都忘光了吧。。。这4题都是ACM基本题啊亲
一面第一题，用并查集更好些
一面第二题，如果要写code的话，用树状数组更好写
二面第一题，别说是二叉树了，就是多叉树都应该秒了它。这丫不就是最大子段和跑到
树上去了么
二面第二题，O(n^2)DP | C******w
发帖数: 23 | 16 1.1 就是判断是否是树，输入的val有可能很大，但节点数很小，所以离散化
2.1 给会树链剖分的大牛跪
2.2 ab cd combine 成 acbd
【在 z****s 的大作中提到】
: 一面题一没看懂，什么叫isTree，判断是不是树？怎么还用离散化了？
: 二面题一直接树链剖分。
: 二面题二也没看懂，什么叫用a，b构成c，怎么构？
| C******w
发帖数: 23 | 17 确实。。。
毕业一年多，没正经做过题
看来以后要多刷刷TC CF比赛了。。。
【在 n*****f 的大作中提到】
: 楼主ACM都忘光了吧。。。这4题都是ACM基本题啊亲
: 一面第一题，用并查集更好些
: 一面第二题，如果要写code的话，用树状数组更好写
: 二面第一题，别说是二叉树了，就是多叉树都应该秒了它。这丫不就是最大子段和跑到
: 树上去了么
: 二面第二题，O(n^2)DP
| t****g
发帖数: 96 | | m*****t
发帖数: 334 | 19 How to solve this one?
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
y2)
inclusive, and there is an infinite stream of such 2 types of
operations which have to supported. How would you store the values for
efficient updates and retrievals ? | w*******s
发帖数: 138 | 20 解答：
http://hawstein.com/posts/binary-indexed-trees.html
【在 m*****t 的大作中提到】
: How to solve this one?
: Given a 2D space of maximum size NxN which supports two operations :
: [1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
: [2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
: y2)
: inclusive, and there is an infinite stream of such 2 types of
: operations which have to supported. How would you store the values for
: efficient updates and retrievals ?
| | | z*****k
发帖数: 57 | 21 这东西如果面试官不懂的话，花20分钟也解释不清楚吧。
【在 w*******s 的大作中提到】
: 解答：
: http://hawstein.com/posts/binary-indexed-trees.html
| e*n
发帖数: 22 | | x******r
发帖数: 367 | 23 问个简单问题。
第一轮电面和第二轮电面第二题分别对应于Leetcode的哪个题？
BTW,我Leetcode没做完。
【在 C******w 的大作中提到】
: 10月17日，第一轮电面：
: 第一题：上海的电话isTree(vector >& edges); (离散化+dfs判环
: 判联通)
: 第二题，
: Given a 2D space of maximum size NxN which supports two operations :
: [1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
: [2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
: y2)
: inclusive, and there is an infinite stream of such 2 types of
: operations which have to supported. How would you store the values for
| P**********k
发帖数: 1629 | 24 这个不就是用integral image
先建一个NxN的pre-sum数组，然后这个数组的(i,j)元素存的是从(0, 0)到(i, j)的
subarray的和，
这样每次query任意sub-array的和，只用取出对应这个pre-sum数组的四个顶点的值
A -----B
| |
| |
C-----D
然后计算A+D-B-C就行了,这样query就是O(1).
【在 m*****t 的大作中提到】
: How to solve this one?
: Given a 2D space of maximum size NxN which supports two operations :
: [1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
: [2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
: y2)
: inclusive, and there is an infinite stream of such 2 types of
: operations which have to supported. How would you store the values for
: efficient updates and retrievals ?
| c******0
发帖数: 260 | 25 你的方法对于query很有效。但是对update不够高效。可能要把整个matrix遍历一遍来
update。
【在 P**********k 的大作中提到】
: 这个不就是用integral image
: 先建一个NxN的pre-sum数组，然后这个数组的(i,j)元素存的是从(0, 0)到(i, j)的
: subarray的和，
: 这样每次query任意sub-array的和，只用取出对应这个pre-sum数组的四个顶点的值
: A -----B
: | |
: | |
: C-----D
: 然后计算A+D-B-C就行了,这样query就是O(1).
| x*********w
发帖数: 533 | | C******w
发帖数: 23 | 27 10月17日，第一轮电面：
第一题：上海的电话isTree(vector >& edges); (离散化+dfs判环
判联通)
第二题，
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
y2)
inclusive, and there is an infinite stream of such 2 types of
operations which have to supported. How would you store the values for
efficient updates and retrievals ? （二维线段树 说算法+分析复杂度）
第一轮答得还可以。
10月30日，第二轮电面：(挂)
美国的电话，面试官很nice：
第一题。一个二叉树，节点值有正有负，求树中的任意路径的最大值。路径的值就
是路径经过点的值的和。然后我说dfs，面试官就让写代码 。 写代码一开始dfs的接
口声明有问题，期间停下来修改了一下，然后写完。被面试官查出1个bug。面试官提示
了，一开始找出了另外个bug；面试官又提示了一下，才找出了面试官想要我fix的bug
。杯具。
第二题。给三个字符串，a，b，c。问a 和b 能不能组成c，且保证c 中a b 的字母
顺序不变。 一开始我给了一个没验证贪心的想法。然后面试官让我验证或举个反例。
我想贪心多数没戏，就又说了种dp的思路。面试官让我写下来。我写完之后，让我解释
了解释。然后突然悲催地发现我的解法是O(2^n)的。。面试后想想如果我的解法状态去
重后，就和普通的dp无异了。。 杯具 。。 然后就挂了。
哎，悲伤，简单题目答成这样，白白浪费了这次机会。
背景：国内渣本科毕业一年，有ACM竞赛经验。平常做算法题还可以，leetcode上
刷题也从没看过其他人的题解。还是把google电面想的太easy了，所以心态上有松懈。
而且加之早上起早有些困。。。 总之这些都是次要原因，主要还是因为太他妈挫了。
好好努力，来年再战！ | a***m
发帖数: 5037 | 28 谢分享 二叉树最大路径 好像是leetcode 原题啊 | j*******t
发帖数: 223 | 29 貌似第一题不是leetcode原题。其他还好。至少第二面都是原题。 | l*n
发帖数: 529 | 30 第三个的最大路径用dfs怎么做的？感觉是recursion的问题啊。
【在 C******w 的大作中提到】
: 10月17日，第一轮电面：
: 第一题：上海的电话isTree(vector >& edges); (离散化+dfs判环
: 判联通)
: 第二题，
: Given a 2D space of maximum size NxN which supports two operations :
: [1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
: [2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
: y2)
: inclusive, and there is an infinite stream of such 2 types of
: operations which have to supported. How would you store the values for
| | | P*******r
发帖数: 210 | 31 最大路径不是也是leetcode上的吗，一般都考虑用recursion.
请问第二题怎么解？能展开一下吗？
【在 l*n 的大作中提到】
: 第三个的最大路径用dfs怎么做的？感觉是recursion的问题啊。
| f********4
发帖数: 988 | 32 第二面都是leetcode原题吧感觉，怎么会挂呢。。 | s****n
发帖数: 147 | | C******w
发帖数: 23 | 34 刚刚看了下，确实是leetcode原题。leetcode没刷全，只刷了100道。这两道题没做。
凄惨。 | f**x
发帖数: 21 | | n****e
发帖数: 678 | 36 楼主能说说第一轮店面的第二题吗？
能展开说说如何用二维线段树来做吗？
【在 C******w 的大作中提到】
: 10月17日，第一轮电面：
: 第一题：上海的电话isTree(vector >& edges); (离散化+dfs判环
: 判联通)
: 第二题，
: Given a 2D space of maximum size NxN which supports two operations :
: [1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
: [2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
: y2)
: inclusive, and there is an infinite stream of such 2 types of
: operations which have to supported. How would you store the values for
| z****s
发帖数: 409 | 37 一面题一没看懂，什么叫isTree，判断是不是树？怎么还用离散化了？
二面题一直接树链剖分。
二面题二也没看懂，什么叫用a，b构成c，怎么构？ | e***s
发帖数: 799 | | n***t
发帖数: 8357 | 39 no disrespect at all.
but, with this kind of effort, people should try to make much bigger money
from market, instead of trying to find an opp to work for other people. | c********p
发帖数: 1969 | | | | n*****f
发帖数: 17 | 41 楼主ACM都忘光了吧。。。这4题都是ACM基本题啊亲
一面第一题，用并查集更好些
一面第二题，如果要写code的话，用树状数组更好写
二面第一题，别说是二叉树了，就是多叉树都应该秒了它。这丫不就是最大子段和跑到
树上去了么
二面第二题，O(n^2)DP | C******w
发帖数: 23 | 42 1.1 就是判断是否是树，输入的val有可能很大，但节点数很小，所以离散化
2.1 给会树链剖分的大牛跪
2.2 ab cd combine 成 acbd
【在 z****s 的大作中提到】
: 一面题一没看懂，什么叫isTree，判断是不是树？怎么还用离散化了？
: 二面题一直接树链剖分。
: 二面题二也没看懂，什么叫用a，b构成c，怎么构？
| C******w
发帖数: 23 | 43 确实。。。
毕业一年多，没正经做过题
看来以后要多刷刷TC CF比赛了。。。
【在 n*****f 的大作中提到】
: 楼主ACM都忘光了吧。。。这4题都是ACM基本题啊亲
: 一面第一题，用并查集更好些
: 一面第二题，如果要写code的话，用树状数组更好写
: 二面第一题，别说是二叉树了，就是多叉树都应该秒了它。这丫不就是最大子段和跑到
: 树上去了么
: 二面第二题，O(n^2)DP
| t****g
发帖数: 96 | | m*****t
发帖数: 334 | 45 How to solve this one?
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
y2)
inclusive, and there is an infinite stream of such 2 types of
operations which have to supported. How would you store the values for
efficient updates and retrievals ? | w*******s
发帖数: 138 | 46 解答：
http://hawstein.com/posts/binary-indexed-trees.html
【在 m*****t 的大作中提到】
: How to solve this one?
: Given a 2D space of maximum size NxN which supports two operations :
: [1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
: [2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
: y2)
: inclusive, and there is an infinite stream of such 2 types of
: operations which have to supported. How would you store the values for
: efficient updates and retrievals ?
| z*****k
发帖数: 57 | 47 这东西如果面试官不懂的话，花20分钟也解释不清楚吧。
【在 w*******s 的大作中提到】
: 解答：
: http://hawstein.com/posts/binary-indexed-trees.html
| e*n
发帖数: 22 | | x******r
发帖数: 367 | 49 问个简单问题。
第一轮电面和第二轮电面第二题分别对应于Leetcode的哪个题？
BTW,我Leetcode没做完。
【在 C******w 的大作中提到】
: 10月17日，第一轮电面：
: 第一题：上海的电话isTree(vector >& edges); (离散化+dfs判环
: 判联通)
: 第二题，
: Given a 2D space of maximum size NxN which supports two operations :
: [1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
: [2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
: y2)
: inclusive, and there is an infinite stream of such 2 types of
: operations which have to supported. How would you store the values for
| P**********k
发帖数: 1629 | 50 这个不就是用integral image
先建一个NxN的pre-sum数组，然后这个数组的(i,j)元素存的是从(0, 0)到(i, j)的
subarray的和，
这样每次query任意sub-array的和，只用取出对应这个pre-sum数组的四个顶点的值
A -----B
| |
| |
C-----D
然后计算A+D-B-C就行了,这样query就是O(1).
【在 m*****t 的大作中提到】
: How to solve this one?
: Given a 2D space of maximum size NxN which supports two operations :
: [1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
: [2] int QUERY(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,
: y2)
: inclusive, and there is an infinite stream of such 2 types of
: operations which have to supported. How would you store the values for
: efficient updates and retrievals ?
| | | c******0
发帖数: 260 | 51 你的方法对于query很有效。但是对update不够高效。可能要把整个matrix遍历一遍来
update。
【在 P**********k 的大作中提到】
: 这个不就是用integral image
: 先建一个NxN的pre-sum数组，然后这个数组的(i,j)元素存的是从(0, 0)到(i, j)的
: subarray的和，
: 这样每次query任意sub-array的和，只用取出对应这个pre-sum数组的四个顶点的值
: A -----B
: | |
: | |
: C-----D
: 然后计算A+D-B-C就行了,这样query就是O(1).
| x*********w
发帖数: 533 | | s******t
发帖数: 229 | | f******n
发帖数: 279 | |
|
