CareerCup

We can also do this with Fenwick Tree.

const int MAXN = ...; // MAXN should be maximum range + a small integer

int tree[MAXN];

void update(int idx, int v) {
	++idx;
	while (idx < MAXN) {
		tree[idx] += v;
		idx += idx & -idx;
	}
}

int query(int idx) {
	int ans = 0;
	++idx;
	while (idx) {
		ans += tree[idx];
		idx -= idx & -idx;
	}
	return ans;
}

bool isOn(int idx) {
	return query(idx) & 1;
}

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

Here's what you are looking for.
Spoj LITE.
I solved it using segment trees. :)

You say to store them as we wish, but then you talk in terms of indexes, leading us to use an array.

But really, what's the catch? Is there something you're not telling us?

Swift 2.2

// TODO: Maybe add some bulbs.
var bulbs = [Bool]()

func toggleBulbs(start: Int, end: Int) {
    if (start >= 0 && end < bulbs.count) {
        for i in start ... end {
            bulbs[i] = !bulbs[i]
        }
    }
}

func isLightOn(bulbIndex: Int) -> Bool? {
    if (bulbIndex >= 0 && bulbIndex < bulbs.count) {
        return bulbs[bulbIndex]
    }
    return nil
    
}

I highly doubt google would ask you to implement a segment tree in an interview, but here it is anyway:

int N = 1 << 10; // or however many lights we'll have
vector<int> toggles(2*N);


void add(int idx, int num) {
	idx += N;
	while (idx > 0) {
		toggles[idx] += num;
		idx /= 2;
	}
}

int sum(int idx) {
	idx += N;
	int ans = 0;
	int lowlim = N;
	while (idx > 0 && lowlim <= idx) {
		if (idx % 2 == 0) {
			ans += toggles[idx];
			idx--;
		}
		idx /= 2;
		lowlim /= 2;
	}
	return ans;
}

bool is_on(int idx) {
	return sum(idx) % 2 == 1;
}

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

The first clue is "store them as you wish" which implies that space usage is not material.

Second clue is given a index get the state of bulb which says the operation of returning state should be O(1) i.e. a constant and hence the choice of storage is an array.

Third clue is given the start and end of the bulb list toggle state of bulbs. This is the trickiest of all since it is asking you to find an efficient way of list traversal (and not necessarily contiguously stored). Using a singly link list from start to end, traversal cost is O(n). A smarter way could be to do this in O(logn) hint think of a AVL ;-)

Here is the solution with an array implemetation

public class BulbArray {
	static Bulb[] bulbs = { new Bulb(0, true), 
							new Bulb(1, false), 
							new Bulb(2,true) };
	
	public static void main(String[] args) {
		int index = 1;
		
		System.out.println(getBulbState(index));

		toggleState(1, 2);
		
		System.out.println(getBulbState(index));
	}
	
	public static boolean getBulbState(int Index){
		return bulbs[Index].getState();
	}
	
	public static void toggleState(int strt, int stop){
			if(strt > bulbs.length || stop > bulbs.length)
				System.out.println("Enter correct indexes within limits!");
			else
				for(int i=strt; i <= stop; i++){
					bulbs[i].toggleState();
				}
	}
	
	public static class Bulb{
		int index;
		boolean state;
		
		Bulb(int index, boolean state){
			this.index = index;
			this.state = state;
		}
		
		public boolean getState(){
			return state;
		}
		
		public void toggleState(){
				state = !state;
		}
	}

}

