Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Java Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 37 38 39 40 41 42 [43] 44 45 46   вперед  Ctrl
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 878
Не усложняйте, требуется только поиск.
2 дек 19, 12:28    [22030229]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
iOracleDev
Member

Откуда:
Сообщений: 1029
ivanra
Чем отличаются эти 2 условия?
например, в классификаторе есть фраза:
шла Маша по шоссе

Тогда эти фразы принадлежат классу
шла Маша
шла Маша по шоссе и сосала сушки

а эта нет
шла Маша по дороге


Вот так?


шла Маша по шоссе
шла Маша - слова закончились - бинго
шла Маша по шоссе и сосала сушки
шла Маша по дороге


шла Маша по шоссе
шла Маша
шла Маша по шоссе и сосала сушки
шла Маша по дороге - слова не совпали - строка мимо
2 дек 19, 13:16    [22030279]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 45456
Я думал тут - про стемминг и лематизацию.
2 дек 19, 13:53    [22030318]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 878
ладно, наверно не интересно
String[] classificator = ...;
Arrays.sort(classificator);
...
boolean accept(String words) {
  words += SEPARATOR;
  int i = Arrays.binarySearch(classificator, words);
  if (i>=0) return true;
  int insPoint = -i-1;
  return insPoint>0 && words.startsWith(classificator[insPoint-1]+SEPARATOR)
      || insPoint<classificator.length && classificator[insPoint].startsWith(words);
}
2 дек 19, 14:16    [22030339]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
iOracleDev
Member

Откуда:
Сообщений: 1029
ivanra,

Огромное количество лишних операций. Тебе просто нужно пройти по массиву и проверить вхождение проверяемой строки в строку из массива и наоборот строки из массива в проверяемую строку.
2 дек 19, 15:00    [22030389]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3785
есть одно но, в реальной жизни это всё бесполезная мура.
академические знания это очень хорошо, но то как человек справляется с реальными задачи это определяет.
я бы в ответ спросил, как часто эти товарищи используют LinkedList, про реализм самой задачи я просто помолчу.
2 дек 19, 15:49    [22030439]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 45456
Вот реальная постановка. Заказчик еще 15 лет назад мне голову проел.

Я говорит хочу вводить в форму - "мос гор бол" а ты мне найди все "Московские Городские Больницы № такойто"
Справочник больниц лежит - где угодно. В базе. В массиве. В xml-файлах.
Обеспечте только быстрый поиск. Чтоб операторы калл-центра не нагнул базу или диск или ваше приложение.

Предлагайте любые алгоритмы.

Любый трансформации исходных данных.

Вобщем предложите генерализованный подход для такого поиска.
2 дек 19, 16:04    [22030455]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
iOracleDev
Member

Откуда:
Сообщений: 1029
mayton,

Считаю тут не обойтись без Intel AI Сколько миллиардов заказчик предложил распилить?
2 дек 19, 16:09    [22030463]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 878
iOracleDev
ivanra,
Огромное количество лишних операций. Тебе просто нужно пройти по массиву и проверить вхождение проверяемой строки в строку из массива и наоборот строки из массива в проверяемую строку.

Тут нет ни одной лишней операции. Если кто-то жалуется, что задача оторвана из жизни, могу сказать, что она как раз из жизни, но добавлено немножко абстракций. А случай из жизни такой: мониторинг файловой системы по заранее заданному списку каталогов (и он может быть немаленький), причем нужно отследить не только вложенные пути, но и все родительские вплоть до заданного корня.
2 дек 19, 16:21    [22030473]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
iOracleDev
Member

Откуда:
Сообщений: 1029
ivanra,

Сколько проходов по массиву в твоей реализации?
2 дек 19, 17:31    [22030547]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 45456
iOracleDev
mayton,

Считаю тут не обойтись без Intel AI Сколько миллиардов заказчик предложил распилить?

Какие миллиарды? Телефонная компания на пост-совестком пространстве.
Заказчик - мой личный начальник. Сказал - ато пилюлей нам влепят. Денег не жди.
2 дек 19, 17:38    [22030553]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 878
iOracleDev,
метод accept выполняется за O(log(n))
См.также тему сообщения
2 дек 19, 17:43    [22030563]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
iOracleDev
Member

Откуда:
Сообщений: 1029
ivanra,

А это типа не считается - Arrays.sort(classificator) ?
2 дек 19, 17:52    [22030572]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 878
iOracleDev
ivanra,
А это типа не считается - Arrays.sort(classificator) ?

Да, не считается. Сортируем 1 раз при инициализации, далее быстро отвечаем - подошел-не подошел. Проверяемый классификатор не меняется в процессе работы.
2 дек 19, 18:03    [22030583]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 878
mayton

Я говорит хочу вводить в форму - "мос гор бол" а ты мне найди все "Московские Городские Больницы № такойто"

