Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
12
of 12 vote

It could be solved using following trick:
When we need to toggle range (s,e), we could add 1 to cell s, and -1 to cell e+1.
Now, every time that we wanna know about the state of a i-th cell, we need to know whether the cumulative sum from 1 to i is even or odd.

For having an efficient updatable cummulative sum array, we could use Binary Index Tree.
So updating and reading the state of a cell would be O(logN)

Code is extremly easy.

//Mehrdad AP

//Binary Indexed Tree(Fenwick Tree) code from Topcoder's Tutorials

#include <iostream>

using namespace std;

const int maxn=100000;
int sum[maxn];

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

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



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

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



int main()
{

	int Q,x,y;
	char ch;
	cin >> Q;//queries
	while (Q--){
		cin >> ch;
		if (ch=='T'){
			cin >> x >> y;//1-based indexed;
			toggle(x,y);
		}
		else{
			cin >> x;
			cout << isOn(x) << endl;

		}

	}

	return 0;
}

- MehrdadAP August 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Slightly problematic, as the toggle method will always be turning on lightbulbs. The update method should be modified. Maybe something like this?

void update(int idx) {
        while (idx <= maxn) {
		int val = sum[idx] == 1 ? -1 : 1
		sum[idx] += val;
		idx = idx + (idx & -idx);
	}
    }

- Nick August 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Nick, I dont understand what is problematic.
sum[i] keeps number of changes we've done, not the state(off/on), And then based on the parity of changes(even/odd) we could decide on the state.

- MehrdadAP August 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Oh I see. Thanks for clarifying!

- Nick August 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree with you. Here is my code.

class BIT {
public:
	BIT(int n) {
		len = n;
		a = new int[n + 1]();
	}

	~BIT() {
		free(a);
	}

	int sum(int i) {
		int ans = 0;
		while (i > 0) {
			ans += a[i];
			i -= i & -i;
		}
		return ans;
	}

	void add(int i, int val) {
		while (i <= len) {
			a[i] += val;
			i += i & -i;
		}
	}


private:
	int *a;
	int len;

};


class Light {
public:
	Light(int n) : bit(n + 1) {}

	bool isOn(int i) {
		return bit.sum(i) & 1;
	}

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

private:
	BIT bit;

};

- malinbupt September 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

MehrdadAP, are you certain this is O(logN) solution?
What if user calls toggle(0, N), would this not cause update() to run in while loop from 0 to maxN?

- blckembr October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@blckembr, Yes, absolutely it is :D

The reason is in fenwick tree, update and read are O(logN). Also, as I explained in this problem, for each update query we just need to do two updates on fenwick tree (on each end of range) and one read for each isON query. So totally it's O(logN) for each query.

I assumed that range in 1-based for simple implementation. So for toggle(1,N) you just need to change 1 and N+1 in array.

- MehrdadAP October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@MehrdadAP, You are absolutely right, I completely ignored the meaning of that bitwise operation :-) And I missed the Fenwick part.
Great solution!

- blckembr October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a neat problem and @MehrdadAP's solution is excellent. One minor improvement that I'd make is instead of using +1/-1 to keep track of range boundaries, use a Fenwick Tree that uses XOR operator, instead of addition. The running time does not change but this is a little more elegant since you don't have to do any further calculations to find if value is even or odd. The Fenwick Tree would just have 0/1 bit values and cumulative XOR of bit values computes 0/1 results. Here is a video tutorial that explains this in full detail: youtu.be/oAR_EYd8im0
One other bonus of this approach is that it uses less space - just a bit array, instead of integer array.

- Stable Sort February 04, 2020 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

Since no requirement is given for "isOn", I would keep a list of all the toggle operations requested so far, and when "isOn(i)" is called I would search this list to determine how many toggle operations affected the i-th light bulb, and return true if the number is odd.

The simplest data structure to use for the list of toggle operations is a simple unsorted array or linked-list, which means that "toggle" will be O(1) and "isOn" would take O(k) time (k = number of toggle operations).

