Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

We can also do this with Fenwick Tree.

const int MAXN = ...; // MAXN should be maximum range + a small integer

int tree[MAXN];

void update(int idx, int v) {
	++idx;
	while (idx < MAXN) {
		tree[idx] += v;
		idx += idx & -idx;
	}
}

int query(int idx) {
	int ans = 0;
	++idx;
	while (idx) {
		ans += tree[idx];
		idx -= idx & -idx;
	}
	return ans;
}

bool isOn(int idx) {
	return query(idx) & 1;
}

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

- Anthony September 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Here's what you are looking for.
Spoj LITE.
I solved it using segment trees. :)

- tourist August 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

You say to store them as we wish, but then you talk in terms of indexes, leading us to use an array.

But really, what's the catch? Is there something you're not telling us?

Swift 2.2

// TODO: Maybe add some bulbs.
var bulbs = [Bool]()

func toggleBulbs(start: Int, end: Int) {
    if (start >= 0 && end < bulbs.count) {
        for i in start ... end {
            bulbs[i] = !bulbs[i]
        }
    }
}

func isLightOn(bulbIndex: Int) -> Bool? {
    if (bulbIndex >= 0 && bulbIndex < bulbs.count) {
        return bulbs[bulbIndex]
    }
    return nil
    
}

- helloru August 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I highly doubt google would ask you to implement a segment tree in an interview, but here it is anyway:

int N = 1 << 10; // or however many lights we'll have
vector<int> toggles(2*N);


void add(int idx, int num) {
	idx += N;
	while (idx > 0) {
		toggles[idx] += num;
		idx /= 2;
	}
}

int sum(int idx) {
	idx += N;
	int ans = 0;
	int lowlim = N;
	while (idx > 0 && lowlim <= idx) {
		if (idx % 2 == 0) {
			ans += toggles[idx];
			idx--;
		}
		idx /= 2;
		lowlim /= 2;
	}
	return ans;
}

bool is_on(int idx) {
	return sum(idx) % 2 == 1;
}

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

- Anonymous August 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The first clue is "store them as you wish" which implies that space usage is not material.

Second clue is given a index get the state of bulb which says the operation of returning state should be O(1) i.e. a constant and hence the choice of storage is an array.

Third clue is given the start and end of the bulb list toggle state of bulbs. This is the trickiest of all since it is asking you to find an efficient way of list traversal (and not necessarily contiguously stored). Using a singly link list from start to end, traversal cost is O(n). A smarter way could be to do this in O(logn) hint think of a AVL ;-)

- RS August 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the solution with an array implemetation

public class BulbArray {
	static Bulb[] bulbs = { new Bulb(0, true), 
							new Bulb(1, false), 
							new Bulb(2,true) };
	
	public static void main(String[] args) {
		int index = 1;
		
		System.out.println(getBulbState(index));

		toggleState(1, 2);
		
		System.out.println(getBulbState(index));
	}
	
	public static boolean getBulbState(int Index){
		return bulbs[Index].getState();
	}
	
	public static void toggleState(int strt, int stop){
			if(strt > bulbs.length || stop > bulbs.length)
				System.out.println("Enter correct indexes within limits!");
			else
				for(int i=strt; i <= stop; i++){
					bulbs[i].toggleState();
				}
	}
	
	public static class Bulb{
		int index;
		boolean state;
		
		Bulb(int index, boolean state){
			this.index = index;
			this.state = state;
		}
		
		public boolean getState(){
			return state;
		}
		
		public void toggleState(){
				state = !state;
		}
	}

}

- liju.leelives August 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

