Трудный вопрос на собеседовании #4

Каким образом можно циклично сдвинуть строку длиной n на m символов при константной дополнительной памяти за линейное время?

UPDATE: ответ.

👍НравитсяПонравилось0
В избранноеВ избранном0
Подписаться на автора
LinkedIn



Підписуйтесь: Soundcloud | Google Podcast | YouTube

47 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

для правильного ответа 2n перестановок— медлено.

Правильный ответ:

Определите, на каком символе от начала строки вы хотите быть после сдвига. Затем разделите строку на две части так, чтобы этот символ был первым во второй «половине» строки. Оберните каждую часть на месте, затем оберните всю результирующую строку.

Вы слишком усложняете.Сдвиг влево на М символов есть перестановка местами двух подстрок из М и N-M символов.Перестановка без дополнительной памяти делается следующим образом: АБЦД1234567 -> ДЦБА1234567 -> ДЦБА7654321 -> 1234567АБЦДКак все уже догадались, на каждом шаге мы разворачиваем некоторую подстроку задом наперед.Вот мы и свели задачу к предыдущей — как обратить строку за линейное время без доп.памяти уже бурно обсуждалась при трудоустройстве в стартапы.Так-то.

Мда... Александру накидали тут кусков кода. Поди разберись чей как работает: -)


char s[] = "asdasfmnsbd sdf".toCharArray();int n = s.length;int m = 3;int count = 0;int j = 0,i;char dop,tmp;// пока не обработали всеwhile (count<n){ i=j;dop = s[i];do {tmp = s[(n+i-m%n)%n];s[(n+i-m%n)%n] = dop;i=(n+i-m%n)%n;dop = tmp;count++;}while (i!=j); // пока не пришли на начало циклаj++; // увеличиваем остаток рассматриваемого класса}System.out.println(s);

Ну, наверное ниче нового не внесу, но как еще один вариант можно рассмотреть.Идея 1) сдвиг на m равносилен сдвигу на m%n2) сдвигать можно в стиле: Идейно цикл: запомнить то, на чем сейчас, перейти на m%n символов влево/вправо, влупить туда то, что запомнил, перед этим запомнить то, что там было.Но тут появляются приколы. Решение математикой.Если m и n не взаимопростые, то цикл пройдется не по всем елементам, а по классу одинаковых остатков стартового символа.Для этого (не вычисляя никаких НСД/НСК) мы просто итерируем все классы одинаковы х остатков. Можно начинать с 0, потом 1,...и так пока не переитерируем все символы, используя каунтер уже сдвинутиых символов. Можно было б вычислить шаги сразу -, но нет смысла, т.к там надо будет НСКНСД...Ну вот такое решение на JAVA. Влом было красиво оформлять с параметрами...

кудато else прапало при посте

} else {m = n-m;for(int i=n-(m/2)-1;i>=0;i--){swap(str,i,((n-m)+(i%m)));}}

при буфере в 1 char, время выполнения = O (n- (m/2)):

public static void main(String[] args) {char[] str = {'0','1','2','3','4','5','6','7','8','9'};int n = str.length;int m=4;if (n/2>=m) {for(int i=0;i=0;i--){swap(str,i,((n-m)+(i%m)));}}System.err.println(Arrays.toString(str)); } static void swap(char[] str, int i1, int i2 ){char t = str[i1];str[i1] = str[i2];str[i2] = t; }

Ага, возвращает std: string: size_type или size_t. Исправлюсь.А по второму вопросу, анализ хидерных файлов студии показал что это тип unsigned. Как по ГОСТУ, я к сожалению не знаю

Евгений, для Вас есть ЛегкийВопросНаСобеседовании:) Даже 2. Результат какого типа возращиет std: string: length () и на каких системах int не совпадает по размерам с этим типом?

Vlad, а Ваш варнинг выдал?

