Какую сортировку применять?

Question

[artshelom]

Предисловие:
Нашел интересную задачу в интернете погуглив, понял что такое на тестировании перед собеседованием.

Вопрос:
Задача мне ясна, как я понял она упирается в сортировку, саму задачу я решил. Но вот сделать, чтобы она выполнялась в указанные 1-10 секунд не получается. Как я понял, надо делать сортировку у которой скорость log2(N). Не могли бы подсказать, на какой стадии лучше делать(Когда словарь только заполняется или сразу как он заполнился или когда нужные слова нашлись) сортировку и какую сортировку делать(Пока думаю о сортировки Шелла, но может есть по лучше)???

Comments

[Денис Загаевский]

Логарифмическая сортировка? Ну-ну.

[Андрей К]

Денис Загаевский: мне тоже сразу бросилось )))
Отсортировать массив не проверив его элементов. Истерика!!!

Answer 1

[longclaps]

Кто ж знает, что ты там нарешал. По идее, нужно было бы по набору слов построить префиксное дерево, в каждом узле которого - однобуквенный префикс (в корне префикс не нужен), количество начинающихся с него и его родителей слов и ссылки (не более 26 - по числу букв алфавита) на дочерние узлы.
При вызовах нужно выбрать ветвь перфикса и отсортировать её дочерние узлы. Для столь коротких массивов актуальна сортировка вставкой (да-да), но если хочешь попонтоваться - выбери что-то еще.

Comments

[artshelom]

Идея классная, чуть позже загружу на github скину ссылку.

Вот так у меня выполняется за 1 минуту

[Odissey Nemo]

Решение похоже на верное. Но можно сделать ещё проще.

1. Отсортировать стандартной сортировкой 1-ю часть списка (со словами и частотой) как массив объектов {строка, частота} в естественном лексическом порядке.

2. Для второй части списка (с начальными частями слов) двоичным поиском искать место, куда вставить искомое начало слова. Результатом будет индекс первого слова в отсортированном массиве, начинающегося с этого префикса.
3. Пройтись последовательно вниз по массиву, выбрав максимум 10 слов с префиксом (или менее 10, как уж придётся). Найденные слова отсортировать той-же сортировкой (потери на универсализм будут не существенны, полагаю) по убыванию частоты и длины слов и выводить на out.

Должно получиться быстро, хотя и не столь внушительно, как с применениями деревьев)))

[longclaps]

odissey_nemo:
Решение похоже на неудачное. Вот тестовая последовательность, которая его убьёт:
15000 однобуквенных префиксов - это 15000 выборок/сортировок по 10^5/26==3846 слов. Это я еще добрый - а если все слова на "a" и все запросы "a"?
Mожно, конечно, их закешировать, но тогда уж надо уметь кэшировать префиксы произвольной длины - чтобы не умереть на выборке слов типа aaaaaaaaaa, aaaaaaaaab ... aaaaazzzzz (все разные, всё по условию) и префиксе aaaaa.
А чем кэшировать? Хэшмэп подойдёт, или дерево. А у меня уже есть дерево ) И все сортировки у меня короткие, и стадии выборки нет - это тоже чего-то стоит. У меня накладные в худшем случае - это создание не более чем ~10^6 (все слова разные 15-буквенные) узлов дерева или 10^5*15 сложений (если слова начинаются одинаково) - и всё.
Кстати, только что обратил внимание: ваше описание решения длиннее моего. Это к вопросу о простоте ) И третья стадия не соответствует условию задачи.

[artshelom]

longclaps: Как разберусь как закидывать проекты на github и допишу последний метод для сортировки. Я скину сюда ссылку.
То что ты написал, мне кажется самое верное(1 коммент). Насчет хеширования не знаю его. Как погуглю подумаю как можно сделать.
Пока сам проект выполняется за 20сек. С новым методом должно быть по меньше!

[longclaps]

artshelom:
кэшировние
хэшировние

[artshelom]

longclaps: odissey_nemo: https://github.com/artem54325/Test3
Вот так получилось сделать. Работает около 20 секунд!
Интересно что не правильно сделал.

