[алгоритмы]Задача построения транслитерационной схемы
прикольно. контора — гугл? =)
я бы начал с изначального полного отображения
слово -> слово
...
а дальше итеративно ищем наиболее часто встречаемые общие префиксы и их выделяем в отдельное правило мапинга.
типа есть дофига правил ax_i -> by_j то делаем a -> b а от тех откусываем.
можно ли это сделать быстро - хз, но если привлечь знания о структуре языка то точно можно.
я бы начал с изначального полного отображения
слово -> слово
...
а дальше итеративно ищем наиболее часто встречаемые общие префиксы и их выделяем в отдельное правило мапинга.
типа есть дофига правил ax_i -> by_j то делаем a -> b а от тех откусываем.
можно ли это сделать быстро - хз, но если привлечь знания о структуре языка то точно можно.
Отправил резюме в одну контору.
Эта та самая вакансия "Java-алгоритмист" или нет?
А сколько предлагают-то? Если меньше 1500-2000, то пусть идут лесом с такими задачками. А то, может быть, что им просто решение надо нахаляву, а не работника.
лоханулся я 
дааа, трэш на первой странице.
я бы не пошёл в контору в которой нет специалиста который может нормально настроить апач чтоб он выдавал правильную кодировку.
дааа, трэш на первой странице.
я бы не пошёл в контору в которой нет специалиста который может нормально настроить апач чтоб он выдавал правильную кодировку.
А сколько предлагают-то? Если меньше 1500-2000, то пусть идут лесом с такими задачками. А то, может быть, что им просто решение надо нахаляву, а не работника.+1, о том же подумал
да, та самая.
Они и расположены далеко и платят не особо много,зато есть надежда,что работа не очень скучная
Они и расположены далеко и платят не особо много,зато есть надежда,что работа не очень скучная
наверное, соответствующий специалист на этапе тестового задания отсеялся
Если эта та вакансия, что я думаю, то вроде 2-2.5 обещают.
я не думаю,что это кидалово
MMM toge ne kidalovo ...
я тоже сомневаюсь, что кидалово, но просто первая мысль именно такая возникает почему-то.
а что там с кодировкой-то не так? 
У меня тоже круто определилась, опера у него, наверное.
угадал, опера =)
то что осёл и мозилла угадывают кодировку ещё не повод чтоб косо настраивать апач, к тому-же древнющий, и кажется дырявый.
то что осёл и мозилла угадывают кодировку ещё не повод чтоб косо настраивать апач, к тому-же древнющий, и кажется дырявый.
у мну фф в линухе тоже не угадывает
я подозреваю, что и осел может не догадывается, просто там на первой страничке одни картинки, и чтоб увидеть траблу с кодировкой надо в линк какой нить ткнуть
я подозреваю, что и осел может не догадывается, просто там на первой страничке одни картинки, и чтоб увидеть траблу с кодировкой надо в линк какой нить ткнуть
угадал, опера =)У тебя не правильная опера.
правильнее некуда:
Version: 9.10
Build: 521
Version: 9.10
Build: 521
правильнее некуда:Есть, куда. У меня все нормально.
В жопу такие конторы. Я ходил в Дойче Банк, так там только элементарные алгоритмы и вопросы по С++ и прочей херне задавали. Я вообще заметил, что чем более сложное собеседование, тем меньше зарплата.
Фигасе задачка.
Во-первых, постановка действительно мутная.
При этом в постановке в неявном и замутнённом виде уже содержится некий алгоритм.
По идее, с таким нужно посылать нафиг: либо нужно формулировать общую задачу и давать _рекомендации_ по её решению, либо давать нормальный алгоритм, над которым не нужно думать.
Хотя мб ты просто опустил разные пояснения.
Насколько я могу понять, они предлагают делать что-то вроде сильно обрезанной цепи Маркова, причём с неспецифицированной длиной. I mean, вот есть, допустим, пара "schtchi" -> щи. Твоя программа выделяет дофига вариантов разбиения, но в результате оказывается, что наиболее вероятный - когда "i" проецируется в "и". Но при этом в каком-то виде запоминается, что буквосочетание "щи" нужно транслировать именно вот так, а слово "ща" можно транслировать и как "sha". Так?
В таком случае, наверное, имеет смысл ограничить количество букв в соответствии каким-нибудь разумным числом (семь как в данном примере) и пытаться строить всевозможные схемы, отсеивая те, в которых получается слишком много соответствий. Но я сильно не уверен, что сработает детерминистический алгоритм (на заданных ограничениях возможно правильней будет что-нить вроде генетического алгоритма замутить и прогнать несколько раз по случайно перемешанным входным данным.
Но я вчитывался не особо внимательно, они как-то вроде попытались описать промежуточные шаги, может всё проще.
Во-первых, постановка действительно мутная.
Транслитерационной схемой называется множество отображений (не обязательно однозначных) некоторого упорядоченного множества английских букв в соответствующие им русские буквы согласно следующим правилам:я так понял, всё-таки не букв, а буквосочетаний. И к отображению прилагаются частоты.
При этом в постановке в неявном и замутнённом виде уже содержится некий алгоритм.
По идее, с таким нужно посылать нафиг: либо нужно формулировать общую задачу и давать _рекомендации_ по её решению, либо давать нормальный алгоритм, над которым не нужно думать.
Хотя мб ты просто опустил разные пояснения.
Насколько я могу понять, они предлагают делать что-то вроде сильно обрезанной цепи Маркова, причём с неспецифицированной длиной. I mean, вот есть, допустим, пара "schtchi" -> щи. Твоя программа выделяет дофига вариантов разбиения, но в результате оказывается, что наиболее вероятный - когда "i" проецируется в "и". Но при этом в каком-то виде запоминается, что буквосочетание "щи" нужно транслировать именно вот так, а слово "ща" можно транслировать и как "sha". Так?
В таком случае, наверное, имеет смысл ограничить количество букв в соответствии каким-нибудь разумным числом (семь как в данном примере) и пытаться строить всевозможные схемы, отсеивая те, в которых получается слишком много соответствий. Но я сильно не уверен, что сработает детерминистический алгоритм (на заданных ограничениях возможно правильней будет что-нить вроде генетического алгоритма замутить и прогнать несколько раз по случайно перемешанным входным данным.
Но я вчитывался не особо внимательно, они как-то вроде попытались описать промежуточные шаги, может всё проще.
то что осёл и мозилла угадывают кодировку ещё не повод чтоб косо настраивать апач, к тому-же древнющий, и кажется дырявый.смирк
короче, хз, где твоя опера там кои8 увидела. у меня cp1251 в обоих рассмотренных выше случаях. 
а что, в DB платят больше 3 тысяч? моя знакомая после стажировки аналитиком (в смысле, аналитиком в программинге. На UML. Предварительно доказав владение C++ и Java) на 800 устроилась
девушки в программировании это вообще отдельная тема. Но: Есть компании которые нехорошо относятстя к сотрудникам,а есть люди,которые боятся назвать большое число для своего же блага
Не знаю, сколько там платят, но контора, по любому, достаточно солидная.
Я лично зарекся делать какие-либо задания, особенно столь маштабные. Потратишь свое время, а тебя еще и на собеседование не пригласят, потому что твой код не понравится какому-нибудь Васе, который привык ставить скобки иначе.
Я лично зарекся делать какие-либо задания, особенно столь маштабные. Потратишь свое время, а тебя еще и на собеседование не пригласят, потому что твой код не понравится какому-нибудь Васе, который привык ставить скобки иначе.
Оставить комментарий
koly
Отправил резюме в одну контору. В ответ прислали задачи для тестирования соискателя.Постановка задач очень мутная, парился целый день, чтобы четко понять условие и придумать какой нибудь вменяемый алгоритм - ничего хорошего в голову не пришло.
Может, у кого-нибудь будут идеи по поводу задач?
---------------
Есть файл (knownmapping в котором записаны русские названия и соответствующие им транслитерированные (записанные с помощью английских букв) названия. Файл имеет следующий формат: русское название<табуляция>английское название<перевод строки>. Например (невидимые символы заменены управляющими эквивалентами: \t для табуляции и \n для перевода строки):
москва\tmoscow\n
москва\tmosqua\n
москва\tmoskva\n
ноcова\tnocowa\n
синицын\tsinitsin\n
синицын\tseeneecyn\n
Количество записей достаточно велико. Русские названия могут дублироваться, английские не могут дублироваться.
Требуется решить две задачи.
Задача 1 (Mapping). Требуется написать программу, которая на основании исходного файла сформирует все варианты использованных транслитерационных схем. Транслитерационной схемой называется множество отображений (не обязательно однозначных) некоторого упорядоченного множества английских букв в соответствующие им русские буквы согласно следующим правилам:
1. Если одна буква (или сочетание букв) имеет несколько вариантов обратной транслитерации, то в качестве основного варианта выбирается тот, который чаще встречается. Другие варианты сохраняются, но добавляются новые — созданные на основе этих и удлинненные за счет контекста до тех пор, пока не станут однозначными. Например, буква "c" имеет в слове "seeneecyn" вариант "ц", а в слове "moscow" — "к" (при том, что в целом "cow" отображается на "ква" а в "nocowa" — "с" . Если второй вариант менее частый, то вместо отображения "c->к" должен быть вариант "cow->ква", а вместо "c->с" — "sowa->сова".
2. Если более длинный вариант может быть собран из более коротких, которые не имеют "конкурентов" по количеству, то длинный вариант не нужен. Например, не нужен вариант "sk->ск", если и у "s" и у "k" и так наибольшее количество по преобразованию в соответственно "с" и "к".
Результат записывается в файл (scheme) в формате английский вариант<табуляция>русский вариант<табуляция>количество<перевод строки> Количество --- это сколько раз данная замена встречается в исходном файле (knownmapping).
Файл должен быть отсортирован по убыванию длины английского варианта, далее по убыванию количества, далее по возрастанию в алфавитном порядке.
Главный класс должен называться ru.hflabs.testalgo.retranslit.MappingMaker и принимать следующие аргументы командной строки:
knownmapping_filename, scheme_filename
Задача 2 (Retranslit). На входе:
1. полученная в результате решения Задачи 1 схема обратной транслитерации (scheme).
2. файл, состоящий из записанных по одному в каждой строке транслитерированных (английских) названий (src).
3. файл, состоящий из записанных по одному в каждой строке русских названий (суть есть справочник) (dictionary).
Требуется написать программу, которая выполнит обратную транслитерацию каждого названия из транслитерированного файла по следующиму правилу:
1. Пробуем подобрать такую схему, чтобы результат обратной транслитерации оказался в справочнике (dictionary).
2. Если не получается, то транслитерируем наиболее вероятным способом. При прочих равных выбирается более длинное подмножество из схемы, при одинаковой длине --- с большим количеством.
Результат записывается в файл (output) в формате русское название<табуляция>английское название<табуляция>+, если попали в справочник, -, если не попали<перевод строки>
Главный класс должен называться ru.hflabs.testalgo.retranslit.Retranslit и принимать следующие аргументы командной строки:
scheme_filename src_filename dictionary_filename output_filename
Общие требования:
1. Код должен быть откомментирован
2. Код должен быть покрыт jUnit-тестами
3. Если принять размеры всех файлов (кроме scheme) равных 10000 записей, то Задача 1 должна выполняться не более, чем за 10 минут, а Задача 2 не более чем за 5 минут (P-IV, 3GHz и обе задачи не должны требовать более 64М оперативной памяти.
4. Если в каких-то местах получится достичь существенной оптимизации, необходимо кратко описать суть решения и желательно оценить выигрыш по сравнению с прямым перебором.