Enhanced Hashmap - Add a number to all keys/values

Question

I had the below problem in a coding test and I got 28/30 tests passes and 2 failed due to a time-out.

Problem
You have created a programming language and now you have decided to add hashmap support to it. It was found that in common programming languages, it is impossible to add a number to all hashmap keys/values. So, you have decided to implement your own hashmap in your new language with following operations.

• insert x y - insert and object with key x and value y
• get x - return the value of an object with key x
• addToKey x - add x to all keys in map
• addToValue y - add y to all values in map

Your task is to implement this hashmap, apply the given queries, and to find the sum of all the results for get operations

For Example

• For queryType=["insert","insert","addToValue","addToKey","get"] and query=[[1,2],[2,3],[2],[1],[3]], the output should be hashMap(queryType,query)=5.

Explanation

1. insert 1 2 - hashmap will be {1:2}
2. insert 2 3 - hashmap will be {1:2,2:3}
3. addToValue 2 - hashmap will be {1:4,2:5}
4. addToKey 1 - hashmap will be {2:4,3:5}
5. get 3 - value is 5

Input/Output

• [execution time limit] 3 seconds (Java)
• [input] array.string queryType
  Array of query types. its is guaranteed that each queryType[i] any one of the above mentioned operation
  1<=queryType.length<=10^5
• [input] array.array.integer query
  Array of queries, where each query is mentioned by 2 numbers for insert and one number for others Key values are in range [-10^9,10^9]

Below is my solution in Java

long hashMap(String[] queryType, int[][] query) {
        long sum = 0;
        Integer currKey = 0;
        Integer currValue = 0;
        Map<Integer, Integer> values = new HashMap<>();
        for (int i = 0; i < queryType.length; i++) {
            String currQuery = queryType[i];
            switch (currQuery) {
            case "insert":
                HashMap<Integer, Integer> copiedValues = new HashMap<>();
                if (currKey != 0 || currValue != 0) {
                    Set<Integer> keys = values.keySet();
                    for (Integer key : keys) {
                        copiedValues.put(key + currKey, values.get(key) + currValue);
                    }
                    values.clear();
                    values.putAll(copiedValues);
                    currValue = 0;
                    currKey = 0;
                }
                values.put(query[i][0], query[i][1]);
                break;
            case "addToValue":
                currValue += values.isEmpty() ? 0 : query[i][0];
                break;
            case "addToKey":
                currKey += values.isEmpty() ? 0 : query[i][0];
                break;
            case "get":
                copiedValues = new HashMap<>();
                if (currKey != 0 || currValue != 0) {
                    Set<Integer> keys = values.keySet();
                    for (Integer key : keys) {
                        copiedValues.put(key + currKey, values.get(key) + currValue);
                    }
                    values.clear();
                    values.putAll(copiedValues);
                    currValue = 0;
                    currKey = 0;
                }
                sum += values.get(query[i][0]);
            }
        }
        return sum;
    }

Is there any other data structure I can use instead of hashmap or Can I improve my code to be more linear?

Answer 1

I would suggest you create your own OffsetIntegerMap that can map between integers and handle an offset on the keys and values.

You don't necessarily have to implement the HashMap from scratch, define your own limited interface and implement it with an existing Map<Integer, Integer> through composition.

By handling the offsets separately from the keys and values the complexity of the offset operations end up O(1) instead of O(n) when doing recalculations and the Map<> put and get operations stay at their original O(1).

An example an "OffsetIntegerMap":

import java.util.HashMap;
import java.util.Map;

public class OffsetIntegerMap {
    private final Map<Integer, Integer> actualMap;
    private int keyOffset = 0;
    private int valueOffset = 0;

    public OffsetIntegerMap() {
        actualMap = new HashMap<>();
    }

    public int size() {
        return actualMap.size();
    }

    public boolean isEmpty() {
        return actualMap.isEmpty();
    }

    public boolean containsKey(int key) {
        var keyWithoutOffset = key - keyOffset;
        return actualMap.containsKey(keyWithoutOffset);
    }

    public boolean containsValue(int value) {
        var valueWithoutOffset = value - valueOffset;
        return actualMap.containsValue(valueWithoutOffset);
    }

    public Integer get(int key) {
        var keyWithoutOffset = key - keyOffset;
        var value = actualMap.get(keyWithoutOffset);
        if (value == null) return null;
        return value + valueOffset;
    }

    public Integer put(int key, int value) {
        var keyWithoutOffset = key - keyOffset;
        var valueWithoutOffset = value - valueOffset;
        var oldValue = actualMap.put(keyWithoutOffset, valueWithoutOffset);
        if (oldValue == null) return null;
        return oldValue + valueOffset;
    }

    public Integer remove(int key) {
        var keyWithoutOffset = key - keyOffset;
        var oldValue = actualMap.remove(keyWithoutOffset);
        if (oldValue == null) return null;
        return oldValue + valueOffset;
    }