[Odissey Nemo]

longclaps: Не понял, откуда такие сложности привиделись? Зачем кэширование и/или хэширование? Для демонстрации способностей и теоретических знаний? Мудр кто знает нужное, а не многое (с) не моё.

Сортировка тут - один раз. Это далеко не заполнение и формирование дерева с его структурами и адресами. Создал массив фиксированного размера, затем линейно заполняешь объектами и 1 (один) раз сортируешь.

Двоичный поиск работает методом деления пополам, т.е на 4 миллиарда элементов в среднем будут 16 обращений к линейной таблице объектов по индексу, не по ссылкам. Явно не медленнее обхода по дереву. Собственно, это логический аналог обхода по дереву.

Сортировать часто придётся только конкретный ответ, т.е. не более 10 элементов на один ответ, в среднем сортировать по 5 элементов (предположительно). Можно для таких целей взять экзотик-сортировку для сверхкоротких выборок.

Про третью стадию либо я не понял Вас, либо Вы не поняли (писал кратко).

Ответ длиннее чем описание.

Дайте мне тестовую выборку и говорить дальше не придётся (пусть говорят пушки))). Сложные решения - для простых задач?

P.S. Преимущество при использовании дерева есть - это более универсальное решение, которое можно использовать при решении других задач, связанных с поиском. По жизни не раз решал реальные задачи двоичным поиском и сложные алгоритмы не требовалось. Времени это вообще не занимало. Впрочем, всё зависит от тестовой выборки. Но, зная размеры максимальных словарей (десятки тысяч слов в реальности), можно предположить, что задача будет идти секунды.

[longclaps]

odissey_nemo:
...функция автодополнения ... показать не более 10 самых часто употребляемых слов, начинающихся с префикса.
Сортировка - один раз - это, видимо лексикографическая сортировка. Тут вопросов нет.
Сортировать часто придётся только конкретный ответ, т.е. не более 10 элементов на один ответ, в среднем сортировать по 5 элементов (предположительно) - оценка среднего доставила. Непонятно только, как ты извлечешь эти не более 10 элементов из диапазона.
Дайте мне тестовую выборку - возьми по ссылке у artshelom

[longclaps]

artshelom: Это питон, 1 сек, лобовое решение.

from heapq import heappush, heappushpop

with open("test.in", "r") as f:
    l = f.read().splitlines()  # читаем файл а список строк
n, d = int(l[0]), {}    # n из условия, d - словарь (хэштаблица)
hpp = (heappush, heappushpop)
for i in range(1, n + 1):  # перебираю инициализирующие строки
    w, s = l[i].split() # расщепляю
    t = (int(s), w)     # создаю кортеж вида (целое, слово)
    while w:            # пока в слове есть буквы
        w = w[:-1]      # отрезаю его последнюю букву - так я перебираю префиксы
        if w in d:      # если префикс уже в словаре
            ww = d[w]   # ww - это буфер из не более чем 10 кортежей, ...
            hpp[len(ww) > 9](ww, t)  # добавляю либо вытесняю кортеж с минимальным числом
        else:
            d[w] = [t]  # создаю и добавляю в словарь новый буфер
for w in l[n + 2:]:     # перебираю запросы
    print("     ~ %s" % w)  # вот префикс
    if w in d:  # если префикс в словаре
        for t in sorted(d[w], reverse=True):
            print("%6d %s" % t)  # печатаю отсортированный буфер

[artshelom]

longclaps: А можете в 2 словах сказать, что делает то что вы написали. То мне не очень понятно.
На мой взгляд программа читает файл. Заполняет массив?? или что?? ну и сортировка(

for t in sorted(d[w], reverse=True):
            print("%6d %s" % t)

)
, но я вообще не понял как сортирует?

[longclaps]

artshelom: Добавил комментарии в ответ выше. Про heap читай здесь
Вот вариант с деревом, подлиннее:

from heapq import heappush, heappushpop

with open("test.in", "r") as f:
    l = f.read().splitlines()
n, root = int(l[0]), ([], [None] * 26) # root - кортеж из пустого буфера и
                                       # списка nil-ссылок на дочерние узлы
