1

Есть задача которая не решается, точнее все верно решается, но в нескольких тесткейсах есть таймаут, на Java 7.

Given a set of hotels and its guests reviews, sort the hotels based on a list of words specified by a user. The criteria to sort the hotels should be how many times the words specified by the user is mentioned in the hotel reviews.

Input:

The first line contains a space-separated set of words which we want to find mentions in the hotel reviews.

The second line contains one integer M, which is the number of reviews.

This is followed by M+M lines, which alternates an hotel ID and a review belonging to that hotel.

Output

A list of hotel IDs sorted, in descending order, by how many mentions they have of the words specified in the input.

Notes

– The words to be find will always be singe words line ‘breakfast’ or ‘noise’. Never double words like ‘swimming pool’.

– Hotel ud is a 4-byte integer.

– Words match should be case-insensitive.

– Dots and commas should be ignored.

– If a word appears in a review twice, it should count twice.

– If two hotels have the same number of mentions, they should be sorted in the output based on their ID, smallest ID first.

– In case one or more test cases time out, consider revisiting the runtime complexity of your algorithms.

Sample output

2 1

1

2 1

Решение вроде как самое быстрое, как можно еще улучшить?

public static void main(String[] args) throws FileNotFoundException {
    System.setIn(new FileInputStream(System.getProperty("user.home") + "/in.txt"));
    Scanner scanner = new Scanner(System.in);
    String lookWords = scanner.nextLine();
    Set<String> lookWordsMap = new HashSet<>();
    for (String s : lookWords.split(" ")) {
        lookWordsMap.add(s.toLowerCase());
    }

    int countReviews = scanner.nextInt();
    Map<Integer, Integer> rate = new HashMap<>();

    for (int i = 0; i < countReviews; i++) {
        int hotelId = scanner.nextInt();
        scanner.nextLine();
        String review = scanner.nextLine();
        if (!rate.containsKey(hotelId)) {
            rate.put(hotelId, 0);
        }
        for (String s : review.split(" ")) {
            s = s.replaceAll("[,.]", "").toLowerCase();
            if (lookWordsMap.contains(s)) {
                rate.put(hotelId, rate.get(hotelId) + 1);
            }
        }
    }
    List<Map.Entry<Integer, Integer>> sortedList = new ArrayList(rate.entrySet());
    Collections.sort(sortedList, new Comparator<Map.Entry<Integer, Integer>>() {
        @Override
        public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
            if (o1.getValue() > o2.getValue()) {
                return -1;
            } else if (o1.getValue() < o2.getValue()) {
                return 1;
            } else {
                if (o1.getKey() > o2.getKey()) {
                    return -1;
                } else if (o1.getValue() < o2.getValue()) {
                    return 1;
                }
            }
            return 0;
        }
        /*if (o1.getValue() == o2.getValue()) {
            return o1.getKey() - o2.getKey();
        } else {
            return o2.getValue() - o1.getValue();
        }*/
    });

    for (Map.Entry<Integer, Integer> integerIntegerEntry : sortedList) {
        System.out.print(integerIntegerEntry.getKey() + " ");
    }
}
3
  • Возможно в 7й версии джавы просто нет некоторых функций, из за чего и не проходит тесты?
    – BogdanBida
    5 мар 2018 в 7:42
  • Предпологается что должно проходить на любом языке, они даже написали в условиях In case one or more test cases time out, consider revisiting the runtime complexity of your algorithms.
    – J Mas
    5 мар 2018 в 8:08
  • У вас ошибка в компараторе, два раза проверяете o1.getValue() < o2.getValue()
    – Zergatul
    29 мар 2018 в 19:08

1 ответ 1

2
+300

Нужно убрать вложенный цикл по всем словам review и применить алгоритм Ахо-Корасик для поиска набора подстрок в строке.

4
  • На эту задачу дается 20 минут, я даже без ахо корасик потратил уйму времени и то не смог, а устраивался не алгоритмистом а просто разработчиком)
    – J Mas
    30 мар 2018 в 18:28
  • Это фейсбук? Интернетом пользоваться было нельзя?
    – ei-grad
    30 мар 2018 в 20:49
  • Я наверное все 20 минут потратил чтобы просто въехать в задачу :-).
    – ei-grad
    30 мар 2018 в 20:56
  • @ei-grad Что порекомендуете почитать? 13 апр 2018 в 7:15

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.