狗家跪经（题真的巨简单跪的也莫名其妙

可能缘分未到～～～

复盘楼主的面试过程，其实跪的并不是那么莫名其妙。（以下假设toggle的操作次数为m，isOn的操作次数是n）

1.这个面试官很鸡贼，出的第一题就是一个区分度很强的题目。这种题目往往看似简单，但套路很深。经验不丰富的coder很容易直接给出暴力解法，这样就会给面试官一个很negative的印象。

2.面试官发现你把这个问题想得太简单的时候，给过一个hint：“需要操作的灯泡数量很少怎么办？”，就是暗示你要考虑到时间空间复杂度。很显然这个hint是让你用位运算来做，因为这样的时空复杂度是最优的（时间 o(m+n))。如果这时候能根据不同计算机的字长（32位？64位？）来回答，肯定是加分项。

3.然后面试官发现你还是没明白他想要考你什么，就非常直白的告诉你，“现在你这个time complexity不太好”，然而你接下来回答的方法的时间复杂度是 o(n*m)。。。

4.最后面试官问你“call很少几次toggle但是call很多次isOn”，意思就是想让你把isOn 操作的时间复杂度降到最低。如果内存足够的的时候，时间复杂度就是o(1)；如果内存不够用，时间复杂度是o(logm)。

从中可以总结两个tips：
1.虽然算法题很重要，但绝不简单的等同于智力题。因为，在实际情况中，用什么样的算法很大程度上取决于具体的应用场景（比如这道题里的各种follow up）和实际的硬件条件（比如，字长是多少？内存够不够？）。所以，熟练掌握计算机相关的基础知识也很重要。面试官往往都是实际经验很丰富的工程师，如果能结合实际情况来答算法题，给面试官的印象肯定要加分不少。

2.对于这种看似简单但套路很深的题目，一定不要上来就给暴力解，这样会正中面试官的下怀。应该直接把题目里隐藏的套路点出来，才能让面试官开心。

把区间修改 单点查询 转化成单点修改 区间查询 就可以用树状数组做了嘛。。

brn 发表于 2017-11-3 00:12
我估计楼主没见过 树状数组 线段树 这种鬼东西。。。

没见过的很难在onsite上当场想出来

segment tree 会写。但是感觉binary index tree还是跟segment tree不太一样。主要面试的时候如果没见过这种题的话会自然而然想到brute force再继续优化。还是gg要求比较高我没有达到要求吧。

这题挺难的

今天电面也是这道题，面试官问如果灯泡很多的话该怎么优化。我给的思路是用一个vector<pair<int,int>>存灯泡亮的range，那样变成一个更复杂一点的merge interval，也没写完。

那些follow up都是应该你主动问的，一楼说的很好。