A better data structure would be an interval or segment tree, in which case both the "toggle" and "isOn" operations will be O(log k).

- gen-y-s August 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

With such data structures we become dependent on k.

But we can store toggle operations in HashTable such format: {interval} -> {number of toggles}. Since number of intervals is about n squared we remove dependency on k and coupled only with number of bulbs.

Complexity of "isOn" become O(n^2). Obviously, this solution is nice only when n >> k.

- wrapper August 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If you're going to go down this route, here's an idea that will guarantee that toggle and update both run in no worse than O(sqrt N).

Use your existing idea to keep a list of all toggles made. When k, the size of the list, exceeds sqrt(N), apply all the toggles in a batch all at once to the array -- this can be done in O(N) time for all the toggles as described below. Since the list will not exceed sqrt(N) in size, the runtime of isOn is capped at O(sqrt(N)).

We analyze the runtime of toggle as follows: the act of recording a new toggle interval is O(1). As for applying the toggles to the array, we only do this every sqrt(N) toggles, and it takes O(N) time, giving an *amortized* time complexity of O(sqrt(N)) for toggle.

I now describe how to apply k toggles in a batch in O(N + K) time. Since we'll be applying sqrt(N) toggles, our batch-toggle method will be O(N) per every O(sqrt(N)) toggles.

Create a new list of size 2k of integers, and for each interval, put 2 values into a list: the start index and the end index of the interval. Then, sort the list using counting sort (the values are all in the range 0 to N, so this is linear time with counting sort).

Now, traverse the sorted list to determine which elements in the original array of size N were toggled. Suppose our sorted index list has elements a0, a1, a2, ... All the elements in the original array of size N having index between 0 and a0 should not be flipped, all the ones with index between a0 and a1 should be, the ones between index a1 and a2 should not be, the ones between index a2 and a3 should be, etc.

- eugene.yarovoi September 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

A solution using bit-wise operator.
Complexity for isOn(i) => O(1)
Complexity for toggle => O(n/32) for n<32, it is O(1)

If we use 64 bit integer, it will be O(n/64)

The assumption is, we take each integer bit-wise operation as one machine instruction.
i.e. (i<<32) is actually one machine instruction.

#include <iostream>
#include <stdio.h>

using namespace std;

typedef unsigned int UINT32;

class Bulbs {
    public:
        Bulbs(int n);
        bool isOn(int i);
        void toggle(int start, int end);
    
    private:
        int val;
        int n;
        int L;
        UINT32 s[200];
};

Bulbs::Bulbs(int val) {
    L = sizeof(UINT32);
    this->val = val;
    n = val/L + val%L ? 1 : 0;
    for(int i=0; i<n; i++) s[i] = 0;
}

bool Bulbs::isOn(int i) {
    int b = i / L;
    int off = i % L;
    return (s[b] & (1<<off)) ? true : false;
}

void Bulbs::toggle(int start, int end) {
    int sb = start / L;
    int so = start % L;
    int eb = end / L;
    int eo = end % L;
    int l = eb - sb + 1;
    
    if(sb == eb) {
        s[sb] = s[sb]^(((1 << l) - 1) << so);
        return;
    }
    
    for (int i=1; sb+i < eb; i++) {
        s[sb+i] = s[sb+i]^0xffffffff;
    }
    
    l = L - sb + 1;
    s[sb] = s[sb]^(((1 << l) - 1) << so);
    s[eb] = s[eb]^((1<<eo)-1);
}

int main() {
    Bulbs b(100);
    
    b.toggle(50, 60);
    
    cout << b.isOn(49) << endl;
    cout << b.isOn(55) << endl;
    cout << b.isOn(155) << endl;
    b.toggle(40, 200);
    cout << "*************************\n";    
    cout << b.isOn(49) << endl;
    cout << b.isOn(55) << endl;
    cout << b.isOn(155) << endl;
    cout << "*************************\n";
    b.toggle(40, 200);
    
    cout << b.isOn(49) << endl;
    cout << b.isOn(55) << endl;
    cout << b.isOn(155) << endl;
    cout << "*************************\n";
    return 0;
}

