Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
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, 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.
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;
};
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, 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, You are absolutely right, I completely ignored the meaning of that bitwise operation :-) And I missed the Fenwick part.
Great solution!
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.
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).
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.
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.
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;
}
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);
}
}
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.
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?
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;
}
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;
}
};
--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;
}
};
you do realize the 'toggle' function is O(n) .. for any large 'n'? this would be O(1) only for upto, say, 64 bulbs ..
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));
}
}
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"); }
}
}
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);
}
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.
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;
}
}
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.
- MehrdadAP August 19, 2015