hpp = (heappush, heappushpop)
for i in range(1, n + 1):
    w, s = l[i].split()
    t = (int(s), w)
    node = root
    for c in w:
        child = node[1][ord(c) - 97]  # ord('a') == 97
        if child is None:
            node[1][ord(c) - 97] = child = ([t], [None] * 26)
        else:
            ww = child[0]
            hpp[len(ww) > 9](ww, t)
        node = child
for w in l[n + 2:]:
    print("     ~ %s" % w)
    node = root
    for c in w:
        child = node[1][ord(c) - 97]
        if child is None:
            break
        node = child
    else:
        for t in sorted(child[0], reverse=True):
            print("%6d %s" % t)

[longclaps]

artshelom:
В самом первом ответе я ошибся по невнимательности: расписал, как выводить наиболее часто встречающиеся буквы, продолжающие префикс. Этот код выводит самые популярные слова.

[Odissey Nemo]

Реализация алгоритма двоичным поиском. Тестовую выборку с утра запросил, но пока не получил.
На небольшой тестовой подборке работает, оценить скорость без реальной выборки нельзя.
Извиняюсь за смесь русских и английских комментариев. В какой-то момент забылся и переключился.

package test;
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Date;

/**
 * Created by nemo_odissey on 10.07.2017 12:45 for <a href="https://toster.ru/q/440261?utm_source=email_notifications&utm_medium=email&utm_content=mention&utm_campaign=notifications#comment_1428657" >Какую сортировку применять?</a>.
 */
public class JapanEditor
{
    /**
     * Compare by frequence and if equal, compare lexicographically
     */
    public static class ComparePrefixWithFreq implements Comparator
    {
        @Override
        public int compare( Object obj1, Object obj2 )
        {
            int cmp = ((WordItem) obj2).count - ((WordItem) obj1).count; // compare in reverse frequencies
            if ( cmp != 0 ) // texts are not equals
                return cmp;
            return((WordItem)obj1).word.compareTo( ((WordItem)obj2).word ); // if freqs are equal, compare lexicographically
        }
    }

    /**
     * Class to store vocabulary item and make it comparable only  lexicographically
     */
    public static class WordItem implements Comparable
    {
        public String word;
        public int count;

        public WordItem( String word, int count )
        {
            this.count = count;
            this.word = word;
        }

        @Override
        public int compareTo( Object obj )
        {
            return this.word.compareTo( ((WordItem)obj).word );
        }
    }