both operations can be done in O(1) time if you use malloc memory object of size = number of bulbs in bits. (lets call it bulbState)
define
isOnOff(i)
{
same size memory object set value to 1 (call it indexSet)
indexSet << i;(now indexSet has ith bit set)
indexSet = indexSet & bulbState;
return indexSet

}
toggle(leftIndex,rightIndex).
{
make a copy of malloc object , << leftIndex, >> (leftIndex +(numberOfBulb - rightIndex) -> This will give an object all zero except the range is copy of original array.(lets call it rangeState)
rangeflipedState = ~rangeState (range fliped state is all ones except range is fliped)
similarly we create one more same size malloc object will all ones but range is set to zero(lets call it mask)
bulbState = bulbState & mask. (all bulb state is original state but range bulbs are all off)
bulbState = bulbState | rangeflipedSate;
}

I am assuing bit wise operation constant time. Please correct me if find anything.

- anup August 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I am also using bits to represent states.

long bulbs = 0L; // bit 0 for off, bit 1 for on

boolean isOn(int bulbIndex) {
    if (bulbIndex >= sizeof(bulbs)*8 || bulbIndex < 0) { 
        throw new IllegalArgumentException(
            "bulbIndex must in between 0 and " + sizeof(bulbs)*8);
    }
    // just test whether bit at bulbIndex is 1 or not.
    return (bulbs & (1L << bulbIndex)) != 0;
}

void toggle(int left, int right) {
    if (left > right) {
        throw new IllegalArgumentException("left must be equal or smaller than right");
    }
    if (left < 0 || left >= sizeof(bulbs)*8 || right < 0 || right >= sizeof(bulbs)*8) {
        throw new IllegalArgumentException("left or right must in between 0 and " + sizeof(bulbs)*8);
    }
    int totalNumBulbs = sizeof(bulbs)*8;
    int numBulbsToToggle = right - left + 1;
    // -1L >> (totalNumBulbs - numBulbsToToggle) is to clear bits after 'right'
    // << left is to clear bits before left
    // xor implements toggle
    bulbs ^= (-1L >> (totalNumBulbs - numBulbsToToggle)) << left
}

- jjongpark August 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think what the interviewer is looking for is an implementation using bit manipulations. If you implement a bit vector, you can just use XOR to toggle the bits in a certain range.

Although, this wouldn't make it asymptotically faster. Say you have n lightbulbs, and represent your bit vector as an array of 32 bit integers, then if you need to toggle all of the lightbulbs, you would perform n/32 operations which is still O(n).

This would be ideal if you have 32 or less lightbulbs though.

- johnbojorquez36 August 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

When I hear 'store as you wish' my first instinct is a hash table. Although I don't know if they would let that fly for this or not.

- AJGoley August 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.BitSet;

public class LightBulbs extends BitSet {

    public boolean isLightOn(int idx) {
        return get(idx);
    }

    public void toggleState(int idx){
        set(idx, !isLightOn(idx));
    }

    public static void main(String[] args) {
        LightBulbs bulbs = new LightBulbs();
        System.out.println(bulbs.isLightOn(1));
        bulbs.toggleState(1);
        System.out.println(bulbs.isLightOn(1));
    }
}

- TG August 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static BitSet bulbs;
public static boolean isSwitchOn(int index){
if(index>=0 && index<bulbs.size())
return bulbs.get(index);
return false;
}

public static void toggle(int start, int end){
if(start >=0 && end < bulbs.size() && start <= end)
bulbs.flip(start, end);
}

- Anonymous September 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static BitSet bulbs;
	public static boolean isSwitchOn(int index){
		if(index>=0 && index<bulbs.size())
			return bulbs.get(index);
		return false;
	}

	public static void toggle(int start, int end){
		if(start >=0 && end < bulbs.size() && start <= end)
			bulbs.flip(start, end);
	}

- Anonymous September 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The correct way to do this efficiently would be :
a. Build a complete Binary Tree with middle element as root.
b. For a update(start, end) operation:
1. Start from the root and move towards start node updating node state as specified later on.
2. Start from the root and move towards end+1 node updating node state as specified later.
Node state is to be updated as follows:
1. When moving to a left child, toggle the node state.
2. When moving to a right child, do not do anything.
In this way update can be done in O(log(n)).
c. Now for a query, just travel to the corresponding state and notice the count of toggles. Again O(log(n)).

- Srikant Aggarwal September 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think toggle operation using BST/AVL tree still have complexity of O(n) and not lg(n)

- Vishsangale September 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think complexity of toggle is still O(n)

- vishsangale September 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This has Log(n) check for whether a light is on and 4Lg(n) +2O(M) (M= dist(i,j)) to toggle the lights.

struct Light {
vector<int> on,off;
int n;
Light(): n(n){  off.resize(n); iota(off.begin(),off.end(),0); on.reserve(2*n),off.reserve(2*n)}
bool get(int i) { return binary_search(on.begin(),on.end(),i)}
toggle(int i, int j) { 
   vector<int> temp_on,temp_off;
start_on= lower_bound(on.begin(),on.end()),i); 
stop_on=upper_bound(on.begin(),on.end(),j);
start_off=lower_bound(off.begin(),off.end()),i);
stop_off=upper_bound(off.begin(),off.end()),j);
on.insert(stop_on,start_off,stop_off);
off.insert(stop_off,start_on,stop_on);
on.erase(start_on,stop_on);
off.erase(stop_on,stop_off);

   
   
}

