Отсортировать дерево?

[Boriskin]

Строить надо trie, кое обычно как раз для такой херни (а также родов автодополнений самых популярных терминов типа как в гугле) и используется.

[Pantigalt]

Немного оффтопика.
Посмотрел я про префиксное дерево - одна из областей где активно применяется - антивирусы.
Теперь понятно кому понадобилось такое ТЗ делать в Москве =).

[OtherSide]

я честно говоря и не знал, как это назвается, решение по моему, очевидное. Компания не Касперский

[Boriskin]

я честно говоря и не знал, как это назвается, решение по моему, очевидное.

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

[Pantigalt]

я честно говоря и не знал, как это назвается, решение по моему, очевидное. Компания не Касперский

Вы про дерево или про кэширование?

Построение структуры хранящей слова можно было сделать и без дерева. Оно не сильно принципиально тут.
В вашем случае ключевым было именно кэширование результатов.

[АццкоМото]

убей меня, не пойму, зачем кэшировать результаты если есть trie

[Pantigalt]

убей меня, не пойму, зачем кэшировать результаты если есть trie

Ну в этом trie список слов только в листьях содержится.
Если префикс короткий будет, например из одной буквы то придется собирать список слов из поддеревьев вместо того чтобы сразу извлечь список из кэша.
Мы при добавлении слова в префиксное дерево, добавляем слово и во все узлы ведущие к корню (в отдельный список слов).
Таким образом каждый узел хранит в себе кроме буквы также и список всех слов с текущим префиксом.

[АццкоМото]

убей меня, не пойму, зачем кэшировать результаты если есть trie

Ну в этом trie список слов только в листьях содержится.
Если префикс короткий будет, например из одной буквы то придется собирать список слов из поддеревьев вместо того чтобы сразу извлечь список из кэша.

Мне лень перечитывать задание, но по памяти - словарь до миллиона слов, а подсказки нужны после "нескольких" букв. Даже если взять префикс из одного символа, что-то около 100 тыщ должно быть максимум в ветке. траверс 100 тыс - это быстро.

Но КМК оптимум - сначала сделать depth first проход по всему дереву и для каждого нода хранить ссылки на 10 наиболее популярных слов. Т.е. _сначала_ проход по всему мульону, а потом все делается за константу. Траверс мульона за секунду - это 2800 тактов на нод у упомянутого 2.8 ГГц процессора. А у него еще и несколько ядер ИМХО если не у доски, то вполне можно. Хотя надо пробовать и смотреть - а лень

UPD. Дерево все равно создавать надо. Вот прямо во время создания и сделать эти ссылки, даже единственного прохода по готовому дереву не потребуется

[Pantigalt]

По хорошему поиск окончаний для одного слово надо сделать почти за константное время (не зависящее от длины словаря).

[АццкоМото]

По хорошему поиск окончаний для одного слово надо сделать почти за константное время (не зависящее от длины словаря).

это фантастика

[katit]

А за LINQ в 2 строчки двойку поставят?

[Pantigalt]

По хорошему поиск окончаний для одного слово надо сделать почти за константное время (не зависящее от длины словаря).

это фантастика

Ну почему сразу фантастика.
Я думаю можно построить префиксное дерево так чтобы значения сортировались в нужном порядке при построении.
При поиске время будет затрачено только чтоб спуститься по префиксу в нужное место и извлечь первые 10 элементов из отсортированного списка.

[Pantigalt]

По хорошему поиск окончаний для одного слово надо сделать почти за константное время (не зависящее от длины словаря).

это фантастика

Я просмотрел вики и нашел описание Trie

Looking up data in a trie is faster in the worst case, O(m) time (where m is the length of a search string), compared to an imperfect hash table. An imperfect hash table can have key collisions. A key collision is the hash function mapping of different keys to the same position in a hash table. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.

[АццкоМото]

По хорошему поиск окончаний для одного слово надо сделать почти за константное время (не зависящее от длины словаря).

это фантастика

Я просмотрел вики и нашел описание Trie

Looking up data in a trie is faster in the worst case, O(m) time (where m is the length of a search string), compared to an imperfect hash table. An imperfect hash table can have key collisions. A key collision is the hash function mapping of different keys to the same position in a hash table. The worst-case lookup speed in an imperfect hash table is O(N) time, but far more typically is O(1), with O(m) time spent evaluating the hash.

Блин, ну да. Май бэд

[OtherSide]

Написали, что не прошел. Дескать префиксное дерево с кешированием - "решение в лоб"

[Pantigalt]

Написали, что не прошел. Дескать префиксное дерево с кешированием - "решение в лоб"

Формально вы удовлетворили их требования но они не нашли более лучшей формулировки для отказа.

[valchkou]

могу предположить, что они хотели аналогию шардинга/map reduce:
разбить лист на маленькие деревья, затем параллельно запустить несколько потоков/workers.

[Boriskin]

Написали, что не прошел. Дескать префиксное дерево с кешированием - "решение в лоб"

Спроси "а как не в лоб", мало ли, может они что принципиально новое придумали.

[OtherSide]

Да никто отвечать не будет. Вон и так две недели смотрели, ответили лишь когда дергать начал:

1. Решение в лоб
2. Код в кашу

Где там, мля каша, я выше постил

[Pantigalt]

Да никто отвечать не будет. Вон и так две недели смотрели, ответили лишь когда дергать начал:

1. Решение в лоб
2. Код в кашу

Где там, мля каша, я выше постил

Это люкс так пишет?

[OtherSide]

Некий "СПБ КОНТУР" ) В люксе был пару раз на собеседованиях, всегда по разному проходят

[Boriskin]

Да никто отвечать не будет. Вон и так две недели смотрели, ответили лишь когда дергать начал:

1. Решение в лоб
2. Код в кашу

Где там, мля каша, я выше постил

Понятно, отмазка, да и та гнилая. Даже отказать культурно - и то не могут.

[tengiz]

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

Хотя такую задачу давать в такой ситуации - даже Амазон такого не делает. Задачи попроще алгоритмически на самом деле даются для домашних заданий, обычно хочется посмотреть насколько "зрелый" код человек пишет, а не что он там может придумать или нагуглить за неделю.

[Berlaga]

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

Хотя такую задачу давать в такой ситуации - даже Амазон такого не делает. Задачи попроще алгоритмически на самом деле даются для домашних заданий, обычно хочется посмотреть насколько "зрелый" код человек пишет, а не что он там может придумать или нагуглить за неделю.

Я там выше даввл решение, размер структуры в районе 10М, поиск константный.

И таки Амазон мне давал довольно таки закавыристые задачки в свое время, на очном интервью. Самое обидное, что завалился совсем не на них.

[tengiz]

И таки Амазон мне давал довольно таки закавыристые задачки в свое время, на очном интервью. Самое обидное, что завалился совсем не на них.

Очное другое дело, там можно много чего заполучить. А для домашнего задания - довольно гнусные (нудные, скучные и много-вариантные) для кодирования, но простые алгоритмически проблемы.