ППП, ППК, ПКК, ПП и другие: задача с собеседований Amazon

Ключевые выводы: Задача из собеседований Amazon предлагает продолжить последовательность ППП, ППК, ПКК, ПП. Существует как минимум семь разных подходов к решению — через двоичную систему, алгоритмы Маркова, циклы и даже скобочные последовательности. Самый частый ответ — ПК, КК, П, К.

Условие задачи

Задача, которая была популярна в своё время на собеседованиях в Amazon. Мы русифицировали её, но смысл остался тот же. Вам нужно продолжить последовательность.

Разбор решения

Вот один из возможных ответов на эту задачу. Последовательности сопоставлены буквы алфавита, закодированные в набор «П» и «К» — некоторых характеристик. Нужно найти что-то, чего в букве А три, в Б — две и т.д. Тут подходит количество прямых штрихов и кривых. Далее несложно догадаться, что букве Д соответствует, например, «ППППП», в случае её написания как на предложенном рисунке.

Последовательности сопоставлены буквы алфавита, закодированные в набор «П» и «К» — некоторых характеристик. Нужно найти что-то, чего в букве А три, в Б — две и т.д. Тут подходит количество прямых штрихов и кривых. Далее несложно догадаться, что букве Д соответствует, например, «ППППП», в случае её написания как на предложенном рисунке.

Идеи и решения от подписчиков

В комментариях к посту с задачей можно было найти множество интересных решений, которые перечислены ниже.

Алгоритмы Маркова

Оба алгоритма работают при проходе с конца строки.

Ответ: ПК, КК, П, К

Ответ: ПК

Двоичная система счисления

П — это 1, К — это 0.

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

• 7 (ППП — 111),
• 6 (=7-1) (ППК — 110),
• 4 (=6-2) (ПКК — 100),
• 3 (=4-1) (ПП — 11),

а значит, далее следуют

• 1 (=3-2) (1 — П) и
• (=1-1) (0 — К).

Ответ: П, К.

Цикл

Существует цикл заполнения строки буквами К с конца, при этом, когда остается всего одна П (очевидно, слева), то вся строка преобразуется к строке из букв П, но на одну меньше, т.е.:

• ППП

заполняем буквами К с конца

• ППК
• ПКК

осталась одна П, уменьшим длину

• ПП
• ПК

снова укорачиваем

• П

Ответ: ПК, П

Скобочная последовательность

Забавный вариант: П — пусть, К — конец, тогда можно построить аналогию с открывающимися-закрывающимися скобками ? Закономерность не найдена.

UPD. Был предложен вариант рассматривать всю последовательность букв как единую скобочную последовательность:

• ((( (() ()) (( )) )))ППП ППК ПКК ПП ККК КК

или

• ППП ППК ПКК ПП КК ККК

Ответ: ККККК (в разных вариантах: КК, ККК или ККК, КК и т.п.)

Несоставные числа

Посчитаем количество «дырок в буквах»:

• ППП — 3
• ППК — 5
• ПКК — 7
• ПП — 2

Заметим, что все это — простые (т.е. не составные) числа до 10. Заметим, что есть еще только одно не составное число, меньшее 10 — это единица.

Ответ: П

Произведение 1 и -1

П — это -1. К — это 1. Вариант наоборот, естественно, также подойдет. Тогда рассмотрим их произведения:

• ППП = -1
• ППК = 1
• ПКК = -1
• ПП = 1

вариантов продолжения несколько, автор предложил такой:

• ПК = -1
• КК = 1
• П = -1
• К = 1

Ответ: ПК, КК, П, К

Сумма

П = 15, К = 10. Естественно, подойдут любые другие числа такие, что П:К = 3:2. Рассмотрим ряд:

• ППП: П+П+П = 45
• ППК: П+П+К = 40
• ПКК: П+К+К = 35
• ПП = 30

в качестве продолжения напрашиваются:

• ПК = 25
• КК = 20
• П = 15* К = 10

Ответ: ПК, КК, П, К

Русский язык в помощь

Вариант с хронологией выпуска девайсов:

• ППП — первое промышленное производство, или первое производство процессоров
• ППК — первый персональный компьютер
• ПКК — первый карманный компьютер
• ПП — первый планшет
• ПС — первый смартфон

Ответ: ПС

Азбука Морзе

К сожалению, закономерности найти никто не смог. Может быть, это удастся вам?

Занимательно то, что при разных вариантах решения очень часто появлялся ответ ПК, КК, П, К…

Часто задаваемые вопросы

Зачем такие задачи дают на собеседованиях?

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

Какой ответ считается правильным?

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

Дают ли такие задачи в российских компаниях?

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