h****p
发帖数: 87 | 1 常见就略去了
1） 不能再常见的题了，判断是否是BST 很简单 我用了递归的版本 然后接着问What
if the most left leaf value equal Integer.MIN_VALUE?
2） 数组（任意数组）find break point使得两边子数组（子数组必须至少有一个
element）sum的差最大 followup： 如
果找2个break point呢（假设2个点把数组分成3个子数组的sum是A,B,C 差异就是|A-B|
+|B-C|+|C-A| ）?使得三个子数组差异最大。。。然后是n的情况。。。后面卡住了没
找出规律。
3） interval的变形 给定很多的timeslots有开始时间和结束时间 让你返回所有有
冲突的timeslot
大家可以写一下交流交流 |
s*****e
发帖数: 1679 | |
u*****o
发帖数: 1224 | 3 找数组break point使得两边子数组差最大
这个数组是ROTATED SORTED ARRAY？中间有个转折点？不太明白题意啊LZ。。。 |
x******2
发帖数: 546 | 4 第2题大于2个点怎么定义差异最大？
What
【在 h****p 的大作中提到】
: 常见就略去了
: 1） 不能再常见的题了，判断是否是BST 很简单 我用了递归的版本 然后接着问What
: if the most left leaf value equal Integer.MIN_VALUE?
: 2） 数组（任意数组）find break point使得两边子数组（子数组必须至少有一个
: element）sum的差最大 followup： 如
: 果找2个break point呢（假设2个点把数组分成3个子数组的sum是A,B,C 差异就是|A-B|
: +|B-C|+|C-A| ）?使得三个子数组差异最大。。。然后是n的情况。。。后面卡住了没
: 找出规律。
: 3） interval的变形 给定很多的timeslots有开始时间和结束时间 让你返回所有有
: 冲突的timeslot
|
h****p
发帖数: 87 | 5 原帖上 解释了下 看下吧~
【在 x******2 的大作中提到】
: 第2题大于2个点怎么定义差异最大？
:
: What
|
u*****o
发帖数: 1224 | 6 如果有一个break point, 是不是找出最小值， 自己为一组，其他所有的数为一组呢？
What
-C
【在 h****p 的大作中提到】
: 常见就略去了
: 1） 不能再常见的题了，判断是否是BST 很简单 我用了递归的版本 然后接着问What
: if the most left leaf value equal Integer.MIN_VALUE?
: 2） 数组（任意数组）find break point使得两边子数组（子数组必须至少有一个
: element）sum的差最大 followup： 如
: 果找2个break point呢（假设2个点把数组分成3个子数组的sum是A,B,C 差异就是|A-B|
: +|B-C|+|C-A| ）?使得三个子数组差异最大。。。然后是n的情况。。。后面卡住了没
: 找出规律。
: 3） interval的变形 给定很多的timeslots有开始时间和结束时间 让你返回所有有
: 冲突的timeslot
|
h****p
发帖数: 87 | 7 break point是把数组分成两个子数组。。不是让你随机组合
【在 u*****o 的大作中提到】
: 如果有一个break point, 是不是找出最小值， 自己为一组，其他所有的数为一组呢？
:
: What
: -C
|
o******e
发帖数: 1001 | 8 第二个题目，如果只有一个break point,比较好做，其实先算一个总和，然后看不同的
分割点之前的和与总和的差值。如果多点break point,是不是用dynamic programming
了？
What
B|
【在 h****p 的大作中提到】
: 常见就略去了
: 1） 不能再常见的题了，判断是否是BST 很简单 我用了递归的版本 然后接着问What
: if the most left leaf value equal Integer.MIN_VALUE?
: 2） 数组（任意数组）find break point使得两边子数组（子数组必须至少有一个
: element）sum的差最大 followup： 如
: 果找2个break point呢（假设2个点把数组分成3个子数组的sum是A,B,C 差异就是|A-B|
: +|B-C|+|C-A| ）?使得三个子数组差异最大。。。然后是n的情况。。。后面卡住了没
: 找出规律。
: 3） interval的变形 给定很多的timeslots有开始时间和结束时间 让你返回所有有
: 冲突的timeslot
|
l*****c
发帖数: 52 | 9 第二题能不能用一个空数组
1. 从左到右扫一遍 记录如果这个点是breakpoint 左边的和
2. 从右到左扫一遍 计算如果当前点是breakpoint 右边的数的和
然后得到最大值
n个点还不知道怎么搞……
What
B|
【在 h****p 的大作中提到】
: 常见就略去了
: 1） 不能再常见的题了，判断是否是BST 很简单 我用了递归的版本 然后接着问What
: if the most left leaf value equal Integer.MIN_VALUE?
: 2） 数组（任意数组）find break point使得两边子数组（子数组必须至少有一个
: element）sum的差最大 followup： 如
: 果找2个break point呢（假设2个点把数组分成3个子数组的sum是A,B,C 差异就是|A-B|
: +|B-C|+|C-A| ）?使得三个子数组差异最大。。。然后是n的情况。。。后面卡住了没
: 找出规律。
: 3） interval的变形 给定很多的timeslots有开始时间和结束时间 让你返回所有有
: 冲突的timeslot
|
H****S
发帖数: 1359 | 10 感觉第二题有点像刷墙那题的变种。如果没有什么非常clever的pattern yet to
discover，就必然是DP无疑了。。。 |
|
|
c********p
发帖数: 1969 | |
s***g
发帖数: 1250 | 12 这样需要两个数组吧？
【在 l*****c 的大作中提到】
: 第二题能不能用一个空数组
: 1. 从左到右扫一遍 记录如果这个点是breakpoint 左边的和
: 2. 从右到左扫一遍 计算如果当前点是breakpoint 右边的数的和
: 然后得到最大值
: n个点还不知道怎么搞……
:
: What
: B|
|
p*****2
发帖数: 21240 | |
h****p
发帖数: 87 | 14 2爷，第三题有什么好思路？
【在 p*****2 的大作中提到】
: n点就是个二维dp吧？
|
h********5
发帖数: 114 | 15 这个怎么处理，麻烦楼主讲一下
然后接着问What
: if the most left leaf value equal Integer.MIN_VALUE? |
l*****c
发帖数: 52 | 16 一个就行 算右边的时候 直接算绝对值就行了
【在 s***g 的大作中提到】
: 这样需要两个数组吧？
|
h****p
发帖数: 87 | 17 我提了下big Integer，面试官也没怎么反馈，不知道大家怎么看？
第2题的扩展面试官最后也说了 会很复杂 不期望我能答出来，就是想看看我有什么思路
第3题大家有什么思路吗
【在 h********5 的大作中提到】
: 这个怎么处理，麻烦楼主讲一下
: 然后接着问What
: : if the most left leaf value equal Integer.MIN_VALUE?
|
D****6
发帖数: 278 | 18 加个check就行了。
【在 h********5 的大作中提到】
: 这个怎么处理，麻烦楼主讲一下
: 然后接着问What
: : if the most left leaf value equal Integer.MIN_VALUE?
|
s******e
发帖数: 493 | 19 3. sorting on start time and then move to check till a start time is bigger
than the end time of the currently checked one. keep going. might not be
optimal. seems to be able to borrow kmp idea for reducing the time. |
z****e
发帖数: 54598 | |
|
|
z****e
发帖数: 54598 | 21 这个sort还是比较生僻的
需要实现Comparator接口
bigger
【在 s******e 的大作中提到】
: 3. sorting on start time and then move to check till a start time is bigger
: than the end time of the currently checked one. keep going. might not be
: optimal. seems to be able to borrow kmp idea for reducing the time.
|
h****p
发帖数: 87 | 22 怎么check？
【在 D****6 的大作中提到】
: 加个check就行了。
|
D****6
发帖数: 278 | 23 most left leaf is MIN_VALUE or most right leaf is MAX_VALUE, 都是special
case需要额外check. 他不是这意思？？
if(root.left == null && root.val == Integer.MIN_VALUE)
return true;
【在 h****p 的大作中提到】
: 怎么check？
|
p*****2
发帖数: 21240 | 24
具体我也不清楚要求，感觉sort一下应该就能处理了吧。
【在 h****p 的大作中提到】
: 2爷，第三题有什么好思路？
|
p*****2
发帖数: 21240 | 25
这个需要特殊处理吗？
【在 h********5 的大作中提到】
: 这个怎么处理，麻烦楼主讲一下
: 然后接着问What
: : if the most left leaf value equal Integer.MIN_VALUE?
|
v***n
发帖数: 562 | |
f*******b
发帖数: 520 | |
c********e
发帖数: 186 | 28 sort之后怎么弄？ interval tree到是可以，觉得写code有点难
【在 z****e 的大作中提到】
: 第三个sort一下
|
