No.0004-CareerCup

You have a bunch of light bulbs. Store them as you wish. Implement a function that tells you if the light is on or off given its index and another one that toggles the state of the light bulbs given a start and end index.
你有一些灯泡，按照你自己的方法存储。实现一个方法，来确定某个序号的灯泡是否亮着；实现另一个方法，来对给定起始位置和结束位置的灯泡的翻转（也就是亮的变关，关的变亮）。

1. 询问

序号从0开始还是1？假设是0.序号有没有可能小于0或者大于最大index？假设不能。

2. 分析

直观解法

一个非常直观的解法就是存储到数组里面，这样查找是O(n)，翻转也是O(n)。空间复杂度O(n)。

如何改进

首先可以想到哈希表。使用哈希表，可以把查找降低为O(1)。但是翻转还是要遍历所有元素，O(n)。空间复杂度O(n)。
有没有更好的方法？考虑到灯泡只有两个状态，对应二进制比特，可以从这方面考虑。

二进制解法

假如有n个灯泡，那么可以表示为n位二进制数b，但是要注意溢出。这方面可以和面试官确认一下。和所用的语言有关，比如Python就无需考虑溢出。
那么，整个问题就转化为Bit Manipulation了。
确认序号为k的灯泡的状态，就是获取第k位二进制的值，即：b&(1<<k)>0，可以规定1代表亮，0代表关，那么这个结果自然就能表示亮或者关。
对起始位置s和结束位置e的灯泡进行翻转，首先获取从起始位置到结束位置的mask：1<<(e+1)-1<<s，然后用b与其异或即可，因为与1异或取反，与0异或不变。b^((1<<(e+1))-(1<<s))。
时间复杂度都是O(1)，空间复杂度O(1)。

3. 代码

class Solution:
    def __init__(self):
        self.b = 0

    def getLight(self, k):
        return self.b & (1 << k) > 0

    def reverseLight(self, s, e):
        self.b ^= ((1 << (e + 1)) - (1 << s))

4. 总结

难度medium，因为短时间内反应过来而且做到bug free确实没那么容易。