On-line: гостей 1. Всего: 1 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 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;
}

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

Спасибо: 0 
ПрофильЦитата Ответить
Новых ответов нет


Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 1
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет