Hash Map implementation with a function to set all values

Question

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"

I added the implementation below - please tell me what you think about it - I mostly care about correctness and efficiency.

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 {
 Thread.sleep(0, 1);
 } catch (InterruptedException e) {
 e.printStackTrace();
 }
 return oldVal;
 }
 public void setAll(V value) {
 this.setAllTime = ZonedDateTime.now();
 try {
 Thread.sleep(0, 1);
 } 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"));
 }
}

Answer 1

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).

• John: 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?
• Pieter Witvoet: 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.