Порридж В Ко-ливинге
Ногие знаю про lower_bound, но питонисты что-то не знают о https://docs.python.org/3/library/bisect.html
Viktor
Одно дело знать и за час вспомнить алгоритм. Другое вот эти цифры гонять по 5-10 заданий за 1.5 часа
кажется, что вспоминать алгоритм надо околонулевое количество раз относительно того когда надо просто писать нормальный код, внимательно.
Null
Коллеги напомнили, что скоро (старт 1 декабря) очередной https://adventofcode.com/ — участвуете? В прошлом году писали «свой космический корабль», любопытно, что будет в этом.
Viktor
Лол, что это?
а ты посмотри что было в прошлом году. там реально классно. ты каждый день постепенно пишешь систему в которой новые требования появляются.
Viktor
начинаешь с набора инструкций, потом на этом ассемблере реальные программы, и так дальше и дальше
Viktor
и все это привязано было к космической тематике
Viktor
прикол в том, что ты строил компьютер для космического корабля
Viktor
ну, только отчасти. на самом деле нет. потому что там есть смысл 😃
Viktor
то есть ты решаешь день за днем «одну большую задачу»
Viktor
а не просто левый набор непонятный
Порридж В Ко-ливинге
Уф, очередное испытание для моей силы воли
Evgeniy
то есть ты решаешь день за днем «одну большую задачу»
Более приближенная к реальности ситуация
Viktor
Вот как пример че чувак творит в экселе https://www.youtube.com/watch?v=7drel2F0_5o
Viktor
есть целый редит посвящённый этому челенджу https://www.reddit.com/r/adventofcode/
Viktor
с завтрашнего дня там снова начнётся жизнь
Viktor
Более приближенная к реальности ситуация
именно. классно, что ты с каждый днем погружаешься все больше и больше в контекст. начинаешь понимать что ты делал не так в прошлые дни и как тебе это мешает. и как надо было делать.
Evgeniy
Интересно, порешаю 👍
Viktor
В чем прикол этого сайта? Какие там задачи? Можешь расскажать вкратце пожалуйтса
раз в день по задаче, но важно, что они все органично связаны в один проект. каждый следующий день открывает новый контекст.
Viktor
Олимпиадные задачи или проект?
в прошлом году было так: задача написать компьютер для космического корабля. сперва пишет набор инструкций, потом программы поверх него. в итоге, начинаем писать на нем игры, как вот тот чувак в экселе выше.
Порридж В Ко-ливинге
Интересный ник
Порридж В Ко-ливинге
Как сделать код еще меньше? 🧐 class Solution: def lengthOfLIS(self, nums: List[int]) -> int: tails = [float('inf')] * len(nums) size = 0 for x in nums: i = bisect_left(tails, x) tails[i] = x size = max(i + 1, size) return size
Порридж В Ко-ливинге
куда уж ещё меньше? 😃
Это питон, хочет еще больше выразительности
Порридж В Ко-ливинге
Господи, как же наверное bisect_left экономит время на олимпиадах. Казалось бы, ну минуту лишнюю. А это зарешивает
Viktor
Господи, как же наверное bisect_left экономит время на олимпиадах. Казалось бы, ну минуту лишнюю. А это зарешивает
каждый раз писать бинарный поиск с нуля такое себе занятие, конечно экономит
Порридж В Ко-ливинге
каждый раз писать бинарный поиск с нуля такое себе занятие, конечно экономит
Причем в JS приходится таких заниматься. Вроде ничего для бинарного поиска нет(
Viktor
там богатая стандартная библиотека, есть все контейнеры и все стандартные алгоритмы
Viktor
можно быстро юзать
Evgeniy
https://leetcode.com/problems/sliding-window-maximum/discuss/549248/C-O(n)-time-O(n)-space
Оказалось, эта задача была позавчера в ноябрьском челленже
Viktor
Оказалось, эта задача была позавчера в ноябрьском челленже
они их крутят по второму разу уже, наверное.
Viktor
каждый месяц челендж, лол.
Evgeniy
они их крутят по второму разу уже, наверное.
Некоторые задачи повторяются, да
Порридж В Ко-ливинге
они их крутят по второму разу уже, наверное.
Лол, в майском 2 задачи повторялись с апрельским вроде
Viktor
Fred @IsabellePlume Hunzoe Japa 👋 напоминаю, что кто добавляется со странными именами и молчит — тот бот. хорошо было с антиспамом 😃
Порридж В Ко-ливинге
Меня больше всего этот акк напрягает
Порридж В Ко-ливинге
https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/discuss/955021/O(NlogN)-3-liner-solution-with-7-lines-helper-funcition
Порридж В Ко-ливинге
Наверное дерьмово объяснил, но как смог( Надо учиться объяснять
Порридж В Ко-ливинге
Решил невероятно громозкую для литкода задачку # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def listLen(self, head: ListNode) -> int: l = 0 while head: l += 1 head = head.next return l def step(self, head: ListNode, steps: int) -> ListNode: for _ in range(steps): head = head.next return head def merge(self, tip: ListNode, step: int) -> None: l = r = step head1, head2 = tip.next, self.step(tip, step + 1) if not head2: return while l + r > 0: if not r or (l and head1.val < head2.val): tip.next = tip = head1 head1 = head1.next l -= 1 else: tip.next = tip = head2 head2 = head2.next r = r - 1 if head2 else 0 tip.next = head2 return tip def sortList(self, head: ListNode) -> ListNode: length = self.listLen(head) root = ListNode(0, head) for i in range(int(length ** 0.5)+1): step = 2 ** i tip = root while tip: tip = self.merge(tip, step) return root.next
Порридж В Ко-ливинге
https://leetcode.com/problems/sort-list/
Sergei
По поводу зп, недавно чел (ex uber, ms, skyscanner) рекомендовал сайт, где данные по зп точнее для европы, т.к. glassdoor в основном по штатам. https://www.levels.fyi/
Sergei
Это который прагматикинженер блог, может попадались на его статьи
Sergei
Вообще дельный чел, написал книгу по тому как правильно резюме делать и поднял за месяц больше $15 тыс на ней и ушел с убера писать другую
Sergei
Для не трудоустроенных программистов бесплатно можно забрать, кстати https://thetechresume.com/
V
первый день advent of code открылся — https://adventofcode.com/2020/day/1 кто участвует? )
Lynn «Кофеман»
Lynn «Кофеман»
Решил тупо в лоб за N^2. А какие могут быть идеи, кроме предварительной сортировки (и соответственно N log N)? PS. Я понимаю что это лёгкая разминочная задачка =)
Порридж В Ко-ливинге
Sergei
Это была ошибка
Он не думал совсем на ней зарабатывать, ушел не из-за книги, а просто хочет делать что-то свое. Денег, я думаю, он уже прилично заработал за годы в компаниях.
Sergei
Опять же многие идут в консалтинг, потому что можно больше заработать и получить больше свободы, а не быть "винтиком" в большой компании
Порридж В Ко-ливинге
А, с такой логикой да
Lynn «Кофеман»
Я так понимаю, что это первая же задача на литкоде — two sums — которая решается с индексов в О(н)
Там в примерах массив отсортирован (хотя нигде этого не сказано), а в AoC несортированный
V
Это не важно
Roman
У вас тоже лежит со словами “We'll be right back!”?
Lynn «Кофеман»
Это не важно
и как в неотсортированном можно найти пару за O(n)?
Roman
и как в неотсортированном можно найти пару за O(n)?
бежишь по всему массиву входных данных. проверяешь на условие (target - input[i]) in m, где m - хэш-таблица с ключами - числами из массива входных данных, а значение - индекс в массиве входных данных. Если выражение возвращает true, то есть по ключу был найден твой индекс, тогда возвращаешь input[i]*input[m[target - input[i]] КА, то есть твоя пара это (input[i], input[m[target-input[i]]); иначе кладешь в хэш-таблицу m[input[i]] = i.
Иван
А у меня чет подзависло
Иван
Roman
тогда только сортировкой и двумя индексами, но это будет за O(nlogn)
Порридж В Ко-ливинге
О, отвисло вроде
Roman
Иван
О, отвисло вроде
Да и правда)
Lynn «Кофеман»
ну можно попробывать counting sort, но не уверен)
Кстати да, у нас числа все целые и нас интересуют числа не более 2020 (а на самом деле там большИх и нет)
Порридж В Ко-ливинге
и как в неотсортированном можно найти пару за O(n)?
Лол, класическая задачка же. O(N) O(N) или O(N logN) O(1)
Порридж В Ко-ливинге