1
\$\begingroup\$

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"));
    }
}
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – John Nov 9 '18 at 19:48
  • \$\begingroup\$ 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. \$\endgroup\$ – Pieter Witvoet Nov 10 '18 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.