Я отправляю этот вопрос интервью, который я недавно нашел
Представьте, что у вас есть компьютерная клавиатура, на которой не совпадают все буквы
Пример:
— ввод q дает вам
— ввод w дает вам b
присутствуют все 26 букв в алфавите, но ввод одной буквы даст вам другуюОграничение: вам нужно каждый раз вводить слово, а не переходить по символам
Целью является
- найти алгоритм для написания заданное слово с помощью этой клавиатуры
- оценить его сложность
- определить пределы подхода
ПРИМЕЧАНИЯ
- Ограничение означает, что невозможно ввести один символ и наблюдать результат, необходимо ввести все слово, прежде чем наблюдать результат.
Это мой подход
Это неявно означает нахождение кнопки для символьного сопоставления клавиатуры.
Как заявлено, что проблема может иметь произвольную сложность, поскольку у нас нет предварительной информации об этой передаточной функции, на самом деле она может быть
- случайной или иметь случайный компонент
- с сохранением состояния, поэтому результат может зависеть от истории
Однако давайте начнем сосредоточиться на простом подмножестве функций передачи, которые имеют следующие особенности
- детерминированный
- без сохранения состояния
Мы можем смоделировать это следующим образом, в терминах Haskell
f :: Char -> Char
Однако есть дополнительная проблема, связанная с этой функцией: возможно, любой нужный нам символ не представлен, т.е.. для этой функции нет ввода, поэтому мы получаем желаемый символ в качестве вывода
Это делает проблему по существу эквивалентной линейному поиску, поэтому она O (N) с N количеством возможных входных символов для функции передачи, следовательно, кнопок на этой клавиатуре
Дополнительное ограничение, которое требует ввода слова, а не отдельных символов, для соблюдения вывод не влияет на сложность: достаточно определить набор неперекрывающихся слов, охватывающий всю входную область, чтобы получить полное представление
В конце этой процедуры мы будем может решить проблему или решить, что она не может быть решена, потому что некоторые символы не представляются
$ endgroup $
Это мой подход
Это неявно означает, что нужно найти кнопку для символьного сопоставления клавиатуры.
Как указано, проблема может быть в произвольной сложности, поскольку у нас нет предварительной информации об этой передаточной функции, на самом деле она может быть
- случайной или иметь случайный компонент
- с сохранением состояния, поэтому результат может зависеть от истории
Однако давайте сосредоточимся на простом подмножестве функций передачи, которые имеют следующие особенности:
- детерминированный
- без состояния
Мы можем смоделировать это следующим образом, в терминах Haskell
f :: Char -> Char
Однако есть дополнительная проблема, связанная с этой функцией: возможно, любой нужный нам char не представлен, то есть для этой функции нет ввода, поэтому мы получаем желаемый символ в качестве вывода
Это делает задачу по существу эквивалентной линейному поиску, поэтому она O (N) с N количество возможных входных символов для функции передачи, следовательно, кнопок на этой клавиатуре
Дополнительное ограничение, которое требует ввода слова, а не отдельных символов, для соблюдения t вывод не влияет на сложность: достаточно определить набор неперекрывающихся слов, покрывающих всю входную область, чтобы получить полное представление
В конце этой процедуры мы будем может решить проблему или решить, что ее невозможно решить, потому что некоторые символы не могут быть представлены