- Anonymous September 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Bulb {
boolean mIsBulbOn = false;

Bulb(boolean state) { // constructor
mIsBulbOn = state;
}

public boolean getState() {
return mIsBulbOn;
}

public void setState(boolean state) {
mIsBulbOn = state;
}

}

public class GetBulbState {

private ArrayList<Bulb> mListOfBulbs;

public static void main(String []args) {

// create bulbs

Random random = new Random();
int lengthOfBulbs = 10;
mListOfBulbs = new ArrayList(10);
for(int i=0;i<lengthOfBulbs;i++) {
	Bulb b = new Bulb((random.next(1) == 1 ? true : false));
	mListOfBulbs.add(b);
}

}

public boolean isLightOn(int index) {

if (mListOfBulbs == null) {return false;}
if(index < 0) {return false;}
if (index > mListOfBulbs.size()) {return false;}
Bulb b = mListOfBulbs.get(index);
return b != null ? b.getState() : false;
}

public void toggleState(int start, int end) {
if (mListOfBulbs == null) {return;}
if (start > end) return;
if (start < 0) {start = 0;}
if (end > mListOfBulbs.size()) {end = mListOfBulbs.size() - 1;}
for (int i = start;i<end;i++) {
	Bulb b = mListOfBulbs.get(i);
	if (b != null) {
		b.setState(!b.getState());
	}
}
}

}

- coder145 October 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think using array is the simplest solution and the complexity o(n) for search; also less memory required.

#include<iostream>

using namespace std;

#define MAX_BULB 10

bool bulb[MAX_BULB];

void resetAllBulb()
{
int i;
for(i = 0; i < MAX_BULB; i++)
bulb[i] = false;
}

void setOnBulb(int index)
{
bulb[index] = true;
}

void resetBulb(int index)
{
bulb[index] = false;
}

void toggleRange(int first, int last)
{
int i;
unsigned int a;
if((first < 0) && (last > MAX_BULB) && (first > last))
return;
for(i = first; i <= last; i++)
{
(bulb[i]) ? a = 1 : a = 0;
a ^= 1;
bulb[i] = bool(a);
}

}
void printStatus()
{
int i;
for(i = 0; i < MAX_BULB; i++)
cout << (bulb[i] ? "ON " : "OFF ");
cout << endl;
}
int main()
{

resetAllBulb();
toggleRange(1,5);
printStatus();
toggleRange(6,9);
printStatus();
toggleRange(1,7);
printStatus();

}

- siva mohan October 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There must be some catch or constraint in this problem. Otherwise using arrays is the simplest solution. Toggle would be O(end index - start index) - > O(n) in worst case. How could anyone optimize that? Is there really a necessity to solve this using segment tree or interval tree or AVL tree or Fenwick tree.

- sanjogj43 November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what about union-find(aka disjoint sets)?
it is O(log*(n)) which is more than O(1) and less than O(log(n))

- ninjaCoder December 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't know anything about code

- Anonymous May 15, 2017 | 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