Тоже делал подобную задачу. Только там было так: пользователи вводят адреса с искажениями (иногда специально, например, заменяя кириллические символы на латинские). Естественно, никакой like тут не поможет - адрес может выглядеть в точности буква в букву, а в базе не искаться.
В общем, дальше гуглим "расстояние Левенштейна" и тому подобное.
Задачу решил с помощью Elastic Search - построение индекса по базе, и дальше нечеткий поиск. Результат с наилучшим скором и есть ответ. При построении индекса и формулировании запроса пришлось поиграться с коэффициентами. Помогла обучающая база (датасет), плюс несложные утилиты, которыми специальные пользователи могут обучать поисковик.
2 дек 19, 18:14    [22030592]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 45456
ivanra
mayton

Я говорит хочу вводить в форму - "мос гор бол" а ты мне найди все "Московские Городские Больницы № такойто"

Тоже делал подобную задачу. Только там было так: пользователи вводят адреса с искажениями (иногда специально, например, заменяя кириллические символы на латинские). Естественно, никакой like тут не поможет - адрес может выглядеть в точности буква в букву, а в базе не искаться.
В общем, дальше гуглим "расстояние Левенштейна" и тому подобное.
Задачу решил с помощью Elastic Search - построение индекса по базе, и дальше нечеткий поиск. Результат с наилучшим скором и есть ответ. При построении индекса и формулировании запроса пришлось поиграться с коэффициентами. Помогла обучающая база (датасет), плюс несложные утилиты, которыми специальные пользователи могут обучать поисковик.

В том далёком 2003-м году у меня был Oracle8, Sybase Power builder.
И про технологии текстового поиска я не знал ничего.
Эластика - не существовало. А java-шный двигатель apache-lucene
только-только зарождался.

Да вобщем. Эластик - это коробочное решение для любого поиска. Но в духе
нашего форума задачек для собеса я-бы хотел увидеть принцип или алгоритмизацию.
2 дек 19, 18:18    [22030600]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
ivanra
Member

Откуда:
Сообщений: 878
mayton,
мой первый опыт индексирования был в 6-м экселе акцессе. Там правда не было нечеткого поиска, но по началу слов искало

Сообщение было отредактировано: 2 дек 19, 18:25
2 дек 19, 18:24    [22030604]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 45456
Брут-форс решения нам не будут интересны.

Представь себе что у тебя база данных на диске. CSV-файл.
И справочник учреждений занял весь диск. И любая
поисковая операция будет блокировать весь диск
(даже для самых быстрых SSD-шников сегодня) это
будет минута.

Нужна индексная структура отдельно которая будет заточена
на такие префиксные поиски.
2 дек 19, 18:27    [22030607]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
apb12
Member [заблокирован]

Откуда:
Сообщений: 490
все это здорово) но чо то энтерпрайз программирование вообще даже близко явой не пахнет.
я неделю в крупном проекте ни строчки кода не написал и если раньше идея была моим домом,то теперь терминал линукса
посему без разницы чо там за разница в листах,оно врядли кому пригодится )
2 дек 19, 18:42    [22030624]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 45456
apb12
все это здорово) но чо то энтерпрайз программирование вообще даже близко явой не пахнет.
я неделю в крупном проекте ни строчки кода не написал и если раньше идея была моим домом,то теперь терминал линукса
посему без разницы чо там за разница в листах,оно врядли кому пригодится )

Тебя просто взяли не разработчиком а девопсом. Эти ребята много сидят в консолях.

Так бывает иногда.
2 дек 19, 18:44    [22030625]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
apb12
Member [заблокирован]

Откуда:
Сообщений: 490
mayton
apb12
все это здорово) но чо то энтерпрайз программирование вообще даже близко явой не пахнет.
я неделю в крупном проекте ни строчки кода не написал и если раньше идея была моим домом,то теперь терминал линукса
посему без разницы чо там за разница в листах,оно врядли кому пригодится )

Тебя просто взяли не разработчиком а девопсом. Эти ребята много сидят в консолях.

Так бывает иногда.

да нет именно разраб я,у нас отдельно есть псы и тестеры)
и у нашей бэк команды уже есть дейли ,именно моя задача написать интеграциионый тест на то ,что напишут мои тимейты

почему я в консоли сижу- сейчас не могу писать ибо жёпа горит и забанят)))
2 дек 19, 19:10    [22030661]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 45456
Лицензию на IDE не купили?
2 дек 19, 19:16    [22030666]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
apb12
Member [заблокирован]

Откуда:
Сообщений: 490
mayton
Лицензию на IDE не купили?

а оно надо?
2 дек 19, 19:28    [22030679]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
mayton
Member

Откуда: loopback
Сообщений: 45456
Просто. Хайпануть. Мы кстати сидим на CommunityEdition.
2 дек 19, 19:30    [22030683]     Ответить | Цитировать Сообщить модератору
 Re: Задачка для собеседования : ArrayList vs LinkedList  [new]
apb12
Member [заблокирован]

Откуда:
Сообщений: 490
mayton
Просто. Хайпануть. Мы кстати сидим на CommunityEdition.

на нем все русские конторы сидят и наверняка вся индия и китай
2 дек 19, 20:11    [22030719]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 37 38 39 40 41 42 [43] 44 45 46   вперед  Ctrl
Все форумы / Java Ответить