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