Написать пост

ППП, ППК, ПКК, ПП и другие

Аватар Типичный программист

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

Обложка поста ППП, ППК, ПКК, ПП и другие

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

ППП, ППК, ПКК, ПП и другие 1

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

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

ППП, ППК, ПКК, ПП и другие 2

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

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

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

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

			
		

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

			
		

Ответ: ПК

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

П — это 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

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

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

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

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

Ответ: ПС

Азбука Морзе

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

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