- diba.bec August 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Isn't O(N/64) still O(N) for N>>64

- blckembr October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

All queries can be answered in log(N) time, if you use binary indexed tree or segment tree. In fact, any data structure that can perform sum(l, r) and get(l) in log(N) time is OK.

- Darkhan.Imangaliev August 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain how toggle can be performed in logN? Assuming your solution updates parent Node(s) covering the specified range (start, end), what happens on further, more specific updates?

- Josh August 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Josh You need to use Lazy Propagation on Segment tree which is a little bit hard to implement.

But if you use a trick for toggle part, it could be easily solve with Segment tree or Fenwick Tree without lazy propagation.

I posted my solution in detail.

- MehrdadAP August 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

isOn(int lights, int i) {
		
	return ((lights >> i) & 1);
}

toggle(int lights, int start, int end) {
	
	int mask = 1 << (end - start + 1);
	mask -= 1;
	lights ^= mask << start;
}

- SK August 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

genius

- Anonymous August 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I couldn't get your toggle to work, but this works.

#include <bitset>

const int NUM_LIGHTS = 20;

class Lights {
    public:
    auto lights = std::bitset<NUM_LIGHTS>();
    Lights(){
        lights.reset();
    }
    bool isOn(int i) { return (lights >> i).test(0);}
    void toggle(int s, int e) {
        int m = (1 << (e - s+1)) -1 ;
        lights ^= m << s;
    }
};

- s.k. August 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

--toggle fixed

#include <bitset>

const int NUM_LIGHTS = 20;

class Lights {
    public:
    auto = std::bitset<NUM_LIGHTS>();
    Lights(){
        lights.reset();
    }
    bool isOn(int i) { return (lights >> i).test(0);}
    void toggle(int s, int e) {
        int m = (1 << (e - s+1)) -1 ;
        lights ^= m << s;
    }
};

- vim August 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

what about if there are 33 lights in the range? 65? 1,000,000...?

- zortlord August 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Fixed it. sorry haha

- SK August 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you do realize the 'toggle' is O(n) for large 'n' (number of light bulbs)?

- foo August 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you do realize the 'toggle' function is O(n) .. for any large 'n'? this would be O(1) only for upto, say, 64 bulbs ..

- foo August 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

obviously. call it a bit vector that could be of any size and it would work.

- SK August 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Given no other constraint, I would just store the list of toggles in a LinkedList, then iterate through the LinkedList to determine whether the current state is on or off.

public class LightBulbs {
    class Interval {
        int start;
        int end;

        public Interval(int _start, int _end) {
            start = _start;
            end = _end;
        }

        public boolean contains(int n) {
            return n >= start && n <= end;
        }
    }

    LinkedList<Interval> intervals = new LinkedList<Interval>();

    public LightBulbs(int n) {
    }

    public boolean isOn(int i) {
        boolean on = false;
        for(Interval interval : intervals) {
            if(interval.contains(i)) {
                on = !on;
            }
        }
        return on;
    }

    public void toggle(int start, int end) {
        intervals.add(new Interval(start, end));
    }
}

- Sunny August 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't handle toggling lights off.

- zortlord August 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Bulb
{
    private final int N;
    private boolean[] bulbs;
    
    public Bulb(int N)
    {    
        this.N = N;
        bulbs = new boolean[N];
    }
    
    public boolean isOn(int i)
    {
        validateIndex(i);
        return bulbs[i];
    }
    
    public void toggle(int start, int end)
    {
        validateIndex(start);
        validateIndex(end);
        
        if (start > end) { throw new IllegalArgumentException("start greater than end"); }
        
        for(int i = start; i <= end; i++) //O(k), where, k = end - start
        {
            bulbs[i] = !bulbs[i];
        }
    }
    
    private void validateIndex(int i)
    {
        if (i < 0 || i >= N) { throw new NoSuchElementException("Bulb " + i + " not in range"); }
    }

}

- Chhet August 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about bit manipulation when the number of light is less than 32 or 64?

