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

Опубликовано 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 и использование его методов также быть может основой реализации, только при оценке обязательно нужно учитывать внутреннюю сложность самих методов этого класса, а также, понимать, выделяется ли в них дополнительная память.

 


3 Коммент. : “Уникальные символы в строке”

  1. Игорь says:
    bool func(string s, char[] uniquechars)
    {
     List<char> lst = s.Where(ch =>!uniquechars.Contains(ch)).ToList();
     if(lst.Count==0)
           return true;
     else
           return false;
    }
  2. самый быстрый способ – создать множество без повторений( оно реализовано на основе красно-черного дерева т.е скорость зависит от высоты) дальше добавлять каждый элемент символа в множество с проверкой нет ли этого символа там. тут сложость чуть меньше чем н ^2. 2 вариант 2 цикла – и проверяем каждый с каждым. тут н^2. по поводу задания на сортировку, пиримидальная только . Быстрая работает с рекурсией – поэтому есть стек, в котором все вызовы. Кстити, был на собиседовании в никссолюшин, задали интересный вопрос по пирамидальной : “В чем минус этой сортировки” – я до сих пор не знаю ответа, может кто-нибудь знает?

  3. Владислав says:

    O(nlog(n)) если я не ошибаюсь.

    bool is_unique_chars(char* given_string){
        set<char> s;
        set<char>::iterator it;
        while(*given_string != 0){
            char ch = *given_string;
            it = s.find(ch);
            if(it == s.end()){
                s.insert(ch);
                given_string++;
             }
            else
                return false;
        }
        return true;
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*