Google 电面两轮

God bless you, god bless me, and god bless others.

我想了一下要大概能说明问题的Fenwick tree至少要有7个node。我刚刚测了一下画这个图大概花20－30秒（照图抄，如果边想边画可能1分钟吧）。
                        0
                 /      |       \
             1         2         4
                        |         / \
                        3       5   6           
然后分三步讲：
1.先讲父子关系，可以举个例子，比如6的parent是4。
2.然后讲每个node存什么，以及prefix sum怎么算的。可以拿6举个例。
3.然后讲更新叶子结点需要更新哪些非叶结点。定义后继关系，需要拿3，5分别举例子。
到这里Fenwick tree算大致讲完，我刚试了一下，大概5－7分钟吧。但前提是面试官自己是懂的或者不纠缠细节（比如后继为什么是那个bit op)，只是来验证你是不是真懂...碰到不懂还非要问细节的感觉没辙...

当然，直接上来就拍一个2D Fenwick tree的，太不友好了...

第一题BIT应该不是面试官想要的答案，不知道他想要的答案是什么？

mnmunknown 发表于 2016-8-31 07:10
假如你当前 window 最左边出现了很多个 'A' ，如 AAAABCD，相对于 A 而言你的窗口向左缩小的过程中，直到 ...

哦哦，相当清楚了！谢谢楼主！

两个LC 加密的hard题，要不要怎么凶残。。

mnmunknown 发表于 2016-8-31 22:10
假如你当前 window 最左边出现了很多个 'A' ，如 AAAABCD，相对于 A 而言你的窗口向左缩小的过程中，直到 ...

那不能用left pointer的话，我是不是得用个堆来得到窗口中最靠左的字符，删除这个字符得到最新的窗口大小呢？

问下楼主 ACBE 中的ACB 算连续子序列么 （就是想问连续子序列的顺序能不能乱）？

whisperty 发表于 2016-9-2 05:53
那不能用left pointer的话，我是不是得用个堆来得到窗口中最靠左的字符，删除这个字符得到最新的窗口大小 ...

恩，我当时就是这么答的

zhucaiyi1234 发表于 2016-9-2 08:57
问下楼主 ACBE 中的ACB 算连续子序列么 （就是想问连续子序列的顺序能不能乱）？

第一题输入是 array of integers，5,7,9,10,11,12,13,20 这种

补充内容 (2016-9-3 02:28):
顺序不能乱，连续的 subarray

请问楼主subarray一定要连续的吗？像 9，100，101，10，11，12这样，是返回9，10，11，12还是100，101？