Monday 7 October 2013

Вопрос на собеседовании #2

Задача в довольно большой, но не IT компании. Туда я вообще не прошел, так как шел на разработку в незнакомую область, но опыт прикольный =)

Задача:
Условие взял отсюда.
Есть односвязный список
struct List {
    int value;
    struct List *next;
} _list;

требуется написать функцию
bool isCycled(struct List *head);

определяющую, есть ли в списке цикл, при этом потребление памяти не должно зависеть от размера списка.





Решение:
Ну я сразу ответа на задачу не нашел. Хотя и времени у меня с минуту было...проговорил пару вариантов, и тут же и отверг...map/set создать не можем, по памяти не проходим. По времени поиска ответа не ограничен, значит можно писать что-то не эффективное.

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

Предлагаются еще решения, но я их толком не разбирал.

Немного подумав придумал следующее решение:

Указатели наверняка указывают на пространство в куче, она не бесконечная, да у нас и в принципе нет бесконечных носителей. Учитывая эти факты: будем отмечать минимальный и максимальный указатель из встречающихся и считать количество указателей после факта смены максимального или минимального указателя. Теперь если текущий указатель с NULL в *next, то список не цикличный. Если текущий указатель равен минимальному(pMin) или максимальному(pMax) указателю, то список цикличный. Если (pMax - pMin) / count < sizeof(List), то список цикличный, ну или что-то вроде такого =) Идею проверял только в уме, может есть в ней баг)

А какие у Вас есть решения данной задачи?

Другие части цикла: #1 #3 #4 #5

2 comments:

  1. Вроде работает ?

    first=list.head
    cur = first.next
    while (cur!=null && cur != first) {
    p = cur
    cur = cur.next
    p.next = first
    }
    if cur == null output no cycle else cycle

    ReplyDelete
    Replies
    1. да, рабочий =) а если список immutable?

      Delete