Порридж В Ко-ливинге
Я вот вообще не удивлюсь, что 80% кода в FAANG пишет 20% программистов
Ilia
Я вот вообще не удивлюсь, что 80% кода в FAANG пишет 20% программистов
Так это нормально. Написанные продукты тоже продавать надо и монетизировать )
Viktor
По факту да. Программисты в FAANGе только наверное первый год карьеры пишуть немного, а потом 90% их деятельности это внутренние митапы, внещние конференции и посты о том "как я попал в FAANG", "как круто в FAANG", "о ужас, целую неделю не придумывали новый гендер" и "о, классный стартап" который купит этот FAANG
да не, на самом деле это чисто статистически нереально. 99% людей просто работают, живут, круты и не говорят об этом. Потому что программирование это не вся их жизнь.
Viktor
Такое впечатление создаётся из-за ютуберов, но их очень мало ж относительно всех разработчиков фаанга.
Viktor
Но идея хайпануть не новая, тот же Клемент построил свой алгоэксперт ровно на этом. Всякие техлиды хайпятся как не в себя.
Порридж В Ко-ливинге
Крутая задачка, O(N^2) не прокатывает
https://leetcode.com/problems/word-ladder/
Evgeniy
На 22 тесте выдаёт TLE
Alex Azarov
Слушайте, а есть какой-то план или порядок в каком вы решаете задачи?
Я пока просто в разнобой или по подборкам в explore
Порридж В Ко-ливинге
Слушайте, а есть какой-то план или порядок в каком вы решаете задачи?
Я пока просто в разнобой или по подборкам в explore
https://leetcode.com/explore/interview/card/top-interview-questions-easy/
Порридж В Ко-ливинге
Я уже на Хард. Сижу туплю
Alex Azarov
А нужно ли хард решать?)
Мы всё-таки не на Staff Developer целимся
Порридж В Ко-ливинге
А нужно ли хард решать?)
Мы всё-таки не на Staff Developer целимся
Не знаю. Я просто подряд решаю
Порридж В Ко-ливинге
Надеюсь когда хард решу открою уже премиум и буду по компаниям решать
Evgeniy
Слушайте, а есть какой-то план или порядок в каком вы решаете задачи?
Я пока просто в разнобой или по подборкам в explore
Беру тему, которая интересна. А потом перехожу по Related Questions
Lynn «Кофеман»
Моя первая задачка на литкоде =)
Lynn «Кофеман»
Порридж В Ко-ливинге
((9(
Lynn «Кофеман»
Обходом в ширину
Порридж В Ко-ливинге
Просто по тому, что 1 символ меняется?
Lynn «Кофеман»
Я не делал дерево.
Порридж В Ко-ливинге
За какую сложность? Я за O(N^2), но TLE
Lynn «Кофеман»
Порридж В Ко-ливинге
Я не делал дерево.
Ну, я тоже. Я имею ввиду по какой логике шли? Сравнивали что слова на 1 букву отличаются? Как сравнивали?
Lynn «Кофеман»
Вот эта функция выше из слова hit делает регулярку
/^(?:.it|h.t|hi.)$/ которая матчит все слова отличающиеся на одну букву.
Порридж В Ко-ливинге
Вот эта функция выше из слова hit делает регулярку
/^(?:.it|h.t|hi.)$/ которая матчит все слова отличающиеся на одну букву.
Да, я точно так же, только без регулярки а ручками.
А вы в итоге весь массив каждый раз регуляркой проверяли?
Lynn «Кофеман»
Нет. Я запихал его в Set. И выкидывал уже пройденные слова
Порридж В Ко-ливинге
Порридж В Ко-ливинге
Нет. Я запихал его в Set. И выкидывал уже пройденные слова
Ну да, это сам собой. Тогда это просто чудо оптимизации, т к. На питоне у меня тоже самое, но TLE
Lynn «Кофеман»
Возможно.
Порридж В Ко-ливинге
class Solution:
def diffOneChar(self, w1: str, w2: str) -> bool:
return sum(ch1 != ch2 for ch1, ch2 in zip(w1, w2)) == 1
def ladderLength(self, b: str, e: str, w: List[str]) -> int:
stack = [b]
check = set(w)
counter = 1
while stack:
counter += 1
temp = []
for word in stack:
for checkWord in check:
if self.diffOneChar(word, checkWord):
temp.append(checkWord)
stack = temp
check -= set(stack)
if e in stack:
return counter
return 0
Lynn «Кофеман»
Ну по сути у меня такой же алгоритм. Возможно тут много лишних действий. Например в diffOneChar можно сэкономить если написать честный цикл и выходить из него как только разница больше одного, а не перебирать все буквы. Ну и всякие вычитания множеств это же по сути тоже скрытый цикл
Порридж В Ко-ливинге
Господи, питон можно любить хотя бы за то, что ВСЕ контейнеры имеют похожий интерфейс с in
Хоть 123 in [123,456,789]
Хоть 123 in {123,654,789}
Хоть 123 in {123: 6, 543: 8, 888: 0}
Порридж В Ко-ливинге
Ну по сути у меня такой же алгоритм. Возможно тут много лишних действий. Например в diffOneChar можно сэкономить если написать честный цикл и выходить из него как только разница больше одного, а не перебирать все буквы. Ну и всякие вычитания множеств это же по сути тоже скрытый цикл
Насчет diffOneChar правда. Насчет вычитания множест одно и тоже получается по сложности
Lynn «Кофеман»
Ну я выкидывал из множества сразу как находил. Правда в js это безопасная операция, а как в питоне я не знаю
Порридж В Ко-ливинге
Ну я выкидывал из множества сразу как находил. Правда в js это безопасная операция, а как в питоне я не знаю
Ошибку кидает. Я так пробывал
Roman
Крутая задачка, O(N^2) не прокатывает
https://leetcode.com/problems/word-ladder/
Решил пуская bfs с начала и с конца
Roman
Гоу
Порридж В Ко-ливинге
На плюсах прошло:
https://pastebin.com/AtbKkSLQ
Порридж В Ко-ливинге
Вот еще одно преимущество питона в том, что кодик маленький, не загруженный ничем лишним, и его можно в чатик кинуть, и впринципе нормально будет.
А если плюсовой код кидать, то это капец. Там будет плато текста со скобками и прочей дичью
Порридж В Ко-ливинге
Ну по сути у меня такой же алгоритм. Возможно тут много лишних действий. Например в diffOneChar можно сэкономить если написать честный цикл и выходить из него как только разница больше одного, а не перебирать все буквы. Ну и всякие вычитания множеств это же по сути тоже скрытый цикл
Не помогло:
def diffOneChar(self, w1: str, w2: str) -> bool:
count = 0
for i in range(len(w1)):
if w1[i] != w2[i]:
count += 1
if count > 1:
return False
return bool(count);
Lynn «Кофеман»
Ну может питон просто медленный? 😀
Попробуй поиск с двух сторон, хотя писать его будет сложнее
Порридж В Ко-ливинге
Ну может питон просто медленный? 😀
Попробуй поиск с двух сторон, хотя писать его будет сложнее
Да нет, выведу в отдельную функцию, и все.
Там правда будет edgecase
Viktor
За какую сложность? Я за O(N^2), но TLE
Проверь не попадаешь ли там в цикл в графе. Не забываешь отмечать посещённые узлы?
Порридж В Ко-ливинге
Проверь не попадаешь ли там в цикл в графе. Не забываешь отмечать посещённые узлы?
Не не не, проьлема исклбчительно в скорости. Падает на очень большом тесте, остальные проходит
Порридж В Ко-ливинге
Я уже разобрался на плбсах
https://pastebin.com/AtbKkSLQ
Viktor
Не не не, проьлема исклбчительно в скорости. Падает на очень большом тесте, остальные проходит
Сейчас кину свой вариант. Я честно построил граф и честно его в ширину обошёл. Я не такой умный как @alexeyten
Viktor
Подучилось громоздко и многословно
Viktor
Порридж В Ко-ливинге
Сейчас кину свой вариант. Я честно построил граф и честно его в ширину обошёл. Я не такой умный как @alexeyten
Так мы все графы сроим, лол.
Просто сразу его и обходим и не нужные старые узлы выкидываем
Viktor
А нужно ли хард решать?)
Мы всё-таки не на Staff Developer целимся
Да вот в фаанге планка одна у всех по алгоритмам. Разве что стажёрам задачи попроще, а на младшего и мидла медиум и хард 🤷🏽♂️
Viktor
Так мы все графы сроим, лол.
Просто сразу его и обходим и не нужные старые узлы выкидываем
https://gist.github.com/vitkarpov/d0c24957b8694cbd7a00f870cb0c643d
Viktor
Так мы все графы сроим, лол.
Просто сразу его и обходим и не нужные старые узлы выкидываем
вот мне и кажется странным что ж на питоне не проходит 🤔
Viktor
по идее, должно
Viktor
Слушайте, а есть какой-то план или порядок в каком вы решаете задачи?
Я пока просто в разнобой или по подборкам в explore
В свое время пробовал сделать список тем + а-ля "must see задач" — https://docs.google.com/document/d/11AdpIPEfGasd6kmrVCm1uR_Yo-VQVmSViZ6oDJCMKYA/edit#heading=h.4a89054n4qjv
Порридж В Ко-ливинге
Да вот в фаанге планка одна у всех по алгоритмам. Разве что стажёрам задачи попроще, а на младшего и мидла медиум и хард 🤷🏽♂️
Ну не, фронтам можно я думаю на медиуме остановиться
Это всяким дтким бэкам и ИИшникам наверное харды
Viktor
Ну не, фронтам можно я думаю на медиуме остановиться
Это всяким дтким бэкам и ИИшникам наверное харды
да может и на изи. я не очень понимаю как от компании к компании это отличается.
Порридж В Ко-ливинге
Хотя в гугол и фронтов могут хардами кошмарить
Viktor
Хотя в гугол и фронтов могут хардами кошмарить
политика такая, мол, не нанимаем фронтов, а нанимаем инженеров, которые потом от избытка ума ангуляр будут делать 🤷
Viktor
чтобы Бену было что хейтить на ютубе 😉
Порридж В Ко-ливинге
политика такая, мол, не нанимаем фронтов, а нанимаем инженеров, которые потом от избытка ума ангуляр будут делать 🤷
Ага, могут себе позволить, т.к. самая крутая и богатая (в плане IT) компания в мире
Viktor
Ага, могут себе позволить, т.к. самая крутая и богатая (в плане IT) компания в мире
крутая вопрос, а вот богатая это верно. можно деньги жечь.
Viktor
Так мы все графы сроим, лол.
Просто сразу его и обходим и не нужные старые узлы выкидываем
я ничего не выкидывал и сразу не обходил. построил честный граф и запустил bfs втупую 😄
Viktor
class Solution:
def diffOneChar(self, w1: str, w2: str) -> bool:
return sum(ch1 != ch2 for ch1, ch2 in zip(w1, w2)) == 1
def ladderLength(self, b: str, e: str, w: List[str]) -> int:
stack = [b]
check = set(w)
counter = 1
while stack:
counter += 1
temp = []
for word in stack:
for checkWord in check:
if self.diffOneChar(word, checkWord):
temp.append(checkWord)
stack = temp
check -= set(stack)
if e in stack:
return counter
return 0
что-то мне кажется сомнительной история с stack = temp, копируешь под капотом и я не очень понимаю какая сложность в итоге.
Lynn «Кофеман»
N^2
В худшем случае ты всё равно сравнишь все со всеми
Порридж В Ко-ливинге
что-то мне кажется сомнительной история с stack = temp, копируешь под капотом и я не очень понимаю какая сложность в итоге.
Это питоновский который TLE
O(N^2)
Порридж В Ко-ливинге
N^2
В худшем случае ты всё равно сравнишь все со всеми
В худшем N*N*L, где L - средняя длина строки
Lynn «Кофеман»
L же константа и в оценке не учитывается
Порридж В Ко-ливинге
L же константа и в оценке не учитывается
Там же не оговорено какой длины слово может быть вроде
Viktor
Это питоновский который TLE
O(N^2)
Ага. Ясно. Я почему упустил суть разговора и подумал, что ты не понимаешь почему TLE, хотя сам же говорил выше, что квадрат не пройдёт.
Порридж В Ко-ливинге
Ага. Ясно. Я почему упустил суть разговора и подумал, что ты не понимаешь почему TLE, хотя сам же говорил выше, что квадрат не пройдёт.
Прикол в том, что у @alexeyten тоже квадрат, но на JS и он проходит
Порридж В Ко-ливинге
Очень похожи алгоритм.
Viktor
В худшем N*N*L, где L - средняя длина строки
Можно все же максимальная, а не средняя? Потому что оценка сверху по смыслу