Virtual Boolean Array - Google Top Interview Questions

                        Solution in C++ :

class BooleanArray {
    public:
    bool base = false;
    set<int> diffs;

    BooleanArray() {
        base = false;
        diffs.clear();
    }

    void setTrue(int i) {
        if (base == false)
            diffs.insert(i);
        else
            diffs.erase(i);
    }

    void setFalse(int i) {
        if (base == true)
            diffs.insert(i);
        else
            diffs.erase(i);
    }

    void setAllTrue() {
        base = true;
        diffs.clear();
    }

    void setAllFalse() {
        base = false;
        diffs.clear();
    }

    bool getValue(int i) {
        return (base == true ? (diffs.count(i) > 0 ? false : true)
                             : (diffs.count(i) > 0 ? true : false));
    }
};
                    

                        Solution in Java :

import java.util.*;

class BooleanArray {
    public Map<Integer, Boolean> map;
    public boolean allTrue;

    public BooleanArray() {
        map = new HashMap<>();
    }

    public void setTrue(int i) {
        map.put(i, true);
    }

    public void setFalse(int i) {
        map.put(i, false);
    }

    public void setAllTrue() {
        map.clear();
        allTrue = true;
    }

    public void setAllFalse() {
        map.clear();
        allTrue = false;
    }

    public boolean getValue(int i) {
        if (map.containsKey(i))
            return map.get(i);
        return allTrue;
    }
}
                    

                        Solution in Python : 
                            
class BooleanArray:
    def __init__(self):
        self.arr = {}
        self.default = False

    def setTrue(self, i):
        self.arr[i] = True

    def setFalse(self, i):
        self.arr[i] = False

    def setAllTrue(self):
        self.arr = {}
        self.default = True

    def setAllFalse(self):
        self.arr = {}
        self.default = False

    def getValue(self, i):
        if i not in self.arr:
            return self.default

        return self.arr[i]

immortal
96

1 year ago
Even more compact memory footprint depending upon assignment.

class BooleanArray:
    def __init__(self):
        self.state = False
        self.d = set()

    def clear(self):
        self.d = set()

    def setTrue(self, i):
        if not self.state:
            self.d.add(i)
        elif i in self.d:
            self.d.remove(i)

    def setFalse(self, i):
        if self.state:
            self.d.add(i)
        elif i in self.d:
            self.d.remove(i)

    def setAllTrue(self):
        self.clear()
        self.state = True

    def setAllFalse(self):
        self.clear()
        self.state = False

    def getValue(self, i):
        if i in self.d:
            return not self.state
        return self.state