    /**
     * Обработки ошибок НЕТ
     * @param args путь_к_файлу_с_данными, где хранится задание
     * @throws IOException
     */
    public static void main( String[] args ) throws IOException
    {
        long start = new Date().getTime();
        BufferedReader brd  = new BufferedReader( new FileReader(args[0]), 32 * 1024 );
        // читаем число слов
        int wordCnt = Integer.parseInt( brd.readLine() );
        WordItem[] wordArr = new WordItem[wordCnt];
        // Читаем все слова и их частоты
        for(int i = 0; i < wordCnt; i++)
        {
            String[] elems = brd.readLine().split( " " );
            wordArr[ i ] = new WordItem( elems[0], Integer.parseInt( elems[1] )  );
        }
        // сортируем массив словаря
        Arrays.sort( wordArr );

        // сортировщик по частоте
        ComparePrefixWithFreq compareWithFrequence = new ComparePrefixWithFreq();

        // считываем и обрабатываем каждый префикс один за другим
        int prefCnt = Integer.parseInt( brd.readLine() );
        System.out.printf( "Счётчик слов %d, счётчик префиксов %d\n", wordCnt, prefCnt );
        System.out.printf( "Словарь считан и отсортирован за %,d млс.\n\n", new Date().getTime() - start );
        int summaryWordCount = 0;
        WordItem prefixItem = new WordItem( null, 1 );
        for(int i = 0; i < prefCnt; i++)
        {
            String prefix = brd.readLine().trim();
            prefixItem.word = prefix;
            int pos = Arrays.binarySearch(wordArr, prefixItem ); // if positive, point to a word in vocabulary started from prefix or equal to it
            if ( pos < 0) // no precise prefix value found in vocabulary
                pos = -(pos + 1); // pos to the first element starting from prefix
            if ( pos >= wordCnt) // префикс отсутствует в словаре
                continue;

            if ( wordArr[pos].word.startsWith( prefix )) // Если префикс есть, ищем его конец в словаре
            {
                char nextLastChar = prefix.charAt( prefix.length() - 1 );
                prefixItem.word = prefix.substring( 0, prefix.length() -1 ) + (++nextLastChar); // готовим следующую не строку
                int pos1 = Arrays.binarySearch( wordArr, pos, wordCnt, prefixItem );  // ищем последнее вхождение префикса в словаре
                if ( pos1 < 0)
                    pos1 = -pos1;
                if ( pos1 > wordCnt)
                    pos1 = wordCnt;
                summaryWordCount += pos1 - pos;
                // pos -> first word with prefix, pos1 -> first word without prefix
                WordItem[] wordsWithPrefix = Arrays.copyOfRange( wordArr, pos, pos1 );
                Arrays.sort( wordsWithPrefix, compareWithFrequence );
                int wordWithPrefCnt = Math.min( wordsWithPrefix.length, 10 );
                for( int j = 0; j < wordWithPrefCnt; j++ )
                    //System.out.printf("%s %d\n", item.word, item.count); // debug output
                    System.out.println( wordsWithPrefix[j].word );
                System.out.println(""); // add empty line according to the task requirements
            }
        }
        brd.close();
        System.out.printf( ">>> Длительность обработки %,d млс., средний размер выборки по каждому префиксу %d\n", new Date().getTime() - start, summaryWordCount / prefCnt);
    }
}

[artshelom]

odissey_nemo: Выборка у меня на githube файл test.in https://github.com/artem54325/Test3/blob/master/De...
На мой работает не верно. При первом запуске выдаёт другие результаты.
Ошибку пишет в: if ( wordArr[pos].word.startsWith( prefix ))
java.lang.ArrayIndexOutOfBoundsException: 100000

Не правильно сортируете. Надо ещё учитывать "мощность" слова
Arrays.sort( wordArr, new ComparePrefixWithFreq() );

[artshelom]

odissey_nemo: Извините. Вариант не плохой, но не подходит к решению данной задачи т.к.
Если сортируешь по алфавиту, то взяв первые десят они не будут самые топовые. Если сортируешь по "мощности"(которое я написал чуть выше), то они не факт, что будут начинаться с нужного префикса
Я не понял к чему этот код:

int pos = Arrays.binarySearch(wordArr, prefixItem ); // if positive, point to a word in vocabulary started from prefix or equal to it
            if ( pos < 0) // no precise prefix value found in vocabulary
            {
                pos = -(pos + 1); // pos to the first element starting from prefix
            }

Почитав, он ищет такой-же объект и возвращает нам первое совпадение. А зачем нам такой-же объект, если нам надо, объект с которого начинается первое слово.

Извините если я сказал что-то не так. После запуска удивился, что он работает за секунду. Разобрался, что он делает и понял в чем не так.

[Odissey Nemo]

artshelom: binarySearch возвращает либо чётко самый ПЕРВЫЙ индекс со словом, совпадающим с префиксом, либо, если нет такого, то отрицательное значение самого раннего индекса, куда надо вставить наше искомое значение минус единица. Т.е. если возращено -1, то вставлять можно было бы в самое начало списка (индекс 0), -2 в индекс 1 и т.д., по возрастанию. На деле это значит, что binarySearch возвращает всегда точную позицию самого ранней позиции префикса в лексикографически отсортированном массиве (-1). Или укажет за границу массива (-array.length() -1).

Итак, самая первая позиция префикса найдена точно! Или префикса вообще нет! Если он есть, берём до 10 первых лексикографических, начинающихся с искомого префикса. Т.к. сортировать можно либо лексикографически, либо по мощности (частоте). Для поиска по префиксу подходит только лексикографическая сортировка, естественно.

