Interview coding test: Searcher

Question

I did a task for an interview and the solution was not accepted. The task was to implement the class search function by name. The number of classes in the input data from 0 to 100000. Class names are no longer than 32 characters, contains only letters and numbers, are unique.

The application starts with flags -Xmx64m -Xms64m -Xss64m. Expected, when the project is opened first time the data is indexed, then searches are performed quickly.

Can you take a look at this and let me know where I went wrong and if is possible to somehow refactor, speed up this implementation (except the normal implementation of cache).

import java.text.Collator;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Searcher implements ISearcher {
    private Map<Character, List<Entity>> storage = new HashMap<>();
    private Map<String, String[]> cache;

    public Searcher() {
    }

    /**
     * Refreshes internal data structures for fast search
     *
     * @param classNames        class names in project
     * @param modificationDates class modification date in ms
     */
    @Override
    public void refresh(String[] classNames, long[] modificationDates) {
        cache = new HashMap<>();

        for (int i = 0; i < classNames.length; i++) {
            char startChar = classNames[i].charAt(0);

            if (!storage.containsKey(startChar)) {
                List<Entity> list = new ArrayList<>();
                list.add(new Entity(classNames[i], modificationDates[i]));
                storage.put(startChar, list);
            } else {
                storage.get(startChar).add(new Entity(classNames[i], modificationDates[i]));
            }
        }
    }

    /**
     * Looking for a suitable class names starting with start
     *
     * @param start beginning of a class name
     * @return an array of length 0 to 12, class names, ordered by modification date
     *         and lexicographically
     */
    @Override
    public String[] guess(String start) {
        if (!storage.containsKey(start.charAt(0))) return new String[0];

        if (cache.containsKey(start)) return cache.get(start);

        Collator collator = Collator.getInstance();

        String[] result = storage.get(start.charAt(0)).stream()
                .filter(entity -> entity.name.startsWith(start))
                .sorted((entity1, entity2) -> {
                    int value = entity2.time.compareTo(entity1.time);
                    return value == 0 ? collator.compare(entity1.name, entity2.name) : value;
                })
                .limit(12)
                .map(e -> e.name)
                .toArray(String[]::new);

        cache.put(start, result);

        return result;
    }

    private static class Entity {
        String name;

        Long time;

        Entity(String name, long time) {
            this.name = name;
            this.time = time;
        }
    }
}

TestDataGenerator:

import java.util.Date;
import java.util.Random;

public class TestDataGenerator {
    private static final char[] LOWER_CHARS = "abcdefghijklmnopqrstuvwxyz".toCharArray();
    private static final char[] UPPER_CHARS = "ABCDEFGHIJKLMNOPQESTUVWXYZ".toCharArray();
    private static final char[] NUMBERS = "1234567890".toCharArray();

    private String[] names;
    private long[] modificationDates;

    private String[] masks;

    public TestDataGenerator(int numberClasses) {
        initMasks();
        init(numberClasses);
    }

    private void initMasks() {
        masks = new String[10];

        StringBuilder sb;
        Random random = new Random();

        for (int i = 0; i < masks.length; i++) {
            sb = new StringBuilder();

            for (int k = 0; k < 4; k++) {
                if (k % 2 == 0) {
                    sb.append(LOWER_CHARS[random.nextInt(LOWER_CHARS.length - 1)]);
                } else {
                    sb.append(UPPER_CHARS[random.nextInt(UPPER_CHARS.length - 1)]);
                }
            }

            masks[i] = sb.toString();
        }
    }

    private void init(int numberClasses) {
        Random random = new Random();

        names = new String[numberClasses];
        modificationDates = new long[numberClasses];

        for (int i = 0; i < numberClasses; i++) {
            names[i] = getName(random);
            modificationDates[i] = getDate(random);
        }
    }

    private String getName(Random random) {
        StringBuilder sb = new StringBuilder();

        int temp;

        sb.append(masks[random.nextInt(masks.length - 1)]);

        for (int i = 0; i < 32; i++) {
            temp = random.nextInt(100);

            if (temp % 2 == 0) {
                sb.append(LOWER_CHARS[random.nextInt(LOWER_CHARS.length - 1)]);
            } else if (temp % 3 == 0) {
                sb.append(NUMBERS[random.nextInt(NUMBERS.length - 1)]);
            } else {
                sb.append(UPPER_CHARS[random.nextInt(UPPER_CHARS.length - 1)]);
            }
        }

        return sb.toString();
    }

    private long getDate(Random random) {
        long max = System.currentTimeMillis();
        long min = new Date(2015, 11, 11).getTime();
        return min + (long) (random.nextDouble() * (max - min));
    }

    public String[] getNames() {
        return names;
    }

    public long[] getModificationDates() {
        return modificationDates;
    }
}

SearcherTest:

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

