Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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)
}
}
}
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;
}
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.
- aonecoding August 09, 2017