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 for FLAG & U)
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 and other top tier companies after weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!



Solution:
I. If it is a write-heavy application, create a Fenwick Tree to store for every toggle(i, j), add 1 to node i and -1 to node j (O(logN)). Upon calling isOn(k), get the cumulative sum (O(logN)) till the kth node. If sum is odd, then bulb is on. Otherwise bulb is off.

II. If it is read-heavy, create a bit map that toggles in linear time and reads in constant time.

//Fenwick Tree Solution
public class ToggleBulbs {

    int[] sum;

    public ToggleBulbs(int n) {
        sum = new int[n];
    }

    public boolean isOn(int i)
    {
        return read(i)%2==1;
    }

    public void toggle(int start,int end)
    {
        update(start,1);
        update(end+1,-1);
    }

    private int read(int idx){
        int ans = 0;
        while (idx > 0){
            ans += sum[idx];
            idx -= (idx & -idx);
        }
        return ans;
    }

    private void update(int idx ,int val){
        while (idx <= sum.length){
            sum[idx] += val;
            idx += (idx & -idx);
        }
    }
}

A much simpler approach using Java BigIntegers:

/* A clean solution using Java BigInteger.
We need to have N bulbs, so N binary digits we need 
To have so, we must have a N+1 size integer.
*/
def Bulbs{
   def $$(N){
     s = str(2 ** ( N + 1 ))
     $.underlying = new ( 'java.math.BigInteger' , s )
   }
   def is_on(i){
    // tutorialspoint.com/java/math/biginteger_testbit.htm 
    $.underlying.testBit(i)
   }
   def toggle(start,end){
     $.underlying = fold([start:end+1],$.underlying){
      // tutorialspoint.com/java/math/biginteger_flipbit.htm
      $.p.flipBit($.o)
     }
   }
}

If the number is square then only it will remain on . Otherwise off.
The square numbers have odd number of factors

class Lamps {
	public:
		Lamps(int size)
		{
			size_ = size;
			block_size_ = sizeof(map_[0]) * 8;
			map_.resize(size / block_size_ + (size % block_size_ != 0 ? 1 : 0));
		}
		void Toggle(int from, int to)
		{
			if (from >= 0 &&
				from < size_ &&
				to >= 0 &&
				to < size_ &&
				from <= to)
			{
				int start_block_idx = from / block_size_;
				int end_block_idx = to / block_size_;
				int head_size = from % block_size_;
				int tail_size = block_size_ - ((to + 1) % block_size_);
				uint64_t head_mask = ~((uint64_t)-1 >> head_size);
				uint64_t tail_mask = ~((uint64_t)-1 << tail_size);
				uint64_t head_stored = map_[start_block_idx];
				uint64_t tail_stored = map_[end_block_idx];
				for (int i = start_block_idx; i <= end_block_idx; ++i) {
					map_[i] = ~map_[i];
				}
				map_[start_block_idx] &= ~head_mask;
				map_[start_block_idx] |= head_stored & head_mask;
				map_[end_block_idx] &= ~tail_mask;
				map_[end_block_idx] |= tail_stored & tail_mask;
			}
		}
		bool IsOn(int idx)
		{
			bool on = false;
			if (idx >= 0 &&
				idx < size_)
			{
				on = (map_[idx / block_size_] >> (block_size_ - ((idx + 1) % block_size_))) & 0x01;
			}
			return on;
		}

		private:
			int size_;
			int block_size_;
			vector<uint64_t> map_;
};

bool is_on(int a, int i){
    return a & (1 << i);
}

void toggle(int& a, int i, int j){
    int mask_i_j = 0;
    
    mask_i_j = mask_i_j | ((1 << (j+1)) -1);
    mask_i_j = mask_i_j & ~((1 << i) - 1);
    
    int x = a & mask_i_j;
    x =  (~x) & mask_i_j;
    a = a & (~mask_i_j);
    a = a | x;
}

int main(){
    int a = 0;
    toggle(a, 1, 3);
    
    for (int i = 8; i>=0; i--){
        cout << (is_on(a, i) ? "1" : "0");
    }
    
    cout << endl;

}

#include<iostream>
#include<vector>

using namespace std;

class BubbleSet{
public:
    BubbleSet(int n){
        bubbles = vector<int>(n/_size);
    }
    bool is_on(int i){
        int b = i/_size;
        i = i % _size;
        return bubbles[b] & (1 << i);
    }
    
    void toggle(int i , int j){
        int b1 = i / _size;
        int b2 = j / _size;
        
        if(b1 == b2){
            _toggle(b1, i%_size, j%_size);
        } else {
            _toggle(b1, i%_size, _size-1);
            _toggle(b2, 0, j%_size);
        }
        
    }
private:
    const int _size = (sizeof(int)*8);
    vector<int> bubbles;
    void _toggle(int k, int i , int j){
        int mask_i_j = 0;
        
        if(j == _size-1)
            mask_i_j = ~0;
        else
            mask_i_j = mask_i_j | ((1 << (j+1)) -1);
        
        mask_i_j = mask_i_j & ~((1 << i) - 1);
        
        int x = bubbles[k] & mask_i_j;
        x =  (~x) & mask_i_j;
        bubbles[k] = bubbles[k] & (~mask_i_j);
        bubbles[k] = bubbles[k] | x;
        
    }
};

int main(){
    BubbleSet bs(64);
    
    bs.toggle(30, 40);
    
    for (int i = 45; i>=25; i--){
        cout << (bs.is_on(i) ? "1" : "0");
    }
    
    cout << endl;
}