- minglotus6 August 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just use xor to reduce the complexity of toggle operation.

#include <stdbool.h>
#include <stdio.h>

const int n = 10;
int onoffstatus[10] = {0};

bool isOn(int i)
{
if(i < n){
if (onoffstatus[i]==1) return true;
else return false;
} else
return false;
}

void toggle(int start, int end)
{
if(start < 0 || end >= 10) return;
int i;

for(i=start;i<end+1;i++){
onoffstatus[i] = onoffstatus[i] ^ 1;
}
}

void main()
{
bool a = isOn(6);
printf("%d \n",a);

toggle(2,7);
a = isOn(6);
printf("%d \n",a);

toggle(2,7);
a = isOn(6);
printf("%d \n",a);

}

- bluepulse5577 September 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I agree with gen-y-s that it can be solved using trees.
However, segment trees are a little overkill here.
In fact this can be solved using just a binary search, although it is easier to visualize this problem using a balanced BST which we can easily build because what we are going to store in it are just indices 0 to N-1 (as the number of bulbs) which are already sorted, so the Tree is actually for visualization purposes. I will try to rewrite this code to not use BST, but to calculate indices of "roots" of intervals directly on the given array of bulbs.

But anyway, here is implementation using BST that is built initially and never changed (as far as its structure). Each is only keeping track of whether some range was toggled even or odd number of times. When asked to get a state of a bulb, it does search on BST, collecting states of nodes on the way. The final result calculated from the accumulated state.

Runs in 3 ms with 10000000 bulbs and doing 1000 toggles.

import com.zaxxer.sparsebits.SparseBitSet;

public class BulbsToggle {
	private SparseBitSet bulbsBitSet;
	private int numOfBits = 0;
	private ToggleNode root = null;

	public byte getState(int idx) {
		byte togglesCount = getTogglesCount(root, idx, (byte) 0);
		if (togglesCount%2==0) {
			return (byte) (bulbsBitSet.get(idx)?1:0);
		} else {
			return (byte) (bulbsBitSet.get(idx)?0:1);
		}
	}
	
	public void toggleRange(int start, int end) {
		if (start==end) {
			ToggleNode node = findNode(start); 
			node.lightSwitch.toggle();
			
			if (node.left!=null) {node.left.lightSwitch.toggle();}
			
			if (node.right!=null) {node.right.lightSwitch.toggle();}
			
			return;
		}
		
		ToggleNode commonRoot = findCommonRoot(start, end);
		commonRoot.lightSwitch.toggle();
		
		//fix range to the left of start, because it might have been "corrupted" by
		//flipping common root
		if (start > 0) {
			leftFix(commonRoot, findNode(start));
		}
		
		//fix range to the right of enf, because it might have been "corrupted" by
		//flipping common root
		if (end < numOfBits  - 1) {
			rightFix(commonRoot, findNode(end));
		}
	}

	private void rightFix(ToggleNode commonRoot, ToggleNode rangeEnd) {
		int currIdx = rangeEnd.idx;
		
		//immediately fix the right subtree if it is above range;
		//based on properties of BST, all nodes from right subtree
		//are higher, so out of range
		ToggleNode right = rangeEnd.right;
		if (right != null && right.idx > currIdx) {
			right.lightSwitch.toggle();
		}
		
		//starting from the root of larger items (LR), fix it. This might have broken a parent which is still in range
		//under that root of larger items (LR), find it and fix it as well. This again might have broken parent of a 
		//tree with larger (out of range indices), find it and fix... continue till actually reached the end of range node
		ToggleNode rootToFix = getRootOfHigherSubTree(rangeEnd, commonRoot);
		while (rootToFix != null && rootToFix != rangeEnd) {
			if (rootToFix.idx > currIdx) {
				rootToFix.lightSwitch.toggle();
				rangeEnd.lightSwitch.toggle();
				rootToFix = getRootOfSmallerSubTree(rangeEnd, rootToFix.left);
			} else {
				rootToFix.lightSwitch.toggle();
				rangeEnd.lightSwitch.toggle();
				rootToFix = getRootOfHigherSubTree(rangeEnd, rootToFix.right);
			}
		}
	}