Если в ответе требуется выводить ответ сортированный по мощности (этого в условии не уловил, похоже), т.е. частоте, то будем (всё равно) сортировать основной массив лексикографически, затем забирать все слова в массиве с префиксами, затем их сортировать и выдавать до 10 первых. Это и будет правильный ответ. Полагаю, на времени результата это не скажется никак.

Из интереса возьму Вашу тестовую выборку и завтра проверю. Спасибо за тренировку :o)

P.S. Ошибки возможны, тестировал на выборке в 10 слов и 5 префиксов. Это к слову о пользе тестирования.
P.P.S. Ошибка понятно, не учёл, если префикс лексикографически выше последнего слова в словаре. Это надо обрабатывать, как пустой результат, т.е. пропускать и переходить дальше, да!

[artshelom]

odissey_nemo: если интересно, можете посмотреть моё решение.
Оно мне кажется легче в понимание

[Odissey Nemo]

artshelom: Посмотрел. Понравилось. Сделано классически, без оптимизации. Вполне возможно, более универсальное.

Исправил свой код. На моём Lenovo ThinkPad T4400 работает 22-24 секунды с выводом или без вывода, разница полсекунды. Быстрее с этим подходом уже не сделаешь. Надо думать дальше, в сторону укладки данных в другом виде, сразу готовом к выдаче. Или многопоточность. Интересно сравнить массив и дерево на этом тесте.

На другом компьютере вполне может срабатывать за 5-10 секунд.
Кстати, средний размер набора слов, содержащего префикс, 3750 слов. Что не тривиально, наверное. Т.е. тест - вырожденный. И набор букв какой-то... японский, 3 буквы)))

[longclaps]

odissey_nemo: Эй, критик строгий, сюда посмотри.

[artshelom]

longclaps: Ахахах. ща посмотрю

[artshelom]

longclaps: Классное решение. Достаточно, просто в понимании.

[Odissey Nemo]

longclaps: artshelom:

Посмотрел и я, критик строгий, на творение творца названием из этого списка антонимов. Мне лично импонирует 7-й номер.

Скажу сразу - мне лично творение понравилось. Кратко, мощно, грамотно. Быстрее моего "древнего" подхода практически на порядок (хэш - 4-5 секунд. двоичный -22 секунд). Не уверен, что код создан без Инет-поиска, но сути это не меняет.

Есть небольшое примечание к коду longclaps: всё таки при отборе префиксов по эталону идёт не вставка, а сортировка вставкой, но т.н. частичная. Есть и микро замечание: при одинаковой мощности найденных префиксов они не сортируются лексикографически, как записано в условиях задачи. Поправить очень легко, при желании.

И, наконец, о главном. Хеш-словарь работает в разы, а то и на порядок быстрее двоичного поиска. И это понятно. Ведь скорость доступа к данным в Хэш-таблице - константа, а при двоичном поиске - двоичный логарифм.

На этой бравурной ноте можно было бы и закончить послание, но что-то меня заело. Неужели, думаю, старые проверенные методы обязаны просто вот так вот уступить новому, неисследованному? И решил посмотреть вглубь, без кислорода.

И обнаружил интересные вещи! Оказывается, число элементов в рабочей хэш-таблице оказалось ... ровно 150 000!!! Т.е. равно всему числу тестовых слов! Что невероятно, если тестовая последовательность слов создавалась без вытаскивания синтетических "слов" из той же хэш-таблицы. Ведь в хэш-таблицу попадали все (ВСЕ) префиксы, созданные из элемента словаря. Казалось бы, в общем случае, число хэш-ключей должно равняться числу исходных слов умноженных на среднюю длину слова. Но нет! Число уникальных ключей равно числу слов! А все слова состоят из 3 символов (a, b и c) в разных комбинациях. Синтетика!

Решил, для начала, попробовать выборку, приближенную к реальности. Взял словарь Лебедева к браузеру Opera, что был под рукой (см. в архиве по ссылке). В нём было 142 000 русских слов, что близко к величине тестового словаря (150 000). Префиксы и их длины сгенерировал случайным отбором, общим числом, заданным в тесте (15 000).