    public void clear() {
        actualMap.clear();
        keyOffset = 0;
        valueOffset = 0;
    }

    public int getKeyOffset() {
        return keyOffset;
    }

    public void setKeyOffset(int keyOffset) {
        this.keyOffset = keyOffset;
    }

    public int getValueOffset() {
        return valueOffset;
    }

    public void setValueOffset(int valueOffset) {
        this.valueOffset = valueOffset;
    }

    public void addToValues(int toAdd) {
        this.valueOffset += toAdd;
    }

    public void addToKeys(int toAdd) {
        this.keyOffset += toAdd;
    }
}

By encapsulating the offset logic the processing loop also becomes much simpler without refactoring much of anything:

static long hashMap(String[] queryType, int[][] query) {
    long sum = 0;
    var map = new OffsetIntegerMap();
    for (int i = 0; i < queryType.length; i++) {
        String currQuery = queryType[i];
        switch (currQuery) {
            case "insert":
                map.put(query[i][0], query[i][1]);
                break;
            case "addToValue":
                map.addToValues(query[i][0]);
                break;
            case "addToKey":
                map.addToKeys(query[i][0]);
                break;
            case "get":
                sum += map.get(query[i][0]);
        }
    }
    return sum;
} 

Answer 2

The most expensive operation is the addToKey x that adds x to all keys in map, because substantially you have to create a new entry key, value + x in your hashmap and delete the old entry key, value. To avoid the need of caching the old entry while iterating over the map, you can distinguish two cases:

x > 0, then if you have iterate over a keyset ordered descending there is no need of caching the old entries

x < 0, same approach but the keyset is ordered ascending

Because you are using hashmap, there is no key order guaranteed, so you need a data structure to store keys to be ordered, before iterating over keys like below:

private static void addtoKey(Map<Integer, Integer> map, int i) {
    if (i != 0) {
        List<Integer> list = new ArrayList<>(map.keySet());

        if (i > 0) {
            Collections.sort(list, Collections.reverseOrder());
        } else {
            Collections.sort(list);
        }

        for(int key : list) {
            map.put(key + i, map.get(key));
            map.remove(key);
        }
    }
}

I excluded the case 0 because map remains untouched. Other operations don't need order of the keys and as already suggested it could be better try to isolate every operation in a private method.

Answer 3

I have some suggestions for you.

Extract some of the logic to methods.

In your code, when the query is insert and get, you have two big blocks of code that are similar; you can extract to a method and reuse the method in both sections.

I suggest a method that returns a boolean based on the if condition, so you will be able to set the currValue and currKey variables to zero.

long hashMap(String[] queryType, int[][] query) {
   //[...]
   switch (currQuery) {
   //[...]
   case "insert":
      if (didWeCopiedValuesToMap(currKey, currValue, values)) {
         currValue = 0;
         currKey = 0;
      }
      values.put(query[i][0], query[i][1]);
      break;
      //[...]
   }
   //[...]
}


private boolean didWeCopiedValuesToMap(Integer currKey, Integer currValue, Map<Integer, Integer> values, HashMap<Integer, Integer> copiedValues) {
   if (currKey != 0 || currValue != 0) {
      Set<Integer> keys = values.keySet();
      for (Integer key : keys) {
         copiedValues.put(key + currKey, values.get(key) + currValue);
      }
      values.clear();
      values.putAll(copiedValues);

      return true;
   }

   return false;
}

Also, to check the current query currQuery, you can extract each of them in a method.

private boolean isGet(String currQuery) {
   return "get".equals(currQuery);
}

private boolean isAddToKey(String currQuery) {
   return "addToKey".equals(currQuery);
}

private boolean isAddToValue(String currQuery) {
   return "addToValue".equals(currQuery);
}

private boolean isInsert(String currQuery) {
   return "insert".equals(currQuery);
}

Always use the primitives when possible

When you know that it's impossible to get a null value with the number, try to use the primitives; they take less memory and is faster than the wrapper class.

Before

Integer currKey = 0;
Integer currValue = 0;

After

int currKey = 0;
int currValue = 0;

Try to put less code in switch blocks

In my opinion, the code becomes less readable when there are more than 3 lines of codes in a switch block; I suggest that you convert it to a is-else-if. This conversion will make the code shorter and more readable.

Before

switch (currQuery) {
case "insert":
   if (didWeCopiedValuesToMap(currKey, currValue, values)) {
      currValue = 0;
      currKey = 0;
   }
   values.put(query[i][0], query[i][1]);
   break;
case "addToValue":
   currValue += values.isEmpty() ? 0 : query[i][0];
   break;
case "addToKey":
   currKey += values.isEmpty() ? 0 : query[i][0];
   break;
case "get":
   if (didWeCopiedValuesToMap(currKey, currValue, values)) {
      currValue = 0;
      currKey = 0;
   }
   sum += values.get(query[i][0]);
}

