Питерский - еду к тебе ;)

[Piterskii]

A знаешь как решать бородатую задачку:
дано начало single direction linked list-а.
Определить: есть или нет внутренний loop в листе.
Копировать элементы листа нельзя (память ограничена).

[Piterskii]

Каждая новая открытая скобка - записываешь в стак. Если закрывающая - проверяешь предыдущую (что б была открывающая того же вида (нужно predifine pairs)), если false - return false.

забыл добавить:
если закрывающая соответствует предыдущей открывающей - удаляешь предыдущую открывающую из стака.
Т.е. always deals with the last opening.

[AlexA]

Можно еще проще?

А я дурак не сообразил, но стал сдуру держать 3 стака для каждого вида скобок - отдельный стак и проверять каждый из них, когда приходила закрытая скобка, да ещё стал держать в тех же стаках позицию этой открытой скобки - в общем , лоханулся по-полной...

[AlexA]

есть или нет внутренний loop в листе.

там по-моему идут д-мя поинтерами причём один всё время "прыгает" на 1 шаг (next), а другой на 2 (next->next) и всё время проверяешь - не являются ли они указателям на один и тот же обьект, если дошёл до null с одним из поинтеров - не закрытый - выходи, а если оба вдруг показывают на один и тот же нод, - закрытый - опять выходи

[Piterskii]

стал сдуру держать 3 стака для каждого вида скобок - отдельный стак и проверять каждый из них, когда приходила закрытая скобка, да ещё стал держать в тех же стаках позицию этой открытой скобки

под стрессом все бывает. Мелочи жизни.
Однако строгие они, за 1 задачу отшили.

там по-моему идут д-мя поинтерами причём один всё время "прыгает" на 1 шаг (next), а другой на 2 (next->next) и всё время проверяешь - не являются ли они указателям на один и тот же обьект, если дошёл до null с одним из поинтеров - не закрытый - выходи, а если оба вдруг показывают на один и тот же нод, - закрытый - опять выходи

ага. Молодец. Я когда-то погорел над этой задачей на интервью.

[AlexA]

ага. Молодец. Я когда-то погорел над этой задачей на интервью.

Я почему-то запомнил её с курса "мивнэ натуним", наверное потому что мы с М-ей (нашим общим знакомым) неправильно её решили в дом. задании, а потом её разбирали в классе. Не боись 1/2 студентов с Тель-Авивского комп. сайнас , 2-ой курс - не решили её правильно тогда...

[AlexA]

А вот вопрос пройденный мной на ура на прошлом интервью амазона:
дано бинарное дерево и 2 нода, надо найти их последнего общего "предка", т.е. к примеру:
  a
/\
  b
/
c
/\
d e

последний общий предок д и е - c,
а предок б и с - а.

[AlexA]

Однако строгие они, за 1 задачу отшили

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