Провёл эксперимент. Результаты были ожидаемы, хотя и не кардинальны: двоичный поиск сработал чуть быстрее, а хэш медленнее, 5-6 секунд вместо 3-4. И, что логично, хэш-таблица резко выросла в размерах, стала около 500 000 вместо 150 000 ранее. И создавалась она теперь раза в два дольше, чем осуществлялась сортировка массива.

На этом уже можно было бы ставить точку. С резюме: хэш-таблица по любому сработала много быстрее двоичного поиска. Но ведь заело!

Стал разбираться в алгоритме longclaps. Удивило использование простой частичной сортировки вставкой. Решил опробовать. Это же сортировка, а сортировкам и противопоставлялся поиск по хэш-таблице. Это же наше, сортировщиков, всё!

Ранее (см. переписку ) думал и утверждал, что тип сортировки при поиске всех соответствующих префиксу слов не должен бы влиять на общую длительность алгоритма. Реализовал в своём алгоритме чудо от longclaps, и - новое чудо! Алгоритм заработал за время сопоставимое с хэш-поиском!!! Т.е. те же секунды!

Итак, теперь двоичный поиск работает не медленнее хэш-таблицы. Но резко меньше (в разы, если не больше) потребляет памяти. Ведь используется только один, простейший, массив объектов. Т.е. дело было не в бобине, а неправильном решении по использованию стандартной сортировки, вместо частичной с одним проходом по словам, включающим префикс.

Можно оптимизировать память и дальше. Скажем, использовать общий массив символов, куда считать весь файл, а слова и префиксы хранить в Java 8 Segment (avax.swing.text.Segment), легко переносимый в более ранние версии. Тогда не будет отдельных строк вообще ни в словах, ни в префиксах. Можно отказаться от объектов вообще, сортировать только индексы. Но это уже сильно затуманит код.

Посему большое спасибо и автору вопроса за тему и longclaps'у за ясность мыслей. Но от двоичной сортировки отказываться ещё рановато)))

Исправленный Java код комментарием ниже. И в нём есть одна логическая неувязочка, которую уже лень устранять.

[Odissey Nemo]

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.nio.charset.Charset;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * Created by nemo_odissey on 10.07.2017 12:45 for
 * <a href="https://toster.ru/q/440261?utm_source=email_notifications&utm_medium=email&utm_content=mention&utm_campaign=notifications#comment_1428657" >Какую сортировку применять?</a>.
 */
public class JapanEditor
{
    /**
     * Class to store vocabulary item and make it comparable only  lexicographically
     */
    public static class WordItem implements Comparable
    {
        public String word;
        public int count;

        public WordItem( String word, int count )
        {
            this.count = count;
            this.word = word.split( "/",0 )[0];
        }

        @Override
        public int compareTo( Object obj )
        {
            return this.word.compareTo( ((WordItem)obj).word );
        }

        public int compareByFrequency( Object obj )
        {
            return this.count - ((WordItem)obj).count;
        }
    }

