Как объединить два отсортированных списка на Python: задача LeetCode.

Альбина раскрывает секреты решения задачи, которую она дает на собеседованиях. Суть задачи заключается в том, что нужно объединить два отсортированных списка. На удивление, не все справляются с этим заданием.
Ссылка на задачу: leetcode.com/p...
GitHub репозиторий github.com/val...
Актуальные вакансии: career.technok...
Telegram: t.me/technokratos
ВКонтакте: technok...
#LeetCode #python #АлгоритмическаяКачалка #Программирование #Алгоритмы

[@user-uq8xs5tr1m]

Всех смутила структура данных - список) а так, алгоритм рабочий)

[@olegbalandin6856]

Я бы обратил внимание, что при улучшении можно было бы вынести повторяющиеся 4 раза код(где меняются циферки 1-2) в отдельный метод... это бы сэкономило более 17 строк кода... при этом код бы стал более красивым, связным... Но на скорость работы сильно не повлияло бы конечно...

[@Alcoholdehydrogenas]

Ничего не понял, но очень интересно

[@user-ui3oj7kv1c]

Чем будет отличаться результат при слиянии списков и сортировке?

[@leonid1753]

Было бы интересно посмотреть на то, как можно улучшить алгоритм, не обязательно даже самому думать, просто посмотреть решения, и объяснить почему это так работает. А то уже в двух роликах вы рассматриваете не самые эффективные алгоритмы.

[@PythonHedgehog]

Это учебные алгоритмы для совсем зеленых. Если интересно посмотреть что-то посложнее, то поищите в интернете алгоритм timsort например.

[@RaptorT1V]

@@PythonHedgehog кста, именно timsort работает под капотом у sorted() в Python

[@user-pq8oo9ye7h]

А разве не нужно делать проверку на то что и последующие элементы второго списка не больше(не меньше) чем текущее значения первого списка? Прим.: 1, 2, 4 1, 7, 9. Ведь при то реализации, что показана на видео не будет сортировки, и запишется 1, 2 ,7, 4, 9?

[@designed6102]

Не досмотрел ещё видос, но по-сути нормальный алгоритм должен двигать курсор дальше и опять проверять меньше ли первый элемент чем второй

[@qulinxao]

код проще если начальный result - сделать пустым элементом (any,None) тогда при выводе выдаем result.Next а вообще через условные выражение решается в одну строку: return list1 if not list2 else list2 if not list1 else ListNode(list1.val,self.mergeTwoLists(list1.next,list2)) if list1.val

[@andreysergeev5916]

Это решается намного проще class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: head = ListNode() current = head while list1 and list2: if list1.val < list2.val: current.next = list1 list1 = list1.next else: current.next = list2 list2 = list2.next current = current.next current.next = list1 or list2 return head.next

[@supreltd]

так же решил, только при проверке на наличие элементов в списке после цикла, использовал тернарник.

[@qrthack]

Привет, у меня такой вопрос, коммерческого опыта нет, знаю C, Python, люблю Computer Science. Хочу в backend, выбираю между Java, C#, Golang что посоветуешь, и почему? интересно твое мнение.

[@Boatengn1prince]

Если ты еще не пошел в дворники, то выбор очень прост. Посмотри и проанализируй рынок

[@user-vt7nf4kc2k]

Я, конечно все понимаю, но в задаче не сказано, что нельзя использовать всю мощь языка Python. Поэтому мне не совсем понятны подобные решения и тем более то, что не каждый мидл может это решить. Можно, конечно писать длинный код, но все решается в 11 строк кода с учетом измерения времени выполнения кода. Может быть я действительно чего-то не понял? Может быть действительно нужен некий изврат и притвориться, что у языка нет встроенных функций для быстрого и качественного решения подобной задачи? Я написал решение с условием, что списки могут быть и не отсортированы. Поправьте меня, если я не прав, пожалуйста class Solution: def mergeTwoLists(self, list1, list2): list3 = list1.copy() list3.extend(list2) print(sorted(list3)) # print(list3) import time start = time.time() sol = Solution() sol.mergeTwoLists(list1 = [1, 2, 4], list2 = [1, 3, 4]) finish = time.time() - start print(finish)

[@user-uv8ef8sn6k]

Слияние уже сортированных списков по сложности проще чем сортировка одного общего списка. Задача именно так поставлена, а если не обращать внимание на отдельные слова в постановке, то зачем браться за решение :)

[@user-vt7nf4kc2k]

@@user-uv8ef8sn6k в моем коде нет разницы, сортирован список, или нет. Результат будет одинаков

[@plathardstuck28]

Что за собесы где можно обычные питонячьи списки?

[@technokratosTV]

Мы и сами в шоке, как так получается. Обычно в качестве ответа мы видим вот это: return sorted(list1 + list2) 🤷‍♂️🤷‍♂️

[@hey-rg9lk]

ну наверно если ты проходишь собеседование на позицию питониста, то задачки будешь решать на питоне и пользоваться структурами и алгоритмами которые тебе предоставил язык?

[@plathardstuck28]

@@hey-rg9lk Никто щас на собесах не спрашивает за списки и даже за deque , потому, что подразумевается что кандидат уже освоил это всё. Спрашивают односвязный список, бинарные деревья, графы и тому подобные вещи. Если приходится использовать встроенные списки, то задача про что-то более сложное (матрица, треугольник паскаля) и подразумевает что ты умеешь работать со списками на уровне сортировки значений.

[@plathardstuck28]

@@technokratosTV может меня на собес позовёте? ;) я правда только 4 месяца учусь и не освоил такие вещи как докер, рэббит и т.п., но в базовые алгоритмы типа сортировки слиянием и пузырьком, просчёта бинарных деревьев умею :)

[@hey-rg9lk]

@@plathardstuck28 в том то и дело что linked list кроме как алгоритмических задач нигде не будет использоваться в боевых решениях) а если обходить те же деревья или графы, мы снова приходим к тому что нужно использовать очереди