Given n input strings and m query strings, find each query frequency in the list of input strings

Question

I'm doing questions on HackerRank to brush up on Java & CS.

---

Problem

This problem is called Sparse Arrays in HackerRank.

There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings.

For example, given input strings = ['ab', 'ab', 'bc'] and queries = ['ab', 'abc', 'bc'], result is [2, 1, 0]

Full Question

Solution

static int[] matchingStrings(String[] strings, String[] queries) {
 Map<String, Integer> counter = new HashMap<>();
 for (String current: strings) {
 counter.put(current, counter.getOrDefault(current, 0) + 1);
 }
 int[] result = new int[queries.length];
 for (int i = 0; i < queries.length; i++) {
 result[i] = counter.getOrDefault(queries[i], 0);
 }
 return result;
}

This passes all the test cases.

1. Can I do it in a better way?
2. Can this be simplified in Java-8, 11 or later?

• Anatolii: I checked the history of edits for your question and originally it didn't look very clear. Maybe that's why someone downvoted that version.
• JaDogg: Fair enough.. Sparse Array title might've been confusing. Hopefully new title makes more sense

Answer 1

Can I do it in a better way?

From the time complexity or space complexity your solution is good enough. Your store all your string frequencies beforehand so that to retrieve a frequency by any given string in O(1) time later. Also, it passes all the test cases so it's a good sign too.

Below are a couple of concerns regarding other aspects of your code.

Variable Naming

Your choice of variable names should be improved. For instance, Map<String, Integer> counter doesn't really reflect for what it stands for. I would call it stringFrequencyMap or stringCountMap.

Also, result sounds too generic here. How about queryResults?

I'll leave it up to you to think about other variable names you have (luckily not many left :) ).

Static method

I guess you've kept this method static as it was like this by default and to avoid creating an instance of your Solution class in the main() method. While it's fine for a small challenge like yours, generally there should be a good reason to add static to your method.

Improvements

Can this be simplified in Java-8, 11 or later?

Of course, if we just use JAVA 8 then we can take advantage of streams and write a solution as :

static long[] matchingStrings(String[] strings, String[] queries) {
 Map<String, Long> stringCountMap = Arrays.stream(strings).collect(Collectors.groupingBy(Function.identity(), counting()));
 return Arrays.stream(queries).mapToLong(query -> stringCountMap.getOrDefault(query, 0L)).toArray();
}

As you can see, we do this in 2 steps. First, we calculate a frequency map and then calculate an array of results using streams again. Please note that I changed the return type from int[] to long[].

UPDATE

Since there was a question why I've used Map<String, Long> rather than Map<String, Integer> - well, Long can hold bigger numbers. But since it's irrelevant for this problem here's a solution for Map<String, Integer>:

int[] matchingStrings(String[] strings, String[] queries) {
 Map<String, Integer> stringCountMap = Arrays.stream(strings).collect(Collectors.groupingBy(Function.identity(), summingInt(x -> 1)));
 return Arrays.stream(queries).mapToInt(query -> stringCountMap.getOrDefault(query, 0)).toArray();
}

Answer 2

I have some suggestions for your code.

1) Since we know the size of the output, I suggest that you initialize the java.util.HashMap with the size + 1, since the default capacity of a Map is 16; this will prevent the map to do a rehashing if you have more than 16 values.

If you want more information about the rehashing / load factor, you can read the java.util.HashMap javadoc.

//[...]
int queryLength = queries.length;
Map<String, Integer> counter = new HashMap<>(queryLength + 1);
//[...]

2) I suggest that you create a method to create a Map containing the count of the similar string; instead of building it in the method.

static int[] matchingStrings(String[] strings, String[] queries) {
 int queryLength = queries.length;
 Map<String, Integer> counter = getSimilarStringCountMap(strings, queryLength);
 //[...]
}
private static Map<String, Integer> getSimilarStringCountMap(String[] strings, int queryLength) {
 Map<String, Integer> counter = new HashMap<>(queryLength + 1);
 for (String current : strings) {
 counter.put(current, counter.getOrDefault(current, 0) + 1);
 }
 return counter;
}

Refactored code

 public static void main(String[] args) {
 String[] strings = {"ab", "ab", "bc"};
 String[] queries = {"ab", "abc", "bc"};
 System.out.println(Arrays.toString(matchingStrings(strings, queries)));
 }
 static int[] matchingStrings(String[] strings, String[] queries) {
 int queryLength = queries.length;
 Map<String, Integer> counter = getSimilarStringCountMap(strings, queryLength);
 int[] result = new int[queryLength];
 for (int i = 0; i < queryLength; i++) {
 result[i] = counter.getOrDefault(queries[i], 0);
 }
 return result;
 }
 private static Map<String, Integer> getSimilarStringCountMap(String[] strings, int queryLength) {
 Map<String, Integer> counter = new HashMap<>(queryLength + 1);
 for (String current : strings) {
 counter.put(current, counter.getOrDefault(current, 0) + 1);
 }
 return counter;
 }
```