4
\$\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
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

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.