Комментарии 33
Буду благодарен за обратную связь, критика приветствуется, желательно аргументированная!)
А где векторизация? Где тестирование на терабайтных списках?....
https://habr.com/ru/articles/682332/ & https://habr.com/ru/articles/688874/
А кто обиделся и ставит минусы?))
Первое и самое главное: этическая сторона дела. Задача на интервью предназначена для проверки самостоятельного мышления соискателя. Выкладывать её успешное решение на всеобщий обзор - это вносить смещение в объективность следующих интервью. Проще говоря: автор выложил спойлер.
Сама по себе задача очень простая (на литкоде имеет уровень easy). Это значит, что обсуждать её есть смысл, когда есть что добавить интересного к эталонному решению. Ну вот выше уже упомянули про терабайтные наборы. Или, например, обсудить существенно разные реализации (в существенно разных языках - или в разных парадигмах на одном и том же питоне). Или ещё что-нибудь... Иначе это как-то не соответствует заявленному автором званию Senior.
Уже сам по себе старт: "давайте сделаем дефолтную реализацию с O(n) дополнительной памяти, а потом разгоним" выглядит странно. Ну ок, тогда давайте поиграем в другой жанр, в ненормальное программирование: найти самый медленный и прожорливый алгоритм? Есть же соревнование в замедлении сортировки, почему бы и в замедление разворота списка не посоревноваться?
В общем, решение на пятёрочку, а статья на двоечку с плюсом. За это и минусы. А не за мифические обидки.
Окей
Мне когда-то попалась эта задача и я не знал как решить, теперь решил рассказать другим как это сделать, визуальное объяснение, каждому подойдет свой вариант подачи материала, надеюсь моя подача тоже будет полезна кому-то. Причем тут мое звание Senior? Где в задаче это упоминается?) Если я Senior, то должен объяснять только hard задачи? Не вижу логики
Если странно, предложите идею как сделать лучше
Я не про минус на статью писал, а про минус на каждый мой коммент) Если подскажете как сделать статью лучше, пишите. Не про террабайты, а именно эту задачу с ограничениями из литкода
Ну блин, если бы вам предложили решить какую-нибудь простенькую задачку по математике, которую почему-то вы забыли, как решали в 9 классе, - то тоже бы расписали? Для 9-классника это норма, для 8-классника это подвиг, для сеньора - это детство.
Я на ютубе встречал каналы по математике с таким контентом, но их ведут репетиторы для школьников, там очень адресная аудитория.
И, на мой взгляд, "один ролик/пост - одна задачка" - это хлебный мякиш. Либо задача должна быть со звёздочками, либо охват предмета должен быть большой: например, класс задач и системный подход к ним, или всевозможные закоулки одной задачи.
Вот, например, алгоритмы бисекции содержат такие закоулки (граничные условия), и наивная реализация "с листа" у многих программистов получается с багами. Можно ли такое сказать про переворот списка?
Я-то, как раз, могу раскрыть тему. Но статью писать мне, пардон, лень. Это надо план изложения продумать и всё такое.
Могу накидать направления работы:
как решать эту задачу с мутабельными и иммутабельными структурами (с мутабельными уже показано)
виды циклов и рекурсий
выразительные возможности разных языков (а не единственное решение в духе "на любом языке можно писать на фортране")
Есть же профессора, которые сидят на ютуб и объясняют как решать задачи 9-го класса и таких очень много, на ваш взгляд это глупо это делать? Но это ваш взгляд.
Для каждого контента свой потребитель, если вам нужны решения сложных задач, то либо решите сами и расскажите, либо ждите кого-то, кто это сделает)
Как решать задачИ - vs как решить задачУ. Я уже написал выше.
Решение этой задачи разными способами я привёл в комментарии, но кому-то оно не понравилось, - обиделся, наверное ;)
Ну а рассказывать решения конкретных задач с литкода - я считаю неэтичным. Может быть, если мне когда-то будет не лень, я расскажу некоторые общие подходы. Они там есть. Но период лютого увлечения литкодом у меня был пару лет назад.
Вообще же, литкод уровня медиум и хард - это такое олимпиадное программирование. Говнокодить write-only, лишь бы пролезло по ограничениям на производительность, - ради бога.
Один раз по приколу я сграбил все тестовые входные данные и написал табличное решение, и его засчитали, ахаха. Куда уж оптимальнее.
Решение этой задачи разными способами я привёл в комментарии, но кому-то оно не понравилось, - обиделся, наверное ;)
Если вы про этот комментарий https://habr.com/ru/articles/838270/comments/#comment_27203550 , то я не увидел там оптимизации, можете ткнуть пальцем в каком месте решение оптимальнее, чем второй решение в статье?
Ну а рассказывать решения конкретных задач с литкода - я считаю неэтичным. Может быть, если мне когда-то будет не лень, я расскажу некоторые общие подходы. Они там есть. Но период лютого увлечения литкодом у меня был пару лет назад.
ваше мнение, имеет место быть) но я в свое время смотрел как другие решают и это мне сильно помогло, решил тоже внести свой вклад.
Последние два абзаца я не понял к чему) ну и в принципе не понял негатива по отношению к этой статье, если вам она не полезна, то найдутся люди, которым она полезна. Если у вас есть конкретный фидбек, как можно сделать статью более полезной для НОВИЧКОВ, просьба написать, буду благодарен. Эта статья не рассчитана на тех, кто как семечки щелкает подобные задачи, коих тут много, насколько я понял и к сожалению они не видят дальше своего носа, думают, что если им все понятно, то и остальным должно быть)
А можно в перерывах между разворачиваниями списков, сделать нормальные фильтры?!
Просто покажу, как можно на ровном месте сделать чуть красивее.
def revert_sequential_and_verbose(head):
prev = None
while head:
tmp = head.next
head.next = prev
prev = head
head = tmp
return prev
def revert_using_tuple_assign(head):
prev = None
while head:
head, prev, head.next = head.next, head, prev
return prevА можно чуть изощрённее, - избавиться от цикла while на верхнем уровне
def iterate_single_linked(head):
while head:
#####################
# здесь был спойлер #
#####################
def revert_using_for_loop(head):
prev = None
for curr in iterate_single_linked(head):
curr.next, prev = prev, curr
return prev
def revert_using_reduce(head):
def op(prev, curr):
#####################
# здесь был спойлер #
#####################
return functools.reduce(op, iterate_single_linked(head), None)Разумеется, использование генераторов и ФВП (и даже кортежей) на питоне вносит лишние накладные расходы по сравнению с наивным строго последовательным "сишно-фортрановым" решением. Но, тем не менее...
Вот, что мы бы тут ожидали увидеть на хабре от автора.
Суть статьи ведь показать как решить просто и как решить оптимально, максимально доступным способом, не было цели показать изощренный вариант решения.
Если вы знаете как решить лучше - отлично, объясните данное решение, напишите статью, чтобы другие могли понять плюсы и минусы, вуаля
// head -> node1 -> node2 -> node3 -> nullptr
reverseList(Node* head)
{
// это будет это будет нового списка
// newHead = head
Node* newHead = head;
// следующий после головного узел
// headNext = node1
Node* headNext = head->next;
// временная переменная
Node* tmp;
// этот узел будет последним с развернутом списке
// head -> nullptr
head->next = nullptr;
while (headNext != nullptr) {
// запомним указатель "через узел"
// 1 tmp = node2
// 2 tmp = node3
// 3 tmp = nullptr
tmp = headNext->next;
// прицепляем головной узел к следующему за ним
// 1 node1 -> head -> nullptr
// 2 node2 -> node1 -> head -> nullptr
// 3 node3 -> node2 -> node1 -> head -> nullptr
headNext->next = newHead;
// делаем следующий после начала узел "головным"
// 1 newHead = node1
// 2 newHead = node2
// 3 newHead = node3
newHead = headNext;
// теперь то, что было "через узел", становится следующим
// 1 headNext = node2
// 2 headNext = node3
// 3 headNext = nullptr
headNext = tmp;
};
return newHead;
}Тоже самое на С. Тут комментариев больше чем кода. Просто. Оптимально. Минимум накладных расходов. Минимум кода (больше комментариев).
Все это решается в голове. Просто представляете что у вас есть картонные квадратики с номером узла и стрелочкой, выстроенные в определенном порядке (по стрелочкам). И начинаете их двигать так, чтобы порядок поменялся на противоположный.
P.S. до этого такую задачу не решал, написал первое, что в голову пришло пока читал. Потом уже увидел что такое решение уже было предложено.
P.P.S. сама по себе задача бессмысленная. Если вам нужно ходить по списку туда-сюда - есть двусвязные списки. С необходимостью разворачивать односвязный список за 30+ лет практики не сталкивался ни разу. Хотя со списками приходилось работать много в самых разных их реализациях.
И к чему вы это?) вы смогли решить это, круто, но есть тысячи других, кто не смог и им нужна помощь, среди них был и я когда-то.
Но на хабре всегда думают, что все всё знают)) ну или думаю, что если они знают, то не надо писать об этом для других
Если хотите помочь - ну предлагайте действительно хорошее решение. А не вот это вот с массивами.
Просто представьте, что вам надо развернуть список из 10 000 000 элементов...
Два поста с оптимальным (по простоте и эффективности) решением - оба с минусами.
там ведь два решения, один с массивом, а другой оптимальный, что не нравится?
мое второе решение даже проще, чем то, что вы написали выше
Ощущение, что прочли половину статьи и решили выплеснуть свое недовольство)
Либо даете аргументированный фидбек, либо пишете свою статью с блэк-джеком и шлюхами, все просто)
Параметры для оптимизации скажите. Вы ведь, как сеньор, знаете, что их несколько.
1) Скорость исполнения. Тут фортран и фортранный стиль рулят.
2) Устойчивость к ошибкам. Тут надо заметно сдвигаться в сторону функциональщины.
3) Читаемость и сопровождаемость. Посреди между фортраном и фп.
Движок литкода смотрит только на скорость исполнения. Но для задач уровня easy это вообще ни разу не является критерием. Можно, конечно, поучаствовать в олимпиаде "ваше решение выполнилось быстрее и сожрало меньше памяти, чем 99.99% других", но для питона перфтесты слишком шумят. А может, там сам тестовый стенд криво настроен и плохо изолирован. Сами убедитесь, запустите ваше решение десять раз и получите десять разных измерений.
Я сейчас запостил и ваше, и мои решения, - и внезапно мои оказались капельку быстрее.
Спасибо за интересные статьи. А что вы собираете делать дальше? 1) Вы станете евангелистом алгоритм собеседований Российских компаний? Т.е. всегда будете знать актуальные алгоритмические собеседования в Российские компании и публиковать их и разбирать их? 2) Или вы будете вести тренинги по алгоритмам в Российские компании?
В постановке еще не определено что должна возвращать функция reverse: это может быть как и оригинальный список с развернутыми указателями так и новый список с копиями элементов оригинального списка (оригинальный список при этом сохраняется в первичном состоянии).
В зависимости от этого и решения могут не все подойти из озвученных выше. А вот не озвученные могут как раз подойти.
Т.е. без доп памяти O(n) может и не обойтись. А неоднозначность постановки может привести и к спорным вариантам когда интервьюер предполагает одно а интервьюируемый - другое. Т.е. сам вопрос с подвохом....
Это литкод и уровень easy. Сгодится абсолютно любое решение.
Проверяльщик смотрит там лишь на то, чтобы поля val у списка результатов были равны ожидаемым. Типизация утиная, можно вместо ListNode вернуть TsilEdon - и он сожрёт.
На эрланге в принципе не получится вернуть не копию. А на питоне можно и так и этак.
Причём стресс-теста для этой задачи нет, O(n) по памяти отлично проходит.
А вот алгоритмом маляра Шлемюэля я проверяльщика не удосужился проверить, хотя думаю, что и O(n^2) по времени тоже пролезет, ну будет в общем зачёте первое место с конца.
Решение задачи с собеседования Reverse Linked List [+ ВИДЕО]