    /**
     * Сортирует и извлекает из массива source начиная с индекса pos1 и до индекса pos2 (не включая его самого) максимальные элементы,
     * по размеру массива result или меньше.
     * @param maxLen максимальный размер массива с максимальными элементами
     * @param dstList {@link ArrayList} для размещения результатов работы. Если {@code null}, то  будет создан внутри. Очищается перед работой и заполняется результатами
     * @param source исходный массив
     * @param pos1 начальный индекс массива source
     * @param pos2 конечный инидекс в массиве source (не включается в сортировку)
     * @return {@link ArrayList} (не может быть {@code null})
     */
    public static final ArrayList<WordItem> partialSort( int maxLen, ArrayList<WordItem> dstList, WordItem[] source, int pos1, int pos2 )
    {
        if ( dstList == null )
            dstList = new ArrayList<WordItem>( 10 );
        else
            dstList.clear();
        dstList.add( source[ pos1++ ] );
        // Проверим все слова с префиксом на предмет их частоты и отберём до 10 самых часто встречающихся
        for( int i = pos1; i< pos2; i++ )
        {
            WordItem item = source[ i ];
            int placeFound = 0;
            int listPos;
            int cmp;
            // Найдём, надо ли вставлять и куда вставить
            for ( listPos = dstList.size() - 1; listPos >= 0; listPos-- )
            {
                if ( ( cmp = item.compareByFrequency( dstList.get( listPos ) ) ) < 0 ) // нашли элемент из списка проверенных, который больше проверяемого
                    break; // дальше не идём, может сможем добавить в конец списка, если там ещё есть место
                if (cmp == 0) // по частоте он равен
                    if ( item.compareTo( dstList.get( listPos ) ) > 0 ) // но элемент из списка проверенных оказался меньше лексически
                        break;
            }
            // пытаемся вставить в массив либо на место элемента, который меньше, либо в конец списка, если там ещё есть место
            if ( listPos == (dstList.size()-1) ) // младший элемент списка больше проверяемого элемента, попробуем просто сдобавить в конец
            {
                if ( dstList.size() < maxLen ) // массив результата ещё не полон, добавляем в конец
                    dstList.add( item );
                continue; // переходим к следующему элементу
            }
            // нашли, куда вставить
            if ( dstList.size() == maxLen )
            {
                // массив результата уже полностью заполнен, сразу удаляем нижний,
                // т.к. он выйдет за разрешённые пределы при вставке нового элемента
                dstList.remove( maxLen - 1 );
            }
            // вставляем ниже большего элемента, или, если listPos == -1, вместо самого большого
            dstList.add( listPos + 1, item );
        }
        return dstList;
    }

    /**
     * Обработки ошибок НЕТ
     * @param args путь_к_файлу_с_данными, где хранится задание
     * @throws IOException
     */
    public static void main( String[] args ) throws IOException
    {
        long start = System.nanoTime();
        BufferedReader brd  = java.nio.file.Files.newBufferedReader( Paths.get( args[ 0 ] ), Charset.forName( "utf-8" ) );
        // читаем число слов
        int wordCnt = Integer.parseInt( brd.readLine() );
        WordItem[] wordArr = new WordItem[wordCnt];
        // Читаем все слова и их частоты
        for(int i = 0; i < wordCnt; i++)
        {
            String word = brd.readLine();
            String[] elems = word.split( " " );
            wordArr[ i ] = new WordItem( elems[0], Integer.parseInt( elems[1] )  );
//            wordArr[ i ] = new WordItem( word.toLowerCase(), freq );
        }

        // сортируем массив словаря
        Arrays.sort( wordArr );

        // считываем и обрабатываем каждый префикс один за другим
        int prefCnt = Integer.parseInt( brd.readLine() );
        System.out.printf( "Счётчик слов %d, счётчик префиксов %d\n", wordCnt, prefCnt );
        System.out.printf( "Словарь считан и отсортирован за %,f млс.\n\n",  1e-9 * (System.nanoTime() - start) );
        int summaryWordCount = 0;
        WordItem prefixItem = new WordItem( "", 1 );
        ArrayList<WordItem> list = new ArrayList<>( 11 );
        for(int i = 0; i < prefCnt; i++)
        {
            String prefix = brd.readLine().trim();
            prefixItem.word = prefix;
            int pos1 = Arrays.binarySearch( wordArr, prefixItem ); // if positive, point to a word in vocabulary started from prefix or equal to it
            if ( pos1 < 0) // no precise prefix value found in vocabulary
                pos1 = -(pos1 + 1); // pos1 to the first element starting from prefix
            if ( pos1 >= wordCnt) // префикс отсутствует в словаре
                continue;

            System.out.printf( "     ~ %s\n", prefix );

            if ( wordArr[pos1].word.startsWith( prefix ) ) // Если префикс есть, ищем последнюю его позицию в словаре
            {
                char nextLastChar = prefix.charAt( prefix.length() - 1 );
                prefixItem.word = prefix.substring( 0, prefix.length() -1 ) + (++nextLastChar); // готовим следующую не строку
                int pos2 = Arrays.binarySearch( wordArr, pos1, wordCnt, prefixItem );  // ищем последнее вхождение префикса в словаре
                if ( pos2 < 0)
                    pos2 = -pos2 -1;
                if ( pos2 > wordCnt)
                    pos2 = wordCnt;
                summaryWordCount += pos2 - pos1;
                list = partialSort( 10, list, wordArr, pos1, pos2 );
                for( WordItem item: list )
                    System.out.printf( "%6d %s\n", item.count, item.word );
            }
        }
        brd.close();
        System.out.printf( ">>> Длительность обработки %,f сек., средний размер выборки по каждому префиксу %d\n",  1e-9 * (System.nanoTime() - start), summaryWordCount / prefCnt);
    }
}

