CareerCup

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for private lessons by FB, Google and Uber engineers

Our ONE TO ONE class offers

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

//Binary Indexed Tree (O(logN) Toggle, O(logN) Get.
public class ToggleBulbs {

    int[] bulbs;

    public ToggleBulbs(int n) { //n bulbs given

        bulbs = new int[n + 1];
    }

    public boolean isOn(int i) {
        //a bulb is on if it's toggled an odd number of times
        return read(i) % 2 == 1;
    }

    // toggle(i, j) is equivalent to
    // toggle(i, n - 1) and then toggle(j, n - 1)
    public void toggle(int i,int j) {
        toggle(i);
        toggle(j + 1);
    }

    //toggle from ith to the last bulb (a standard update in BITree)
    private void toggle(int idx){
        int node = idx + 1;
        while (node < bulbs.length){
            bulbs[node] = (bulbs[node] + 1) % 2;
            node += (node & -node);
        }
    }

    //get the number of times bulb i toggled (read prefix sum from 0 to i in BITree)
    private int read(int idx) {
        int node = idx + 1;
        int sum = 0;
        while (node > 0) {
            sum += bulbs[node];
            node -= (node & -node);
        }
        return sum;
    }

}

No, I think a bitset is by far the easiest solution. O(n) toggle, O(1) access, and the most space efficient. The (Fenwick) tree solution is O(log n) toggle, but it's also O(log n) access, so pick your poison (are you going to toggle lots, or query lots?). However you'd need to know the number of bulbs beforehand, you can't dynamically allocate a bitset in C++. But a bool vector is about as good.

{{

std::vector<bool> lightbulbs(false);
lightbulbs.resize(N);


void toggle(int i, int j){
for(int u=i; u <=j; u++) lightbulbs.at(u) ^= lightbulbs.at(u);
}

bool isOn(int i){
return lightbulbs.at(i);
}

}}

Why would you need an Indexed Binary Tree for these use cases?

Why an indexes binary tree?

To do it optimally for toggle(i, j), we update arr[i] (using 1 based index) to 1 and arr[j+1] to 1, so that to get isOn for any index, we just have to sum the values from 1st index to that index, if its cumulative sum is 1 (mod 2), then it is ON, otherwise OFF.

E.g. In array of size 10, if we have to toggle (2, 5), then make arr[2] = 1 and arr[6] = 1, then to get isOn(3), sum from arr[1] to arr[3] = 1, thus ON, to get isOn(8) = sum from arr[1] to arr[8] = 2 = 0(mod2), thus OFF

Now to store cumulative sum optimally, use BIT.

int[] arr = new int[n+1];

public static void toggle(int i, int j) {
        i++;
        j++;
        set(i);
        set(j+1);
}

public static boolean isOn(int i) {
        i++;
        int sum = 0;
        int pos = i;
        while (pos > 0) {
            sum += arr[pos];
            sum %= 2;
            pos -= (pos & (-pos));
        }
        return (sum%2 == 1);
}

private static void set(int i) {
        int pos = i;
        while (pos <= n) {
            arr[pos] += 1;
            arr[pos] %= 2;
            pos += (pos & (-pos));
        }
}

isOn(int i){
return a[i]=="OFF"? "OFF":"ON";
}

toggle(int i, int j){
//N is length of array
if (j<N)
int (k=i;k<=j;k++){
if(a[k] == "OFF"){
 a[k] = "ON";
}
else{
 a[k] = "OFF";
}
}
}

Why not use an interval tree, with the tree nodes storing lists of pairs of the form <Interval,count_of_toggles_done_to_the_interval>.
On each toggle operation on (i,j), follow the interval tree construction algorithm to locate/create the node where the new interval can be added. If the interval has already been toggled, we'd discover it, and therefore increment the toggle_counter. Otherwise,we'd just insert the pair <(i,j),1>. This can be achieved in log(n) time, where n is the current size of the interval tree.

isOn(i) would then just be an interval tree lookup for enumerating all the intervals that contain i. We can then sum up the toggle_counters of the intervals in that intersection list, and return (sum%2 != 0) (since the bulbs were initially all off)

bool A[n]={false};
isOn(int i){
if(0 <=i <n) return a[i];
}

toggle(int i, int j){
//N is length of array
if (0<= j<N) && (0<= i<N) && (i<j)
int (k=i;k<=j;k++){
A[k] = !A[k];
}
}

It sounds to me that we could simply use a bit vector and the toggle of [i,j] would be a xor with 1 on the related bits.
Am I missing something?