Об одной задаче, которую больше не предлагают на собеседовании

    В одной компании кандидатам на вакансию программиста какое-то время предлагалась следующая задача. Найти значение дроби:

    $\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{1+...}}}} $


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

    $x=\frac{1}{1+x}$

    А это, в свою очередь, приводит к обычному квадратному уравнению:

    $x^2+x-1=0\\ x=\frac{sqrt(5)-1}{2}\\ x=0,618033988...$



    Теперь скажем, что данные дроби имеют особое название, это цепные дроби, и они используются, как одна из форм записи вещественных чисел. В рассмотренном примере бесконечная цепная дробь имеет самое простое представление. В ее записи используются только единицы, и длина её периода тоже равна единице. Любопытно, что выражаемое ею число очень широко представлено, и не только в математическом мире, и даже имеет собственное название — обратная величина для «золотого сечения». Получим несколько приближений для данного числа, используя его представление через цепную дробь. На первом шаге отбросим второе слагаемое в знаменателе. Получим $\frac{1}{1}$, теперь запишем следующее приближения, используя полученный результат, как второе слагаемое в сумме под знаком дроби $\frac{1}{1+\frac{1}{1}}=\frac{1}{2}$ Повторим эту операцию ещё раз $\frac{1}{1+\frac{1}{2}}=\frac{2}{3}$ В результате мы получим следующий ряд:

    $\frac{1}{1},\frac{1}{2},\frac{2}{3},\frac{3}{5},\frac{5}{8},\frac{8}{13}...$


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

    $1,1,2,3,5,8,13,21...$

    Составим ряд образованный отношениями двух соседних членов последовательности Фибоначчи

    $\frac{1}{1},\frac{1}{2},\frac{2}{3},\frac{3}{5},\frac{5}{8},\frac{8}{13}...$

    Не правда ли, знакомая запись? Действительно, предел отношения двух чисел Фибоначчи выражается обратной величиной «золотого сечения». Получим этот результат.
    Из определения следует, что

    $F_{i+1}=F_i+F_{i-1}$

    $\frac{F_{i+1}}{F_i}=1+\frac{F_{i-1}}{F_i}$

    Введем следующее обозначение

    $s_{i-j}=\frac{F_i}{F_j}$

    Тогда предыдующее равенство запишется как

    $s_1=1+s_{-1}$

    В пределе

    $s_1=\frac{1}{s_{-1}}$

    Введем обозначение $x=s_{-1}$. Тогда мы получим уравнение, которое уже приводили в начале статьи.

    $x=\frac{1}{1+x}$


    Теперь рассмотрим последовательность, у которой три первых члена равны единицы, а каждый последующий равен сумме трех предыдущих.

    $1,1,1,3,5,9,17,31,57,105,...$

    Найдем предел, к которому стремится отношение двух соседних членов последовательности. По определению

    $F_{i+3}=F_i+F_{i+1}+F_{i+2}$

    Разделим левую и правую часть на $F_{i+1}$. Тогда в используемых ранее обозначениях мы можем записать:

    $s_2=s_{-1}+s_1+1$

    Теперь разделим левую и правую часть на $F_{i+2}$. Получим следующее cоотношение:

    $s_1=s_{-2}+s_{-1}+1$

    Обозначим

    $s_1=x\\ s_2=y$

    В новых обозначениях система уравнений будет выглядеть так:

    $y=\frac{1}{x}+x+1\\x=\frac{1}{x}+\frac{1}{y}+1$

    Данная система приводится к следующему уравнению:

    $y^3-3y^2-y-1=0$

    Оно имеет одно вещественное решение

    $y=3,382976...$

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

    $1,1,1,1,4,7,13,25,49,94,181,349,...$

    то мы придем к системе из трех уравнений:

    $z=x+y+\frac{1}{x}+1\\ y=x+\frac{1}{x}+\frac{1}{y}+1\\ x=\frac{1}{z}+\frac{1}{y}+\frac{1}{x}+1 $

    А эта система приводится к следующему нелинейному уравнению:

    $y^4-3y^3-3y^2+y+1=0$


    Это уравнение имеет два вещественных корня. Решением нашей задачи будет:

    $y=3,715495... $


    Вот такие наблюдения произошли, благодаря одной задаче на собеседовании.
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 61
      0
      Задачка из славного учебника SICP.
        +10
        Это на какую должность такая задача? О_о. Я понял, что ничего не знаю.
          +6
          Нужно только заметить, что предложенное выражение самоподобно

          автору осталось раскрыть — что такое «самоподобное выражение»…
            +2
            Объясните мне как это
            image
            вдруг стало отрицательным? — чтобы значение дроби получилось 3,7
            1/(1-0,72)=3,7
              0
              3.7 — это решение другой задачи.
              +55

              А потом фронтендик говнокодить :)

                0
                Значение первой дроби из собеседования автор так и не назвал…
                0

                Запись
                image
                предполагает, что все соседние подходящие дроби (а следовательно, все они между собой) равны, что очевидно неверно.


                Я уже не говорю о том, что золотое сечение представляется вовсе не уравнением x^2 + x - 1 = 0, а, внезапно, x^2 - x - 1 = 0.

                  0

                  Разумеется, отношения чисел с одинаковой разницей индексов не равны. Равенство возникает при предельном переходе.
                  Замечание по золотому сечению учел, значение.дроби — это обратная к золотому сечению величина.

                  +5
                  В чём практический смысл такой задачи на собеседовании? Если соискатель знает как решать — он решит, если не знает — вряд ли догадается. Олимпиадников набираете? Или на работе они будут математикой заниматься?
                    –1

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

                      +4
                      Тогда при чём тут слово «собеседование» в заголовке статьи? (Да-да, понимаю, это потому что такая задача попалась на собеседовании). Видите ли в чём дело, я против таких задач на собеседовании. Именно потому что на собеседовании не вижу в них особого смысла. А к самой статье никаких претензий, разумеется, нет.
                        +2
                        Да не так чтобы очень. Вспомнить хотя бы известную задачу на собеседовании дизайнера: «Нарисуйте круг в фотошопе не пользуясь мышью».

                        Я теперь тоже могу эту конкретную задачу решить.
                        Но это не делает меня дизайнером.
                        –1
                        Смысл как раз есть, эта задача имеет единственное решение — одно это уже намного лучше абстрактных про люки или шарики. Поскольку интервьюируемый скорее всего не математик, его слегка напугает эта страшная формула (предусловие теста по выведению из зоны комфорта выполнено). С другой стороны, смысл её понятен даже школьнику. Решение так же не требует специальных знаний, нужно только заметить закономерность. В общем, идеальный тест для навыков необходимых программисту.
                          –2

                          Приятно читать такие комментарии.

                            +8
                            Мы в свое время пробовали давать тесты про люки и шарики. Потом давать математические задачки.
                            За более чем 10 лет собеседований, у меня сложилось мнение, что все эти тесты никак не коррелируют с дальнейшей работой сотрудника. Есть люди, которых хлебом не корми дай задачки порешать, но работают увы, плохо. И наоборот.
                            В подавляющем большинстве случаев, если человек пришелся «по душе» во время беседы «ни о чем», то и далее работать с ним комфортно, не зависимо от результата решения головоломок.
                            Пришел к тому, в итоге, что на собеседовании эффективнее обсуждать темы максимально близкие к тем, которыми будет заниматься сотрудник и тестовое задание на знание продукта (в нашем случае Transact SQL), с которым будет работать сотрудник, а не математические задачки и ребусы с шарадами.
                            Если в работе нужна реально математика, тогда имеет смысл спрашивать математическую базу, но таких мест относительно мало, хотя задачки любят спрашивать многие.
                            А уже как работает человек в реальной работе, все равно открывается только во время испытательного срока на реальных задачах.
                              –1

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

                                +7
                                Я и не возражаю, если нужна математика в работе, математику нужно спрашивать.
                                Я про то, что есть много работ, где математика не используется, но ее все равно спрашивают.
                                Как пример:
                                Работал я в банке неск. лет. Там тоже любили спрашивать математические задачки и рассказывать о мега перспективах. И текучка была просто бешенная. Когда мне поручили участвовать в собеседованиях, я говорил кандидатам: работа мега скучная. Ковырять отчетность. Математика выше арифметики не нужна. Продукт устоявшийся, прорывов не намечается. Перестали меня брать на собеседования, ты говорят, нам всех кандидатов распугаешь. Но себе в группу я все же собеседовал и у меня текучка стала близка к 0, просто люди понимали, что их ждет и уже решали, нужно ли им это. Я считаю, что это выгоднее, чем обучать человека системе, а он через 2-3 месяца сваливает.
                                От приведенного примера отказались, задавать некому.

                                Молодцы, в Кайдзен это называется «провести корректирующие мероприятия» :)
                                  0
                                  Если бы так везде рассуждали :) Честный подход — это всегда хорошо.
                              +3
                              эта задача имеет единственное решение

                              Вообще-то нет. Еще как минимум -1,618… =(-sqrt(5)-1)/2, и я подозреваю есть ещё много периодических последовательностей
                              Х[i+1] = 1/(X[i] + 1)
                              X[0] = X[N]
                                0
                                Я про исходную задачу говорил, а не квадратное уравнение. Т.е. решение в данном случае это подмножество решений квадратного уравнения. Поскольку оно является множеством оно однозначно определено.

                                Вообще это неформальное решение, так что отрицательное x можно отбросить из рассмотрения что бы не доказывать что знаменатель на каждом шаге не может быть 0, иначе придётся давать формальные определения сходимости и доказывать каждый шаг, т.е. строить теорию цепных дробей.

                                При чём тут эта последовательность, куда вы её собрались подставлять???
                                +6
                                С другой стороны, смысл её понятен даже школьнику.

                                Смысл великой теоремы Ферма тоже понят школьнику. Но на доказательством бились три века xD

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

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

                                        0
                                        Я вот даже смутно помню как эту формулу использовать. Даже если бы я ее вывел.
                                          0

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

                                            0
                                            Та если бы мне сейчас было необходимо, то я бы нагуглил детали и решил. Я знал, как решаются эти уравнения. Даже участвовал в математических олимпиадах и занимал неплохие места. Но это было уже лет 10-15 назад, и все это очень сильно забылось, потому на собеседовании я бы так и сказал:
                                            — Я не помню, как решать квадратические уравнения, так как 10 не решал, но если для работы будет необходимо, то вспомнить это — полчаса времени.
                                0

                                Собеседование в НИИ ?

                                  +2

                                  У вас очень странное мнение о том, чем занимаются в НИИ.

                                  +14
                                  В ответ на такую задачку я попросил бы её же задать каждому действующему сотруднику в этой компании примерно той же должности. И всех не ответивших уволить как не прошедших «собеседование»
                                    –1

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

                                      +7
                                      уровень соискателей сильно упал

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

                                      Вообще у меня сложилось впечатление, что у подобных задач одна цель — показать соискателям что они дно и прогнуть по з.п.
                                        +1
                                        Против таких, которые хотят «показать соискателям что они дно и прогнуть по з.п.» есть один довольно известный и очень действенный способ. Надо в ответ на глубокие вопросы задавать в ответ точно такие же глубокие вопросы собеседующему. Суть вот в чём. Не все кандидаты понимают смысл «СО-беседования». То есть, не только они отбирают кандидатов, но и вы отбираете интересную компанию и команду.
                                        И когда слышите в свой адрес издевательские вопросы, то можете смело задавать точно такие же вопросы. На удивлённые взгляды отвечайте: «А что? Я хочу работать в команде профессионалов, которые знают как применять volatile и чем семафор отличается от мьютекса, а шаблон стратегии от фабрики. Что, не знаете? Жаль. Видно, нам с вами не по пути»
                                          0
                                          И в лице собеседующих коллег эти «умники» будут поставлены в неловкое положение
                                      +1
                                      Должность — программист математик?
                                        0

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

                                        0
                                        Обычный матан. Сходящиеся и расходящиеся ряды. Единственное, что многие после универа это подзабывают, а так никакой сверх математикой тут и не пахнет. Если курил матан в свое время, то все вполне легко решаемо, даже если и подзабыл.
                                          0
                                          > Вот такое исследование получилось

                                          Исследование про три частных случая?
                                            0

                                            Ну нет. Из статьи понятно как получить систему уравнений для поиска предельных отношений в рассмотренных рядах. А вот для решения таких систем при количестве исходных уравнений больше трех, скорее всего, уже нужно ПО для символьной математики. С карандашом и ручкой я справиться не могу. Да и смысла большого в этом не вижу.

                                              0
                                              Вот если бы вы исследовали эти системы/уравнения, нашли подходы к их решению, ну и вообще что-то общее про «расширенные Фиббоначи» — было бы хорошее исследование. А пока что это выглядит как преамбула к исследованию.
                                                0

                                                Соглашусь с Вашим мнением, это не исследование, а наблюдение. Исправил текст.

                                            0
                                            Прикола ради такую задачку написал своим коллегам на доске. Сказал, что это задачка на собеседование. Почесали голову, доску исписали. Ну, вообщем коллективно всё свелось к «развёртыванию» дроби и выводе квадратного уравнения с нахождением корня. Кто-то подтянул матлаб и циклом определил схождение ряда. Было весело )))

                                            Я просто к тому, что будучи вчерашними студентами любой из нас наверняка бы её и решил или хотя бы попытался. А 10-15-летние разработчики — уже не факт, что даже пробовать станут, хотя интерес и проявят. А в целом даже грустно — время идёт и уже многое напрочь забывается, когда годами пилишь какие-нибудь высокоскоростные интерфейсы (хотя надо заметить что я не «чистый» программист, а хардварный инженер-программист).
                                              0

                                              С обращением непрерывной дроби в простую через подходящие дроби можно ознакомиться здесь (§2).


                                              Вообще кажется, что такую задачу решит:


                                              • тот, кто знает, как решать (помнит рекуррентные правила Эйлера, к которому здесь имеет отношение и ряд Фибоначчи) или что эта задача имеет отношение к золотому сечению;
                                              • тот, кто сам сможет повторить все математические выкладки (да, а на работе будет заниматься максимум арифметикой).
                                                0

                                                А вот любопытно, если попросить на собеседовании написать программу для расчета данной дроби с требуемой точностью, это вызовет затруднение? Это сложная задача для программистов ?

                                                  0

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

                                              +15
                                              Автору спасибо за интерес к математике. Надеюсь, он не исчезнет после небольшого холодного душа.

                                              Во первых, существование предела нужно доказывать. Если кто-то думает, что можно обойтись, пусть поинтересуется парадоксом Перрона.
                                              Во вторых, даже постановка «найдите отношение соседних членов» может оказать некорректной. Поясню.
                                              Возьмём соотношение f(n+1) = 2f(n) — 2f(n-1), f(1) = 1, f(2) = 1.
                                              Не поленитесь посчитать пару десятков следующих членов. Сюрприз — будут нули, причём их бесконечно много.
                                              Можете взять другие начальные условия. Например, f(1) = 1, f(2) = 3. Сюрприз номер два — отношение будет принимать значения 3, 4/3, 1/2, -2 и дальше по кругу. Предела опять нет.
                                              А у последовательности f(n+1) = 2f(n) — 3f(n-1) отношение будет прыгать без никакого намёка на предел.

                                              Логичный вопрос — а что же тогда делать? Ответ — то, что вы можете обосновать. Допустим (допустим, а не постулирем!), у отношения f(n+1)/f(n) существует существует предел x. Тогда у f(n+2)/f(n) = (f(n+2)/f(n+1))/(f(n+1)/f(n)) тоже есть предел и он равен x^2. Аналогично для f(n+3)/f(n) стремится к x^3.
                                              Для примера возьмём последнее уравнение. Поделив обе части на f(i), получим, что предел должен быть корнем уравнения x^4 — x^3 — x^2 — x — 1 = 0. Или предела нет, ещё ничего не доказано. Это и есть граница того, что можно доказать совсем на пальцах.

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

                                              Мораль 1. Баги бывают не только в наших программах, но и в рассуждениях.
                                              Мораль 2. Если решаете математическую задачу, отвлекитесь от программистского подхода «сейчас машина всё нам посчитает».
                                                0

                                                Прекрасный комментарий. Я занимаюсь скорее арифметикой, чем математикой. Как правило, свои размышления произвожу по дороге на работу, в электричке. Доказать наличие предела я не могу. В таких вопросах поступаю как физик, делаю предположение, потом ставлю эксперимент. Тоже самое и с этими пределами. Посмотрел в Excel и сравнил корнем полученного выражения. А за общий подход к таким задачам большое спасибо. Я его не увидел. Теперь этот пробел исправлен.

                                                  +4
                                                  Здесь вспоминается анекдот:
                                                  Как доказать что все нечётные числа простые?

                                                  Математик: 3-простое, 5-простое, 7-простое, дальше по индукции…
                                                  Физик: 3-простое, 5-простое, 7-простое, 9-ошибка эксперимента, 11-простое,…
                                                  Инженер: 3-простое, 5-простое, 7-простое, 9-простое,...
                                                  Надеюсь, что никого не обидел.
                                                    0
                                                    Ещё несколько соображений.
                                                    Существование предела можно доказать, если работает один из таких подходов.
                                                    1. Последовательность x(n) будет, например, монотонно возрастать и при этом все x(n) не превышают x (единственно возможный кандидат в пределы).
                                                    2. Монотонности может и не быть, x(n) «прыгает» вокруг x, но всё же можно сравнить |x(n+1) — x| с |x(n) — x| и окажется, например, что их частное не превышает какого-нибудь у<1 или наличие другой оценки гарантирующей сходимость (тут придётся вспоминать матанализ). Для примера можете посмотреть на итеративный процесс для вычисления корня t(n+1) = (t(n) + a/t(n))/2 и обоснование его сходимости.

                                                    И есть сильное подозрение, что если рекуррентное соотношение «короткое», коэффициенты и начальные значения «небольшие», то расчёт вручную нескольких сотен первых членов будет достаточным основание для сходимости. Но доказательство (если утверждение вообще верно) со всеми выкладками и обоснованиями, включая точные оценки для «короткое», «небольшие» и «несколько сотен» займёт приличный размер.
                                                    Для тех, кто знает, как выглядит общее решение
                                                    Отсутствие предела и при этом малое изменение x(n) говорит о том, что доминирующим членом в f(n) будет a^n sin(bn +c) при очень малом b. Само a не может быть большим (по предположениям на коэффициенты), поэтому при слишком малом b свободный член уравнения забьёт остальные.
                                                    А вот при больших степенях могут оказаться близкие комплексные корни и здесь можно серьёзно завязнуть в оценках.

                                                    Куда удобнее просто получить явную формулу для f(n), тогда поведение частного сразу станет очевидным.
                                                      0

                                                      Куда удобнее просто получить явную формулу для f(n), тогда поведение частного сразу станет очевидным.


                                                      Вы говорите о явной формуле для n -ого члена последовательности? Для чисел Фибоначчи — это формула Бине, для следующего случая (узнал, что такие числа называются числа трибоначчи) общая формула есть в статье по ссылке. А есть ли формула для произвольного n? И есть ли свое название у того вида рядов, которые были рассмотрены в статье? Заранее благодарен.

                                                        0
                                                        Для знакомых с линейной алгеброй
                                                        Перейдём от уравнения (где все члены перенесены в левую часть) к системе. Обозначим через g(n) вектор-столбец из последовательных членов (f(n), f(n-1), ..., f(n-k))^T, где k = количество членов в рекуррентном соотношении минус два. Например, для соотношения Фибоначчи это (f(n), f(n-1))^T. В результате получим, что g(n+1) = A g(n), где в матрице A первая строка — это коэффициенты уравнения, а последующие — (0… 1… 0) — единица в i cтроке стоит на i-1 месте, остальные нули.
                                                        Тогда g(n) = A^n g(0). Переходим к собственному базису, A=T^{-1}BT, и всё сводится к возведению в степерь Жордановых клеток.
                                                        Эту конструкцию вы могли видеть в решении линейных дифференциальных уравнений с постоянными коэффициентами. Практически всё дословно перенеосится на дискретный случай.

                                                        Итого, общее решение можно найти таким образом. Решаем то самое «уравнение для потенциального предела». Пусть a, b, c… — его корни. Тогда общий член выглядит как Aa^n + Bb^n + Cc^n +… Если корни простые, то A, B, C — константы. Для кратных корней это будут многочлены от n степени на единицу меньше кратности. В случае комплексных корней лучше разбить их на пары сопряженных и от экспонент (a+bi)^n, (a-bi)^n перейти к r^n sin(n phi), r^n cos(n phi). Все коэффициенты находятся из начальных условий.
                                                        Теперь по поводу «формула для произвольного n». Лень разбираться, но я сильно сомневаюсь, что корни для произвольного n будут выражаться в радикалах. Можно поставить вопрос иначе — как будут распределяться корни при росте стпени. Тут ответа не знаю, увы. Можете спросить на dxdy.ru, там люди подкованные.
                                                    0
                                                    Я бы сказал, что парадокс Перрона не соблюдает все условия бесконечности (самого большого числа): 1² = 1, но 1+1 = 2, а это больше 1, значит 1 не самое большое число. Бесконечность + бесконечность = бесконечность.
                                                    0
                                                    Пожалуйста, объясните, как получилось уравнение x = 1 / (1 + x). Первоначальное обобщение должно выглядеть как x(n) = 1 / (1 + x(n-1)), по идеи.
                                                      0

                                                      Равенство выполняется при предельном переходе. Устремляем n в бесконечность и говорим, что если предел существует, то он будет удовлетворять этому соотношению.

                                                        –1
                                                        Сложно. Не припомню чтоб подобное решали на мат. анализе. Похоже это теорема какая-то и ещё нужно предел найти.
                                                        +1
                                                        Если предел существует, то при стремлении n к бесконечности x(n)~x(n+1). А в пределе равенство x(n)=x(n+1).
                                                          0
                                                          А как доказать что предел существует?
                                                        0
                                                        Задача, на мой взгляд, сравнима с вопросом на интервью мальчика из Amazon-а об оптимальном поиске всех палиндромов в строке. Т.е. мальчик хочет увидеть реализацию алгоритма Манакера, написанную на доске (хотя сам узнал об этом алгоритме за день до интервью).

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

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