## 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)
{
}

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

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 tail_mask = ~((uint64_t)-1 << tail_size);
uint64_t tail_stored = map_[end_block_idx];
for (int i = start_block_idx; i <= end_block_idx; ++i) {
map_[i] = ~map_[i];
}
}
}
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 x = 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){

if(j == _size-1)
else

int x = 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;
}``````

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.

### 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.