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