3
\$\begingroup\$

For an interview, I was tasked with writing a program that consumes a list of strings, and produces a mapping between every character in the list, and the characters found most frequently with it (let's call them Companion Characters).

For example, if it was given ["aabc", "bcdddd", "cde"], it would return {a=[b, c], b=[c], c=[b, d], d=[c], e=[c, d]}. a maps to b, c because they were together in the first word, b maps to c because they were together in two words ("aabc" and "bcddd"), while a and d were only with it for one word, etc.

To solve it, I used two HashMaps – One which mapped every character to a map of companion characters, to integers (the number of times found), and another which mapped character to the list of companion characters found most frequently with it. My code (which compiles and works) is below.

import java.util.*;

public class MaxMap {
   private Map<Character, Map<Character, Integer>> charMap;
   private Map<Character, List<Character>> maxMap;

   public MaxMap() {
       charMap = new HashMap<>();
       maxMap = new HashMap<>();
   }

   public void computeMap(List<String> strs) {
       for(String str: strs) {
           //Will contain all of the starting letters encountered in the string
           Set<Character> seenOriginal = new HashSet<>();
           for(int i = 0; i < str.length(); i++) {
               char original = str.charAt(i);
               if(!charMap.containsKey(original)) {
                   charMap.put(original, new HashMap<>());
               }
               //Haven't yet calculated the mappings for this character - and dups don't matter
               if(!seenOriginal.contains(original)) {
                   seenOriginal.add(str.charAt(i));
                   Set<Character> seenMapping = new HashSet<>();
                   for(int j = 0; j < str.length(); j++) {
                       //This is the same character, or a character previously encountered.
                       if(i == j || str.charAt(i) == str.charAt(j) || seenMapping.contains(str.charAt(j))) continue;
                       char added = str.charAt(j);
                       seenMapping.add(added);
                       int num = charMap.get(original).getOrDefault(added, 0);
                       num++;
                       charMap.get(original).put(added, num);
                       setMaxMapping(original, added);
                   }
               }
           }
       }
   }

   public void setMaxMapping(char original, char added) {
       List<Character> current = maxMap.getOrDefault(original, new ArrayList<>());
       int oldCount = 0;
       if(current.size() > 0) {
           oldCount = charMap.get(original).get(current.get(0));
           //Special case, in case the first char in list was the one adjusted
           if(current.get(0) == added) {
               oldCount--;
           }
       }

       int addedCount = charMap.get(original).get(added);
       if(addedCount > oldCount) {
           current = new ArrayList<>(Arrays.asList(added));
       } else if (addedCount == oldCount) {
           current.add(added);
       }
       maxMap.put(original, current);
   }

   public Map<Character, List<Character>> getMaxMap() {
       return this.maxMap;
   }
}

The main class which constructed and called it is

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        List<String> strings = new ArrayList<>(Arrays.asList("aabc", "bcdddd", "cde"));
        MaxMap mm = new MaxMap();
        mm.computeMap(strings);
        System.out.println(mm.getMaxMap());
    }
}

I didn't get the job, because my code wasn't optimal enough. How should I improve it?

\$\endgroup\$
  • 1
    \$\begingroup\$ Shouldn't a map to a as well? \$\endgroup\$ – vnp Nov 21 '18 at 19:10
  • \$\begingroup\$ For each character, keep count of companions. When you finish looking at all strings, sort the counts and get the most frequent for each character. You can do the first part in O(chars * 26) assuming all characters go from a-z \$\endgroup\$ – juvian Nov 21 '18 at 20:46
1
\$\begingroup\$

Here are some tips to keep in mind when writing code that needs to be optimal:

  1. The single biggest thing is: reduce the time complexity! This is by far the most significant improvement you can possibly make. Avoid iterations over the data as much as possible. For instance, every time you check if the char was added to charMap, the containsKey() function iterates over data in the Map. There aren't many letters so you can have a small data structure where the position of the data (index) indicates what character it relates to, this will remove the need to iterate to search for a specific character. In other cases you may reduce the number of iterations by sorting your data and using an efficient search algorithm such as binary search.
  2. Arrays are the fastest data structure, use them instead of more complex data structures wherever it makes sense to do so.
  3. Minimize the amount of data to be stored/manipulated - this can too be achieved by position-coding the data in your data structure, the position where the numbers are saved tells you what character these numbers relate to, so there are no actual Character variables being created until you need to create them, and then you can write code that will create only the chars you need to use/output.

Here is my implementation of the function you were tasked to write, I also avoided some of the logic checks you did, but getting rid of a few if statements is not a significant optimization so don't worry about it, focus on the main points I explained and see how they are implemented.

(notice the difference caused by improving the time complexity: according to my benchmarking, my implementation works about as fast as yours (1.1 times faster) with an input of 3 strings in the list, but it works ~5.4 times faster than yours when given an input list of 30 strings, the speed gap grows the bigger the input gets)

public static Map<Character, List<Character>> companionChars(List<String> strings){
    Map<Character, List<Character>> result = new HashMap<>(27, 1);
    int[] lengths = {26, 26};
    int[][] companionCounts = (int[][]) Array.newInstance(int.class, lengths);

    for(String str : strings){
        int[] charsFound = new int[26];
        for(int x = 0; x < str.length(); x++)
            charsFound[str.charAt(x) - 'a'] = 1;
        for(int x = 0; x < 26; x++)
            if(charsFound[x] == 1){
                for(int y = 0; y < 26; y++)
                    companionCounts[x][y] += charsFound[y];
                companionCounts[x][x]--;
            }
    }

    for(int x = 0; x < 26; x++){
        ArrayList<Character> chars = new ArrayList<Character>();
        int max = 1;
        for(int y = 0; y < 26; y++){
            if(companionCounts[x][y] > max){
                max = companionCounts[x][y];
                chars.clear();
                chars.add((char)('a' + y));
            }
            else if(companionCounts[x][y] == max)
                chars.add((char)('a' + y));
        }
        if(!chars.isEmpty())
            result.put(new Character((char)('a' + x)), chars);
    }
    return result;
}

Main function:

public static void main(String args[]) {
    List<String> strings = Arrays.asList("aabc", "bcdddd", "cde");
    System.out.println(companionChars(strings));
}
\$\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.