# Enhanced Hashmap - Add a number to all keys/values

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;
currValue += values.isEmpty() ? 0 : query[i][0];
break;
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?

• 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. – dariosicily Jun 25 at 8:38
• @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. – Praveen Jun 25 at 9:30
• Thanks, now I got it. – dariosicily Jun 25 at 11:48

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 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;
currValue += values.isEmpty() ? 0 : query[i][0];
break;
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]);
currValue += values.isEmpty() ? 0 : query[i][0];
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]);
currValue += values.isEmpty() ? 0 : query[i][0];
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 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;
}



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.

• 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()); – Praveen Jun 26 at 8:32
• @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. – dariosicily Jun 26 at 8:45