предыдущая задачка, и еще одна (программистское)

[avva]

Я раскрываю все скрытые комментарии с правильными решениями к позавчерашней задачке. Если хотите все еще решать ее самостоятельно, не заглядывайте в комментарии. Спасибо всем, кто решал. Первый, кто нашел оптимальное решение за O(N) времени и O(1) памяти - ilyaraz.

Вот еще одна программистская задачка. Я когда-то знал ее решение и забыл, недавно с удовольствием решил снова. Эта задачка довольно хорошо известна, и в частности часто преподается на курсах продвинутых структур данных, и упоминается в учебниках. Так что многие наверняка ее знают - если вы знаете решение, то не пишите в комментариях. Для тех, кто не знает, это отличное упражнение для ума, по-моему.

Задача: требуется воплотить массив с дефолтным значением для всех элементов, т.е. структуру данных с тремя операциями: get(i), set(i, value) и setdefault(value). Любой вызов get() с индексом, который до сих пор ни разу не передавался set(), должен возвращать последнее выставленное дефолтное значение (или 0, если такого не было). Сложность в том, что все три операции: get, set и setdefault, должны занимать O(1) времени. При этом нельзя рассчитывать на то, что отведенная нам память имеет какой-либо специальный вид, например, заполнена нулями. Любая используемая память изначально содержит случайные байты, которые мы никак не можем контролировать.

Comments

[avva.livejournal.com]

Возможно, там недочет в коде, я уже не помню. Суть в том, что надо начинать искать цикл с точки, в которую невозможно вернуться обратно, потому что ее индекс за пределами значений массива. Какая эта точка, зависит от того, откуда массив считать. Если мы считаем индексы от 1 до N, значения от 1 до N-1, надо начинать с индекса N, но иметь в виду, что индексы концептуально начинаются с 1, и код строить соответственно. Поскольку в Питоне индексы начинаются с 0, нужно писать что-то вроде i = arr[i-1]. Если вы пройдете так по вашим данным, то дойдете до единицы.

Или можно наоборот сказать: будем считать индексы массива от 0 до N-1, а значения от 1 до N-1, и тогда начнем цикл с первого значения (индекс 0), потому что к нему невозможно будет вернуться. Тогда начинаем с i=0 и делаем i = arr[i].