Головоломка
На той неделе сушил мозги над очень простой (с виду) задачей: одномерный массив размерностью N сдвинуть циклически право на i элементов.
Дополнительно память не выделять, рекурсию не использовать, количество операций постараться минимизировать.
Если вы никогда раньше не сталкивались с этой задачей -- очень советую, прямо сейчас взять листик бумаги, ручку и попытаться ее решить. А потом продолжить чтение дальше...
В общем, хоть какое-то решение я смог получить только через несколько дней.
Проблема в том, что интуитивно я понимал, что должно быть решение со сложностью, близкой к O(N), бился над ним и мозг даже не пытался пойти по самому очевидному пути: выполнить i раз сдвиг на один элемент вправо.
После получения такого вот ужасно не оптимального способа, я естественным образом пришел к выводу, что если дать дополнительный буфер на i элементов, я смогу выполнить задачу довольно оптимальным способом.
Ничего лучше я так и не придумал -- полез в интернет и изучил материалы по теме.
В сторону т.н последовательного способа я двигался, однако путь показался мне слишком сложным и я не смог докрутить его до конца.
Перестановка блоков -- тоже довольно не тривиальная вещь.
Ну и решение на основе переворотов -- фантастически красивое, но встает вопрос: а может ли простой смертный "вдруг" открыть такое вот решение?
В общем, мой тотальный fail хорошо уложился в рамки моей же теории, что такие вот еб@нные шарады есть чистая математика, к программированию имеющая весьма и весьма опосредованное отношение. И очень вряд ли я стал бы давать подобную штуку на собеседовании. Ну разве что для того, чтобы помучать человека.
Решение -- http://codelab.ru/task/cycle_shift/
Дополнительно память не выделять, рекурсию не использовать, количество операций постараться минимизировать.
Если вы никогда раньше не сталкивались с этой задачей -- очень советую, прямо сейчас взять листик бумаги, ручку и попытаться ее решить. А потом продолжить чтение дальше...
В общем, хоть какое-то решение я смог получить только через несколько дней.
Проблема в том, что интуитивно я понимал, что должно быть решение со сложностью, близкой к O(N), бился над ним и мозг даже не пытался пойти по самому очевидному пути: выполнить i раз сдвиг на один элемент вправо.
После получения такого вот ужасно не оптимального способа, я естественным образом пришел к выводу, что если дать дополнительный буфер на i элементов, я смогу выполнить задачу довольно оптимальным способом.
Ничего лучше я так и не придумал -- полез в интернет и изучил материалы по теме.
В сторону т.н последовательного способа я двигался, однако путь показался мне слишком сложным и я не смог докрутить его до конца.
Перестановка блоков -- тоже довольно не тривиальная вещь.
Ну и решение на основе переворотов -- фантастически красивое, но встает вопрос: а может ли простой смертный "вдруг" открыть такое вот решение?
В общем, мой тотальный fail хорошо уложился в рамки моей же теории, что такие вот еб@нные шарады есть чистая математика, к программированию имеющая весьма и весьма опосредованное отношение. И очень вряд ли я стал бы давать подобную штуку на собеседовании. Ну разве что для того, чтобы помучать человека.
Решение -- http://codelab.ru/task/cycle_shift/