2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Synchronized? In task there is string "That class search function will be used not only by yourself." As I understand it, it is telling me, that program will be used by some people, not one. All your refactoring is awesome, get it into my code with minor edits. About oldest first - you were right, date in long format fainted me, and i thought that lowest is newest. And I do not understand last paragraph of your answer. How do i store newestClasses before it is sorted by value? And thank you very much for your review, it clears many things to me. \$\endgroup\$ – Eli. G Oct 5 '16 at 14:06
  • \$\begingroup\$ Synchronized depends on how your class will be used. If you can guarantee that refresh will only be called by one Thread, and is finished before guess() is called, you don't need to use synchronized. The guess will be called by many threads, but that is ok, because it doesn't modify the instance and will not be called when refresh is running. \$\endgroup\$ – RobAu Oct 5 '16 at 21:37
1
\$\begingroup\$

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

}
\$\endgroup\$
  • \$\begingroup\$ Yes, exception handling isn't my strong side. Thanks for a tip. Though I see that this is much too larger code, than post before. How do i measure effectiveness like memory usage or smth? \$\endgroup\$ – Eli. G Oct 6 '16 at 6:51
  • \$\begingroup\$ There is more code, but if you skip the error handling, documentation, imports and the main method, it is about the same size as your original version :). You measure memory usage by attaching a profiler, like VisualVM, and then your your program. \$\endgroup\$ – RobAu Oct 6 '16 at 6:57

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.