Уникальные символы в строке

Опубликовано Sep 30, 2011 в Массивы и строки | 3 коммент.


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

 bool is_unique_chars(char* given_string)
{
  //ваш код - нужно вернуть true, если символы уникальны
  //и false - в противном случае
}
1 Цель задания быстрая проверка умения придумать и реализовать простейший алгоритм
2 Время выполнения 10 минут
3 Формат выполнения код пишется на листике, без доступа к документации

Критерии оценки FulcrumWeb:

Нужно продемонстрировать умение увидеть различные алгоритмы решения задачи, а так же сравнивать их по критерию сложность (в нотации “O”). Для собственно реализации выбирается какой-то один вариант. Другие варианты можно описать словами и сделать сравнение по сложности, в предположении, что длина строки равна n.

Ожидаемые вопросы:

  1. Можно ли считать, что строка дана в ANSI кодировке?
  2. Можно ли поменять сигнатуру метода и работать с классом string из стандартной библиотеки?
  3. Различаются ли случаи с выделением дополнительной памяти на один символ и массива символов по всю строку?
  4. Можно ли испортить исходную строку?

Оценка результатов:

 

От начинающего программиста ANSI кодировка подразумевается и ожидается реализация без выделения дополнительной памяти со сложностью O(n2), основанная на двух вложенных циклах для сравнения каждого символа строки с каждым. Правильная оценка сложности должна быть дана. Желательно так же описать вариант без выделения памяти, основанный на сортировке символов строки (сложность O(n log n), строка испортится) и проверке того, что соседние символы различны (сложность O(n)). Для этого решения будет поднят вопрос о знании алгоритма сортировки с указанной сложностью, который сам по себе не требует выделения дополнительной памяти.

 

От программистов с опытом ожидается указание на существование предыдущих вариантов и реализация решения сложности O(n) с выделением дополнительной памяти в виде массива размером под полную таблицу символов в нужной кодировке. Ожидаемый размер элемента массива 8 байт (тип bool), но можно исхитриться и использовать битовый массив. Переход к классу string и использование его методов также быть может основой реализации, только при оценке обязательно нужно учитывать внутреннюю сложность самих методов этого класса, а также, понимать, выделяется ли в них дополнительная память.