both operations can be done in O(1) time if you use malloc memory object of size = number of bulbs in bits. (lets call it bulbState)
define
isOnOff(i)
{
same size memory object set value to 1 (call it indexSet)
indexSet << i;(now indexSet has ith bit set)
indexSet = indexSet & bulbState;
return indexSet

}
toggle(leftIndex,rightIndex).
{
make a copy of malloc object , << leftIndex, >> (leftIndex +(numberOfBulb - rightIndex) -> This will give an object all zero except the range is copy of original array.(lets call it rangeState)
rangeflipedState = ~rangeState (range fliped state is all ones except range is fliped)
similarly we create one more same size malloc object will all ones but range is set to zero(lets call it mask)
bulbState = bulbState & mask. (all bulb state is original state but range bulbs are all off)
bulbState = bulbState | rangeflipedSate;
}

I am assuing bit wise operation constant time. Please correct me if find anything.

I am also using bits to represent states.

long bulbs = 0L; // bit 0 for off, bit 1 for on

boolean isOn(int bulbIndex) {
    if (bulbIndex >= sizeof(bulbs)*8 || bulbIndex < 0) { 
        throw new IllegalArgumentException(
            "bulbIndex must in between 0 and " + sizeof(bulbs)*8);
    }
    // just test whether bit at bulbIndex is 1 or not.
    return (bulbs & (1L << bulbIndex)) != 0;
}

void toggle(int left, int right) {
    if (left > right) {
        throw new IllegalArgumentException("left must be equal or smaller than right");
    }
    if (left < 0 || left >= sizeof(bulbs)*8 || right < 0 || right >= sizeof(bulbs)*8) {
        throw new IllegalArgumentException("left or right must in between 0 and " + sizeof(bulbs)*8);
    }
    int totalNumBulbs = sizeof(bulbs)*8;
    int numBulbsToToggle = right - left + 1;
    // -1L >> (totalNumBulbs - numBulbsToToggle) is to clear bits after 'right'
    // << left is to clear bits before left
    // xor implements toggle
    bulbs ^= (-1L >> (totalNumBulbs - numBulbsToToggle)) << left
}

I think what the interviewer is looking for is an implementation using bit manipulations. If you implement a bit vector, you can just use XOR to toggle the bits in a certain range.

Although, this wouldn't make it asymptotically faster. Say you have n lightbulbs, and represent your bit vector as an array of 32 bit integers, then if you need to toggle all of the lightbulbs, you would perform n/32 operations which is still O(n).

This would be ideal if you have 32 or less lightbulbs though.

When I hear 'store as you wish' my first instinct is a hash table. Although I don't know if they would let that fly for this or not.

import java.util.BitSet;

public class LightBulbs extends BitSet {

    public boolean isLightOn(int idx) {
        return get(idx);
    }

    public void toggleState(int idx){
        set(idx, !isLightOn(idx));
    }

    public static void main(String[] args) {
        LightBulbs bulbs = new LightBulbs();
        System.out.println(bulbs.isLightOn(1));
        bulbs.toggleState(1);
        System.out.println(bulbs.isLightOn(1));
    }
}

static BitSet bulbs;
public static boolean isSwitchOn(int index){
if(index>=0 && index<bulbs.size())
return bulbs.get(index);
return false;
}

public static void toggle(int start, int end){
if(start >=0 && end < bulbs.size() && start <= end)
bulbs.flip(start, end);
}

static BitSet bulbs;
	public static boolean isSwitchOn(int index){
		if(index>=0 && index<bulbs.size())
			return bulbs.get(index);
		return false;
	}

	public static void toggle(int start, int end){
		if(start >=0 && end < bulbs.size() && start <= end)
			bulbs.flip(start, end);
	}

The correct way to do this efficiently would be :
a. Build a complete Binary Tree with middle element as root.
b. For a update(start, end) operation:
1. Start from the root and move towards start node updating node state as specified later on.
2. Start from the root and move towards end+1 node updating node state as specified later.
Node state is to be updated as follows:
1. When moving to a left child, toggle the node state.
2. When moving to a right child, do not do anything.
In this way update can be done in O(log(n)).
c. Now for a query, just travel to the corresponding state and notice the count of toggles. Again O(log(n)).

I think toggle operation using BST/AVL tree still have complexity of O(n) and not lg(n)

I think complexity of toggle is still O(n)

This has Log(n) check for whether a light is on and 4Lg(n) +2O(M) (M= dist(i,j)) to toggle the lights.

struct Light {
vector<int> on,off;
int n;
Light(): n(n){  off.resize(n); iota(off.begin(),off.end(),0); on.reserve(2*n),off.reserve(2*n)}
bool get(int i) { return binary_search(on.begin(),on.end(),i)}
toggle(int i, int j) { 
   vector<int> temp_on,temp_off;
start_on= lower_bound(on.begin(),on.end()),i); 
stop_on=upper_bound(on.begin(),on.end(),j);
start_off=lower_bound(off.begin(),off.end()),i);
stop_off=upper_bound(off.begin(),off.end()),j);
on.insert(stop_on,start_off,stop_off);
off.insert(stop_off,start_on,stop_on);
on.erase(start_on,stop_on);
off.erase(stop_on,stop_off);

   
   
}

public class Bulb {
boolean mIsBulbOn = false;

Bulb(boolean state) { // constructor
mIsBulbOn = state;
}

public boolean getState() {
return mIsBulbOn;
}

public void setState(boolean state) {
mIsBulbOn = state;
}

}

public class GetBulbState {

private ArrayList<Bulb> mListOfBulbs;

public static void main(String []args) {

// create bulbs

Random random = new Random();
int lengthOfBulbs = 10;
mListOfBulbs = new ArrayList(10);
for(int i=0;i<lengthOfBulbs;i++) {
	Bulb b = new Bulb((random.next(1) == 1 ? true : false));
	mListOfBulbs.add(b);
}

}

public boolean isLightOn(int index) {

if (mListOfBulbs == null) {return false;}
if(index < 0) {return false;}
if (index > mListOfBulbs.size()) {return false;}
Bulb b = mListOfBulbs.get(index);
return b != null ? b.getState() : false;
}

public void toggleState(int start, int end) {
if (mListOfBulbs == null) {return;}
if (start > end) return;
if (start < 0) {start = 0;}
if (end > mListOfBulbs.size()) {end = mListOfBulbs.size() - 1;}
for (int i = start;i<end;i++) {
	Bulb b = mListOfBulbs.get(i);
	if (b != null) {
		b.setState(!b.getState());
	}
}
}

}

I think using array is the simplest solution and the complexity o(n) for search; also less memory required.

#include<iostream>

using namespace std;

#define MAX_BULB 10

bool bulb[MAX_BULB];

void resetAllBulb()
{
int i;
for(i = 0; i < MAX_BULB; i++)
bulb[i] = false;
}

void setOnBulb(int index)
{
bulb[index] = true;
}

void resetBulb(int index)
{
bulb[index] = false;
}

void toggleRange(int first, int last)
{
int i;
unsigned int a;
if((first < 0) && (last > MAX_BULB) && (first > last))
return;
for(i = first; i <= last; i++)
{
(bulb[i]) ? a = 1 : a = 0;
a ^= 1;
bulb[i] = bool(a);
}

}
void printStatus()
{
int i;
for(i = 0; i < MAX_BULB; i++)
cout << (bulb[i] ? "ON " : "OFF ");
cout << endl;
}
int main()
{

resetAllBulb();
toggleRange(1,5);
printStatus();
toggleRange(6,9);
printStatus();
toggleRange(1,7);
printStatus();

}

There must be some catch or constraint in this problem. Otherwise using arrays is the simplest solution. Toggle would be O(end index - start index) - > O(n) in worst case. How could anyone optimize that? Is there really a necessity to solve this using segment tree or interval tree or AVL tree or Fenwick tree.

what about union-find(aka disjoint sets)?
it is O(log*(n)) which is more than O(1) and less than O(log(n))

I don't know anything about code