## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

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);
}
}
}``````

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

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)
}
}
}``````

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

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

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

``````class Lamps {
public:
Lamps(int size)
{
size_ = size;
block_size_ = sizeof(map_) * 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_;
};``````

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

``````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;``````

}

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

``````#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;
}``````

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