# Hash Map implementation with a function to set all values

This is an interview question I saw online and thought to give it a try.
The question is about implementing a hash map with a setAll(V value) function. This function assignes a value to all the keys in the map at O(1).
Examples:

HashMapSetAll<Integer,String> map = new HashMapSetAll<Integer,String>();
map.put(1, "1");
map.put(2, "2");
map.setAll("all");
map.put(3,"3");

System.out.println(map.get(1)); // prints "all"
System.out.println(map.get(2)); // prints "all"
System.out.println(map.get(3)); // prints "3"


Also, pay attention to the call to Thread.sleep(0,1) - the reason I'm calling it is beacuase isAfter method of ZonedDateTime smallest unit compare is nano-seconds (and I want to make sure that at least one nano-seconds passes between to calls to ZonedDateTime.now()). Please tell me if there is a cleaner way of doing this time compare.

HashMapSetAll.java:

import java.time.ZonedDateTime;
import java.util.HashMap;
import java.util.Map;

public class HashMapSetAll<K,V> extends HashMap<K,V> {

private Map<K,ZonedDateTime> keyDates;
private ZonedDateTime setAllTime;
private V setAllVal;

public HashMapSetAll() {
super();
keyDates = new HashMap<K,ZonedDateTime>();
setAllTime = null;
setAllVal = null;
}

@Override
public V get(Object key) {
ZonedDateTime time = this.keyDates.get(key);
if (time == null)
return null;

if ( (this.setAllTime == null) || (time.isAfter(this.setAllTime)) )
return super.get(key);

return this.setAllVal;
}

@Override
public V put(K key, V value) {
V oldVal = super.put(key, value);

this.keyDates.put(key, ZonedDateTime.now());
try {
} catch (InterruptedException e) {
e.printStackTrace();
}

return oldVal;
}

public void setAll(V value) {
this.setAllTime = ZonedDateTime.now();
try {
} catch (InterruptedException e) {
e.printStackTrace();
}
this.setAllVal = value;
}
}


Also added some tests in HashMapSetAllTest.java:

import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class HashMapSetAllTest {

HashMapSetAll<Integer, String> setAllMap = new HashMapSetAll<Integer, String>();

@BeforeEach
void setUp() throws Exception {
setAllMap.clear();
}

@Test
void testPutFirst() {
String val = setAllMap.put(1, "hi");
assertNull(val);

}

@Test
void testPutSecond() {
String val;

setAllMap.put(1, "hi");
val = setAllMap.put(1, "hi2");

assertTrue(val.equals("hi"));
}

@Test
void testGetNormalNull() {
assertNull(setAllMap.get(1));
}

@Test
void testGetNormalValue() {
setAllMap.put(1, "hi");
assertTrue(setAllMap.get(1).equals("hi"));
}

@Test
void testGetValAfterSetAll() { // value assigned after setAll
setAllMap.setAll("all");
setAllMap.put(1, "mine");

assertTrue(setAllMap.get(1).equals("mine"));
}

@Test
void testGetValBeforeSetAll() { // values assigned before setAll
setAllMap.put(1, "mine");
setAllMap.setAll("all");

assertTrue(setAllMap.get(1).equals("all"));
}

@Test
void testGetValBeforeAndAfterSetAll() { // values assigned before setAll
setAllMap.put(1, "1");
setAllMap.setAll("all");
setAllMap.put(2, "2");

assertTrue(setAllMap.get(1).equals("all"));
assertTrue(setAllMap.get(2).equals("2"));
}
}


The obvious solution, replacing all values, is $$\O(n)\$$ - the trick is to do it in $$\O(1)\$$. With that in mind, your approach makes sense - store the new 'all' value, and customize get so it knows whether it should return the actual value for a key or the 'all' value.

I wouldn't use insertion time for that, however - that'll lead to hacks like Thread.sleep. A counter field that is only incremented when you call setAll should work just fine.

I would also wrap V in a custom class that stores both V and the last-modified-counter-value, so get doesn't need to perform two hash-map lookups in the worst case.

With that, get would look something like this:

public V get(K key) {
VWrapper wrapper = super.get(key);
if (wrapper.counter < setAllCounter)
return setAllVal;
return wrapper.value;
}


In your example, at the end keys 1 and 2 would have a counter value of 0 (they were added before any setAll call), 3 has a counter value of 1 (it was added after the first setAll call) and setAllCounter is 1 (setAll has been called one time).

• Thanks for the comment. Two things: first, how can I call the HashMap constructor for creating map with type <K, Wrapper>, when the generics for HashMapSetAll are <K,V>? Second, I thought about the idea of counter field - but that can cause an overflow - how can you handle overflow case? – John Nov 9 '18 at 19:48
• You can't if you inherit from HashMap<K,V>, but you can if you implement the Map<K,V> interface, while using an internal HashMap<K,VWrapper> for the actual work. During an interview I would only implement the most relevant methods though, and explain what else I would do if I had more time. Your approach is also ok, as long as you explain the trade-offs. As for overflow, an int will let you call setAll 2 billion times, a long allows 9 quintillion. Should be plenty for most use-cases. – Pieter Witvoet Nov 10 '18 at 17:48