[artshelom]

odissey_nemo: А моё решение так себе?
Я понял решение longclaps. Оно просто и гениально. Он чуть дальше зашел чем я. Я только первые буквы брал, а он отдельно делал для каждого сочетания букв.
Я думал так же делать, но когда я запихивал всё в arrayList и сортировал. То выходило очень долго. Может быть не правильно что-то писал.

[Odissey Nemo]

artshelom: Абсолютно нормальное решение. Отвечающее задаче. Что и требовалось. Честно говоря, на скорость его не тестировал. Если интересно, протестирую. Но думаю, это лучше сделает автор, как лицо заинтересованное.

Некоторая дискуссия тут возникла лишь по поводу нового и старого подходов. Двоичный поиск использовался в древние времена (я оттуда), когда в обиход ещё не вошли хэш-таблицы и прочие прелести современных стандартных библиотек.

Фишка же современных (ПМСМ) собеседований в том, что сегодня на них ищут людей, знающих конкретные технологии, а не тех, которые способны реально мыслить в новых, неизвестных условиях. Что-то типа роботов, настроенных на конкретные операции. Не делаешь эту, новейшую операцию? Ты плохой робот, нам тебя не надо. От тебя нет немедленной отдачи, что есть наша основная цель.

В целом это объективно оправдано в условиях перехода на индус-кодирование. Люди теперь - винтики, которых легко вывинтить и выбросить. И ими в таких условиях много легче командовать и эксплуатировать. И они не скрипят при быстром ввинчивании-вывинчивании :o). Всё - ПМСМ. Успехов!

[longclaps]

odissey_nemo:
Не уверен, что код создан без Инет-поиска, но сути это не меняет
Зависть - плохой советчик, а мелочность - дурная черта.

[Odissey Nemo]

longclaps: Обострённая чувствительность - преходяща. Но только со временем. Ну какая зависть, уважаемый longclaps? Я подсознательно восхищён тем, как Вы быстро решили стандартными средствами не тривиальную (по кр. мере для меня) задачу. Если всё было сделано Вами вручную, с нуля - готов публично признаться в Вашем превосходстве в этой области.

[longclaps]

odissey_nemo: Вы вступили в разговор репликой "зачем кэширование/хэширование? Для демонстрации способностей и теоретических знаний?". Затем я дал пару решений на питоне (я - питонист, что нетрудно видеть по моему профилю) - одно решение на dict (это - питоновский hashmap), другое - с деревом. Пользовался ли я для этого поиском? Знаете, если я хочу посоревноваться, я иду на codeforces, и там никому в голову не прийдёт этот странный вопрос. Пользовался, не пользовался - неважно, решил быстро и правильно - молодец.
Поскольку питон топикстартеру непонятен, я просто попробовал сделать то же на java. Вот тут я ручками написал сортировку вставкой, о которой говорил в самом первом комментарии (на питоне обошелся библиотечными функциями). Разница в быстродействии - и 1.5 раза в пользу java, по длине кода - 2.5 в пользу питона. Для меня тема закрыта.
Но вам хочется продолжить. Ради бога. Я написал, что ваш подход (тогда еще подход, а не код) можно похоронить плохим набором данных. Вы это проигнорировали, зато подыскали такой набор, в котором есть выигрыш по потреблению памяти. Поздравляю, вы решили задачу, которую сами себе придумали, а не ту, что в условии. А теперь попробуйте сделать решение, устойчивое по скорости к плохим данным, и сохранить выигрыш в памяти. Просто чтобы разобраться, "зачем кэширование/хэширование?" )