Google | Data structure to set all values in O(1)
Sithis
8882
GoogleMicrosoftUberPhone ScreeningOnsiteInterview

Design a list with the follwoing methods:

class CustomMap {

	public void set(int key, int value) {
	}

	public Integer get(int key) {
	}

	public void setAll(int value) {
	}
}

All methods should work in O(1) time.

Example:

CustomMap map = new CustomMap();
map.set(0, 1);
map.get(0); // 1
map.set(1, 2);
map.get(1); // 2
map.setAll(5);
map.get(0); // 5
map.get(1); // 5
map.get(2); // null, there's no such key
map.set(2, 7);
map.get(0); // 5
map.get(1); // 5
map.get(2); // 7
Solution 
class CustomMap {
    private final Map<Integer, Entry> map;
    private int allValue;
    private long allValueLastUpdate;

    public CustomMap() {
        map = new HashMap<>();
        allValueLastUpdate = System.nanoTime();
    }

    private static class Entry {
        int value;
        long lastUpdate;
    }

    public void set(int key, int value) {
        Entry entry = map.computeIfAbsent(key, (k) -> new Entry());
        entry.value = value;
        entry.lastUpdate = System.nanoTime();
    }

    public Integer get(int key) {
        Entry entry = map.get(key);
        if (entry == null) return null;
        if (entry.lastUpdate >= allValueLastUpdate) {
            return entry.value;
        }
        return allValue;
    }

    public void setAll(int value) {
        allValue = value;
        allValueLastUpdate = System.nanoTime();
    }
}
Comments (17)