Я имел ввиду, что количество обменов зависит от длины строки, а не от велечины сдвига.А чем конструкция «const int m=str.length (); » плоха? Я специально ее и вводил, чтобы если ненароком захочу изменить m, то компилятор выдал бы мне предупреждение. Стараюсь стремиться к безопасному программированию так сказать...

Правда у Vladа алгоритм тоже вроде как линейный. По крайней мере количество перестановок при любом n одинаково.

Если количество перестановок было одинаково при любом n, то алгоритм был бы с константной сложностью, а не линейной;)

Евгений, Ваш компилятор не ругается на всякие «const int m=str.length (); »?

Правда у Vladа алгоритм тоже вроде как линейный. По крайней мере количество перестановок при любом n одинаково.

Вот версия без вложенных циклов и рекурсий

void move(std::string& str, int n){const int m=str.length();int pos=0, start=0;char ch=str[0];for(int i=0;i<m;i++){pos=(pos+n)%m;std::swap(str[pos], ch);if(pos==start){pos=start+=1;ch=str[start];}}}

2 ВладНе знаю, думаю, що просто глюки з областями видимості.

> Хоча в сьомій студії таке працювало, коли я тестува (змінна і зберігає значення, якого вона набула в циклі, а з областями видимості у них проблеми) А если между циклом и рекурсивным вызовом добавить еще какой-нибудь вызов процедуры, что-бы перезаписать эту область стека все равно работать будет? Не имею возможности в Линуксе проверить это в какой либо из студий...

2 ВладА, вірно, треба замінити на doMove (s, last, m — ((i — start) % m)); наdoMove (s, last, m — ((last — start) % m)); Хоча в сьомій студії таке працювало, коли я тестува (змінна і зберігає значення, якого вона набула в циклі, а з областями видимості у них проблеми)


void doMove(string& s, int start, int m) {m %= (s.length() - start);if (m == 0)return;int last = s.length() - m;for (int i = start; i < last; i++)swap(s[i], s[i + m]);doMove(s, last, m - ((i - start) % m));}

Вас не смущает, что переменная i используется за пределами ее области видимости?

2 VladВін розбиває перестановку букв на незалежні циклічні перестановки, і переставляє кожну таку циклічну перестановку окремо (красиво, до речі, вийшло:)

O (n + log n) конечно же. Можно отбросить логарифм, как некоторое число, значительно меньшее чем собственно сдвиг линейной сложности, но все же ума не приложу зачем ждесь GCD:)

2 Pro100Oleh> int k = Наибольший общий делитель; Может я что-то забыл, но нахождение GCD вроде как в лучшем случае O (log n), тоесть Ваш алгоритм вобщем — O (n log n). Правда ума не приложу зачем Вам GCD...

Принаймні при додатніх m:)

if (m > n) m %= n; еквівалентноm %= n;

2 1mdmif (m < n) это защита от дурака. Много сэкономим если кто-то решит сдвинуть 100-символьную строку на 876345 символов:)

2 VladА що твій код робить? Можеш словами пояснити?