	private void leftFix(ToggleNode commonRoot, ToggleNode rangeEnd) {
		int currIdx = rangeEnd.idx;
		
		//immediately fix the left subtree if it is below range;
		//based on properties of BST, all nodes from left subtree
		//are smaller, so out of range
		ToggleNode left = rangeEnd.left;
		if (left != null && left.idx < currIdx) {
			left.lightSwitch.toggle();
		}
		
		//starting from the root of smaller items, fix it. This might have broke a parent which is in range
		//under the root of smaller items, find it and fix it. This again might have broken parent of a tree with smaller (out 
		//of range indices, find it and fix... continue till actually reached the end of range node
		ToggleNode rootToFix = getRootOfSmallerSubTree(rangeEnd, commonRoot);
		while (rootToFix != null && rootToFix != rangeEnd) {
			if (rootToFix.idx < currIdx) {
				rootToFix.lightSwitch.toggle();
				rangeEnd.lightSwitch.toggle();
				rootToFix = getRootOfHigherSubTree(rangeEnd, rootToFix.right);
			} else {
				rootToFix.lightSwitch.toggle();
				rangeEnd.lightSwitch.toggle();
				rootToFix = getRootOfSmallerSubTree(rangeEnd, rootToFix.left);
			}
		}	
	}
	
	// HELPER METHODS------------------------
	private byte getTogglesCount(ToggleNode node, int idx, byte toggleCount) {
		if (node == null) {
			return toggleCount;
		}
		
		toggleCount =  (byte) ( (toggleCount + node.lightSwitch.getState()) % (byte) 2);
		if (idx == node.idx) {
			return toggleCount;
		} else {
			if (idx <= node.idx) {
				return getTogglesCount(node.left, idx, toggleCount);
			} else {
				return getTogglesCount(node.right, idx, toggleCount);
			}
		}
	}
	
	private ToggleNode getRootOfSmallerSubTree(ToggleNode node, ToggleNode commonRoot) {
		ToggleNode rootOfSmaller = null;
		if (node == commonRoot) {
			return null;
		}
		while (node.parent != null ) {
			if (node.parent == commonRoot) {
				if (node.parent.idx < node.idx) {
					rootOfSmaller = node.parent;
				}
				break;
			}
			
			if (node.parent.idx < node.idx) {
				rootOfSmaller = node.parent;
			}
			node = node.parent;
		}
		return rootOfSmaller;
	}
	
	private ToggleNode getRootOfHigherSubTree(ToggleNode node, ToggleNode commonRoot) {
		ToggleNode rootOfHigher = null;
		if (node == commonRoot) {
			return null;
		}
		
		while (node.parent != null ) {
			if (node.parent == commonRoot) {
				if (node.parent.idx > node.idx) {
					rootOfHigher = node.parent;
				}
				break;
			}
			if (node.parent.idx > node.idx) {
				rootOfHigher = node.parent;
			}
			node = node.parent;
		}
		return rootOfHigher;
	}

	public ToggleNode findCommonRoot(int m, int n) {
		return findCommonRoot(root, m, n);
	}
	
	private ToggleNode findCommonRoot(ToggleNode node, int m, int n) {
		if (m == node.idx || n == node.idx) {
			return node;
		}
		
		if (m < node.idx && n < node.idx) {
			return findCommonRoot(node.left,m, n);
		} else if (m> node.idx && n > node.idx) {
			return findCommonRoot(node.right,m, n);
		} else {
			return node;
		}
	}

	private ToggleNode buildTree(int first, int last, ToggleNode parent) {
		if (first>last) {
			return null;
		}
		
		if (first == last) {
			ToggleNode leaf = new ToggleNode();
			leaf.lightSwitch = new LightSwitch();
			leaf.left = leaf.right = null;
			leaf.parent = parent;
			leaf.idx = first;
			return leaf;
		}
		
		int mid = first + (last-first)/2;
		ToggleNode node = new ToggleNode();
		node.idx = mid;

		node.parent = parent;
		node.left = buildTree(first, mid-1, node);
		node.right = buildTree(mid+1, last, node);
		
		return node;
	}

