6
\$\begingroup\$

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?

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

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;
} 
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you. Looks like a better implementation. I will check on this logic. \$\endgroup\$ – Praveen Sep 17 at 8:57
  • \$\begingroup\$ 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 \$\endgroup\$ – Joop Eggen Sep 17 at 8:58
  • \$\begingroup\$ You can use the example from the question. Just replace [] with {}. queryType is String[] and query is int[][]. \$\endgroup\$ – Johnbot Sep 17 at 9:47
  • \$\begingroup\$ 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. \$\endgroup\$ – superb rain Sep 17 at 11:27
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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()); \$\endgroup\$ – Praveen Jun 26 at 8:32
  • \$\begingroup\$ @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. \$\endgroup\$ – dariosicily Jun 26 at 8:45
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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;
}
| improve this answer | |
\$\endgroup\$

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.