Google – Toggle Problem

Google – Toggle Problem
类似开关灯泡的题。要求实现
isToggled(long idx)
toggle(long start, long end)
这题难点在于有无限数量的灯泡，所以不能另开数据结构来存每个灯泡的状态。
[Solution]
[Solution #1]
Merge Interval
维护一个sorted list of interval表示已经toggled的灯泡。每次call toggle(start, end), 就生成一个新的Inveral [start, end], 扫描整个list，把和新interval重叠的部分删掉，把没有重叠的部分加进sorted list就可以了。
Query的时候就看idx是不是在list里面。
Pros: Query time O(k), where k is the number of toggled bubbles.
Cons: A little bit hard to implement
[Solution #2]
Bit Manipulation
因为这道题说了是无限量的灯泡，所以bit manipulation其实没法解。但是如果数量有限且在可接受范围之内的话，bit manipulation是个不错的解法。就有几个灯泡就开几个bit然后toggle就好了。时间空间复杂度都还可以。
[Solution #3]
Interval Tree
Interval Tree是一个BST, 每个node是记录一个range [low, high]，BST结构根据low来维护。除了记录range，每个node还记录一个maxValue表示以该结点为root的整个subtree的最大high值。
Insert node的时候不需要像segment tree那样考虑partial overlap的情况，如果不是complete overlap, 都作为一个新的node加入到bst，沿路更新每个node的maxValue就好了。
那么这道题就是维护一个interval tree, 每次call toggle()就加入新node，query的时候就计算包含idx的node有多少个。

class Solution {       ITNode root;       public boolean isToggled(long idx) {     int[] count = {0};     dfs(root, count, idx);     return count[0] % 2 != 0;   }       private void dfs(ITNode root, int[] count, long idx) {     if (root == null) {       return;     }           if (root.interval.low <= idx && idx <= root.interval.high) {       count[0]++;     }     dfs(root.left, count, idx);     dfs(root.right, count, idx);   }       public void toggle(long start, long end) {     if (root == null) {       root = new ITNode(new Interval(start, end));     }     else {       insert(root, new Interval(start, end));     }   }       private ITNode insert(ITNode root, Interval interval) {     if (root == null) {       return new ITNode(interval);     }     if (interval.low < root.interval.low) {       root.left = insert(root.left, interval);     }     else {       root.right = insert(root.right, interval);     }   }       private class ITNode {     Interval interval;           ITNode left;     ITNode right;           ITNode(Interval interval) {       this.interval = interval;     }   }       private class Interval {     long low;     long high;           Interval(long low, long high) {       this.low = low;       this.high = high;     }   }     }

https://instant.1point3acres.com/thread/130512
有一排数量无限的object，每个object有两个状态，可以用true和false来表示，object的状态是可切换的，初始情况下所有object的状态都是false。让你设计一个class，实现两个方法：isToggled(long idx), toggle(long start, long end)。这题没记错的话之前面经里也出现过。我最后给出的方法是维护一个list of intervals, 每次执行toggle时都要新加入一个新interval，然后把这个新interval merge进已有的interval list里面，这个解法的问题在于实现起来非常复杂，因为做merge操作时你需要反转所有和新interval重叠的interval的状态，最后才把新interval里不重叠的部分加进list里面。最后代码也没写完，

但是写到中间我突然想起来之前看到一个面经里的比较类似的题，可以只记录每个object的toggle操作的次数，最后根据操作次数的奇偶来判断object的状态，如此一来就不需要实际记录状态，只需要维护一个balanced interval tree，每次toggle就把新interval加进tree里，执行isToggled(long idx)时计算所有包含给定idx的interval的数量就能决定对应的object的状态了。跟面试官提了提这个做法，面试官表示这就是他的解法，但是他觉得我给的解法也不错，查询的复杂度要比他的方法低，就是难实现。

https://github.com/UmassJin/Leetcode/blob/master/Experience/google面经集合.py
不，面试官就是期待我提出这样的解法，他也说了如果写对应的代码的话不需要实现balanced interval tree，假设有这么个现成的数据结构给你用就行了。
因为interval tree不难写，但是balanced的就没那么好写了。。

Read full article from Google – Toggle Problem