Вариант эффективного интервью

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

    А ты записался добровольцем?
    А ты записался добровольцем прошел собеседование?

    Интервью состоит из трех частей, занимает 30-60 минут.
    1. Рассказ программиста о себе.
    2. Короткие вопросы на кругозор.
    3. Решение задач

    Рассказ программиста о себе.


    В первую очередь прошу человек рассказать, как пришел к web-программированию. Когда начал, когда подсел на программирование :)
    Очень спрашиваю про последнее место-два работы, что человек делал, за что отвечал, что в техническом и организационном плане там делал.

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

    Как только становится понятно, что движет человеком и какой у него опыт, переходим к технической части.

    Короткие вопросы на кругозор.


    Web-программирование — это зоопарк технологий, вспоминается анекдот про требования к водителям, если бы они были такие же мощные, как и программисты :)

    За 10-15 минут нужно понять, а как глубоко человек владеет той или иной технологией, понять уровень его понимания.
    Опрашиваю по следующим сферам: СУБД, SQL, алгоритмы, структуры данных, языки, командная строка, ООП, *nix.

    Опыт и понимание делю на три уровня — elementary, OK, advanced :)

    Прежде всего, базы данных. Есть среди вопросов первого типа есть «чем right join отличается от JOIN?», а третьего — «что такое B+-tree и почему они так часто применяются в реализации индексов?».

    Очень интересно про ООП. Если вопрос «что такое инкапсуляция, полиморфизм, наследование» это второй уровень, то объяснить, что это такое на деле, зачем нужно, какие метрики архитектуры ухудшает/улучшает рефакторинг с упором на SOLID + DRY + IoC, могут единицы (или не путают рефакторинг с оптимизацией производительности).

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

    Конечно, я спрошу про Линукс и обрадуюсь, если человек сидит хотя бы под Ubuntu. Спрошу на деле, как вывести список файлов с «test» в имени с grep (ls | grep «test»), или что такое ls | xargs svn up.

    «Но и это еще не все» (С) TV-SHOP 90х

    Решение задач


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

    И даю задачи. Я согласен со статьей, которую тут переводили как-то, что настоящий программист определяется умением применять рекурсию и указатели.

    Во многом, это сродни эволюции человека. Говорят, что нас отличает от обезьян умение оперировать в уме сразу 7+-2 элементами, и понимание рекурсии (нужно для заточки зубил, узор, рекурсивно уменьшаясь, позволяет сделать лезвие очень острым и хорошо режущим).

    Так и умение в уме представлять, что такое арифметика указателей, и понять работу рекурсии выделяет программистов среди простых людей.

    Как правило, даю простую задачу и прошу писать код прямо онлайн, безо всяких проверок. В последнее время даю 10-15 минут без меня, если человек переволновался.

    И за одну-две задачи становится понятно, каков итог собеседования.

    Вопросы про люки — нафиг. Да здравствует рекурсия!

    upd. задача с устного собеседования и допзадача на дом.
    Задача 1
    Дан массив неограниченной вложенности, нужно написать функцию, которая выведет его в виде вложенного списка с отступами, пропорциональными глубине, и текущем путем к элементу.

    Вызов showMenu(menu);
    должен выдавать HTML-код, как по адресу
    image

    Массив:
    menu = [
        'simple item',
        [
        	'title' => 'Complex item',
    	'items' => [
    	     'simple item2',
    	     'simple item3',
    	     [
    	            'title' => 'Another complex item',
      	            'items' => [ '...' ]
    	      ]
    	]
        ]
    ];
    


    Задача 2
    Сделать, чтобы для строки
    "{Пожалуйста|Просто} сделайте так, чтобы это {удивительное|крутое|простое} тестовое предложение {изменялось {быстро|мгновенно} случайным образом|менялось каждый раз}." выдавались все возможные варианты (вложенность не ограничена)

    например
    для str="{A | B | C} тест"
    три варианта
    «А тест»
    «Б тест»
    «С тест»

    для str = "{A | B} {A | B}" четыре варианта
    «A A»
    «B B»
    «A B»
    «B A»
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 49

      0
      Спасибо, читать статью легко и просто, но могли бы написать пример который вы даете?
        +4
        Ну да, читать такие длинные и информативные статьи к кучей примеров всегда легко и просто!
          +1
          Эх, была, не была :)
          Все равно хотел менять задачи. Из теста они уже есть в инете, а устной еще не было.

          Итак.
          Дан массив неограниченной вложенности, нужно написать функцию, которая выведет его в виде вложенного списка с отступами, пропорциональными глубине, и текущем путем к элементу.

          Вызов showMenu(menu);
          должен выдавать HTML-код, как по адресу


          Массив:
          menu = [
              'simple item',
              [
              	'title' => 'Complex item',
          	'items' => [
          	     'simple item2',
          	     'simple item3',
          	     [
          	            'title' => 'Another complex item',
            	            'items' => [ '...' ]
          	      ]
          	]
              ]
          ];
          
          
            +6
            После всех вопросов про «инкапсуляция, полиморфизм, наследование, B+-tree с упором на SOLID + DRY + IoC» — вы даете такие тестовые задачки? )
            Зачем же так мучить соискателя )
              +3
              ну да, в этой задаче сплошной SOLID. хочу заметить что D(ependency injection) в SOLID это и есть IoC. и какой смысл доказывать кандидату что перед ним не девочка HR? опытного человека можно отпугнуть навсегда такими вопросами. не лучше ли о чем-то более серьезном и соответственно интересном пообщаться?
                0
                DI это разновидность IoC, если быть строгим, как я это понимаю. IoC еще можно делать через контейнеры и другими хитрыми способами, всякие Service LocatorЫ и тд.

                Спрашиваю потому, что знающий и __понимающий__ эти принципы, считай, владеет и принципами-паттернами, и ему не нужно втолковывать кучу вещей.

                А доказывать никому не нужно, просто нужно настроить человека на технический лад :)
                0
                Нет, вопросы про B+tree стоят вот так.

                1. Сначала, что такое индекс в БД, зачем нужен, как устроен.
                (одно предложение)
                2. А знаете ли что такое B+tree.
                (если ДА, то что, одним предложением. дополнительные пару вопросов, если чел врет, что знает)
                (если нет, идем дальше).

                и все :)

                А задача потому, что человек разогрет, мозг работает в техническом контексте, а не отвечания на вопросы про люки и «как вы видите себя через 3 года» (=повторение заученных ответов).

                Рекурсия заставляет в голове представить обход одного уровня этого массива, а затем правильный уход в рекурсию.
                Впрочем, есть и методы решения через жопу, но мы ведь не о них :)
            +9
            >полчаса поговорить с кандидатом, чтобы он понял, что перед ним не HR-девочка
            … а тимлид-девочка? :)
              0
              Почему бы и нет :)
              0
              Я сначала спрашиваю о себе, потом даю FizzBuzz, и если он решает, то перехожу к теории и далее.
              Пару раз пробовал идти далее, когда не решают FizzBuzz, но эта стратегия провальная.
                0
                Иногда важно посмотреть за ходом мыслей человека.
                Как он решает незнакомую задачу.
                А не простая оценка «решил» или «не решил».
                  0
                  Конечно же слежу за ходом мысли. Прощаю описки, иногда прощаю что не знает оператор целочисленного деления. Но если он откровенно тупит, или, и такое тоже было, говорит, что хочет унести с собой задачу, решить дома и прийти обратно, то дальше проводить собеседование бесполезно.
                –3
                Все-таки «люки» нужны.
                На них можно посмотреть насколько нестандартно человек мыслит.
                Но нужна своя задачка, чтобы человек заранее не знал ответ.
                  +7
                  Это все очень интересно, но многие веб-программисты в состоянии решать поставленные перед ними задачи без знания указателей и тонкостей реализации индексов в базах данных. Безусловно, те, которые знают про все, что вы у них спрашиваете, абстрактно лучше как программисты, но ведь и дороже в итоге как правило. А если стоит задача скажем вьюшки в джанге собирать до посинения, или там в каком php-фреймворке ковыряться, то зачем платить больше?
                    +15
                    А как часто вы собеседуете людей, превосходящих вас по уровню? Или вакансии такого в принципе не подразумевают?
                      +2
                      +1, тоже интересен ответ на этот вопрос.
                        +1
                        Раз в несколько месяцев.

                        Вы поймите, я менеджер проектов. Я не занимаюсь 100% времени программированием уже 3 года, и мой уровень, конечно, уступает даже хорошим программистам.

                        Пишу иногда какие-то куски вовсе неидеальным образом.
                        Разве что опен-сорс пилю втайне :)
                      +14
                      Прошерстив сотни резюме, проведя десятки собеседований, хочу поделиться

                      Написав сотни топиков на Хабре хочу поделиться советом, не используйте radikal для картинок. Он «не справляется» с Хабром
                        +3
                        да, я не написал ни одной рекурсии в громадном проекте :) зато без указателей не обошлось. видимо я не прошел бы собеседование :)
                        мой критерий гораздо проще. вот задача, вот нотбук — реши ее. и потом объясни решение. Если чел написал вложенный цикл а на вопрос зачем сказал — мне надо быстро а 99% смартфонов в этом месте не загнутся — это факт принять его на работу.
                          –4
                          Shrek is Love, Shrek is life.
                            +14
                            Вот я читаю подобные статьи и думаю. Может я еще зеленый (да, да, я такой, студент еще), но ведь главное умение программиста — вникать в задачу/технологию и генерировать идею ее разрешения/быстро осваивать.
                            Почему на собеседованиях никогда не проверяют эти качества, а проверяют то, что уже точно умеет человек? То есть конечно ясно, что есть какая-то база, которую нужно знать, но вот я на пример не знаю нормально регулярки, просто в силу того, что не часто с ними сталкивался, зато точно знаю как решить задачку с рекурсией. Хотя должен заметить когда-то плохо знал как с рекурсией обращаться, а в дальнейшем даже понравилось.
                            История из жизни
                            Проходил собеседование на практику в небольшой фирме занимающейся разработкой сайтов. За час до собеседования понял что ничего не знаю про джойны. Ну вообще ничего, просто никогда не требовались.(нет, циклами в запросах я не обходился, просто не требовалось) И как назло интернет в метро плохо ловил, ничего прочитать так и не смог. Приехал, перенервничал, наделал глупых ошибок, вроде вместо strlen использовал count. Пообещали созвониться до конца недели.
                            Выйдя — понял что все скорее всего провалил. Около входа в метро стоит ростикс — зашел, сел, разобрался с джойнами быстро и отослал тестовые задания, в решенном виде. Уж не знаю повлияло ли это на решение — мне на следующий день предложили работу. По своим причинам в итоге отказался.
                            Сейчас с джойнами разобрался, но эта история, как мне кажется показывает одно из решающих и важных умений программиста — как обучаемость.
                              +1
                              Поддерживаю это мнение. Все знать не возможно, да и не нужно — для этого есть документации, интернет,… А вот умение быстро обучаться и находить решения задач является решающим для отличного веб програмиста. И конечно же, человек должен любить свое дело. А все остальное приложится;)
                                +7
                                Для джуниора обучаемость — основной фактор, это да.
                                Но блин, сейчас любой студент, пять лет бухавший ягу и годик проработавший младшим подаваном в какой-нибудь говноконторке, из которой в итоге был уволен за прогулы и непроходимую тупость, мнит себя как минимум синиором, если не тимлидом, и желает соответствующую личку.
                                А компаниям чаще всего нужны не джуниоры и не синиоры, а просто готовые программисты. Которые не просто могут за один день разобраться с джойнами, а которые собаку на этих джойнах съели и соотвественно могут написать этот джойн за 1 минуту, причем правильно, и пойти решать другие задачи.
                                В конечном счете для компании все упирается в деньги. Успевает нанятый программист за месяц закрыть столько тасков, чтобы компания отбила его зарплату в три раза, или не успевает. (Только не надо думать, что «три конца» это много и компания слишком много кушать, нет. «Один конец» съедают налоги и праздники с отпусками, а второй — содержание организации, включая аренду офиса, зарплаты таких бесполезных, но необходимых нахлебников как бухгалтера, юристы и сейлзы).
                                  +2
                                  Согласен. Но в таких статьях не пишут кого ищут на работу. Какой уровень? Человек может отлично знать SQL, но никогда не иметь дело с ORM. Да, он разберется, но тонкостей не знает, и скорее всего часть возможностей сразу использовать не будет, а пользоваться query-builder'ом.
                                  Опять же, возможно мое наивное мнение, но как мне кажется программисту нужно знать хорошо базу + какие-то специализированные вещи. Кто-то хорошо рефакторит и тесты пишет. А кто-то левой рукой сервер поднимает, а правой базу оптимизирует. Я утрирую, но мысль ясна. Мне казалось идеальная команда состоит из таких программистов, где каждый умеет и могет, но каждый лучший в какой-то своей области.
                                  И тогда так и писать в требованиях — нужен человек отлично знающий следующие технологии. Тогда студенты вроде меня не будут тратить ваше время. Но в требованиях четко пишут — отличное знание *стек технологий*, думаю соискатели, о которых отзываются дурно в таких статьях думают так: «ну что php54, ну трейты — понимаю. SQL… да, джойнить умею, связи строить тоже могу, индексы вроде правильно ставлю, не дурак… JS — да, синтаксис знаю, замыкания прототипы умею, jquery в каждом проекте использую», а когда приходят — закидывают вопросами о которых в требованиях и в помине небыло.
                                  Зачем веб-программисту знать красно-черные деревья и указтели — я не совсем понимаю. Такое зашито глубоко в языки и это уже совсем не веб-программирование.
                                +2
                                А какже пиремущества и недостатки третьей нормальной формы и её отличия от формы Бойса-Кодда?
                                  0
                                  Ну такие вопросы тоже можно задавать, просто если я вижу, что человек не пугается слов O(N) — могу и спросить, почему quicksort это O(NlogN). Но если человек не шарит, а мы беседуем про индексы — спрашиваю на воображение и понимание, что один алгоритм решает задачу для 10 элементов за столько действий, а другой за столько*дохрена, и почему первый лучше.

                                  0
                                  ошибся окном
                                    +3
                                    Я бы внес поправки.

                                    Интервью состоит из трех пяти частей, занимает 30-60 минут.
                                    1. Рассказ программиста о себе.
                                    2. Короткие вопросы на кругозор.
                                    2.1. Рассказ работодателя о себе.
                                    2.2. Ответы работодателя на вопросы соискателя.
                                    3. Решение задач

                                    Вы же не раба выбираете.
                                      +1
                                      Из-за вашей аватарки подумал, что автор сам с собой общается :)
                                        0
                                        Некоторым людям трудно спуститься с трона на один уровень с соискателем.
                                        +3
                                        Вот честно, какую-то фигню устраиваете.
                                        Достаточно выпить с человеком пару чашек кофе за ненапряжной беседой, чтобы понять, подходит он или нет.
                                          +2
                                          [irony] Я вам так про ООП расскажу, сами поверите, что оно лучше всех, даже если привыкли писать в функциональном стиле. [/irony]

                                          Бывают и такие гуру, что говорят, аки твой соловей. А попросишь написать решение простой задачи на ООП (только рассуждавший про Стратегию не знает, зачем она нужна конкретно тут и как ее написать) — молчание в ответ.

                                          Платят за красивые слова писателям, а за красивый РАБОТАЮЩИЙ код — программистам.
                                            +1
                                            Если вы расскажите так, что я вам поверю — значит у вас определённо талант убеждать людей. Хорошего менеджера, как и хорошего программиста, не так-то просто и найти.

                                            По большому счёту, текущие знания (в пределах разумного, разумеется) не так важны, если вы планируете длительное сотрудничество с человеком. Гораздо важнее его социальные навыки, в том числе: обучаемость, мотивация, адекватность, способность к самокритике.
                                            Можно и обезьяну научить программировать, но только что с ней потом делать?!
                                              0
                                              По моему не такому большому опыту, на целый час прикинуться обучаемым и горящим глазами проблем нет, а вот долго маскироваться в работе нет.

                                              Одновременно, чем больше компания, тем более готовых спецов она хочет к себе брать, чтобы они быстрее окупали себя и делали продукты мирового уровня.

                                              Зато закосить под умного на испытательный срок с гуглом можно, а вот перед батареей вопросов устоять нельзя, особенно с задачей. Либо вы супербыстро гуглите и вникаете :)

                                              А обучаемость и все остальное прекрасно видны на первой неделе. Один ставит софт сразу, ковыряет, задает __осмысленные__ вопросы, работает на совесть. Второй ставит три дня, задает кучу глупых вопросов, сам не старается, ждет, что за него сделают все сразу.

                                              Это не выявишь на собеседовании, и не нужно :)
                                                0
                                                Всё верно говорите: нужно брать самых адекватных на испытательный срок, и уже на первой неделе станет понятно, кто и чего стоит.

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

                                                  Мир, увы не идеален :((

                                                  Мы пробовали давать более сильный тест, но люди его не заполняют, влом. Поэтому часть вопросов перекочевала в устное интервью. Оно, кстати, одно, а не три. Вот три интервью — это реально задница ИМХО. Допросы :)
                                                    +4
                                                    Вконтакте стал показателем… эм… чего-то вообще?

                                                    Согласен, мир не идеален и, благодаря задачам на интервью, вы делаете его его менее идеальным, отсеивая и тех, кто не может от волнения собраться с мыслями, и тех, кто не знает решения, но в целом быстро схватывает, и тех, кто готов на вас сутками пахать, лишь бы войти в одну из ваших команд.
                                                    2 интервью, я считаю — идеально. Первая кружка кофе — с HR'ом, который отсеит совсем неадекват, ненавязчиво узнает про основные ценности человека, снимет напряжение, подготовив кандидата ко второму интервью. Вторая кружка — с техническим специалистом, который просто «за технологии» поговорит с кандидатом и которому не составит труда понять, вольётся ли человек в команду. Смотрите, что получилось: мы из допроса с пристрастием сделали милую, светскую беседу, по окончанию которой, ни одной стороне не нужно будет снимать напряжение Корвалолом или крепкими алкогольными напитками.
                                          0
                                          2-ая задача (JavaScript)
                                          // Приветствуются конструктивные замечания по коду
                                          
                                          function problem2(input) {
                                          	var openIndex = input.indexOf('{');
                                          
                                          	if (openIndex === -1) return [input];
                                          
                                          	var result = [''];
                                          
                                          	while (openIndex !== -1) {
                                          		var firstPart = input.substring(0, openIndex);
                                          		var parts = [];
                                          
                                          		var openCount = 0;
                                          
                                          		for (var i = openIndex + 1, length = input.length; i < length; ++i) {
                                          			if (input[i] === '{')
                                          				++openCount;
                                          			else if (input[i] === '}') {
                                          				--openCount;
                                          
                                          				if (openCount < 0) {
                                          					parts.push(input.substring(openIndex + 1, i));
                                          
                                          					input = input.slice(i + 1);
                                          					break;
                                          				}
                                          			}
                                          			else if (openCount === 0 && input[i] === '|') {
                                          				parts.push(input.substring(openIndex + 1, i));
                                          
                                          				openIndex = i;
                                          			}
                                          		}
                                          
                                          
                                          		var newResult = [];
                                          
                                          		parts.forEach(function (part) {
                                          			problem2(part).forEach(function (partResult) {
                                          				result.forEach(function (resultItem) {
                                          					newResult.push(resultItem + firstPart + partResult);
                                          				});
                                          			});
                                          		});
                                          
                                          		result = newResult;
                                          
                                          		openIndex = input.indexOf('{');
                                          	}
                                          
                                          	if (input.length > 0) {
                                          		result.forEach(function (element, index, array) {
                                          			array[index] = element + input;
                                          		});
                                          	}
                                          
                                          	return result;
                                          }
                                          


                                          И часто в ваших проектах приходится писать такие алгоритмы?
                                            0
                                            иногда бывает и сложнее :)

                                            вообще, лексический анализатор — весчь :)
                                              0
                                              работу ищете?
                                                0
                                                На неделе задумался об этом.
                                                0
                                                Не претендуя на скорость и оптимальность, на скорую руку набросал свой вариант:
                                                2 задача
                                                var parseExpression = function(str) {
                                                	var openBracket, closeBracket, variants, head, tail;
                                                	var result = [];
                                                	closeBracket = str.indexOf('}');
                                                	if (closeBracket === -1)
                                                		return str;
                                                	openBracket = str.substr(0, closeBracket).lastIndexOf('{');
                                                	if (openBracket === -1)
                                                		return str;
                                                	variants = str.substr(openBracket+1, closeBracket - openBracket - 1).split('|');
                                                	head = str.substr(0, openBracket)
                                                	tail = str.substr(closeBracket + 1);
                                                	for(var i=0; i < variants.length; i++) {
                                                		result.push(parseExpression(head + variants[i] + tail));
                                                	}
                                                	return [].concat.apply([], result).filter(function(elem, pos, self){return self.indexOf(elem) == pos});
                                                }
                                                

                                                  0
                                                  Красивое решение. Мне так сделать и в голову не пришло.

                                                  Ради интереса сравнил производительность: jsfiddle.net/EzwkA/
                                                0
                                                Вопросы — сборная солянка для поиска многорукого шивы: он у нас и кодит отлично и дизайн и юних заадминит и NF6, а в перерывах деревья напишет. Да не простые а, наверное какие-то именно веб-tree.

                                                Когда я вижу такие интервью мне становится понятно, что у интервьюера или какие то комплексы или он просто не понимает кто ему нужен.
                                                  0
                                                  Если вы, как один мой знакомый, который сказал — я хочу писать только на JS и больше ни на чем, то вы сильно отстали от мира. Web-программирование это зоопарк технологий. Без понимания, что такое индексы в СУБД, вы не сможете оптимизировать большую часть проектов под highload. Не зная HTML/CSS вообще, вы не то что не сможете сделать супер frontend MVC интерфейс — банальную верстку, где статусы элементов определяются классами, не сможете оживить.

                                                  Без понимания рекурсии и указателей — ну, вон, выше прекрасно написали в тему.

                                                  Поэтому нужны профи. Многоруких шива как раз НИКТО обычно не проверяет — берут подешевке, и дают все, что попало, заставляя разбираться поверхностно.

                                                  А деревья с наскоку не понять, как это не удалось вам в этом комменте (гуглить binary tree, если интересно)
                                                    0
                                                    Ну не знаю-не знаю) Я на 1 курсе учусь, второкурснику писал лабу, по бинарным деревьям. У его одногруппников поспрашивал — какую-то ахинею несли, вроде «нужны просто чтобы показать что такие есть», когда разобрался и поиск и сортировку и все что нужно было написал, заинтересовали другие разновидности, но пока нет времени разобраться. А бинарные деревья можно сказать с наскоку понял, у меня не графов, ни матана ничего нормального небыло еще.
                                                  –1
                                                  ls | grep "test"
                                                  Што-о-о?! То есть `ls *test*` не подходит в качестве правильного ответа?
                                                    0
                                                    Хорошо, если человек это скажет, я тогда доспрошу, как это сделать с grep. Или что-нибудь с xargs — find. | xargs rm (удаление дохренища файлов в папке, когда rm дохнет, чит-хак-неправильно-но-работает)

                                                    Чтобы понять, как человек понимает строку — просто одну команду, или знаменитую философию unix тоже читал и даже тыкал (не только патч Бармина, ха ха).
                                                    0
                                                    Посмотрел я на приведенный JS код, на то как все в одну кучу смешано, как ошибки во входной строке не обрабатываются, как выражения не оптимизируются. И, в основном с целью с parser combinators поиграться, переписал на Scala. Мухи получились отдельно, котлеты отдельно, потом еще оптимизацию прикрутил.

                                                    2-ая задача (Scala)
                                                    import scala.util.parsing.combinator._
                                                    import scala.util.parsing.input.CharSequenceReader
                                                    
                                                    sealed abstract trait Expr {
                                                      def allStrings: List[String]
                                                      def isLiteral = false
                                                      def isEmpty = false
                                                    }
                                                    case class Literal(s: String) extends Expr {
                                                      override def allStrings: List[String] = List(s)
                                                      override def isLiteral = true
                                                    }
                                                    case object Empty extends Expr {
                                                      override def allStrings: List[String] = Nil
                                                      override def isEmpty = true
                                                    }
                                                    case class Multi(es: List[Expr]) extends Expr {
                                                      override def allStrings: List[String] = es.flatMap(_.allStrings)
                                                    }
                                                    case class Concat(es: List[Expr]) extends Expr {
                                                      override def allStrings: List[String] = allStrings(List(""), es)
                                                    
                                                      private def allStrings(prefixes: List[String], es: List[Expr]): List[String] = es match {
                                                        case Nil => prefixes
                                                        case h :: t => allStrings(for (p <- prefixes; s <- h.allStrings) yield p + s, t)
                                                      }
                                                    }
                                                    
                                                    trait ExprParsers extends RegexParsers {
                                                      override val skipWhitespace = false
                                                    
                                                      def literal: Parser[Literal] = """[^{|}]+""".r ^^ { Literal(_) }
                                                      def multi: Parser[Multi] = "{" ~> repsep(cexpr, "|") <~ "}" ^^ { l => Multi(l.distinct) }
                                                      def concat: Parser[Concat] = (mexpr +) ^^ { Concat(_) }
                                                      def cexpr: Parser[Expr] = concat
                                                      def mexpr: Parser[Expr] = literal | multi
                                                    }
                                                    
                                                    trait ExprOptParsers extends ExprParsers {
                                                      override def cexpr: Parser[Expr] = super.cexpr ^^ { _ match {
                                                        case Concat(List(x)) => x
                                                        case Concat(l) if l.forall(_.isLiteral) => Literal(l.map(_ match {case Literal(t) => t}).mkString)
                                                        case Concat(l) if l.exists(_.isEmpty) => Empty
                                                        case x => x
                                                      }}
                                                      override def mexpr: Parser[Expr] = super.mexpr ^^ { _ match {
                                                        case Multi(Nil) => Empty
                                                        case Multi(List(x)) => x
                                                        case Multi(l) if l.exists(_.isEmpty) => Empty
                                                        case x => x
                                                      }}
                                                    }
                                                    
                                                    object Parser extends ExprOptParsers {
                                                      private lazy val main: Parser[Expr] = phrase(cexpr)
                                                      private def parse(s: String): Expr = main(new CharSequenceReader(s)) match {
                                                        case Success(e, _) => e
                                                        case NoSuccess(m, n) => throw new IllegalArgumentException("Parsing error at " + n.pos + "\n" +
                                                            n.pos.longString + ": " + m)
                                                      }
                                                    
                                                      def printAll(s: String): Unit = {
                                                        val p = parse(s)
                                                        println(p.allStrings.mkString("\n"))
                                                        println(p)
                                                      }
                                                    
                                                      def shouldFail(s: String): Unit = {
                                                        try {
                                                          val p = parse(s)
                                                        } catch {
                                                          case e: IllegalArgumentException => println(e.getMessage)
                                                        }
                                                      }
                                                    
                                                      def main(args: Array[String]): Unit = {
                                                        shouldFail("{")
                                                        shouldFail("}")
                                                        shouldFail("")
                                                        printAll("тест")
                                                        printAll("тест {тест}")
                                                        printAll("{тест} {тест}")
                                                        printAll("{тест {тест}}")
                                                        printAll("{}")
                                                        printAll("{{{{{{{{{{тест {тест}}}}}}}}}}}")
                                                        printAll("{A | B | C} тест")
                                                        printAll("{A | B} {A | B}")
                                                        printAll("{A |A | B} {A | B| B}")
                                                        printAll("{Пожалуйста|Просто} сделайте так, чтобы это {удивительное|крутое|простое} тестовое предложение {изменялось {быстро|мгновенно} случайным образом|менялось каждый раз}.")
                                                        printAll("{Пожалуйста|Просто} сделайте так, чтобы это {удивительное|крутое|простое} тестовое предложение {изменялось {быстро{}|мгновенно} случайным образом|менялось каждый раз}.")
                                                      }
                                                    }
                                                    

                                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                    Самое читаемое