Более 12 лет опыта в программировании. Более 10 лет активного участия в интервью как интервьювер и как соискатель. Я бы даже смог бы написать книгу на этот счет. Я знаю много характерных задач, читал много книг, учил других. Данная задачка всегда была одной из самых тривиальных. Но вчера случился ступор. Пришел на первое интервью, в хорошем настроении, выспавшийся, даже на улице светило солнце. Мы нормально познакомились с интервьювером, поболтали немного ни о чем, и, когда пришла пора написать технических вопросов, меня попросили сделать Reverse Single Linked List. Я обрадовался, ведь я это делал много раз до этого — почти всякий раз как проходил куда-либо интервью. И я начал довольно бодро. Задал кучу сопутствующих вопросов, объяснил алгоритм "на пальцах". И потом начал кодировать на доске. Опыт работы с доской также у меня богатый, так что ничего не предвещало беды. Но спустя несколько строчек у меня случился невероятный ступор — в голове смешались все мысли. Deadlock. Полнейший провал памяти и сознания. Через пять минут бормотания я решил стереть все с доски и начать все заново. Интервьювер уже начал недобро на меня коситься. Я понял, что я только что заработал заочно — "no hire", но все же попытался написать код правильно. И опять ступор. Теперь уже из-за расстройства по поводу заочно проваленного интервью. Мне было стыдно. Хотелось провалиться под землю. Хотелось убежать из офиса и ... В общем, бред какой-то.
Никогда такого не было. Что-то во мне сломалось.
А у Вас бывало такое? Как Вы фокусируете мысли на интервью, если случился ступор?
Здравствуйте, SemiCoder, Вы писали:
SC>сделать Reverse Single Linked List.
SC>Я обрадовался...И потом начал кодировать на доске.
Ошибка в последнем предложении.
Не нужно сразу начинать кодировать — сначала подумать, а лучше — нарисовать, особенно если не помните решение задачи наизусть.
Задача довольно необычна т.к. в большинстве случаев используется двунаправленный список.
Кодинг сразу — ненужный выпендрёж. Более того, я бы спросил, что мы вообще пишем, внешний код по отношению к списку, или метод списка?
Потом бы обязательно представил, или написал то, как будет выглядеть элемент списка.
class SingleLinkedListNode<T>
{
public T Value;
public SingleLinkedListNode<T> Tail;
}
Если вот так нарисовать, то сразу станет очевидным, что голову в хвост засовывать — ошибка.
| | Скрытый текст |
| | SingleLinkedList<AnyT> TargetList;
{
SingleLinkedListNode tail = TargetList.Tail;
while (tail != TargetList.head)
{
LinkedListNode head = TargetList.Head;
TargetList.Add ( head );
TargetList.RemoveNode ( head ); //Предполагаем, что поиск нода начинается с головы.
}
}
|
| | |
Вот так похоже на правду, но как-то коряво...
SingleLinkedList<AnyT> TargetList;
{
SingleLinkedList<AnyT> result = new SingleLinkedList<AnyT>();
while (TargetList.Head != null)
{
result.Add(TargetList.Tail)
TargetList.RemoveNode ( TargetList.Tail );
}
}
В конце-концов смотрим на рисунок и пишем метод:
public void Reverse()
{
SingleLinkedListNode<T> tail = m_head;
LinkedListNode head = tail;
while (m_head != null)
{
SingleLinkedListNode<T> tmp = new SingleLinkedListNode<T>();
tmp.Value = m_head.Value;
tmp.Tail = head;
head = tmp;
RemoveHead();
}
}
Кстати, двунаправленный список может быть написан так, что его реверс будет иметь сложность O(1).
SC>>сделать Reverse Single Linked List.
SC>>Я обрадовался...И потом начал кодировать на доске.
Ф>Ошибка в последнем предложении.
Ф>Не нужно сразу начинать кодировать — сначала подумать, а лучше — нарисовать, особенно если не помните решение задачи наизусть.
Ф>Задача довольно необычна т.к. в большинстве случаев используется двунаправленный список.
Я обрадовался, ведь я это делал много раз до этого — почти всякий раз как проходил куда-либо интервью. И я начал довольно бодро. Задал кучу сопутствующих вопросов, объяснил алгоритм "на пальцах". И потом начал кодировать на доске.
Ф>Кодинг сразу — ненужный выпендрёж. Более того, я бы спросил, что мы вообще пишем, внешний код по отношению к списку, или метод списка?
не было кодинга сразу.
Ф>Потом бы обязательно представил, или написал то, как будет выглядеть элемент списка.
аналогично.
