## Google Interview Question for Software Engineers

• 0

Country: United States

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

We can record the timestamp / operation number of each of the operation. With that said we will store the last time setAllTrue was executed and last time setAllFalse was executed. Also we store the last time particular index was updated. We can compare the time to get the value at that index.

``````vector<bool> arr(n);
vector<int> lastUpdatedAt;
int op = 0;
int lastSetTrue, lastSetFalse;

void setTrue(int i) {
op++;
arr[i] = true;
lastUpdatedAt[i] = op;
}

void setFalse(int i) {
op++;
arr[i] = false;
lastUpdatedAt[i] = op;
}

void setAllTrue() {
op++;
lastSetTrue = op;
}
void setAllFalse() {
op++;
lastSetFalse = op;
}

bool get(int i) {

if(lastUpdatedAt[i] < lastSetTrue && lastUpdatedAt[i] < lastSetFalse) {
return lastSetTrue > lastSetFalse;
}
if(lastUpdatedAt[i] < lastSetTrue) {
return true;
}
if(lastUpdatedAt[i] < lastSetFalse) {
return false;
}
return arr[i];
}``````

}

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

Assume 32 bit integer

``````bit_vector = vector<int>;

void setTrue(index) {
int remainder = index % 32;
bit_vector[index/32] |= 1 << remainder;
}

void setFalse(index) {
int remainder = index % 32;
bit_vector[index/32] &= ~(1 << remainder);
}

void setAllTrue() {
for (int& i : bit_vector) {
i |= 0xFFFF;
}
}

void setAllFalse() {
for (int& i : bit_vector) {
i &= 0;
}
}

bool getIndex(index) {
int remainder = index % 32;
return (bit_vector[index/32] >> remainder) & 1;
}``````

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

``````type Bit struct {
V bool
T int
}
type BitStreamer struct {
Bits     map[int]Bit
AllTrue  int
AllFalse int
Time     int
}
func NewBitStreamer() *BitStreamer {
return &BitStreamer{
Bits: map[int]Bit{},
}
}
func (b *BitStreamer) SetTrue(index int) {
b.Bits[index] = Bit{true, b.Time}
}
func (b *BitStreamer) SetFalse(index int) {
b.Bits[index] = Bit{false, b.Time}
}
func (b *BitStreamer) SetAllTrue() {
b.Time++
b.AllTrue = b.Time
}
func (b *BitStreamer) SetAllFalse() {
b.Time++
b.AllFalse = b.Time
}
func (b *BitStreamer) GetIndex(index int) bool {
bit, ok := b.Bits[index]
if ok && bit.T >= b.AllTrue && bit.T >= b.AllFalse {
return bit.V
}
return b.AllTrue > b.AllFalse
}``````

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

``````class InfiniteArray {
constructor() {
this.arrayDict = {};
this.default = false;
}

getIndex(index) {
if(this.arrayDict[index] != undefined || this.arrayDict[index] != null) {
return this.arrayDict[index];
}
return this.default;
}

setFalse(index) {
this.setIndex(index, false);
}

setTrue(index) {
this.setIndex(index, true);
}

setIndex(index, value) {
if(index < 0 )
return;
this.arrayDict[index] = value;
}

setAllTrue() {
this.default = true;
this.arrayDict = {};
}

setAllFalse() {
this.default = false;
this.arrayDict = {};
}
}

/********Usage**********/

var infiniteArray= new InfiniteArray();
infiniteArray.getIndex(12) //false
infiniteArray.setAllTrue()
infiniteArray.getIndex(12) //true
infiniteArray.setFalse(12)
infiniteArray.getIndex(12) //false``````

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

Solution in JS

``````class InfiniteArray {
constructor() {
this.arrayDict = {};
this.default = false;
}

getIndex(index) {
if(this.arrayDict[index] != undefined || this.arrayDict[index] != null) {
return this.arrayDict[index];
}
return this.default;
}

setFalse(index) {
this.setIndex(index, false);
}

setTrue(index) {
this.setIndex(index, true);
}

setIndex(index, value) {
if(index < 0 )
return;
this.arrayDict[index] = value;
}

setAllTrue() {
this.default = true;
this.arrayDict = {};
}

setAllFalse() {
this.default = false;
this.arrayDict = {};
}
}

var infiniteArray= new InfiniteArray();
infiniteArray.getIndex(12) //false
infiniteArray.setAllTrue()
infiniteArray.getIndex(12) //true
infiniteArray.setFalse(12)
infiniteArray.getIndex(12) //false``````

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

what do you mean set all of values to be true? Does it mean that we need to set all of values which have been appeared to be true?

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

yes it means to set all values in stream to be true

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

What was Space Complexity expected? if O(N)
You can use 2 Hashmap as <int, Boolean> can use to store value at index
One hashmap trueHM for True and another hashmap falseHM for false values

i) setTrue(index) : Search in falseHM and remove that value, make entry in trueHM.
else if this index is in trueHM no need to update
Time : O(1)
ii) setFalse(index) : Same as above
iii) setAllTrue() : Set all to true in falseHM
Time complexity O(N) worst case.
iv) setAllFalse() : Set all to false in trueHM
v) getIndex(index) : Search in both.

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.