Class name search algorithm

Question

Here is a test task from a company, where I'd like to work eventually. I solved all they wanted to me to do, however failed to get an interview. I do not know what is wrong with my solution, because it IS working fine and fast.

I do not have any real experience in programming, and will be very grateful if some java-veteran show me some flaws in my solution and also give any advice how to improve my skill in programming.

Here's the task itself.

"Imagine that you - the developer from the ancient times, when IDE were only start to exist. You have big project in Java with hundreds of thousands files. To get your life more easy, you decided to implement the class search function by its name. For convenience, you enter only the first letters of the name of the class, IDE gives you a list of 12 classes that start with the characters entered. In the list classes are sorted by last modification (recently saved at the beginning), if changed at the same time - sorted lexicographically.

It is expected that when the project is opened, data is indexed one time, then searches are performed quickly. That class search function will be used not only by yourself."

Decision must have a class with a default constructor that implements the interface ISearcher.

That is the searcher-class

class Searcher implements ISearcher { private SortedMap<String, Long> classes = new TreeMap<>(); @Override public synchronized void refresh(String[] classNames, long[] modificationDates) { Timer.start("One-time indexing"); /* Indexing data - adding arrays sorted by map keys. */ for (int i = 0; i< classNames.length; i++){ classes.put(classNames[i], modificationDates[i]); } Timer.finish(); } @Override public synchronized String[] guess(String start) { Timer.start("Search"); ArrayList<String> list = new ArrayList<>(); //auxiliary list for transferring data from map to array String[] result; //resulting list of class names //If search string is not empty: if(start.length() > 0) { //Searching string in map char nextLetter = (char) (start.charAt(start.length() - 1) + 1); String end = start.substring(0, start.length()-1) + nextLetter; //Result map SortedMap<String, Long> map = classes.subMap(start, end); //Sort all results by last mod.date Map <String, Long> sortedSet = sortByValue(map); list.addAll(sortedSet.keySet()); //Printing results (no more than 12) if (map.size() < 12) { result = new String[map.size()]; for (int i = 0; i < map.size(); i++) { result[i] = list.get(i); } } else { result = new String[12]; for (int i = 0; i < 12; i++) { result[i] = list.get(i); } } Timer.finish(); return result; } //If search string is empty - 12 last modified classes printed. list.addAll(sortByValue(classes).keySet()); result = new String[12]; for (int i = 0; i<12; i++){ result[i] = list.get(i); } Timer.finish(); return result; } /* Auxiliary method, creating linked hash map to sort by value instead of key. */ private static Map<String, Long> sortByValue(Map<String, Long> map) { LinkedHashMap<String, Long> result = new LinkedHashMap<>(); //Create a set of records <String, Long>, to implement custom comparator. SortedSet<Map.Entry<String, Long>> sortedEntries = new TreeSet<>( new Comparator<Map.Entry<String, Long>>() { @Override public int compare(Map.Entry<String, Long> e1, Map.Entry<String, Long> e2) { //Sort by value int res = e1.getValue().compareTo(e2.getValue()); //If values are equal - sort by key return res != 0 ? res : e1.getKey().compareTo(e2.getKey()); } } ); sortedEntries.addAll(map.entrySet()); for (Map.Entry<String, Long> e : sortedEntries){ result.put(e.getKey(), e.getValue()); } return result; } } 

This is ISearcher interface

public interface ISearcher { /** * Refreshes internal data structures to find it easily * @param classNames project classes' names * @param modificationDates modification date in ms format since 1 jan 1970 */ void refresh(String[] classNames, long[] modificationDates); /** * Seeking a suitable class names * The name must begin with the 'start' * @param start the beginning of a class name * @return an array of length 0 to 12, class names, sorted by date modifications and lexicographic. */ String[] guess(String start); } 

Here is all my (working) solution on Github.

Answer 1

Synchronized?

Why is this synchronized? Is it multithreaded? If not, then this would seem to be unnecessary.

Prefer interfaces as types

 ArrayList<String> list = new ArrayList<>(); //auxiliary list for transferring data from map to array 

More common would be

 List<String> list = new ArrayList<>(); //auxiliary list for transferring data from map to array 

This makes it easier to change the type of list in the future.

Don't gate the main part of the method

