Hey, I have the same output as commented in main (also tested it a bit and everything works fine) but it's not passing. keySet() seems obvious (or not?).
@Override
public Set<K> keySet() {
    return map.keySet();
}
remove():
@Override
public V remove(Object key) {
        if( map.get(key).size() == 0 ) {
            map.remove(key);
        } else {
            V val = map.get(key).get(0);
            map.get(key).remove(0);
            return val;
        }
    return null;
}