Найдите алгоритм, чтобы написать данное слово с помощью этой сломанной клавиатуры

Я отправляю этот вопрос интервью, который я недавно нашел

Представьте, что у вас есть компьютерная клавиатура, на которой не совпадают все буквы
Пример:
— ввод q дает вам
— ввод w дает вам b
присутствуют все 26 букв в алфавите, но ввод одной буквы даст вам другую

Ограничение: вам нужно каждый раз вводить слово, а не переходить по символам

Целью является

  • найти алгоритм для написания заданное слово с помощью этой клавиатуры
  • оценить его сложность
  • определить пределы подхода

ПРИМЕЧАНИЯ

  • Ограничение означает, что невозможно ввести один символ и наблюдать результат, необходимо ввести все слово, прежде чем наблюдать результат.

$ begingroup $

Это мой подход

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

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

  • случайной или иметь случайный компонент
  • с сохранением состояния, поэтому результат может зависеть от истории

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

  • детерминированный
  • без сохранения состояния

Мы можем смоделировать это следующим образом, в терминах Haskell

f :: Char -> Char

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

Это делает проблему по существу эквивалентной линейному поиску, поэтому она O (N) с N количеством возможных входных символов для функции передачи, следовательно, кнопок на этой клавиатуре

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

В конце этой процедуры мы будем может решить проблему или решить, что она не может быть решена, потому что некоторые символы не представляются

$ endgroup $


Это мой подход

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

Как указано, проблема может быть в произвольной сложности, поскольку у нас нет предварительной информации об этой передаточной функции, на самом деле она может быть

  • случайной или иметь случайный компонент
  • с сохранением состояния, поэтому результат может зависеть от истории

Однако давайте сосредоточимся на простом подмножестве функций передачи, которые имеют следующие особенности:

  • детерминированный
  • без состояния

Мы можем смоделировать это следующим образом, в терминах Haskell

f :: Char -> Char

Однако есть дополнительная проблема, связанная с этой функцией: возможно, любой нужный нам char не представлен, то есть для этой функции нет ввода, поэтому мы получаем желаемый символ в качестве вывода

Это делает задачу по существу эквивалентной линейному поиску, поэтому она O (N) с N количество возможных входных символов для функции передачи, следовательно, кнопок на этой клавиатуре

Дополнительное ограничение, которое требует ввода слова, а не отдельных символов, для соблюдения t вывод не влияет на сложность: достаточно определить набор неперекрывающихся слов, покрывающих всю входную область, чтобы получить полное представление

В конце этой процедуры мы будем может решить проблему или решить, что ее невозможно решить, потому что некоторые символы не могут быть представлены

Оцените статью
techsly.ru
Добавить комментарий