 if(start.length() > 0) { 

This seems backwards to me. You check if there's stuff in the string. If there is, then you do the main logic of the method and return. If not, you drop out of the if and process an exceptional case. Usually I'd expect the exceptional case to be first, as it's generally shorter. So I'd say

 if (start.isEmpty()) { 

It's preferable to use isEmpty to check for emptiness rather than manually writing your own using length.

Don't Repeat Yourself (DRY)

 ArrayList<String> list = new ArrayList<>(); //auxiliary list for transferring data from map to array String[] result; //resulting list of class names //If search string is not empty: if(start.length() > 0) { //Searching string in map char nextLetter = (char) (start.charAt(start.length() - 1) + 1); String end = start.substring(0, start.length()-1) + nextLetter; //Result map SortedMap<String, Long> map = classes.subMap(start, end); //Sort all results by last mod.date Map <String, Long> sortedSet = sortByValue(map); list.addAll(sortedSet.keySet()); //Printing results (no more than 12) if (map.size() < 12) { result = new String[map.size()]; for (int i = 0; i < map.size(); i++) { result[i] = list.get(i); } } else { result = new String[12]; for (int i = 0; i < 12; i++) { result[i] = list.get(i); } } Timer.finish(); return result; } //If search string is empty - 12 last modified classes printed. list.addAll(sortByValue(classes).keySet()); result = new String[12]; for (int i = 0; i<12; i++){ result[i] = list.get(i); } Timer.finish(); return result; 

A side issue is that you always return twelve elements sorted by modification data. Why can't you share some of the logic?

 SortedMap<String, Long> map; if (start.isEmpty()) { map = classes; } else { // get the next string after start char nextLetter = (char) (start.charAt(start.length() - 1) + 1); String end = start.substring(0, start.length()-1) + nextLetter; map = classes.subMap(start, end); } List<String> oldestClasses = new ArrayList<>(map.entrySet()); Collections.sort(oldestClasses, new Comparator<Map.Entry<String, Long>>() { @Override public int compare(Map.Entry<String, Long> e1, Map.Entry<String, Long> e2) { // Sort by modification date int res = e1.getValue().compareTo(e2.getValue()); // If values are equal - sort by name return res != 0 ? res : e1.getKey().compareTo(e2.getKey()); } } ); // Returning results (no more than 12) String results = new String[Math.min(oldestClasses.size(), 12)]; for (int i = 0; i < results.length; i++) { results[i] = oldestClasses.get(i).getKey(); } Timer.finish(); return results; 

Twice you had repeated code that this does only once. The first time by refactoring the repeated code out of what was effectively an if/else.

The second time, I observed that both for loops filled results. Only the length changed. It's better practice to limit by the length of the array anyway. That way if you changed the 12 to 15, you wouldn't have to do so in multiple places.

I renamed result to results, as it is an array not a single value. I find it to be a good convention to make collections and arrays plural if possible.

I got rid of the sortByValue, as I wanted to work with a List rather than a Map that I'd put in a List. If you want, you could make sortByValue return a List with the new code instead.

Prefer descriptive names like oldestClasses to names like list if there is a sensible name available.

Bug

Isn't your date sort backwards? I think it is sorting oldest first. Don't you want newest first?

Bug 2

Your code wouldn't handle the situation where there were less than twelve classes. Yes, there are supposed to be thousands in the general case. But what about a new IDE? This would be a common unit test in a test harness.

Alternative

If there is no search string, you keep sorting the whole class map to get the twelve most recent classes. Consider storing that instead. Then you could say something like

 if (start.isEmpty()) { return newestClasses; } 

and then continue with the rest of the logic.

The problem statement is ambiguous, but they may have been expecting you to do this. Index once; use many.

Answer 2

In addition to the already great answer above:

• take a look the NavigableMap interface on the TreeMap, it offers a lot of nice methods like ceilingKey(), making the code a lot simpler.
• error handling. You never know for sure how callers will abuse your implementation. Try to defend it as well as you can, without giving away the internal workings of you implementation.

Here is the code:

package classname.searcher; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.NavigableMap; import java.util.SortedMap; import java.util.TreeMap; public class Searcher implements ISearcher { // Use a NavigableMap so we can efficiently get next keys, etc. private NavigableMap<String, Long> classMap; // We cache the results for the empty search. private String[] newestClassesCache; // We have two comparators, one for sorting the cached classes for empty // search private static final Comparator<Map.Entry<String, Long>> NEWEST_COMPARATOR = createsNewestComparator(); // ..and one that first sorts on name private static final Comparator<Map.Entry<String, Long>> NAME_NEWEST_COMPARATOR = createNameNewestComparator(); private static final int MAX_RESULTS = 12; @Override public void refresh(String[] classNames, long[] modificationDates) { if (classNames == null) { throw new IllegalArgumentException("'classNames' cannot be null"); } if (modificationDates == null) { throw new IllegalArgumentException("'modificationDates' cannot be null"); } if (classNames.length != modificationDates.length) { throw new IllegalArgumentException("'classNames' and 'modificationDates' are not the same size"); } classMap = new TreeMap<>(); for (int i = 0; i < classNames.length; i++) { if (classNames[i] == null) { throw new IllegalArgumentException("'classNames' at index[" + i + "] cannot be null"); } classMap.put(classNames[i], modificationDates[i]); } // cache the top MAX_RESULTS classes newestClassesCache = getLimitedResultList(classMap, NEWEST_COMPARATOR); } @Override public String[] guess(String start) { if (classMap == null) { throw new IllegalStateException("Please make a succesfull call to 'refresh()' first!"); } if (start == null || start.isEmpty()) { // if there is no sensible input, we return the top MAX_RESULTS // newest classes // for better performance, we haved cached this list. return newestClassesCache; } else { int resultCount = 0; String currentClassKey = start; SortedMap<String, Long> resultMap = new TreeMap<String, Long>(); // We continue adding results until either there are no more // classKeys, or the result has enough results currentClassKey = classMap.ceilingKey(currentClassKey); //I assume checking the startWith for MAX_RESULTS will be faster on a set //of 100.000 classes that might have 10.000 similar matches on the 'start' String. while ( currentClassKey != null && currentClassKey.startsWith(start) && resultCount < MAX_RESULTS) { resultMap.put(currentClassKey, classMap.get(currentClassKey)); resultCount++; currentClassKey = classMap.higherKey(currentClassKey); } return getLimitedResultList(resultMap, NAME_NEWEST_COMPARATOR); } } /** * We want to have a maximum number of keys of entries (MAX_RESULTS) from a * map, sorted by a certain comparator. * <p> * For example, we want them sorted based on the key, and if the key is * equals, by the value. * * @param map * @param comparator * @return The resulting array. */ protected String[] getLimitedResultList(Map<String, Long> map, Comparator<Map.Entry<String, Long>> comparator) { // Put them in a list to be able to sort as we like List<Entry<String, Long>> descendingList = new ArrayList(map.entrySet()); // Do the actual sort Collections.sort(descendingList, comparator); // Get the top MAX_RESULTS keys, using java 8 streams. Unfortunately, // toArray() returns Object[] so // We need a cast. return descendingList.stream().map(e -> e.getKey()).limit(MAX_RESULTS).toArray(String[]::new); // Alternatively, build a array and fill it with a for loop. This will // be more code. } //Create a comparator that only looks as the modification date (that is stored in the value private static Comparator<Entry<String, Long>> createsNewestComparator() { return new Comparator<Map.Entry<String, Long>>() { @Override public int compare(Entry<String, Long> o1, Entry<String, Long> o2) { // descending, so switch sign return -o1.getValue().compareTo(o2.getValue()); } }; } private static Comparator<Entry<String, Long>> createNameNewestComparator() { return new Comparator<Map.Entry<String, Long>>() { @Override public int compare(Entry<String, Long> o1, Entry<String, Long> o2) { int result = o1.getKey().compareTo(o2.getKey()); if (result != 0) { return result; } else { // descending, so switch sign return -o1.getValue().compareTo(o2.getValue()); } } }; } //Mini use case public static void main(String[] args) { Searcher s = new Searcher(); s.refresh(new String[] { "class1", "class2", "meh" }, new long[] { 111, 222,333 }); for (String result : s.guess("")) { System.out.println(result); } System.out.println("-------------------"); for (String result : s.guess("c")) { System.out.println(result); } } }