Replies (20)

  • @kb, считать длину, когда выйдет за sizeof(void*) — вернуть true
  • @max630, указатель не ограничен в размере
  • @max630, ну, или, скажем так, есть решение оптимальнее.
  • @kb, я преслагаю решение O(1), оптимальнее некуда :)
  • @kb, ага
  • @kb, ага. а теперь за линейную сложность по памяти и O(N) по проходам.
  • @kb, я думаю по памяти можно логарифмическую сделать
  • @kb, меня недавно на собеседованиии просили найти общий хвост у двух списков
  • @max630, причём чувак говорил что "one of them is currupted — it points to element of another list" и вообще был похож на менеджера
  • @max630, а можно константную
  • @max630, ага, и описывал просто свою проблему из жизни :)
  • @kb, на собеседовании спросили однажды — протупил, через час из маршрутки прислал ответ им на мэйл, но всё равно даже не ответили...
    Запостить мой ответ сюда?
  • @ak, да пость на здоровье. если не ты — придется мне же :)
  • @kb, Какбе мат.индукция:
    пусть ячейки от a_1 до a_n без замыканий. Проверяем, указывает ли a_1 на себя. Проверяем a_(n+1) указывает ли она на ячейки от a_1 до a_n. Если нет — увеличиваем число n на единицу. Короче, каждая следующая ячейка проверяется по предыдущим. В лоб и долго, но вариант.
  • @ak, короче вот решение: заводим два курсора, один за шаг ходит на 1 элемент, другой на 2. если один другого догонит — значит закольцовывается. вот.
  • @kb, тот который ходит на 2 (второй), может пропустить закольцованный элемент и тогда первый никогда не догонит, потому что будет бегатб по кругу, а второй дойдёт до конца
  • @ak, туплю, не так прочитал
  • @ak, если дойдёт до конца — значит кольца нет :)
  • @max630, я понял так, что второй прыгает через ячейку, т.е. его скорость в два раза больше, но он может пропустить закольцованную ячейку. Хочется ввести третий курсор, который будет скакать по чётным, тогда как второй — по нечётным.