Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 5 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)
    private int read(int idx) {
        int node = idx + 1;
        int sum = 0;
        while (node > 0) {
            sum += bulbs[node];
            node -= (node & -node);
        }
        return sum;
    }

}

- aonecoding January 16, 2018 | Flag Reply
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);
}

}}

- Anonymous February 11, 2018 | Flag Reply
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?

- fOx January 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why an indexes binary tree?

- Asd January 17, 2018 | Flag Reply
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[2] = 1 and arr[6] = 1, then to get isOn(3), sum from arr[1] to arr[3] = 1, thus ON, to get isOn(8) = sum from arr[1] to arr[8] = 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));
        }
}

- Aim_Google January 17, 2018 | Flag Reply
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";
}
}
}

- msrv499 January 17, 2018 | Flag Reply
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)

- random January 18, 2018 | Flag Reply
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];
}
}

- shailendra singh rajput January 21, 2018 | Flag Reply
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?

- Anonymous January 23, 2018 | Flag Reply


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