	public static class ToggleNode {
		ToggleNode left = null;
		ToggleNode right = null;
		ToggleNode parent = null;
		int idx = 0;
		
		LightSwitch lightSwitch = new LightSwitch();
		
		public LightSwitch getToggle() {
			return lightSwitch;
		}
	}
	
	public boolean isInSubtreeOf(ToggleNode parent, ToggleNode node) {
		return findNode(parent, node.idx) != null;
	}
	
	public ToggleNode findNode(int k) {
		return findNode(root, k);
	}
	
	private ToggleNode findNode(ToggleNode node, int k) {
		if (node.idx == k) {
			return node;
		} else {
			if (node.left != null && k <= node.idx) {
				return findNode(node.left, k);
			} else if (node.right != null && k > node.idx) {
				return findNode(node.right, k);
			} else {
				return null;
			}
		}
	}
	
	public static class LightSwitch {
		byte state = 0;
		
		public void toggle() {
			state = (byte) (state ^ (byte)0x1);
		}
		
		public byte getState() {
			return state;
		}

		@Override
		public String toString() {
			return Byte.valueOf(state).toString();
		}
	}
	
	public void setBulbs(int[] bulbs) {
		numOfBits = bulbs.length;
		bulbsBitSet = new SparseBitSet(numOfBits);
		for (int i = 0; i<bulbs.length ; i++) {
			if (bulbs[i]==0) {
				bulbsBitSet.set(i, false);
			} else {
				bulbsBitSet.set(i, true);
			}
		}
		
		root = buildTree(0, bulbs.length-1, null);
	}
	
	public void setBulbs(SparseBitSet bitSet, int numOfBits) {
		this.numOfBits = numOfBits;
		bulbsBitSet = bitSet;
		
		root = buildTree(0, numOfBits-1, null);
	}
}

- blckembr October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think I can optimize it from the current O(log(N)*log(N)) to just logN by doing traversal strictly down in search of parent to be fixed, instead of going up from range end node every time in the whiles.

- blckembr October 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a bitset question.

Represent each lightbulb as a bit. On isOn(i) return bit(i).
On toggle(start,end) xor the range with 11111. If light-bulb was off (i.e 0) then 0^1=1. Else if lightbulb was on i.e(1) then 1^1=0. This will correctly toggle the range as long as the mask is built correctly.

- Eugen Hotaj November 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I store the bulbs in a byte where each bit is a bulb so I can use mask and XOR to toggle the state of a set of bulbs
I did not test the code but is the idea.

public class BulbsManager
{
	private int numBulbs
	private byte[] bulbs;
	
	public BulbManager(int n)
	{
		this.numBulbs = n;
		this.bulbs = new byte[n/8 + 1];
	}
	
	public bool IsOn(int index)
	{
		int n = index / 8;
		int i = index % 8;
		
		byte mask = 1 << i;
		return this.bulbs[n] & mask != 0;
	}
	
	public void Togle(int start, int end)
	{
		if (end < start)
			throw new ArgumentException();
			
		int sb = start / 8;
		int eb = end / 8;
		int i1 = start % 8;
		int i2 = end % 8;
		
		bulbs[sb]= bulbs[sb] >> i1;
		bulbs[sb] = bulbs[sb] << i1;
		
		mask = 0xFF;
		for (int i=sb+1; i < eb; i++)
			bulbs[i] = bulbs[i] ^ mask;
	
		int n2 = 7 - i2;
		bulbs[sb] = bulbs[se] << n2;
		bulbs[sb] = bulbs[se] >> n2;
	}
}

- hnatsu May 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is naive solution, and makes toggle operation in O(n) time. I don't think that this solution what interviewer expected

- Darkhan.Imangaliev August 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Specifically says "write toggle so that it is less than O(N) complexity"

- Josh August 19, 2015 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More