public class SearcherTest {
    public static void main(String[] args) {
        TestDataGenerator generator = new TestDataGenerator(1000);
        Searcher searcher = new Searcher();
        Random random = new Random();
        String[] searchBy = getSearchBy(generator.getNames(), random);

        searcher.refresh(generator.getNames(), generator.getModificationDates());

        List<Long> timeGuess = new ArrayList<>();
        long start, end;

        try {
            File file = new File("/users/kubreg/result.txt");

            if (!file.exists()) {
                file.createNewFile();
            }

            FileWriter fw = new FileWriter(file);

            fw.write("GENERATED DATA, ELEMENTS - " + generator.getNames().length + "\r\n");
            for (int i = 0; i < generator.getNames().length; i++) {
                fw.write(generator.getNames()[i] + " " + generator.getModificationDates()[i]  + "\r\n");
            }
            fw.write("\r\n");

            String search;
            String[] result;

            for (int i = 0; i < 10000; i++) {
                start = System.currentTimeMillis();
                search = searchBy[random.nextInt(searchBy.length - 1)];
                result = searcher.guess(search);
                end = System.currentTimeMillis();
                timeGuess.add(end - start);

                fw.write(search + "\r\n");
                fw.write(result.length  + "\r\n");
                for (String aResult : result) {
                    fw.write(aResult  + "\r\n");
                }
                fw.write("\r\n");
            }

            System.out.println("Average time GUESS - " + timeGuess.stream().collect(Collectors.averagingLong(l -> l - 1)));

            fw.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static String[] getSearchBy(String[] names, Random random) {
        int range = random.nextInt(names.length - 1);
        String[] result = new String[range];

        for (int i = 0; i < range; i++) {
            String tmp = names[random.nextInt(names.length - 1)];

            result[i] = tmp.substring(0, random.nextInt(16) + 1);
        }

        return result;
    }
}

Answer 1

Java 8 Map

Since you're already on Java 8, you can use Map.computeIfAbsent(K, Function) to put a List into your Map if none exists:

storage.computeIfAbsent(startChar, k -> new ArrayList<>())
        .add(new Entity(classNames[i], modificationDates[i]));

Java 8 Comparator

You can also use a number of Comparator methods, starting with Comparator.comparing(Function), to replace the in-line lambda you are using to sort your Stream<Entity>:

// assuming getters are given as such
Comparator<Entity> COMPARATOR = Comparator.comparing(Entity::getTime).reversed()
                                            .thenComparing(Entity::getName,
                                                            Collator.getInstance());

According to your implementation, you want to compare entity2.time - entity1.time first, so you have to reverse the Comparator, then comparing on the name.

Immutable classes and getters

As hinted above, providing getter methods lets you use method references for your Entity class, and you can make it immutable too by final-ing the fields.

Deprecated Date constructor

new Date(2015, 11, 11).getTime()

This constructor is deprecated, and in Java 8, you should consider using the new java.time.* APIs:

long min = ZonedDateTime.of(LocalDate.of(2015, 11, 11), 
                            LocalTime.MIDNIGHT, ZoneOffset.UTC).toEpochSecond() * 1000;

try-with-resources and hard-coding file paths

You should use try-with-resources on your FileWriter for safe and efficient handling of the underlying I/O resource.

Is there any special reason why you have went with a decidedly non-Unix line-separator (\r\n) while writing to a seemingly Unix-based filesystem?

Also, do consider not hard-coding the file path and take that as an input from String[] args instead.

edit: Since you do intend to write to a file using OS-dependent line separator, consider using a PrintWriter to do so too...

File outputFile = getOutputFile(args); // construct from program inputs
try (PrintWriter printWriter = new PrintWriter(outputFile)) {
    // ...
    printWriter.println();
    // ...
}

Answer 2

Let's start with the tests...

That's not a test is it? It's what I'd call a driver. A test should be written using some standard testing framework, such as junit. Each feature being tested should be clearly delineated in the tests, and each test method should have a meaningful name and be isolated from the other tests. Every feature should be tested exactly once and tests should be as small as possible with lots of them. Each test method should have three comments -- //given //when and //then describing the different phases of the test. Each test class should test a single target class, and all collaborators to that class should be replaced with mocks. Tests should be written before the code that makes them pass.

I would have failed you for not doing TDD -- not writing any tests at all is pretty bad.

---

On to the implementation itself. ISearcher is not a standard java name for an interface. We don't use hungarian notation in java. The correct name is Searcher. The implementation is SearcherImpl. I know that you can find examples with the I in place, but they're all bad.

public static void main(String[] args) since java 6 has been: public static void main(String... args)

The test can run with more memory than the searcher itself, so you could have used nio2 file writing: Files.write(file, buf). Also, you could have used try-with-resources, introduced in java 7, rather than the outdated try-catch block you did use. On this point, you didn't close your resources in the event of an exception.

If storage is a hashmap why do you need cache at all? What does it get you other than slowing things down and using double the memory?

You rely on arrays too much. Java collections (maybe a list) would have been more useful.

Finally, If speed were a factor, then you'd want to sort the big list once at the start and keep it's order in case of future inserts. Then you wouldn't have to sort for every find.

---

Taking all of this along with h.j.k's excellent points, I'd say that you come across as an inexperienced java 6 developer. If you are in fact more experienced than this then you'd want to practice your java 8 quite a lot more, and read some other people's code as a guide to style.

Answer 3

I think you misunderstood the exercise. I don't see in the description anything about starting character. I see starting string. I think you were supposed to produce results fast not only for prefixes of length 1, but also length 2, 3, and so on.

As such, the implementation doesn't produce results nearly fast enough. For a prefix of length 3, it takes the names with the first matching character in constant time, but then it switches to linear search.

Take a look at the trie (prefix tree) data structure, I think that was the goal of this exercise.

The caching is another misunderstanding. A cache is useful when the same requests are expected to be repeated many times. A programming challenge typically uses a large number of distinct test cases to verify the speed of the implementation, with no repetitions. So caching is most certainly pointless. In fact if you never get any cache hits then the cache only makes the implementation slower. Finally, the caching logic should be separated from the main logic, a pluggable piece.

Lastly, instead of sorting the results in every search request, you could sort storage during initialization, once.