## Google Interview Question for Software Engineers

• 2

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 6 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 of FB, LinkedIn, Amazon, Google & Uber etc.)
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, MS and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

``````//Binary Indexed Tree (O(logN) Toggle, O(logN) Get.
public class ToggleBulbs {

int[] bulbs;

public ToggleBulbs(int n) { //n bulbs given

bulbs = new int[n + 1];
}

public boolean isOn(int i) {
//a bulb is on if it's toggled an odd number of times
return read(i) % 2 == 1;
}

// toggle(i, j) is equivalent to
// toggle(i, n - 1) and then toggle(j, n - 1)
public void toggle(int i,int j) {
toggle(i);
toggle(j + 1);
}

//toggle from ith to the last bulb (a standard update in BITree)
private void toggle(int idx){
int node = idx + 1;
while (node < bulbs.length){
bulbs[node] = (bulbs[node] + 1) % 2;
node += (node & -node);
}
}

//get the number of times bulb i toggled (read prefix sum from 0 to i in BITree)
int node = idx + 1;
int sum = 0;
while (node > 0) {
sum += bulbs[node];
node -= (node & -node);
}
return sum;
}

}``````

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

No, I think a bitset is by far the easiest solution. O(n) toggle, O(1) access, and the most space efficient. The (Fenwick) tree solution is O(log n) toggle, but it's also O(log n) access, so pick your poison (are you going to toggle lots, or query lots?). However you'd need to know the number of bulbs beforehand, you can't dynamically allocate a bitset in C++. But a bool vector is about as good.

{{

std::vector<bool> lightbulbs(false);
lightbulbs.resize(N);

void toggle(int i, int j){
for(int u=i; u <=j; u++) lightbulbs.at(u) ^= lightbulbs.at(u);
}

bool isOn(int i){
return lightbulbs.at(i);
}

}}

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

Why would you need an Indexed Binary Tree for these use cases?

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

Why an indexes binary tree?

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

To do it optimally for toggle(i, j), we update arr[i] (using 1 based index) to 1 and arr[j+1] to 1, so that to get isOn for any index, we just have to sum the values from 1st index to that index, if its cumulative sum is 1 (mod 2), then it is ON, otherwise OFF.

E.g. In array of size 10, if we have to toggle (2, 5), then make arr = 1 and arr = 1, then to get isOn(3), sum from arr to arr = 1, thus ON, to get isOn(8) = sum from arr to arr = 2 = 0(mod2), thus OFF

Now to store cumulative sum optimally, use BIT.

``````int[] arr = new int[n+1];

public static void toggle(int i, int j) {
i++;
j++;
set(i);
set(j+1);
}

public static boolean isOn(int i) {
i++;
int sum = 0;
int pos = i;
while (pos > 0) {
sum += arr[pos];
sum %= 2;
pos -= (pos & (-pos));
}
return (sum%2 == 1);
}

private static void set(int i) {
int pos = i;
while (pos <= n) {
arr[pos] += 1;
arr[pos] %= 2;
pos += (pos & (-pos));
}
}``````

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

``````isOn(int i){
return a[i]=="OFF"? "OFF":"ON";
}

toggle(int i, int j){
//N is length of array
if (j<N)
int (k=i;k<=j;k++){
if(a[k] == "OFF"){
a[k] = "ON";
}
else{
a[k] = "OFF";
}
}
}``````

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

Why not use an interval tree, with the tree nodes storing lists of pairs of the form <Interval,count_of_toggles_done_to_the_interval>.
On each toggle operation on (i,j), follow the interval tree construction algorithm to locate/create the node where the new interval can be added. If the interval has already been toggled, we'd discover it, and therefore increment the toggle_counter. Otherwise,we'd just insert the pair <(i,j),1>. This can be achieved in log(n) time, where n is the current size of the interval tree.

isOn(i) would then just be an interval tree lookup for enumerating all the intervals that contain i. We can then sum up the toggle_counters of the intervals in that intersection list, and return (sum%2 != 0) (since the bulbs were initially all off)

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

bool A[n]={false};
isOn(int i){
if(0 <=i <n) return a[i];
}

toggle(int i, int j){
//N is length of array
if (0<= j<N) && (0<= i<N) && (i<j)
int (k=i;k<=j;k++){
A[k] = !A[k];
}
}

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

It sounds to me that we could simply use a bit vector and the toggle of [i,j] would be a xor with 1 on the related bits.
Am I missing something?

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.