17 мая 2009 г.

Задачи на собеседованиях: односвязные списки

Простая задача на понимание односвязных списков. Однако, несмотря на то, что задача несложная, многие кандидаты пугаются и начинают путаться в показаниях.

Дано: односвязный список N1->N2->N3->...->Nn и указатель на его голову N1.

Нужно: развернуть список за один проход так, чтобы стало Nn->Nn-1->Nn-2->...->N1.
Автор White Knight , опубликовано в 16:43
Теги: , ,

6 комментариев:

  1. Sergey Rozovik18 мая 2009 г. в 13:07

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

    ОтветитьУдалить
  2. White Knight18 мая 2009 г. в 17:21

    Да, я согласен. Собеседование - это всегда стресс.

    ОтветитьУдалить
  3. Анонимный16 октября 2010 г. в 23:23

    Опублекуйте, пожалуйста, ответ. Мне как новичку было бы полезно знать;)

    ОтветитьУдалить
  4. White Knight17 октября 2010 г. в 17:17

    Задача довольно простая. Нужно перебрать все элементы списка и на каждой итерации изменять значение поля next, чтобы оно указывало на предыдущий элемент.

    ОтветитьУдалить
  5. Анонимный29 января 2011 г. в 19:13

    Задача на самом деле совсем не простая. Уважаемый, White Knigh, Вы сами-то пробовали сесть и написать код, который решает эту задачу?

    Если у нас есть уже реализованный SinglyLinkedList, то задача сведется примерно к следующему:

    for(int i=0, size=list.size(); i<list.size; i++) {
    list.add(list.pop());
    }

    Но! Покажите мне существующую в Java реализацию настоящего односвязного списка?!

    Итого, задача про разворот односвязного списка сводится к реализации односвязного списка! А это уже совсем-совсем другое дело.

    Вот Вы говорите: "Нужно перебрать все элементы списка и на каждой итерации изменять значение поля next". Это же чушь!

    Класс Entry лежащий, например, внутри LinkedList (двунаправленный связный список) - приватный! И взять от него next невозможно!

    Итого: этот вопрос идиотский. На собеседовании его задавать нельзя! Можно спросить "Что такое связанный список?" и выяснить, знает ли кандидат базовые структуры данных.

    ОтветитьУдалить
  6. White Knight29 января 2011 г. в 21:42

    Уважаемый, Анонимный.
    Эта задача именно на знание структуры данных под названием "односвязный список" и содержит все необходимые для решения условия. Её на собеседованиях задают как раз после ответа на вопрос "Что такое связанный список и как он устроен?" :) Решить эту задачу можно даже в псевдокоде. Попробуйте отбросить эмоции и временно забыть свои глубокие познания языка Java и взглянуть на задачу с точки зрения базовых структур данных.

    ОтветитьУдалить

Подписаться на: Комментарии к сообщению (Atom)