Отправлено: 22.07.19 18:10. Заголовок: Тестовое задание для начинающих программистов. Сжатие строки - как из мухи сделать слона.

Эта тема мною создана на основе вопроса на Stackoverflow Does my code have memory leak? C++ Junior job interview question check

Так как автор собирается удалить свой вопрос, то опишу его здесь подробнее.

цитата:

I was at a job interview the other day and I had the following function to implement:

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

char* Compress (char * text);

которая сжимает строку.

Например, если исходная строка есть "11112222333344411", то нужно получить строку "12341". Или если исходная строка есть "aaAbbBBcCCa", то нужно получитьб строку "aAbBcCa".

И, вот, какое решение выдал автор вопроса.

 
 #include <iostream> 
  
 char* Compress(char* text) { 
  
     char* temp; 
     char* _compText; 
  
     int size = 1; 
  
     _compText = nullptr; 
  
     for (size_t i = 0; text != '\0'; ++i) 
     { 
         if (text != text[i + 1]) { 
  
             ++size; 
  
             temp = _compText; 
  
             _compText = new char[size]; 
  
             for (size_t j = 0; j < size-2; ++j) 
             { 
                 _compText[j] = temp[j]; 
             } 
  
             _compText[size-2] = text; 
             _compText[size-1] = '\0'; 
             delete[] temp; 
         } 
  
     } 
  
     return _compText; 
 } 
  
 int main() 
 { 
     char t[] = "111122222233333444444555555111"; 
  
     char* compedT; 
  
     std::cout << "Before:\n"; 
  
     std::cout << t; 
  
     compedT = Compress(t); 
  
     std::cout << "\nAfter: \n"; 
  
     std::cout << compedT; 
  
     delete[] compedT; 
  
     return 0; 
 }

При этом он задачался вопросом: а есть ли в его функции утечка памяти.

Очевидно, что его реализации функции совершенно не эффективна. Он постоянно переписывает строки в каждый раз динамически размещенный символьный массив. Кроме того в сравнение, используемом в условии цикла j < size-2, сравниваются беззнаковое и знаковое числа.

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

Так из совершенно простого задания сделано награмождение неэффективного кода.

Как на самом деле следует реализовать функцию?

Автор вопроса совершенно не обратил пристального внимания на объявление функции. Ее параметр объявлен без квалификатора const.

char* Compress (char * text); 
                ^^^^^^^

Что это означает?

Это означает, что функции требуется изменить саму исходную строку "на месте" и возвратить указатель на ее первый символ.

Для этого совершенно нет никакой необходимости динамически выделять память. Все делается внутри одного цикла.

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

 
 #include <iostream> 
  
 char * Compress( char *s ) 
 { 
     for ( char *p = s, *q = s; *q; ) 
     { 
         if ( *++q != *p ) *++p = *q; 
     } 
      
     return s; 
 } 
  
 int main() 
 { 
     char s1[] = "11112222333344411"; 
      
     std::cout << Compress( s1 ) << '\n'; 
      
     char s2[] = "aaAbbBBcCCa"; 
      
     std::cout << Compress( s2 ) << '\n'; 
 }

Вывод программы на консоль:

 
 12341 
 aAbBcCa

Функция также может быть определена следующим образом

 
 char * Compress( char *s ) 
 { 
     for ( char *p = s, *q = s; *q; ) 
     { 
         if ( ( *++q != *p ) and ( ++p != q ) ) *p = *q; 
     } 
  
     return s; 
 }

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