CareerCup

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];
}

}

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;  
}

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
}

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;
        //GC is your friend
        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

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

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?

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.