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?

• dariosicily: Welcome to Code Review. I don't understand why you creates a new Map every time you make insert or get queries, if you can explain me why I appreciate it.
• Praveen: @dariosicily, Its because I don't want to overwrite the existing value while updating a key or map. Example: For {2:3,3:1}, If you want to add key 1 and value 1. In the first iteration, It will become {3:4}. Here, I will lose the actual 3:1 which is the next key value pair. In short, to avoid overwriting/collision of key value pairs.
• Joop Eggen: For such problems: realize that addToKey and addToValue are cummulative+global and can be held outside an internal wrapped map. get(7) after addToKey(4) and addToKey(1) means internalMap.get(7-(4+1)). And than create a solution.

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

• Praveen: Thank you. Looks like a better implementation. I will check on this logic.
• Joop Eggen: I find this answer top. Using a class separate from testing all cases. keyWithoutOffset and valueWithoutOffset (I think I saw a bug in the original code w.r..t. to that). The clear names (offset). Just the method names are Map centric instead of those in the requirements
• Johnbot: You can use the example from the question. Just replace [] with {}. queryType is String[] and query is int[][].
• superb rain: Ah, overlooked that. And I'm too spoiled by coding challenge sites just giving me a "Run" button :-). Modified this solution into my own answer now.
• rohan: Offset will not be same for every key in hashmap! - start with keyset (1,2,3) - add 10 to all keys, now keyset is (10,11,12) - insert new key (5), now keyset is (10,11,12,5) - add 10 to all keys, now keyset is (20,21,22,15). So the first 3 keys effectively had offset 20 added to them, but last key had offset only 10 (i.e. key additions done before this key (5) was inserted will be ignored).

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.

• Praveen: Thanks @dariosicily for the answer. Isn't sorting every time while making addToKey operation is costly as well?. Or Can I use a SortedMap to keep the insertion order descending. Like, SortedMap<Integer, Integer>values = new TreeMap<Integer, Integer>(Collections.reverseOrder());
• dariosicily: @Praveen You are welcome. Yes it is sorting every time , but with ArrayList after sorting you proceed in a linear way. I was convicted you could use only HashMap; if you can use TreeMap instead of HashMap you can use an iterator and a reverse iterator and iterate over your TreeMap in a straight way.

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

• adamhurwitz.eth: Why does uniformly adding addedToKey to the value's key not work, yet subtracting it for the insert and get actions does work?

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

We are looking for answers that provide insightful observations about the code in the question. Answers that consist of independent solutions with no justification do not constitute a code review, and may be removed.

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

• Sara J: You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process.
• greybeard: How does this differ from superb rain's answer? Down to both (all, in all fairness) implementations making me parse [i][0] more often than I care to.