After

if ("insert".equals(currQuery)) {
   if (didWeCopiedValuesToMap(currKey, currValue, values)) {
      currValue = 0;
      currKey = 0;
   }
   values.put(query[i][0], query[i][1]);
} else if ("addToValue".equals(currQuery)) {
   currValue += values.isEmpty() ? 0 : query[i][0];
} else if ("addToKey".equals(currQuery)) {
   currKey += values.isEmpty() ? 0 : query[i][0];
} else if ("get".equals(currQuery)) {
   if (didWeCopiedValuesToMap(currKey, currValue, values)) {
      currValue = 0;
      currKey = 0;
   }
   sum += values.get(query[i][0]);
}

Refactored code

    long hashMap(String[] queryType, int[][] query) {
        long sum = 0;
        int currKey = 0;
        int currValue = 0;

        Map<Integer, Integer> values = new HashMap<>();

        for (int i = 0; i < queryType.length; i++) {
            String currQuery = queryType[i];
            if (isInsert(currQuery)) {
                if (didWeCopiedValuesToMap(currKey, currValue, values)) {
                    currValue = 0;
                    currKey = 0;
                }
                values.put(query[i][0], query[i][1]);
            } else if (isAddToValue(currQuery)) {
                currValue += values.isEmpty() ? 0 : query[i][0];
            } else if (isAddToKey(currQuery)) {
                currKey += values.isEmpty() ? 0 : query[i][0];
            } else if (isGet(currQuery)) {
                if (didWeCopiedValuesToMap(currKey, currValue, values)) {
                    currValue = 0;
                    currKey = 0;
                }
                sum += values.get(query[i][0]);
            }
        }

        return sum;
    }

    private boolean isGet(String currQuery) {
        return "get".equals(currQuery);
    }

    private boolean isAddToKey(String currQuery) {
        return "addToKey".equals(currQuery);
    }

    private boolean isAddToValue(String currQuery) {
        return "addToValue".equals(currQuery);
    }

    private boolean isInsert(String currQuery) {
        return "insert".equals(currQuery);
    }

    private boolean didWeCopiedValuesToMap(int currKey, int currValue, Map<Integer, Integer> values) {
        HashMap<Integer, Integer> copiedValues = new HashMap<>();

        if (currKey != 0 || currValue != 0) {
            Set<Integer> keys = values.keySet();

            for (Integer key : keys) {
                copiedValues.put(key + currKey, values.get(key) + currValue);
            }

            values.clear();
            values.putAll(copiedValues);

            return true;
        }

        return false;
    }

Answer 4

Modified version of Johnbot's answer without an extra class. I think the extra class is overkill and rather distracts from the algorithm, as I have to search through a lot of code (a lot of it boilerplate) to see what's going on. It's not that extra class that makes the processing loop much simpler. It's the algorithm.

Further changes:

• keyOffset isn't clear to me in which direction it's offset, so I renamed that to addedToKey (likewise for value).
• Ordered the operation names as in the problem specification, both to stay close to the specification and because that order makes more sense to me.
• Introduced args to save some code repetition.
• Used long/Long for everything, not just for the sum. After all, adding to the keys/values could make them overflow if we just use int/Integer.

static long hashMap(String[] queryType, int[][] query) {
    Map<Long, Long> map = new HashMap<>();
    long sum = 0, addedToKey = 0, addedToValue = 0;
    for (int i = 0; i < query.length; i++) {
        int[] args = query[i];
        switch (queryType[i]) {
            case "insert":
                map.put(args[0] - addedToKey, args[1] - addedToValue);
                break;
            case "get":
                sum += map.get(args[0] - addedToKey) + addedToValue;
                break;
            case "addToKey":
                addedToKey += args[0];
                break;
            case "addToValue":
                addedToValue += args[0];
        }
    }
    return sum;
}

Answer 5

What about just storing an offset value for keys and values and building wrapper methods around the hashmaps get/put methods to account for this offset.

Answer 6

Simple O(nlogn) code

long long hashMap(vector<string> query, vector<vector<int>> q) {
    int n = query.size();
    int KeyOff = 0, ValOff = 0;
    map<int, int> mp;
    int x, y;
    int ans = 0;
    for(int i = 0 ; i < n ; i++) {
        if(query[i] == "insert") {
            x = q[i][0];
            y = q[i][1];
            mp[x-KeyOff] = y - ValOff;
        }
        else if(query[i] == "addToValue") {
            y = q[i][0];
            ValOff += y;
        }
        else if(query[i] == "addToKey") {
            x = q[i][0];
            KeyOff += x;
        }
        else {
            x = q[i][0];
            ans += mp[x-KeyOff] + ValOff;
        }
    }
    return ans;
}