Опоздал, Vlad уже опубликовал: (

Сдвиг вправо для C#:

        public static string Shift(string s, int m)        {            char[] input = s.ToCharArray();            int n = s.Length;            int k = <a href="n, m">Наибольший общий делитель</a>;            int count = n / k;            for (int shift = 0; shift < k; shift++)            {                char old = input[shift];                for (int index = 1; index < count; index++)                {                    int currentIndex = (shift + index * m) % n;                    char tmp = input[currentIndex];                    input[currentIndex] = old;                    old = tmp;                }                input[shift] = old;            }            return new string(input);        }

2 VladУсловие if (m > n) избыточно.


char shiftStr(char str, size_t m, size_t n){size_t i, j;size_t guard = 0;if (m > n)m %= n;for (i = 0; i < m && guard < n; ++i) {char tmp = str[i];for (j = i+m; j != i && guard < n;) {char tmp_inner = str[j];str[j] = tmp;tmp = tmp_inner;j = (j + m < n ? j + m : m - (n - j));++guard;}str[j] = tmp;++guard;}return str;}

Автар, либо показывай красивое решение, либо получаешь одну звезду. И вопрос как для собеседование плоховат, если не знать сразу со всеми подводными камнями не напишеш...

@4, не поможет ли

code { white-space: pre }

? Если это портит малину для кода внутри строки, то можно добавлять

pre

автоматически если внутри

code

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

>> Кстати, чтобы код был секси, надо заключать его в теги pre+codeЩось ніяк не виходить.


void doMove(string& s, int start, int m) { m %= (s.length() - start); if (m == 0) return; int last = s.length() - m; for (int i = start; i < last; i++) swap(s[i], s[i + m]); doMove(s, last, m - ((i - start) % m));}

void doMove(string& s, int start, int m) {m %= (s.length() - start);if (m == 0)return;int last = s.length() - m;for (int i = start; i < last; i++)swap(s[i], s[i + m]);doMove(s, last, m - ((i - start) % m));}

2 mdm>> Тогда нужно с начала строки и до shift-1 копировать символы в буфер размером kбайт, затем сдвигать всю строку влево на k байт и символы из буфера копировать в конец строки.Так, а що робити, якщо вони не влізуть в буфер розміром к байт, бо к менше, ніж shift?

Класна задача, раніше такої не бачив.Будемо вважати, що зсуваємо вліво.Яка ідея придумалась: Йдемо зліва направо, і обмінюємо символ з номером і на символ з номером і + m, допоки не дійдемо до моменту, коли цього зробити не можна, бо і + m вилазить за межі.Наприклад, зсуваємо рядок «abcdefg» на 3 символи вліво: abcdefg -> dbcaefg -> decabfg -> defabcg -> defgbcaТепер запускаємо рекурсивно ту саму операцію на хвості, але з іншим m (в даному випадку — зсуваємо bca на два символи вліво). Якщо тепер акуратно реалізувати, то виходить: void doMove (string& s, int start, int m) { m %= (s.length () — start); if (m == 0) return; int last = s.length () — m; for (int i = start; i < last; i++) swap (s [i], s [i + m]); doMove (s, last, m — ((i — start) % m)); } На д/з лишаємо доведення того, що час виконання буде лінійним.ПСДана реалізація, насправді, теоретично може жерти лінійну пам’ять, якщо підібрати правильні Н та М (питання — які?:) через те, що траплятиметься забагато вкладених викликів методу, але цей самий метод можна легко переписати ітеративно, а не рекурсивно.

2 ВсеволодНаверное вы правы.Тогда уместно будет использовать XOR для перестановки соответствующих символов в строке. Время будет = O (m/k).

2 IgorО каком коде вы говорите? В первом комментарии я писал псевдокод.

А ведь-таки так! Тогда нужно с начала строки и до shift-1 копировать символы в буфер размером k байт, затем сдвигать всю строку влево на k байт и символы из буфера копировать в конец строки. Или наоборот.

2 1mdmА мне кажется что этот код не будет работать вообще

Условие «за линейное время» в моём решение соблюдено.А условие «при константной доп. памяти» решается копированием символовиз первой части строки в конец второй части с использованием фиксированногопо размеру буфера. Если буфер будет равен одному символу, то мы решаем этузадачу на O (m) времени.

В некотором смысле, эта задача есть частным случаем предыдущей.

Кстати, чтобы код был секси, надо заключать его в теги pre+code.

Задачка сама по себе не очень сложная — сделать из «колбаса» «басакол».

str = str.substr(shift) + str.substr(0, shift-1);
А вот решить ее, соблюдая ограничения — уже труднее:

при константной дополнительной памяти за линейное время

Символы «съелись». Короче, свопаем вот так: swap (start... (shift-1), shift...end), где «...» это диапазон.

Псевдокод: shift = m % n; str = str.substr (shift) + str.substr (0, shift-1); Сначала вычисляем на сколько символов нужно реально сдвинуть (если вдруг m > n), а затем меняем местами части строки: start... (shift-1) shift...end.Вроде так:)

Подписаться на комментарии