Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 5
×

Решаем задачи с LeetCode

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Привет, меня зовут Павел Дмитриев и помимо мобильной fullstack-разработки, я являюсь одним из менторов в школе компании PostIndustria, где мы помогаем студентам IT-специальностей прокачать свои навыки. За несколько лет стало понятно, что главное требование к потенциальным обучающимся — это умение мыслить алгоритмически, именно это является залогом успешного обучения. Как же проверить потенциальных кандидатов по этому параметру?

FizzBuzz, конечно, задание показательное, но очень уж набившее оскомину. Где взять больше интересных задач? Память сразу же подкидывает главное «хранилище» программистских задачек, давно ставшем синонимом подготовки к собеседованиям, LeetCode. В этой статье я дам несколько советов о том как начать «прокачивать» свои скилы на LC и покажу разные варианты решения нескольких задач на Python.

Знайте возможности языка

Обычно на собеседованиях целью решения задачи не стоит получить «абсолютный идеал», скорее это повод поговорить об ограничениях, алгоритмической сложности, оптимизации и других схожих аспектах. Давайте посмотрим как это может выглядеть на практике.

Обычно всё начинается с простых заданий. Кратко сформулирую условия (подробней их можно глянуть по ссылке). На вход функции подается целое число со знаком, необходимо вернуть число, в котором цифры идут в обратном порядке. Отрицательные числа должны остаться отрицательными.

Для простоты, на собеседованиях обычно сокращают задание, фокусируясь на основном вопросе. Например, в этой задаче можно не добавлять условие про попадание числа в интервал 32-битных целых (Python защищает от потенциальных проблем с переполнением, а написать if с двумя сравнениями могут почти все). Но в этой статье давайте рассмотрим решение целиком.

Задание это весьма не сложное, и пойти тут можно двумя путями: используя преобразование в строку или серией делений на 10. Разумеется, «более правильным» является второй способ, хотя то, что кандидат использует средства языка — тоже хороший знак. LeetCode такие решения «принимает», да и на собеседованиях вариант вроде приведённого ниже вполне может стать отправной точкой интересной беседы.

class Solution:
    def reverse(self, x: int) -> int:
        is_neg = x < 0
        pure = int(str(x).strip("-")[::-1])
        
        result = -pure if is_neg else pure

        if result < -2147483648 or result > 2147483647:
            return 0
        else:
            return result

Отмечу что заворачивать решение в класс Solution — предложение самого LeetCode.

На самом деле, я бы даже предпочёл увидеть такое решение, чем «правильное», потому что тут сразу видно владение Python: удаление префикса с помощью метода .strip() (не все знают что он может принимать параметры), инверсия строки с помощью оператора среза [::-1]. Но даже в этом случае есть что улучшить. Например, сохранить переменную знака не как булевский флаг, а как одно из двух чисел: -1 или 1 и потом просто помножить на него результат.

class Solution:
    def reverse(self, x: int) -> int:        
        sign = -1 if x < 0 else 1
        
        result = sign * int(str(x).strip("-")[::-1])

        if result < -2147483648 or result > 2147483647:
            return 0
        else:
            return result

Можно ещё немного полихачить и вычислить sign как-то так

sign = x // abs(x)

Но тут в силу очевидных причин ещё придётся проверять x на равенство нулю в начале функции, да и, пожалуй, это уже идёт чуть-чуть в ущерб читаемости.

«Правильное» решение пишется большинством кандидатов как-то так (на этот раз я опущу проверку диапазона).

num = abs(x)

result = 0
while num > 0:
    last_digit = num % 10
    result *= 10
    result += last_digit
    num //= 10

return -result if x < 0 else result

Решение достаточно эффективное, его можно ещё сократить, записав меньшим количеством строк, но это уже опциональное улучшение.

Кстати, на схожем принципе строятся очень многие похожие задачи, начиная с вот этой, и заканчивая классикой вроде преобразования числа в строковую запись в другой системе счисления. Вообще, советую вам потренироваться в манипуляциях с числами: например, написать сложение двух чисел неограниченной длины. Это задание есть на LeetCode, но они его усложнили использованием связанных списков. Для тренировки можно сперва сделать сложение для чисел, хранящихся в виде строки или массива цифр и подумать, какие тут есть способы обхода сложностей и оптимизации. Также полезным навыком будет умение манипулировать битами и понимание роли логических операторов в этом.

Понимайте ресурсоёмкость

Рассмотрим ещё одну задачу. На вход функции подаётся список строк и нужно найти общий для всех этих строк префикс максимальной длины. Например, для списка ["programming", "product", "procrastination"] — ответом будет "pro". На LeetCode это задание помечено как easy (как, кстати, и ставшая уже мемом задача инверсии бинарного дерева), но именно такие задачи и хороши для собеседований, тут есть о чём поговорить. Относительно опытный Python программист, знакомый с функцией zip и концепцией передачи параметров может написать что-то такое.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        result = []
        for items in zip(*strs):
            if len(set(items)) == 1:
                result.append(items[0])
            else:
                break
                
        return "".join(result)

Фактически, цикл for транспонирует наш список строк, на первом шаге возвращая список из нулевых букв всех строк, потом из первых, и так далее, как раз до конца самой короткой строки. Нам остаётся проверить этот список на уникальность, в данном случае преобразовывая его в set и сравнивая его длину с 1, если это так — то во всех строках буквы совпадают, и наш общий префикс продолжается.

Можно блеснуть лихостью и записать всё в виде однострочника.

"".join(items[0] for items in zip(*strs) if len(set(items)) == 1)

Выглядит это эффектно, но, кроме непонятности, у данного кода есть ещё одна проблема: он весьма не оптимален. Высокоуровневые конструкции языка скрывают от нас манипуляции с данными, которые в случае больших строк и массивов относительно накладны по скорости и памяти. Я пишу относительно, потому что современные процессоры — очень быстрые, а памяти — много, поэтому проблема будет заметна только на больших списках/строках либо если это будет часто повторяемая операция.

Более оптимальное решение позволяет нам не осуществлять дополнительных манипуляций со строками, обходясь только переменной-индексом. Приведу один из необычных вариантов, предложенных кандидатами.

def lcp2(strs: List[str]) -> str:
    if len(strs) == 0:
        return ""

    lcp_len = 0

    while True:
        try:
            if any(strs[0][lcp_len] != strs[idx][lcp_len] for idx in range(1, len(strs))):
                break
        except IndexError:
            break

        lcp_len += 1

    return strs[0][:lcp_len]

Идея ловить исключение для обработки выхода «за пределы» какой-то из строк — достаточно интересна, хотя решение с циклом while True делает метод достаточно «хрупким», есть риск попасть в вечный цикл. С этим примером, кстати, так и происходит, если подать ему на вход список из одной строки. В целом, это можно исправить с помощью второй проверки.

if len(strs) == 1:
    return strs[0]

Избавиться от необходимости сложных манипуляций можно если мы сразу выберем самую короткую строку и будем сравнивать все символы с ней.

if not strs:
    return ""

min_str = min(strs, key=len)

for idx, chr in enumerate(min_str):
    for other in strs:
        if other[idx] != chr:
            return min_str[:idx]

return min_str

Тут у нас, конечно, появляется «лишний» проход по списку в поисках самой короткой строки, но зато мы экономим память. Тут также важно не забыть, что цикл может завершиться потому что min_str «закончилась», в таком случае она и является нашим общим префиксом.

Не используйте «читы»

Вообще, «прокачиваясь» на LeetCode надо понимать, какую цель вы ставите перед собой, иногда бывает так, что задачи уровня «hard» решаются с помощью встроенных средств языка. Например, вот эта. Я намеренно беру задачи из самого начала списка LeetCode, чтоб уменьшить «спойлерность» статьи. Задача формулируется достаточно просто: у вас есть два отсортированных массива произвольной длины, нужно найти медиану массива, образованного их слиянием. «Правильное» решение в данном случае затянет на отдельную статью, поэтому если вы хотите знать как «нужно» сделать — прекрасное объяснение есть на самом LeetCode.

Но на самом деле, сайт принимает вот такое решение.

from statistics import median

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:     
        return median(nums1 + nums2)

Что особенно забавно, этот вариант работает быстрее чем 18% всех решений и оптимальней чем 80% решений по памяти, впрочем, статистика самого LeetCode тут не особо показательна.

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

Ищите «паттерны»

Постепенно, решая задачи, начинаешь понимать некоторые шаблоны, например, многие задания можно свести к некому варианту «парсинга» ввода с использованием упрощённых вариантов автоматов. Так что, если вы не знакомы с этим походом, очень советую устранить данный пробел. Всегда создавать полноценную грамматику, конечно, перебор, но с некоторым «срезанием углов» этот метод позволяет решать многие прикладные задачи. Вот типовой пример проблемы с LeetCode, требующий использования упрощённого варианта подхода. В этом задании все манипуляции сводятся к сравнению с предыдущим (или следующим) элементом.

Вот сама задача. На вход подаётся отсортированный список уникальных целых чисел, нам надо преобразовать его в список минимальных диапазонов идущих подряд чисел, используя указанный синтаксис. Например, список [[0,1,2,4,5,7]] преобразуется в ["0->2","4->5","7"], так как у нас есть три диапазона: от 0 до 3, от 4 до 5 и отдельно 7.

Сразу приведу решение.

class Solution:
    def format_range(self, min: int, max: int) -> str:
        return f"{min}" if min == max else f"{min}->{max}"

    def summaryRanges(self, nums: List[int]) -> List[str]:
        if len(nums) == 0:
            return []

        result = []
        start = 0

        for idx in range(len(nums)-1):
            if (nums[idx+1] - nums[idx]) != 1:
                result.append(self.format_range(nums[start], nums[idx]))
                start = idx + 1

        result.append(self.format_range(nums[start], nums[-1]))

        return result

Как видите, оно очень прямолинейно и укладывается в приведённую выше схему. Мы храним начало очередного диапазона и проходимся по списку, «подглядывая» следующее значение. Если оно больше чем на 1 отличается от текущего, значит текущий элемент — конец очередного диапазона. Мы сохраняем найденный диапазон в список результатов и устанавливаем начало текущего диапазона на следующий за текущим элемент (он с него в самом деле и начнётся).

Ну и в конце нам надо не забыть добавить последний диапазон, так как цикл его не обработает. По схожему принципу строится много задач в стиле «удалить повторы из строки», «найти длину максимальной не-убывающей подпоследовательности» и так далее. Если же вы хотите потренироваться в более формальном подходе и всё-таки применить конечный автомат на практике, вот классическое задание парсинга числа из строки. Вы можете попытаться тут обойтись и без КА, но почти наверняка решение включающее его в неявном виде родится у вас само.

Заключение

Я хотел закончить каким-то абзацем в стиле «надеюсь я сумел вас заинтересовать решением задач на LeetCode...». Но потом подумал, что это звучит слишком шаблонно, поэтому просто скажу задачи оттуда нужны не только для желающих устроиться в FAANG, иногда они действительно позволяют по-новому посмотреть на свой язык программирования и оптимизацию кода.

👍ПодобаєтьсяСподобалось20
До обраногоВ обраному25
LinkedIn

Найкращі коментарі пропустити

Літкод допомагає тримати себе в формі. Як зарядка зранку. Зробив задачку-дві на день, кілька разів на тиждень — і знаєш де ти є, що можеш. Допомагає від синдрому самозванця.

Літкод ок, якщо ти джун-студент, поганяти себе, перевірити свій скіл. Але мідл, сініору це нащо?

Чому не законтрібутити в бібліотеку, яку використовуєте в проекті? Чому не попрофайлити якийсь фреймворк і не закинути перфоманс імпрув туди? Та ви просто загляньте в середину любої ліби, там зазвичай такий ад твориться, що просто гріх не законтрібутити.

Від сініора я б очікував якийсь «реальний» вклад. 1 PR в лібу, якою користуються тисячі девів краще 1000 літкод задач.

Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

З явилась цікава проблематика.

Припустимо, ти хочешь створити іскіна бота здатного спілкуватися
Тобі знадобиться перш за все дві речі: словник слів та словник звязків
Що якщо обидва ці словники не будуть обчислюємими?
Це важливо — зрозуміти, які це дає переваги.
Ці словники — не обчислюються, не вираховуються. Їх можно тільки накопичити.
Тобто взяти статистичні дані десь та поєднати із словником слів.
І далі вже можно створювати рендомні речення та шукати відклику у зовнішньому середовищі на цей рендом. А якщо рендом буде фильтрований згідно умов, то такі речення вже більш менш стануть схожі на якесь спілкування чи обговорення.
Характери зв язків у іскіна параноїка та у іскіна Елізи,яка його лікує (відсилка до самих перших ботів) мабуть такі будуть відрізнятися. Беремо дві ідентичних пустих форми та заповнюємо кожну своїми зв язками.

Ось така вправа пропонується. Що скажете?

Ось така вправа пропонується. Що скажете?

Береш Amazon Alexa і робиш...

Дякую. Але я й початку алгоритму цього не знаю зараз. Наприклад: «тепла підлога» який тут є зв язок між словами «тепла» та «підлога» ? Тобто, що ми повинні записати у словник зв язків?

Я не експерт в NPL.

Тобто, що ми повинні записати у словник зв язків?

Apache Lucene, використовує score.
Amazon Alexa — ML, тобто ти можеш вивчити skill через ML (там по суті також буде якесь число).

Після обмірковування прийшов ось до чого:
Тепла підлога це составний ідентифікатор. Виходить, словник звязків це словник составних ідентифікаторів. І якщо: кіт є твариною, кіт — тварина, тварини включають котів, коти живі
то можно стверджувати:
1. кіт тварина це составний ідентифікатор
2. множина котів перетинається із множиною тварин
3. множина тварин перетинається із множиною живих
4. Те, що кіт живий можно вирахувати перетинанням множин або якими то операціями над составними ідентифікаторами — які і є зв язки.

Тобто «тепла підлога» це усі підлоги одфільтровані по якійсь температурі.
А як це у Амазоні я не знаю. Я не у маангах (і не хочу).

Попалась такая задачка на телефонке
leetcode.com/...​0629/Google-or-Is-Manager

Given as below, find the direct employee of the variables.

manager(P, Q) = P is the manager of Q
manager(Q, R) = Q is the manager of R
peer(R, S) = S is the peer of R.

is_manager(P, S) = True
is_manager(S, Q) = False

У меня ещё было условие, что данные могут приходить в проищвольном порядке типа peer (a, b) когда для них менеджер ещё неизвестен.

Пошёл пилить union-find и спецобработку для висящих пиров, за время интервью, к сожалению, не вложился, но допилил потом из спортивного интереса. В принципе, medium уровень.

Кто б как решил?

Побудувати всі можливі дерева, а потім кожне перевірити на відповідність цим умовам?

Фанат ДП детекдед) давайте код, подивимось. Завтра дам свiй

Дякую за пропозицію. Не настільки фанат. Сьогодні вже пізно. Можливо завтра, але не обіцяю. Зараз розмірковую над властивостями трикутної системи координат. Де крапка то трикутник. Є й інші справи. У нас 4 employeе це буде 4 дерева де кожен співробітник є менеджер, але нема інших у нього. Це перша ітерація. Друга — таке дерево, де P > Q тобто у дереві P manager of Q а більше там нікого нема. Ну й так далі. Алгоритм генерації наступної ітерації.
Ще тут наче можна use shadow of tree or bread crumbs щоб не повторюватися у ітераціях.
Так щоразу глибше зможемо пройти.

Якщо що, тут було тільки саме перше моє наближення до того, що з себе являє ця задача, тому тут трохи фантазій і ще трохи маячні. Думки програміста або free thread of thinking. Дуже невизначено, трохи надлишково, і ще щось таке.

Пошёл пилить union-find и спецобработку для висящих пиров, за время интервью, к сожалению, не вложился, но допилил потом из спортивного интереса. В принципе, medium уровень.

Это ты в комментах прочитал? Можешь обьяснить свою идею с union-find?
Я вот думаю про графы.

То есть:
manager(P, Q) = P is the manager of Q
manager(Q, R) = Q is the manager of R
peer(R, S) = S is the peer of R.

is_manager(P, S) = True
is_manager(S, Q) = False

P, Q, R, and S are nodes of the directed graph.
manager(P, Q) is the edge from P to Q
manager(Q, R) is the edge from Q to R
peer(R, S) means all incoming edges to R should be replicated to S and another way around.

Graph (with the list of edges):
P -> Q
Q -> R
Q -> S

So in order to find out if is_manager(P, S), we need to do DFS from P to S (check to see if S is reachable from P)

Вот какие-то такие мысли.

Хотя, учитывая условие:

У меня ещё было условие, что данные могут приходить в проищвольном порядке типа peer (a, b) когда для них менеджер ещё неизвестен.

Что значит в произвольном порядке? Я ж могу просто сделать обработку peers в самом конце, даже если они пришли первыми. Итого, не сильно понятно...Peers можно хранить в union-find, а дальше что?

Не совсем. Я гуглил решение, конечно, но внятного не нашёл.

С union-find идея простая, если 10 — это папа 5, то пишем в массив или мапу arr[5] = 10 и так мы инкрементально строим дерево, по которому можно добраться до рута. Множественные руты тоже поддерживаются из коробки.

С пирами — если парент хоть одного из них известен, то всё просто, цепляем их аналогичным образом к известному менеджеру. Иначе я совал их в отдельную мапу a — b и b — a. (2 записи).
При добавлении менеджера делаем поиск сирот и проходимся по цепочкам, что нашли, пихаем в union-find структуру.

Код запощу завтра

С union-find идея простая, если 10 — это папа 5, то пишем в массив или мапу arr[5] = 10 и так мы инкрементально строим дерево, по которому можно добраться до рута. Множественные руты тоже поддерживаются из коробки.

Чем это отличается от графа? Дерево это граф, граф это дерево.
Я вижу union-find только для peers. Union-find дает возможность определить быстро или две ноды находятся в одной группе, но никак не понять кто менеджер кого (у тебя в итоге P->Q->R все попадают в одну группу). Для этого нужен directed graph и возможно дополнительно union-find.

С пирами — если парент хоть одного из них известен, то всё просто, цепляем их аналогичным образом к известному менеджеру. Иначе я совал их в отдельную мапу a — b и b — a. (2 записи).

А что если peer будет первой инструкцией и на моменте у тебя ничего нету?

Чем это отличается от графа? Дерево это граф, граф это дерево.

Ничем

А что если peer будет первой инструкцией и на моменте у тебя ничего нету?

В этом и загвоздка

Що заважає створити ноду тимчасову — в яку запхати два піра, потім при появі менеджера, міняєш isSet з false на true

Виглядає як дерево, яке треба пройти лише раз
Якщо менеджер — приєднієш до нього існуюче дерево підлеглих
Якщо підлеглий — всґтикає в існуюче дерево під потрібним менеджером
Якщо пір — те саме
Якщо в тебе є два піра, але наразі нема менеджера — створюєш тимчасову ноду і маркуєш її бульвим параметром

Потім — проходишся по дереву

Так можна? Два піра — у кожного свій невизначений_ менеджер.
Тобто класи AbstractManager <- UnknownManager
І тоді екземпляри звязків будуть такі:
UnknownManager1 — Peer1 та UnknownManager2 — Peer2

Якщо в тебе 2 піра, в них має бути спільний менеджер, хіба ні?

Менеджер невизначений. Він квантовий. Ще у майбутньому. Волнова функція його ще не «схлопнулась» Тому я вважаю що не можна його вважати одним менеджером. Та й коли визначать менеджера одному із peer, а другий залишиться ще без менеджера?
Хоча а що тут peer ? Той самий менеджер чи рівень менеджменту (генеральний 0 — нач відділу 1 — тімлид 2) peer(R,S) = 2

У фінальному рішенні прийшов до висновку що об єкт — пара перший — другий треба починати із ось такої ініціалізації:
UnknownManager — UnknownSubordinate
P.S.
Саме рішення у другій гілці.

Виглядає як дерево, яке треба пройти лише раз

Це не дерево, це граф.

Ось тобі приклад:
manager(A, B)
manager(C, D)
manager(E, F)

Ітого: A->B, C->D, E->F 3 окремі дерева, або просто граф с 3-ма non-connected components.

Я чомусь подумав, що в кінцевому результаті в тебе мають бути всі конеушени сулкїтись.
Я думаю такі дерева тоді треба в масиві зберігати.
Щоб це був граф — тоді робітник може мати два менеджера, це в принципі суть не дуже міняє, лише додає лінків в структурі даних.
Теоретично, може бути ще А -В — А і це взагалі пекло :) але імхо, це не схоже на структуру менеджменту :)

Два окремі дерева можуть об’єднуватись через any node.
Наприклад:

______A______________________________P
____/____\__________________________/____\
___B_____C_-_-_-_-_- (С->T)-_-_-_-_-_T_____F
_/___\____/___\_____________________________\_
D___E___F____G____________________________Z

Мені тільки в цій задачі не зрозуміло с peers (типу я можу отримати peers як першу інструкцію. На leetcode цього немає в умові). Але що мені заважає всіх peers процесити в останню чергу?

Тоді для цієї нод створюєш тимчасового менеджера.

Хоча насправді я би зробив так:
1) Union-find для peers
2) Graph для інструкцій типу manager(P, Q)
3) Далі просто DFS по графу для is_manager(P, S), але додатково для кожної ітерациї перевіряв би чи given node is peer to someone (тобто можлива ситауція, коли S не буде в graph-і, але S це peer для R, тобто якшо я знайшов R, то це значить що я знайшов S). Це можно легко реалізувати через додатковий map(node, isPeer) + union-find (S, R)

Було б зрозуміліше, якби ще була умова: is_manager(Q, S) = True
Тоді якщо peer(R,S) = True то manager(Q, R) = Q
Гм. Наче тут таки є якась невизначенність.
Ось у мене теж обхід random filling

Було б зрозуміліше, якби ще була умова: is_manager(Q, S) = True
Тоді якщо peer(R,S) = True то manager(Q, R) = Q

логiчно

Не розумію, навіщо у умовах цього завдання ось це:
is_manager(S, Q) = False
Будувати всі дерева наче вже немає необхідності.
Тут два ланцюжка:
P - Q - R, P - Q - S
Але це трьох ланкові ланцюжки. Якщо їх можна спростити до двох, то побачимо:
P - Q, Q - R, P - Q, Q - S
Далі треба думати. Бо P — Q дублюється, але чи необхідна ця надлишковість?
Звісно не забуду й про ось такі ланки (та їм подібні) :
Unknown - P, S - Unknown, Unknown - Unknown 

Офiцiйнi лiткодовськi задачi теж часто мають муторнi умови, треба втикати

Після здобуття найпростіших ланок, прихожу до таких тверджень:
 всі менеджери s це всі менеджери q без q       | q   всі менеджери q це всі менеджери p без p       | p    всі менеджери p це всі менеджери Unknown без Unknown  |  Unknown
Бачу тут ітерації, then type result of each, та вихід із безкінечного циклу по досягненню
Unknown  |  Unknown
Далі треба думати ще...

Тут теж трохи помилково...
Тут треба

всі менеджери s це більш ніж всі менеджери q
всі менеджери q це більш ніж всі менеджери p
всі менеджери p це більш ніж всі менеджери Unknown

Як можна бачити, on_your_right з явилася інформація about managers тобто про
q,p,UnknownManager
Нижче ще більше наближення

(частина друга, перша вище)
Ну й нарешті, подальший розвиток алгоритму такий:


de s drugiy? u lanci 4 
hto tam pershiy? q

de q drugiy? u lanci 1
hto tam pershiy? p

de p drugiy? u lanci unknown
hto tam pershiy? unknown

skilki vsiogo pershih bez unknown? q,p,unknown
reverse: unknown, p, q

Тільки я схлопнув дві ланки p — q у одну. Не певний що так коректно, але наче працювати буде.
Чи є якісь зауваження?

Набросал решение (на самом деле union-find и не нужен здесь):

public class Google {

    public static void main(String[] args) {
        Google google = new Google();
        google.peer("R", "S");
        google.manager("P", "Q");
        google.manager("Q", "R");
        google.manager("A", "B");
        System.out.println(google.isManager("P", "S")); // true
        System.out.println(google.isManager("S", "Q")); // false
        System.out.println(google.isManager("A", "Q")); // false
    }

    private Graph graph;

    private Map<String, Set<String>> peers;

    public Google() {
        graph = new Graph();
        peers = new HashMap<>();
    }

    void peer(String a, String b) {
        peers.computeIfAbsent(a, k -> new HashSet()).add(b);
        peers.computeIfAbsent(b, k -> new HashSet()).add(a);
    }

    void manager(String a, String b) {
        graph.addEdge(a, b);
    }

    boolean isManager(String a, String b) {
        DFS dfs = new DFS(graph);
        dfs.dfs(b, a);
        return dfs.isConnected(peers.containsKey(b) ? peers.get(b) : new HashSet<String>() {
            {add(b);}
        });
    }

    class Graph {

        public Map<String,Set<String>> adj = new HashMap<>();

        public void addEdge(String v, String w) {
            adj.computeIfAbsent(v, k -> new HashSet<>());
            adj.computeIfAbsent(w, k -> new HashSet<>());
            adj.get(v).add(w);
        }
    }

    class DFS {

        Map<String, Boolean> marked;

        boolean hasCycle;

        Graph g;

        public DFS(Graph g) {
            this.g = g;
            this.marked = new HashMap<String, Boolean>();
            for (Map.Entry<String, Set<String>> e : g.adj.entrySet()) {
                this.marked.put(e.getKey(), Boolean.FALSE);
            }
        }

        private void dfs(String u, String v) {
            marked.put(v, Boolean.TRUE);
            if (g.adj.containsKey(v)) {
                for (String w : g.adj.get(v)) {
                    if (Boolean.FALSE == marked.get(w)) {
                        dfs(v, w);
                    } else if (!u.equals(w)) {
                        hasCycle = true;
                    }
                }
            }
        }

        boolean isConnected(Set<String> peers) {
            boolean res = false;
            for (String peer : peers) {
                if (Boolean.TRUE == marked.get(peer) ) {
                    res = true;
                    break;
                }
            }
            return res;
        }
    }
}

Мое решение, дальше полировать не стал

public class ManagerPeers {
    //  subordinate -> manager
    Map<Integer, Integer> parents = new HashMap<>();
    // a -> b and b -> a
    Map<Integer, Set<Integer>> danglingPeers = new HashMap<>();

    // union
    // setManager(A, B) sets A as a direct manager of B
    public void setManager(int manager, int subordinate) {
        parents.put(subordinate, manager);

        Set<Integer> peers = getDanglingPeersOf(subordinate);
        peers.forEach(peer -> danglingPeers.remove(peer));
        peers.forEach(peer -> setManager(manager, peer));
    }

    public void setPeer(int a, int b) {
        if (parents.containsKey(a)) {
            setManager(parents.get(a), b);
        } else if (parents.containsKey(b)) {
            setManager(parents.get(b), a);
        } else {
            addDanglingPeers(a, b);
        }
    }

    public boolean query(int manager, int subordinate) {
        while (parents.containsKey(subordinate) && parents.get(subordinate) != subordinate) {
            if (parents.get(subordinate) == manager) {
                return true;
            }

            subordinate = parents.get(subordinate);
        }

        return false;
    }

    private Set<Integer> getDanglingPeersOf(int peer) {
        Set<Integer> peers = new HashSet<>();
        if (danglingPeers.containsKey(peer)) {
            peers.addAll(danglingPeers.get(peer));

            // handle reversed connection between peers
            danglingPeers.forEach((p, neighbours) -> {
                if (neighbours.contains(peer))
                    peers.addAll(neighbours);
            });
        }

        return peers;
    }

    private void addDanglingPeers(int a, int b) {
        danglingPeers.computeIfAbsent(a, HashSet::new);
        danglingPeers.computeIfAbsent(b, HashSet::new);

        danglingPeers.get(a).add(b);
        danglingPeers.get(b).add(a);
    }

    public static void main(String[] args) {
        ManagerPeers s = new  ManagerPeers();
        s.setManager(1, 2);
        s.setManager(2, 3);
        boolean res1 = s.query(1, 2);  //true
        boolean res11 = s.query(2, 1);  //false because other way around
        boolean res2 = s.query(1, 3);  //true
        boolean res3 = s.query(3, 4);  //false as there is no such relation yet

        s.setPeer(4, 5);
        s.setPeer(4, 8);
        s.setPeer(10, 5);
        s.setManager(3, 4);
        s.setManager(10, 11);
        s.setPeer(11, 12);
        boolean res4 = s.query(3, 4);  //true

        boolean res5 = s.query(4, 5) || s.query(5, 4); // false because they're peers
    }
}

В конце
parents = {2->1, 3->2, 4->3, 5->3, 8->3, 10->3, 11->10, 12->10}

Можно по человечески условие задачи описать? Какие входные данные, что ожидается как результат?

Ну вот примерно оно так и давалось.
На вход ребра графа в произвольном порядке или признак, что общий парент.

В любой момент может поступить запрос, является ли А менеджером В, прямым или через цепочку промежуточных. Ответ может меняться при поступлении новой информации.

manager(P, Q) — это только для direct report отношений, или indirect тоже?
Peer(A, B) — значит что у A и B один и тот же direct manager?

Могут ли входные данные быть конфликтными или неполными для получения ответа?

Indirect тоже.
Да, тот же прямой менеджер.
Конфликтные — нет, неполные да. Тот же запрос может вернуть false при неполных данных и true после добавления новых.

Задача выглядит так, что ее надо решать на Prolog

Ну в треде было моё решение через union-find с кешированием висящих нодов, пока не найдётся куда их прицепить.

запилил longestCommonPrefix на пыхе, ну чет разброс у него от 2 до 20 мс по скорости

class Solution {

    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        return $this->solve($strs, 0, '');
    }
    
      private function solve($strs, $index, $prefix) {

        if(!isset($strs[0][$index])) {
            return $prefix;
        }

        $ch = $strs[0][$index];

        foreach($strs as $str) {

            if(!isset($str[$index]) || $ch != $str[$index]) {
                return $prefix;
            }
        }
          
        return $this->solve($strs, $index + 1, $prefix.= $ch);

    }
}

Попробуй запилить без рекурсии.

та же хрень:

class Solution {

    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        $continue = true;
        $prefix = '';
        $index = 0;

        while($continue) {

            if(!isset($strs[0][$index])) {
                return $prefix;
            }

            $ch = $strs[0][$index];

            foreach($strs as $str) {
                if(!isset($str[$index]) || ($ch != $str[$index])) {
                    $continue = false;
                    break;
                }
            }

            if($continue) {
                $prefix .= $ch;
            }
            
            $index++;
        }

        return $prefix;
    }

}

думаю оно там запускает на разных энвах поэтому такое

public String longestCommonPrefix(String[] strs) {
        StringBuilder prefix = new StringBuilder();
        if (strs.length == 0) {
            return prefix.toString();
        }
        if (strs.length == 1) {
            return strs[0];
        }

        int prefixInd = 0;
        while (true) {
            for (int i = 1; i < strs.length; i++) {
                if (prefixInd >= strs[i].length() ||
                        prefixInd >= strs[i - 1].length() ||
                        strs[i - 1].charAt(prefixInd) != strs[i].charAt(prefixInd)) {
                    return prefix.toString();
                }
            }
            prefix.append(strs[0].charAt(prefixInd));
            prefixInd++;
        }
    }

Интересно, насколько по-другому оценивается решение задачи на интервью в тех компаниях куда я интервьювался / где интревьюваю в Европе и Америке.

1. Задача подаётся как бизнес проблема а не просто алгоритмическая головоломка. Например, не «найти длиннейшую общую подстроку», а «реализовать алгоритм автокомплита в строке поиска на веб сайте». От кандидата ожидается способность свести расплывчатую бизнес-задачу к конкретной алгоритмической путём задания уточняющих вопросов

2. Кандидат может использовать наиболее комфортный для него/неё язык программирования, с которым интервьювер может быть и не знаком. Соотвественно, знание тонкостей языка не оценивается, оценивается алгоритмические способности

3. Очень важно насколько кандидат уделяет внимания edge cases & preconditions — может «написать if с двумя сравнениями могут почти все», но способность их идентифицировать важна

4. Уделяется внимание читаемости кода и названиям переменных — за названия вроде «lcp_len» кандидату поставят минус

4. Об использовании ресурсов просят объяснить в терминах big-O — за пределами этого дальнейшие микро-оптимизации редко обсуждаются

Задача формулируется достаточно просто: у вас есть два отсортированных массива произвольной длины, нужно найти медиану массива, образованного их слиянием.

leetcode.com/...​ian-of-two-sorted-arrays
Там еще есть условие: The overall run time complexity should be O(log (m+n))
Оптимально пока не решил, но довольно простое линейное решение написанное без длинных раздумий бьет 90% по времени.

Тесткейсы стоило бы сделать пожестче, чтобы тупые решения в лимит времени не укладывались.

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int mid = (length1 + length2) / 2;
        int prev = 0, cur = 0;
        int idx1 = 0, idx2 = 0;

        for (int i = 0; i <= mid; i++) {
            prev = cur;
            if (idx1 < length1 && idx2 < length2) {
                if (nums1[idx1] < nums2[idx2])
                    cur = nums1[idx1++];
                else
                    cur = nums2[idx2++];
            } else if (idx1 < length1) {
                cur = nums1[idx1++];
            } else {
                cur = nums2[idx2++];
            }
        }

        if ((length1 + length2) % 2 == 0)
            return ((double) prev + (double) cur) / 2;
        else
            return cur;        
    }

leetcode.com/...​lems/koko-eating-bananas
в этой задаче тесткейсы подобраны так, чтобы даже оптимизированный брутфорс в лимит не укладывался

Недавно делал эту.
Обычный binary search: left = 1, right = max pile...

Угу, я решал двумя способами с верхней и нижней оценкой, чтоб меньше итераций было. Для binary search выигрыша особого не даст.

Угу, надо бы нарисовать на бумажке с нормальным примером
Пока на очереди leetcode.com/...​ems/parallel-courses-iii

Обьясните лучше эту задачу (решения я и сам могу найти):

As the ruler of a kingdom, you have an army of wizards at your command.

You are given a 0-indexed integer array strength, where strength[i] denotes the strength of the ith wizard. For a contiguous group of wizards (i.e. the wizards’ strengths form a subarray of strength), the total strength is defined as the product of the following two values:

The strength of the weakest wizard in the group.
The total of all the individual strengths of the wizards in the group.
Return the sum of the total strengths of all contiguous groups of wizards. Since the answer may be very large, return it modulo 109 + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: strength = [1,3,1,2]
Output: 44
Explanation: The following are all the contiguous groups of wizards:
— [1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1
— [3] from [1,3,1,2] has a total strength of min([3]) * sum([3]) = 3 * 3 = 9
— [1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1
— [2] from [1,3,1,2] has a total strength of min([2]) * sum([2]) = 2 * 2 = 4
— [1,3] from [1,3,1,2] has a total strength of min([1,3]) * sum([1,3]) = 1 * 4 = 4
— [3,1] from [1,3,1,2] has a total strength of min([3,1]) * sum([3,1]) = 1 * 4 = 4
— [1,2] from [1,3,1,2] has a total strength of min([1,2]) * sum([1,2]) = 1 * 3 = 3
— [1,3,1] from [1,3,1,2] has a total strength of min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5
— [3,1,2] from [1,3,1,2] has a total strength of min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6
— [1,3,1,2] from [1,3,1,2] has a total strength of min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7
The sum of all the total strengths is 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44.
Example 2:

Input: strength = [5,4,6]
Output: 213
Explanation: The following are all the contiguous groups of wizards:
— [5] from [5,4,6] has a total strength of min([5]) * sum([5]) = 5 * 5 = 25
— [4] from [5,4,6] has a total strength of min([4]) * sum([4]) = 4 * 4 = 16
— [6] from [5,4,6] has a total strength of min([6]) * sum([6]) = 6 * 6 = 36
— [5,4] from [5,4,6] has a total strength of min([5,4]) * sum([5,4]) = 4 * 9 = 36
— [4,6] from [5,4,6] has a total strength of min([4,6]) * sum([4,6]) = 4 * 10 = 40
— [5,4,6] from [5,4,6] has a total strength of min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60
The sum of all the total strengths is 25 + 16 + 36 + 36 + 40 + 60 = 213.

Constraints:

1 <= strength.length <= 105
1 <= strength[i] <= 109

Смотри, условно у тебя есть массив чисел. Тебе нужно разбить его на подмассивы, посчитать что-то внутри подмассива по формуле (не важно какой), посчитать сумму подмассивов. При этмо разбить на подмассивы нужно так, чтоб итоговая сумма была максимизирована.

Условно, если назовем группы a, b, c, d, e, ..., то мы считаем
calc(a) + calc(b) + calc© + calc(d) ...

Учитывая особенности сложения, очевидно, что мы также можем посчитать, например,

(calc(a) + calc(b)) + (calc© + calc(d))

или

calc(a) + (calc(b) + (calc© + calc(d)))

Сначала подумаем, как решить перебором — решение по идее тривиально. Берем массив, и начинаем перебирать все возможные варианты для первой группы

псевдокод, который считает мощь первой группы:

fn get_max(array) -> i32 {
    if array.len() == 0 {
         return 0;
    }

    for group_len in 0..array.len() {
        let group = array[0..group_len];
        let group_value = calculate_group_power(group);
    }
}

Мы получили мощь первой группы, теперь надо посчитать мощь остального массива (который в свою очередь может быть разбит на маленькие группы) и добавтиь его к мощи первой группы, мы можем для этого отрезать остаток массива и передать его рекурсивно в get_max, посчитать сумму и выбрать максимум:

fn get_max(array) -> i32 {
    if array.len() == 0 {
         return 0;
    }


    let max_value = i32::MIN_VALUE;

    for group_len in 0..array.len() {
        let first_group = array[0..group_len];
        let first_group_value = calculate_group_power(first_group);

        let remaining = array[group_lan..];
        let remaining_value = get_max(remaining);

        let total_value = first_group_value + remaining_value;
        max_value = max(max_value, total_value);
    }

    return total_value;
}

Это неэффективный перебор, сложность скорее всего O(N**N)

Чтоб оптимизировать, нужно проанализировать как работает рекурсия и заметить, что мы будем постоянно рекурсивно вызывать get_max(...) для одного и того же подмассива.
Это легко лечится кешированием (aka memoization) — каждый раз когда вызываешь get_max, сначала проверяй, есть ли результат в кеше, если есть, то не вызывай его еще раз, а бери из кеша.
Это должно тебе снизить сложность до O(N**a), скорее всего O(N**3), лень точно считать.

Дальше, если ты знаком с динамическим программированием, то ты можешь заметить, что эту же задачу можно реализовать через DP. Вместо того, чтоб начинать решение с самой большой задачи и решать подзадачи, ты сначала решаешь самую маленькую задачу на начале массива (массив размером 0), сохраняешь, затем увеличиваешь размер массива на 1, и при решении обращаешься к прерыдущим решениям и так далее.

Таким образом вместо рекурсии получается пара циклов.

Дальше как реализовать сам calculate_group_power. Тривиальное решение — перебрать все элементы группы, найти минимум и посчитать сумму.
Это можно немного оптимизировать. Вместо тривиального подсчета суммы можно делать эффективный suffix sum, позволяющий подсчитать сумму подмассива за O(1). Вероятно, для поиска минимума подмассива можно тоже запилить эфективный алгоритм O(1), но сходу не придумал.

Максимально эфективное решение с DP со всеми оптимизациями должно быть O(N**2)

Не могу придумать как минимум подмассива найти за O(1), но есть вариант за O(log n) с помощью бинарного дерева. Т.е. с моим подходом будет O(n*n*log n)

Не могу придумать как минимум подмассива найти за O(1), но есть вариант за O(log n) с помощью бинарного дерева. Т.е. с моим подходом будет O(n*n*log n)

Монотонная очередь/стек?

З.Ы. Пока сильно не вчитывался в твои рассуждения.

Забей, я неправильно понял условие задачи. Я думал, что нужно разбить на подгруппы и посчитать максимум мы можем достичь, но на самом деле там надо все возможные в принципе подгруппы просуммировать. Я подумаю позже.

Небольшая сложность с тем, что при вычислении будет переполнение. Я б считал в домене 128-битных целых чисел и потом взять модуль.

Небольшая сложность с тем, что при вычислении будет переполнение

Не вижу сложности в том, чтобы делать % (10^9 + 7) по мере вычисления суммы и при этом используя обычный long...

Тебе нужно постоянно считать max, а считать max от результата mod даст неверный результат. Если я правильно понимаю, worst case не вместится в 64-битный инт (надо проверять)

Обожаю условия задач на литкоде, особенно свежих. Пока воткнешь, половина интервью и пройдёт 🤦‍♂️

Условие как раз понятное, brute-force решение тоже.
Нужно чтобы было меньше чем O(N ^ 2)

Ну в пятницу вечером не догнал сходу)
Была ещё задача с обубенным описанием условия, которая после вкуривания разбивалась на две вроде найти points of interest на графе и проранжировать по критериям. В условии это всё было изрядно сложнее описано.

Где написано, что нужно меньше, чем O(N^2)?

Я видел решение, но я его не понимаю.
Думал местные гуру обьяснят более простое решение и расскажут как его понять.

Я б попробовал заменить операцию умножения сложениями, и пытаться понять, как кучу сложений в итоге можно заменить умножениями в другом измерении.

Короче, решил за O(N), но объяснение решения и способ как к нему прийти ппц сложно пишется.

Если не можешь обьяснить, то, наверное, сам до конца не понимаешь решение..

Аксакали, підкажіть, що можна покращити?

Задача

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Рішення:

Складність виходить n2logn
Ідея була відсортувати і бінарним пошуком звужувати пошук третього
І наче швидко все працює, порівняно з наївним перебором (n3) в 20 раз швидше, але

318 / 318 test cases passed, but took too long.

public class Solution {
        private static bool ValidateCandidate(int first, int second, int third, List<IList<int>> result)
        {
            if (first + second + third != 0)
                return false;
            if (result.Any(x =>
              x[0] == first && x[1] == second && x[2] == third))
            {
                return true;
            }
            result.Add(new List<int> { first, second, third });
            return true;
        }
        public static IList<IList<int>> ThreeSum(int[] nums)
        {
            var result = new List<IList<int>>();
            if (nums.Length < 3)
                return result;

            int numsLength = nums.Length;
            Array.Sort(nums);

            for (int i = 0; i < numsLength; i++)
            {
                int first = nums[i];
                for (int j = i + 1; j < numsLength-1; j++)
                {
                    int second = nums[j];

                    int startInd = j + 1;
                    int endInd = numsLength - 1;

                    while (true)
                    {
                        int k = (startInd + endInd) / 2;

                        int third = nums[k];

                        if (first + second + third == 0)
                        {
                            ValidateCandidate(first, second, third, result);
                            break;
                        }
                        else if (first + second + third > 0)
                        {
                            endInd = k;
                        }
                        else
                        {
                            startInd = k;
                        }

                        if (endInd - startInd <= 1)
                        {
                            third = nums[startInd];
                            if (!ValidateCandidate(first, second, third, result))
                            {
                                third = nums[endInd];
                                ValidateCandidate(first, second, third, result);
                            }

                            break;
                        }
                    }

                }
            }
            return result;
        }
}

Вирішив

        private static bool ValidateCandidate(int first, int second, int third, List<IList<int>> result)
        {
            if (first + second + third != 0)
                return false;

            if (result.Any())
            {
                var count = result.Count;
                var i = count-1;
                while (true)
                {
                    var current = result[i];
                    if(current[0] != first)
                    {
                        break;
                    }
                    if (current[0] == first && current[1] == second && current[2] == third)
                    {
                        return true;
                    }
                    
                    i--;
                    if (i < 0)
                    {
                        break;
                    }
                }
            }
            result.Add(new List<int> { first, second, third });
            return true;
        }

Runtime: 983 ms, faster than 13.07% of C# online submissions for 3Sum.
Memory Usage: 47.3 MB, less than 21.28% of C# online submissions for 3Sum.

Що ще можна покращити?

Колись вирішував схожу задачку, але там трішки умови були інші. Якщо не помиляюсь, не було умови a != b, b != c, c != a, та target могла бути не 0, а різною.
Ідея рішення полягало у тому, що коли масив відсортований, то можна за O(n^2) ітерацію віднайти усі три числа, які будуть задовольняти умову. При цьому не має потреби у використанні Hash-map

Для начала посмотри leetcode.com/problems/two-sum
Аналогичная задача, где нужно сложить только 2 числа, решается за O(N) времени с использованием хеш таблицы.

Третье значение добавляет еще одну размерность, решение должно быть не хуже O(N*N).

Можешь решить следующим образом:

Допустим, массив [n1, n2, n3, n4, n5, n6, n7, n8, n9, n10]

Берешь какой-то префикс массива, и следующее за ним число например,
Arr = [n1, n2, n3, n4]
Target = -n5
Решаешь задачу 2Sum с этими входными данными, оно даст тебе результат дла 3sum (если, скажем, n1 + n3 == -n5, то n1 + n3 + n5 == 0).

Делаешь этот проход для всех префиксов, от нулевого размера до N-1.

Я с твоим кодом глубоко не разбирался, но беглый взгляд показывает как минимум одну проблему — у тебя не используется HashSet для хранения результатов, из-за этого поиск дубликатов в решении занимает линейное время (с HashSet будет константное время).

Так, проблема була в пошуку дублікатів dou.ua/...​rums/topic/33361/#2258912

Але я бачу ще одну проблему — як визначити, який підхід буде краще? Адже хоча підхід з бінарним пошуком і вирішив задачу і навіть пройшов по LeetCode, але рішення з хештаблицею, схоже, дадуть більш оптимальне рішення. То як обрати зразу хештаблицю, а не бінарний пошук?

На литкоде указаны лимиты на входные данные. По ним ты можешь прикинуть, какое решение пройдет, какое нет.
Очень грубо говоря прикинь что на каждую операцию тебе нужен один такт и у тебя частота гигагерц, т.е. бюджет где-то миллиард операций

Если лимит 3000 элементов, то N*N скорее всего пройдет (3000*3000 = 9 000 000, что легко должно вложиться в лимит), а N*N*N (27 миллиардов) скорее всего не пройдет, т.е. нужно будет пытаться найти решение в области N*N или лучше.
Если лимит 10 элементов, то там будет хардкор типа N!

Прогнать оба варианта по пару раз и забенчмаркить? Там есть и 4sum с фолловапом на 5 и так далее

leetcode.com/...​-hyderabad-may-2021-offer человек пишет как получил оффер. Я бы за 20 минут Maximal Rectangle не решил бы, но в целом не самые хардовые задачки. Сриннинг выглядит вменяемо, как по мне.

добавили новый функционал — теперь можно создавать и проводить онлайн интервью. Сделано довольно просто и удобно, как по мне. Вангую, некоторые компании и нас возьмут на вооружение.

Збс, теперь даже не нужно копипастить задачи с литкода, можно просто дать ссылку на задачу и сказать «решай!»

А у кандидата сразу подгружается его последний сабмит.

А от питання — як ви вирішуєте задачи на перебор? Я все ніяк не можу їх толком опанувати. Важка артилерія — створити динамічний масив, який є варіантом того, шо перебирається і по ньому там довго і нудно шаритись і інкрементити. Якось воно дуже косо та криво в мене виходить. Чи є щось краще у вас?

Есть пример такой задачи?

leetcode.com/tag/backtracking хоч і не усі.
Combination Sum II, Generate Parentheses відкладені от.

я вже колись писав, що мій добрий друг любить політкодити і часто постить прикольні пояснення (ну іноді просто код, по настрою так сказать). я подивися що у нього є з цього списку. оці з поясненнями в картинках:
* leetcode.com/...​(explained-with-pictures
* leetcode.com/...​solutions-(with-pictures
тут просто код:
* leetcode.com/...​-three/discuss/1122664/ok
* leetcode.com/...​/922798/2-short-solutions
* leetcode.com/...​uss/977457/few-variations
* leetcode.com/...​cuss/1042321/lookup-table
може щось з цього буде корисним.

ще пару штук знайшлось. оце з картинками:
* leetcode.com/...​heses/discuss/1177483/dfs
* leetcode.com/...​uss/972529/3-EXPLANATIONS
остання — лол-задача на „return n-1;” (жду коментарі про нечитабельний код)
просто код:
* leetcode.com/...​atch/discuss/926268/short
* leetcode.com/...​number/discuss/1181049/ok

Да.
Такая вот задача:
Паук должен съедать по три мухи в день. Пока он не заполнит свою квоту, у него есть 50% шанс поймать любую муху, которая попытается пролететь через его сеть. Каковы шансы мухи на выживание (вмысле 6-й), учитывая, что сегодня уже пролетело пять мух и больше не будет? Сделай мне функцию с двумя аргументами: колличество пролетов мухи на сейчас (n), вероятность мухи быть пойманой (p) и чтобы она возвращала мне вероятность выживания на n + 1 попытки мухи пролететь через паука.

При чому тут Зеленський перебор? Це простенька матем задача на теор імов.

Яка імовірність бути з’їдженою першою: імов що не з’їли нікого з (n-1) до тебе ((1-p)^(n-1)) помножина на імов, що тебе з’їдять (p). Ітого: (1-p)^(n-1)*p.

Яка імовірність бути з’їдженою другою: імов що з’їли когось одного з (n-1) до тебе (p(1-p)^(n-2)) помножина на кількість способів вибрати кого з’їли (binom(n-1, 1)) помож на імов, що тебе з’їдять (p). Ітого: binom(n-1, 1)*p*(1-p)^(n-2)*p.

Яка імовірність бути з’їдженою третьою: імов що з’їли двох одного з (n-1) до тебе (p^2(1-p)^(n-3)) помножина на кількість способів вибрати кого з’їли (binom(n-1, 2)) помож на імов, що тебе з’їдять (p). Ітого: binom(n-1, 2)*p^2*(1-p)^(n-3)*p.

Просумувавши і розкривши біноми:
1) p*(1-p)^(n-1)
2) (n-1) * p^2 * (1-p)^(n-2)
3) (n-1)*(n-2)/2 * p^3 * (1-p)^(n-3)
====
p*(1-p)^(n-3)*[ (1-p)^2 + (n-1)*p*(1-p) + (n-1)*(n-2)*p^2 ]

Усьо. Імов вижити = 1 — сума он тих трьох доданків = 1 — p*(1-p)^(n-3)*[ (1-p)^2 + (n-1)*p*(1-p) + (n-1)*(n-2)*p^2 ]

То что ты решишь, я не сомневался.

Мне просто всегда смешно когда люди копипастят код, который легко можно найти в инете. Поэтому я решил посмотреть, а что если спросить задачу «из головы» (или по мотивам другой задачи, скажем так), которую не найдешь в инете и как эти люди будут ее решать, если решения в инете найти нельзя.

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

в жизни да, встречал продолжение
да, и рассчитайте нам параметры безубыточности нашей паучьей фермы.
ответ обычно в стиле:
— могу конечно... только кто отвечать за банкротство будет? если и тоже я — тогда давайте как-то меня в собственники прописывать

свеженькое, из серии «и как тебе спится, программист?»
Почтальонов 20 лет по ошибке сажали в тюрьму из-за «кривого» ПО
Японский софт указывал на недостачу денег, и сотрудники, ответственные за нее, попадали в тюрьму или лишались личных сбережений.
...
Post Office признала ошибку

На момент публикации материала компания Post Office призналась в том, что слишком непоколебимо верила в надежность ПО Horizon
23 апреля 2021 г. Королевский суд Лондона вынес 39 оправдательных приговоров в отношении сотрудников Post Office. Ранее все они были по ошибке осуждены за кражу денег у компании — кто-то поплатился увольнением, а кто-то — свободой.
nevsedoma.com.ua/index.php?newsid=485064

Post Office признала ошибку
На момент публикации материала компания Post Office призналась в том, что слишком непоколебимо верила в надежность ПО Horizon

да перестань там ситуация бредовая во всех отношениях и софт там оказался только случайно с тем же ж успехом на его месте могли бы б быть калькуляторы у которых плохо нажималась десятичная точка там ситуация бредова по чисто человеческому фактору включая фактор человечесткой организации и не в последнюю очередь она бредова суммами об которых вообще идёт речь

It then became a central issue in a civil court case brought by 550 postmasters in 2017. The Post Office agreed to pay £58m to settle the case last year.
she was sentenced to 15 months in prison in 2010 for stealing £74,000 from her branch in West Byfleet.

т.е. post office годами сажал каких-то маленьких людей за какие-то смешные суммы до 100,000 не особо разбираясь в том кто что и как включая видимо британский суд видимо местной юрисдикции который опять же ж как-то так принимал все эти evidence на веру просто штампуя дела подряд «по одному в неделю» (к) а вся фишка видимо в том что маленькие люди не могли себя толком защищать и представлять плюс ещё не факт что там реально все подряд были совсем не виновные а фишка про маленьких людей именно в том что если система дырявая то через неё бы б потекли бы б миллиарды а тут дело на 58 миллионов фунтов за 15 лет по 385 тысяч в год на 15 тысяч отделений итого по 25 фунтов в год на отделение готов спорить там скрепок ручек и марок утекало «безвозвратно утраченных» на порядок больше и без всякого участия всякого софта

программисты там на столько не при чём что сам факт попытки притянуть туда «не работающий софт» уже просто как показатель именно того что софт то как раз и не при чём

готов спорить там скрепок ручек и марок утекало «безвозвратно утраченных» на порядок больше и без всякого участия всякого софта

та это так обычно и есть :)
всплывают только иногда истории, то там в штатах в каком-то айти отделе библиотечного управления повязали — закупал тонера в разы больше и в свой гараж, а потом толкал на ебае. лет 10 или 15
то вона, в Италии, 15 лет получал зарплату в гос больничке и не ходил ни дня.
«жалованье за все эти годы составило 538 тыс. евро.»

программисты там на столько не при чём что сам факт попытки притянуть туда «не работающий софт»

та это ж мем шутка — «как тебе спится программист»
тут тоже понятно — баги в проде скорее обыденность, чем исключение, и «фиксятся» без таких ужасов при здравом использовании ПО.

уже просто как показатель именно того что софт то как раз и не при чём

я недавно баг выловил, не жаловались, но — какие-то странные иногда ворнинги в логах.
ыть, а оказалось, иногда, дважды с пользователя списывало по мелочи!
был бы это Баг — вой стоял бы в первый день выкатки на прод. а так, эти ворнинги мной заметились с год назад.
пожаловался бы хоть один — то же бытенько нашел бы.

вообще, сам удивился, какое однако бывает сочетание мелких недоделок, в сочетании приводящее к такому двойному списанию.
но, даже у нас — хлопская система контроля попискивала — что-то не так...

я даже бизнесу не докладывал. пофиксал и вернул всем ложно снятое. втихаря :)

тут тоже понятно — баги в проде скорее обыденность, чем исключение, и «фиксятся» без таких ужасов при здравом использовании ПО.

дык аб том и речь что конкретно по сабжу так прямо и пишут «из-за бага в программе тысячи людей в тюрагу» но постойе ка это же ж не программа сажала людей это какой-то суд какое-то следствие ну хоть что-нибудь но тут видимо очень удобно написать «программная ошибка» а то как говорится копая слишком глубоко слишком растёт вероятность выйти на себя самого ))

и пишут «из-за бага в программе тысячи людей в тюрагу»

так классный же заголовок!
Мне понравился, поднимает Важность нашей профессии :)

чтоб в фаанг попасть надо наверное. хотя там тоже тебе такие алгоритмы спускать сверху будут.

Що за єрунда? Ніхто нічого не буде зверху спускати. Наша над-команда (Ads Optimization) постійно ставила різні експерименти і нам постійно доводилось доказувати, що наші покращення це дійсно покращення, а не рандомне відхилення. Ми там постійно юзали як внутрішні тулзи так і самі писали расчотки. Коли мені вперше прийшлось рахувати t-test стьюдента я дуже знатно прихуїв.

edit: я був простим рядовим інженером (L4?) коли це робив, хоча у нас цим займались і L3 і навіть стажори — там не важко, насправді.

Наша над-команда (Ads Optimization)

Аргумент блондинки:
А вот я знаю случай!

Мне тоже доводилось предлагать и на ура принимались улучшения по амортизации основных средств. хотя я никак не экономист и не бухгалтер.
или сейчас, гауса логарифмом душил и дискретным вторым проходом, и если от первого варианта тру математиков бизнес морщился, то от моего — оно! то что надо!
и что?

Прикольно было наблюдать еще и сам спор:
«математики» — у нас все правильно! кривые ж гладкие! а бизнес — да-а-а, гладкие, но это не то... мы в математике не сильны, но это, как-то не то что нам надо ...

такое бывает «раз в сто лет», если взять сколько там миллионов программистов, если даже у меня такое бывает пару раз на проект.

Я тобі не про якийсь рандомний випадок, який стався з другом друга друга говорю. Я говорю про свій безпосередній досвід. Мало того, там реально багато команд де треба знання математики — search quality, ads, abuse/spam це чисто сходу. В ФБ це були feed, abuse, coefficients. Тобто це реальний інструмент який багато де можна юзати, але якщо ти не знаєш його, то просто пройдеш мимо і не замітиш, що була якась opportunity зробити щось круте.

Програмістам реально варто попрацювати на непрограмістських роботах щоб охуїти і проникнутись тим, наскільки багато речей в світі зроблені через сраку просто тому, що народ не вміє програмувати. У мене є друг, який прийшов був в одну будівельну компанію і охуїв від того, що там всьо на екселі, переписав це їм з екселя на пару скиптів на пітоні і зекономив компанії мільйони.

Я говорю про свій безпосередній досвід

а я про типову роботу програміста.

до речі, який, той типовий НЕ працює і ніколи не працюватиме у фаангу, щоб приплітати ще й ФБ

світ програмування набаго більший вашого: Я говорю про свій безпосередній досвід

що народ не вміє програмувати

так, тому мені й цікаво займатися з дітьми

бо є маячня що програмування то розділ математики.
і так, з тею маячнею чимало програмістів так і не вміють програмувати :)

бо їх тому не вчили. а вчили — математиці

Соромлюсь запитати, а що ти думаєш за функціональне програмування та його теорію? Забавка чи все ж таки є щось пов’язане з математикою?

Забавка чи все ж таки є щось пов’язане з математикою?

скільки років і на якій ФМ і що пишеш?
от тобі і буде відповідь, і не придется нікого «соромитися питати».
власним досвідом доведеш те чи інше.

про відповідність Каррі — Говарда, і що вона значит у практичному сенсі — може іншим разом.
бо за 15 років той хайп про ФП вже не зачіпає.

так що — доводь власним досвідом — вчи математику, а не питай на форумах. треба ж мати власну думку, чи не так?
бо зазвичай ті що за математику — або студенти, або ті що знали її колись. виключення звісно є, і може цілих 5%!

Пайк на презентаціях Golang колись все пояснив про студентів з найкращих амер вишів. інших у Гуглі майже і немає.

Питання було до твого ставлення. Бавлюся хаскелом декілька років для себе. Але не бачу як воно стосується до питання.
Ось чому ти так математику хейтиш?
Програмування і математика як на мене можуть співіснувати.
Подивлюся презентації Голанга (якщо швидко нагуглю). Може краще тебе зрозумію

Питання було до твого ставлення

моє особисте ставлення

Функціональне программування так, пов’язане з математикою
але не тою що вчать масово.
І є корисною науково-дослідницькою лабораторією.
а коли домєн — має математичний опис — то й чудово можна писати ПЗ на ньому. майже без «перекладу».

Бавлюся хаскелом декілька років для себе.

почни розробляти на ньому. за гроші.

я про цей власний досвід.

Ось чому ти так математику хейтиш?

з яких це пір? не пам’ятаю за собою.

я тролю віру у неї. якої вона — не потребує, якщо її знати, розуміти про що вона.
та тіпа математиків, які до неї не мають відношення :)
самі математики, всесвітньо відомі чимало так хейтять.
НЕ математику, якою вони все життя займаються.

Програмування і математика як на мене можуть співіснувати.

вони і співіснують.
з чого б це математика не могла співіснувати з будівництвом наприклад?
тільки — будівництво від того — не стає різновидом математики.
і щоб бути вправним будівельником — тра мати інші знання і навички, котри математика не дає.
навіть архитектору — недостатньо математики для його творчості.

Може краще тебе зрозумію

чому може? звісно що краще зрозумієш :)
головне що треба зрозуміти: Пайк — інженер та прагматик.
і тоді стане зрозуміло й про сам Golang, чому він такий «покоцаний».

а далі, стане зрозуміло й про популярність js, php, та plain C.

ну і про міце Хаскель, у великому світі программування.

Доречі, якщо закинеш відео або кейворди — буде круто. Бо зараз я дивлюсь Пайка (дякую, раніше його не бачив), але наразі нічого про студентів по кейвордах не було. Я лише на другій відяшці з цікавого для мене.

але наразі нічого про студентів по кейвордах не було

є, навіть у перекладах на російську :)
просто треба враховувати — політкоректність, та головне
контекст його такої думки.

для цього треба або самому бути прагматиком, або уважно його послухати
наприклад ось один з самих цитованих докладів:
www.youtube.com/watch?v=5kj5ApnhPAE

головне ж — не думка як результат.
а шлях до неї.

як там нижче є комент:
та вже завчили ті задачкі з літкоду так, що й не зрозуміло по ним — то вміє людина думати чи ні?

Бо зараз я дивлюсь Пайка

повністю підтримую.
слідкуй за шляхом його думкі, і буде користь.

з цитат, яких завгодно від кого завгодно — користі набагато менше.
контекст — ось що головне, а не ті заповіді що мойсей проголосив.

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

Каковы шансы мухи на выживание (вмысле 6-й), учитывая, что сегодня уже пролетело пять мух и больше не будет?

кстати не указано что нам известно за других мух и летают ли они ещё или уже летать не будут не зависимо от того что какая-то часть из них уже была поймана с некоторой вероятностью )) в результате применения этого «отсутствующего условия» может оказаться на пример что простая функция будет возвращать всегда только

вероятность мухи быть пойманой (p)

просто потому как от пролёта мухи она не меняется просто потому как она прямо задана по условиям

у него есть 50% шанс поймать любую муху, которая попытается пролететь через его сеть.

просто потому как условие барьера

Паук должен съедать по три мухи в день. Пока он не заполнит свою квоту

никогда не будет выполнено и сама система от числа пролёта единственной оставшейся мухи никак не зависит

Мой point в том, 5 лет назад, ещё до появления литкодов в том виде в котором они есть, я любил спрашивать задачу (она в литкоде есть, но я ее просто из практики в университете помнил): задача простая — сделай мне функцию заливки области (у тебя есть метод getColor(x, y)). Я, наверное, эту задачу или такого плана спросил у 40-50 человек (не помню точно). Реально, без помощи могли решить только 3 (и это была позиции на middle или senior). Почему? Потому что в действительности программистов умеющих хороший problem solving skills мало. И этот problem solving skills мало корелирует с тем сколько ты задач на leetcode-е решил, то есть это повальное увлечение leetcode-ом можно описать фразой: fake it until you make it. То есть, если поменять правила игры (вместо leetcode спросить просто математику), то это не решит проблему отсутствия «problem solving skills». Короче, людей с действительно классным «problem solving skills» очень мало и обычно они ОЧЕНЬ хорошие математики....

обычно они ОЧЕНЬ хорошие математики....

а дефицит — программистов :)

потому что бОльшая часть проблем уже после первого месяца разработки c нуля — не по математике
а после полугода вообще уходит в peopleware

Я, наверное, эту задачу или такого плана спросил у 40-50 человек (не помню точно). Реально, без помощи могли решить только 3 (и это была позиции на middle или senior). Почему?

потому что давно написано стопицот библиотек это реализующие.
теми 3мя.

то есть тут как в управлении пирамида — пирамида скилов.
40-50 писателей getColor(x, y)) просто не нужны отрасли.

хватило бы и 2ух.
3ий то просто — от бас фактора защита.
библитеки тоже надо писать, саппортить, и чтобы версии появлялись новые.

problem solving skills мало корелирует с тем сколько ты задач на leetcode-е решил

Чому ви так думаєте? Літкод якраз цьому вчить, як на мене. Я от вчив математику, тому наче можу розв’язати задачу про павука, навіть якщо він к мух їсть. Хто не вчив настільки математику — не може. Хто вчив алгоритми та структури даних, хоч би й через літкод — той може алгоритмічні задачки вирішувати.

І ви, наприклад, можете придумати рішення вашої простої задачи з О(1) по пам’яті?

І ви, наприклад, знаєте рішення вашої простої задачи з О(1) по пам’яті?

Я не претендую на хороший «problem solving skills».
Про O(1) слабо себе представляю, но в целом есть два классических способа или BFS или DFS.
З.Ы. В универе делал — построчно, работает быстрее чем классический DFS.

Реально, без помощи могли решить только 3 (и это была позиции на middle или senior). Почему? Потому что в действительности программистов умеющих хороший problem solving skills мало.

я могу обобщить это до «людей умеющих хороший problem solving skills мало» что я могу прекрасно наблюдать на примере своих рабочих и ещё на примере манагеров разного уровня что в последнем случае резко смущает меня как они вообще дожили до такого уровня по корпоративной вертикали но возможно это уже чуть другая история

и здесь к.м.к. 2 важных нюанса № 1 мы (здесь обобщение) возможно просто обобщаем «программисты уже избранные по способностям» но тут наступает № 2 когда современное то что называется «программирование» уже прямо скажем не совсем или даже совсем не «инженерная дисциплина» ну селяви

fake it until you make it.
То есть, если поменять правила игры (вместо leetcode спросить просто математику), то это не решит проблему отсутствия «problem solving skills».

exactly )) см. п.п. «и ещё на примере манагеров разного уровня» видимо работает не то чтобы я проверял но на имеющихся фактах делаю такой предположение

когда современное то что называется «программирование» уже прямо скажем не совсем или даже совсем не «инженерная дисциплина»

это да, и мой уверенный вывод.
что
от математики программирование оторвалось уже в 80ых, и стало «инженерной дисциплиной»
а после 90ых — и уходит от инженерной, и уходит в сторону больше филологии-лингвистики, «прикладной философии». но это дискуссионо конечно. даже сам выбор слов не готов долго обосновывать.

главное что оно становится самостоятельной, уникальной дисциплиной, деятельностью. с своим, уникальным наборов скилов, и все меньше нуждается в бирочке «программирование это вид, подраздел чего-то»

оно просто — программирование. как и многие другие профессиональные сферы.

то что традиция записывать его куда-то осталась — нормально.
традиции они такие — могут пережить многие поколения, при том что всякое рациональное пояснение причин давно исчезло и прочно забыто.

Недавно общался со своим знакомым с «галеры» на тему собеседований — они там на андроид и куа автоматизаторов давали задачки уровня «изи» на кодилити и хаккерранке. Поймал себя на том, что задачка решается несколькими способами (с различными оверхедами памяти и процессора), но я просто ушел бы с такого собеседования сейчас.
Так ли эти задачи нужны? Что конкретно вы хотите из реальных навыков/знаний проверить?
Последний раз мне приходилось несколько лет назад вспоминать теорию и делать свою реализацию циклического буфера (ring-buffer).
Так что если проект очередной проходной, то подобные вопросы на собеседовании, как по мне, просто маркер, что собеседующий (компания) не сильно парится с тем, кто им нужен.

Так ли эти задачи нужны? Что конкретно вы хотите из реальных навыков/знаний проверить?

Суть немного в другом. Могу тебе сказать одного из 3-х (решивших) взяли в команду этот человек был очень «способным программистом». Задача вообще не требуют знаний чего-либо, но показывает умеет ли человек думать. Сейчас с leetcode-м это проверить сложно, потому что большиство людей просто на собеседовании решают то, что уже решали в том или ином виде (зачастую просто помнять подход в решении той или иной задачи). Грань между умении думать и умении решить какой-то leetcode немного стирается, потому что решать leetcode это как бренд уже или как список вопросов и ответов которые люди учат перед тем как пойти куда-то на собеседование.

Перебори дуже просто кодитяться через dfs (рекурсію). Маєш якусь конкретну задачу на приміті?

Загалом схема тіпа така:

bool dfs(State s) {
  if is_final(s):
    return is_win(s);

  for each possible move s' from s:
    if dfs(s'):
      return true;
  return false;
}

але якщо робити аж настільки акуратно, то буде повільно. Набагато частіше зручно винести State в «глобальну змінну» і її міняти на початку і в кінці. Наприклад задача на генерування всіх чисел чисел з d[0] нулів, d[1] одиниць, ..., d[9] дев’ток.

vector<int> d;
string num;
void dfs(int num_digits_left) {
  if (num_digits_left) {
    cout << num << "\n";
    return;
  }

  for (int i = 0; i <= 9; i++) {
    if (d[i] == 0) continue;  // can't use digit i, become none are left
    if (res.empty() && i == 0) continue;  // don't want to start number from 0

    // use digit i
    d[i]--;
    res += ('0' + i);

    // generate the remaining digits
    dfs(num_digits_left-1);

    // undo "use digit i"
    res.resize(res.size()-1);
    d[i]++;
  } 
} 
(писав прямо в браузері, сорі за помилки/описки)

Рекурсія там часто допомага, але хотілося б без неї. Плюс от приклад реалізації en.cppreference.com/...​lgorithm/next_permutation як на мене красивіше.

Рекурсія це супер-загальний підхід, який дає тобі можливість відсікати завідомо неправильні варіанти. Наприклад твоя ж Generate Parentheses має супер-просте рішення — генеруєш 2^(2n) послідовностей дужок і кожну з них перевіряєш на правильність. Це тупо, бо насправді тільки мала кількість послідовностей наспарвді є правильною (бонусна ультракласична задача: скільки правильних дужкових послідовностей довжини 2n?). Тобто ти перевірятимеш дохуя (2^(2n-1)) строк тіпа )..., які очевидно що неправильні. А от рекурсією зможеш вчасно відрубати неправильні послідовності і згенерувати всі послідовності за приблизно О(кількість послідовностей).

Мало того, рекурсивний підхід це круто, бо ти перетворюєш задачу з мистецтва (тобто кожна потребує креативного рішення) на інженерну (маєш фреймворк — ***рь).

Наприклад твоя задача з генеруванням дужкових послідовностей пишеться просто:

class Solution {
private:
    vector<string> res;
    string cur;
    
    void gen(int balance, int remain) {
        if (balance < 0 || balance > remain)
            return;  // abort -- no way to fix this
        if (remain == 0) {
            res.push_back(cur);
            return;
        }
        
        cur += '(';  // put (
        gen(balance+1, remain-1);
        cur.resize(cur.size() - 1);  // unput (
        
        cur += ')';  // put )
        gen(balance-1, remain-1);
        cur.resize(cur.size() - 1);  // unput )
    }
    
public:
    vector<string> generateParenthesis(int n) {
        gen(0, 2*n);
        return res;
    }
};
Тут gen це тупо dfs.

Або от за цим же фреймворком Generate Parentheses:

class Solution:
    def gen(self, pos, remain):
        if remain == 0:
            self.res.append(self.cur)
            return
        if remain < 0 or pos >= len(self.cand_count):
            return
        
        el, cnt = self.cand_count[pos]
        for i in range(cnt+1):
            self.cur += [el] * i  # add `el` i times 
            self.gen(pos+1, remain - el*i)
            if i > 0:
                self.cur = self.cur[:-i]  # remove
            
    
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # cand_count is list of pair List[(candidate, count)]
        # for input seq = [10,1,2,7,6,1,5] cand_count will be [(10, 1), (1, 2), (2, 1), (7, 1), (6, 1), (5, 1)]
        self.cand_count = list(Counter(candidates).items())
        
        self.res = []  # list of all seq
        self.cur = []  # current seq
        self.gen(0, target)
        return self.res

Цікаво, подивився своє рішення яке кілька місяців тому писав під час підготовки до інтерв’ю і побачив, що вирішів там просто створювати новий рядок замість морочитися з прибиранням останнього символу :)

Також думаю, що коли показуєш рішення треба в першу чергу показати, що воно в тебе є чисто як алгоритм, потім вже закодити цей алгоритм (тут я і зупиняюсь коли всі тести проходять), а потім вже можна говорити про ефективність з точки зору часу виконання та використання пам’яті.

class Solution {
public:
    void appendBrackets(string s, int openCount, int closeCount) {
        if (m_brackets == openCount && openCount == closeCount) {
            m_res.push_back(s);
            return;
        }
        
        if (openCount < m_brackets)
            appendBrackets(s + "(", openCount + 1, closeCount);
        
        if (closeCount < openCount)
            appendBrackets(s + ")", openCount, closeCount + 1);
    }
    
    vector<string> generateParenthesis(int n) {
        m_brackets = n;
        if (n >= 1)
            appendBrackets("", 0, 0);
        
        return m_res;
    }
    
private:
    vector<string> m_res;
    int m_brackets;
};

Так реально краще. В своє оправдання можу сказати що писав більше для демонстрації прийому (зробити якусь дію, запустити рекурсію, відмінити дію). Якщо переписати по-твоєму, то буде дійсно сильно симпатичніше:

class Solution {
private:
    int n;
    vector<string> res;
    
    void gen(string cur, int balance) {
        if (balance < 0 || balance > 2*n-cur.size())
            return;  // no way to fix this
        if (cur.length() == 2*n) {
            res.push_back(cur);
            return;
        }
        
        gen(cur + '(', balance+1);
        gen(cur + ')', balance-1);
    }
    
public:
    vector<string> generateParenthesis(int n) {
        this->n = n;
        gen("", 0);
        return res;
    }
};

Та ні, мені якраз твоє рішення більше сподобалося :)

OK, я так зрозумів, що це — DFS і треба писати саме його, можна спочатку через рекурсію, потім у стек розгорнути якщо шо.

DFS це обхід в глибину. Уяви собі дерево, де вершинами є «стан системи» а (направленим) ребром є можлива операція. Це може бути як дерево гри (ребра — можливі ходи), так і просто якийсь проміжний стан. Власне в багатьох випадках ти можеш швидко сообразити, що ти вже запоров рішення, тому немає сенсу перебирати далі.

Уяви собі задачу, що треба поставити N ферзів на дошку так, щоб вони не били один одного. Стан — позиція перших k ≤ N. Кроком ти ставиш k+1-ого ферзя і дивишся щоб він нікого не бив, якщо ок, то перебираєш далі — викликаєш рекурсивний перебор.

Власне в ідеалі ти пишеш перебір так, що весь стан передається аргументом в твій dfs. З ферзями це зробити досить просто. З дужками теж. Але деколи ти прийдеш до того, що весь цей стан обновляти дуже дорого, легше «зробити крок» і потім «відкотити назад». Наприклад уяви собі генерацію всіх можливих перестановок від 1..n. Станом може бути префікс послідовності. Але якщо ти будеш кожен раз копіювати весь вектор при виклику рекурсії, то буде повільно (в O(n) раз). Набагато простіше мати глобальний стан cur який міститиме теперішній префікс, потім перед рекурсією ти будеш дописувати в нього елемент, а після рекурсії удаляти з нього.

Решить эту задачу уже было делом принципа:

/// Place N queens on the chessboard. As a result, no two queens are attacking each other.

enum QueenPuzzleSolverError: Error {
    case negativeSize
}

class QueenPuzzleSolver {
    
    private var route: [Int] = []
    private var solutionList: [[Int]] = []
    let size: Int
    
    init(size: Int) throws {
        if size < 0 {
            throw QueenPuzzleSolverError.negativeSize
        }
        self.size = size
    }
    
    func allSolutions() -> [[Int]] {
        solutionList = []
        for index in 0..<size {
            dive(x: index, y: 0)
        }
        return solutionList
    }
    
    func dive(x: Int, y: Int) {
        route.append(x)
        if y >= size - 1 {
            solutionList.append(route)
            route.removeLast()
            return
        }
        for index in 0..<size {
            if canAttackAnything(x: index, y: y + 1) {
                continue
            }
            dive(x: index, y: y + 1)
        }
        if !route.isEmpty {
            route.removeLast()
        }
    }
    
    func canAttackAnything(x: Int, y: Int) -> Bool {
        for (index, value) in route.enumerated() {
            if isMutualThreat(x: x, y: y, otherX: value, otherY: index) {
                return true
            }
        }
        return false
    }
    
    func isMutualThreat(x: Int, y: Int, otherX: Int, otherY: Int) -> Bool {
        return x == otherX || y == otherY || abs(x - otherX) == abs(y - otherY)
    }
}

do {
    let manager = try QueenPuzzleSolver(size: 4)
    print(manager.allSolutions())
}
catch {
    print(error) // I am from your ex-project.
}

canAttackAnything можно сделать за O(1) вместо O(n) с небольшими оптимизациями, можете посмотреть здесь leetcode.com/...​oblems/n-queens/solution

Всьо ок, але можна трошки спростити. У тебе dive досить сильно рознесений: він підрозумиває, що точно можна поставити в (x, y) але цю перевірку роблять в зовсім іншому місці. Трохи чистіше (імхо) було б якось так:

    func dive(x: Int, y: Int) {
      if canAttackAnything(x, y) {
        return;
      }
      route.append(x)
      // main code
      route.removeLast()  // if !route.Empty -- не потрібен
    }

але можна піти ще далі — давай взагалі не казати dive’у на який x ставити ферзя, тільки на який y і єдина штука, яку він підрозумиватиме, це те, що до нього всі інші ферзі з меншими y стояли без конфліктів:

    func dive(y: Int) {
      if y == size {
        solutionList.append(route)
        return
      }
      for x in 0..<size {
        if !canAttackAnything(x: x, y: y) {
          route.append(x)  // put
          dive(y: y + 1)  // continue recursive
          route.removeLast()  // undo put
        }
      }
    }

Якщо вже дійсно прискорювати, то Артем правильно сказав, що там canAttackAnything можна за константу зробити. Перша тривіальна штука — тобі не треба перевіряти чи y співпадають — вони за побудовою різні. Друге цікаве спостереження в тому, що якщо у тебе є ферзь на (x, y), то він б’є всі клітинки:

  1. на тій же вертикалі: (x, y+1), (x, y-1), ...
  2. на тій же горизонталі (x+1, y), (x+2, y), ..., (x-1, y), (x-2, y), ...
  3. на тій же діагоналі /: (x+1, y+1), (x+2, y+2), ..., (x-1, y-1), (x-2, y-2), ...
  4. на тій же діагоналі \: (x+1, y-1), (x+2, y-2), ..., (x-1, y+1), (x-2, y+2), ...

Як вже вияснили, (2) можна взагалі не перевіряти.

Щоб швидко перевірити (1) можна просто зберігати всі заборонені x’и: тобто масив булів xForbidden розміру size, де xForbidden[x] == true, якщо на цій горизонталі вже хтось стоїть.

З діагоналями той же прикол: тобі просто треба пронумерувати діагоналі / і окремо \, кожної з таких діагоналей є 2n-1. Ферзь в (x, y) б’є по діагоналі типу \ всіх інших ферзів (x1, y1), у яких x-y == x1-y1, тому заводиш ще один булевий масив diag2Forbidden розміру 2n-1 де індексами від -(n-1) до (n-1) включно (ну або додаєш до всіх індексів n-1 і тоді буде стандартний масив розміру 2n-1 з індексами від 0 до 2n-2).

Ітого canAttachAnything(x, y) виглядатиме десь так:

  return xForbidden[x] || diag1Forbidden[x+y] || diag2Forbidden[x-y+n-1]
додати елемент буде виглядати так:
  route.append(x)  // put
  xForbidden[x] = diag1Forbidden[x+y] = diag2Forbidden[x-y+n-1] = true
undo додати буде так:
  xForbidden[x] = diag1Forbidden[x+y] = diag2Forbidden[x-y+n-1] = false
  route.removeLast()

менш чисто, але чуток (в n раз) швидше.

P.S. я дійсно був на всеукрі в Чернівцях в 2002 :)

Так-то пример про доску-не самый лучший
1.Действуя жадно и ставя так,чтоб условие выполнялось сейчас вы можете не добится оптимального исхода.
К примеру для доски 8×8 такая последовательность (0,0),(1,7),(2,1),(3,6),(4,3) сделает невозможной постановку всех 8 фигур
2.Несложно доказать что ставя ферзей на расстоянии хода коня(сначала на нечетных столбцах,потом на четных) вы поставите максимальное число ферзей за линейное время

1.Действуя жадно и ставя так,чтоб условие выполнялось сейчас вы можете не добится оптимального исхода.
К примеру для доски 8×8 такая последовательность (0,0),(1,7),(2,1),(3,6),(4,3) сделает невозможной постановку всех 8 фигур

Я не думаю, что оратор предлагал жадный алгоритм, речь идет о переборе.

Если выбрал неправильную конфигурацию в начале и зашел в тупик, алгоритм откатится назад до места, где была совершена последняя ошибка, попробует что-то другое и так далее пока не найдет правильное решение.

2.Несложно доказать что ставя ферзей на расстоянии хода коня(сначала на нечетных столбцах,потом на четных) вы поставите максимальное число ферзей за линейное время

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

Если выбрал неправильную конфигурацию в начале и зашел в тупик, алгоритм откатится назад до места, где была совершена последняя ошибка, попробует что-то другое и так далее пока не найдет правильное решение.

Конечно, он найдёт, только блуждание в тупиках может занять много времени.

Если говорить про оптизизацию, то я бы делал так: текущее состояние перебора храниться в виде массива длины N, в котором храняться N-битные целые, 1 соответствует тому, что туда можно ставить ферзя, 0 отвечает тому, что туда ставить ферзя нельзя.

Далее, для каждого поля у нас отдельно храниться маска полей, где нулями обозначены поля, которые надо вычеркнуть (становяться недоступными), если туда поставить ферзя.

Далее, шаг перебора. Если у нас в массиве все единички, то готово. Иначе для каждой единицы выбираем элемент у которого наименьшее количество единиц, не считая одиноких единиц. Для каждой единицы в нём копируем состояние, делаем AND с заранее посчитанной маской и если у нас не получились нули, то начинаем новую итерацию.

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef uint64_t mask_t;

#define QBITS ((int)(8 * sizeof(mask_t)))
#define ONE(n) (((mask_t)1) << n)
#define ONES(n) ((~((mask_t)0)) >> (QBITS - n))

static inline int pop_count(mask_t value)
{
    return __builtin_popcountll(value);
}

static inline int first_one(mask_t value)
{
    return __builtin_ctzll(value);
}

void usage(void)
{
    printf("Usage: nqueen N\n");
    printf("  N - board size, 1 <= N <= %d\n", QBITS);
    exit(0);
}

mask_t * magic_masks;

void calc_masks(int N, int col, int row, mask_t * restrict const columns)
{
    for (int i=0; i<N; ++i) {
        columns[i] = ONES(N);
    }

    static int delta_col[8] = {  0, +1, +1, +1,  0, -1, -1, -1 };
    static int delta_row[8] = { +1, +1,  0, -1, -1, -1,  0, +1 };

    for (int i=0; i<8; ++i) {
        int c = col + delta_col[i];
        int r = row + delta_row[i];
        while (c >= 0 && c < N && r >= 0 && r < N) {
            columns[c] ^= ONE(r);
            c += delta_col[i];
            r += delta_row[i];
        }
    }
}

void init_masks(int N)
{
    magic_masks = malloc(N * N * N * sizeof(mask_t));
    mask_t * ptr = magic_masks;
    for (int col = 0; col < N; ++col) {
        for (int row = 0; row < N; ++ row) {
            calc_masks(N, col, row, ptr);
            ptr += N;
        }
    }
}

void visit(int N, const mask_t * restrict const state)
{
    printf("Find");
    for (int i=0; i<N; ++i) {
        printf(" %d", first_one(state[i]));
    }
    printf("\n");
}

void enumerate(int N, mask_t avail, const mask_t * restrict const state)
{
    if (avail == 0) {
        visit(N, state);
        return;
    }

    int best_col = -1;
    int best_pops = N + 1;
    mask_t mask = avail;
    while (mask) {
        int col = first_one(mask);
        mask &= (mask-1);

        int pops = pop_count(state[col]);
        if (pops < best_pops) {
            best_col = col;
            best_pops = pops;
        }
    }

    mask = state[best_col];
    while (mask) {
        int row = first_one(mask);
        mask &= (mask-1);

        mask_t new_state[N];
        memcpy(new_state, state, sizeof(new_state));

        int ok = 1;
        const mask_t * possible = magic_masks + N*N*best_col + N*row;
        for (int i=0; i<N; ++i) {
            new_state[i] &= possible[i];
            if (new_state[i] == 0) {
                ok = 0;
                break;
            }
        }

        if (ok) {
            enumerate(N, avail ^ ONE(best_col), new_state);
        }
    }
}

int main(int argc, char * argv[])
{
    if (argc != 2) {
        usage();
    }

    const int N = atoi(argv[1]);
    if (N <= 0 || N > 64) {
        usage();
    }

    init_masks(N);

    mask_t state[N];
    for (int i=0; i<N; ++i) {
        state[i] = ONES(N);
    }

    enumerate(N, ONES(N), state);

    free(magic_masks);
    return 0;
}

Тестирование

$ time  ./nqueen 16 | wc -l
14772512

real    0m53.048s
user    0m55.254s
sys     0m9.053s

Для размера доски 16×16 как раз 14772512 вариантов согласно wiki, и все прога нашла примерно за минуту. Если брать размер доски 15×15, то где-то менее 10 секунд.

Написание кода 2 часа вышло

Так-то я пересмотрел и это не всегда работает(работает лишь для n нечетных и не кратных 3).Учитывая что на википедии есть про это статья и там не придумано математическое решения то видимо действительно неочевидно:(Тогда извиняюсь за несправедливое замечание.
Кстати,в решении приведеном выше наверное можно пронумеровать диагонали,таким образом мы будем считать какие диагонали заняты и нам не прийдется сравнивать поклеточно

Там комбинаторный взрыв, от судьбы не уйдёшь, ни от своей, ни от мировой. Вроде как есть утверждения, что подсчёт количества расстановок NP-полная задача. Поэтому рано или поздно ресурсов не хватит.

Если интересна математика, то это последовательность A000170, там же можно найти несколько математических статей по этой теме, если совсем уж интересно. То решение, что я привёл, как по мне, баланс между очевидной оптимизацией и влазаньем в дебри. Хотя могут быть ещё более эффективные простые решения.

shorturl.at/grtL5

Похоже на то, что мы в Черновцах пересекались.

Prolog же, изи... Там уже этот DFS встроен :)

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

мне в своё время помогла разобраться в вопросе книга Вирта «Алгоритмы и структуры данных». Старая и на Паскале (новая редакция на обероне есть вроде бы), но перебор с возвратом там разобран был хорошо, помогает решить целый класс задач, все эти ферзи и прочее

Ну... неэффективно это часто. Те же танцующие связи порвут этот перебор с возвратами... Вообще, есть же четвёртый том Дональда Кнута, там всё расписано для идиотов.

Прежде чем бежать марафон — надо научиться ходить. Потом — быстро ходить. Потом немного бегать... Ну и так далее

Ну а литкод учит тебя ползать всё более искушенно :)

Я как-то учил php при помощи leetcode. github.com/...​ree/master/src/Algorithms

Мне помогло.

Научился создавать классы-контейнеры.

class Status {
    var $key;
    var $i;
    var $j;
    function __construct($key, $i, $j) {
        $this->key = $key;
        $this->i = $i;
        $this->j = $j;
    }
}

И всё? А не проще было просто взять сэмпл, когда он тебе понадобился? Сказал бы ещё вообще зачем городить класс, на пэхе, если можно по классике тупо работать с массивом и всё.

Конструкторы у классов вообще сложная вещь. Когда у тебя 1 аргумент, это ещё читаемо. Два — уже шанс их путать. А когда много... ой, непросто тебе будет найти ошибку, если протупил с порядком.

Классы вообще не самая лучшая субстанция для данных. Они нужны либо для ООП, либо для замыкания в себе сущностей, то есть для удобочитаемости кода. Скорости они не дают, компактности тоже.

Пример: у тебя класс, который ты инициализируешь в конструкторе. Вопрос: а что бы случилось, инициализируй ты его голым, и заполнив прямо в коде? Мой ответ — повысилась бы читабельность кода. Явный конструктор нужен тогда, когда тебе действительно есть смысл спрятать логику от бессмысленного просмотра, когда там выполняются мелочи, в которые не нужно вникать при пользовании, понимая лишь саму идею.

А за переменные $key, $i, $j в продакшене по тебе плачет тряпка с жёлтым контентом. Их применяют как итераторы, никто не будет ждать от них иного смысла. Умение именовать и компоновать сущности — это в буквальном смысле половина профессии. И от этого зависит ценность и полезность кода.

Умение именовать и компоновать сущности — это в буквальном смысле половина профессии

А ещё выдерживать стиль, ритм-темп кода. Причём не свой, а тот что уже сложился.
А то когда то хороводное, то из психодела строчки, а потом бац — в лесу родилась ёлочка, и завершается торжественно текстом гимна Аргентины
И улучшение — был нарисован рыцарь,мобилочку ему в руку! Чё он,как не настоящий пацан!

А ещё выдерживать стиль, ритм-темп кода. Причём не свой, а тот что уже сложился.

Его не существует в природе. Есть разница на 3 порядка между тем, что надо реально решать и раскапывать крупицы истины в стоге маркетингового навоза вместо документации. И тем, что можно тупо накопипастить с минимальными изменениями. И тем, что вообще хрен знает как делать, потому что нихрена толком не согласовано, а тебе наврали с три короба, и теперь рассказывают какой ты дурак давай переделай (а вдруг на этот раз нам понравится).

Касательно стиля — вот не поверишь, но при активной правке и в стабильной фазе у кода должно быть разное форматирование. Попробуешь сделать по-другому, и здрасьте вам низкая читаемость и тяжесть поиска ошибок одновременно. А посему, получите-распишитесь подделку тестов, потому что на настоящее покрытие тестами тупо не осталось времени.

А если к этому ритму добавляется право звонить и постоянно заё****ть, то смело множьте ожидания по времени на 30. Этому лит-кукареку-код вас не учил, не так ли?

Ещё как существует. С этого начинает свой Мифический чел месяц Брукс.

Есть разница на 3 порядка между тем, что надо реально решать и раскапывать крупицы истины в стоге маркетингового навоза вместо документации

Естественно. Это и есть программирование, а традиция что это набивка перфоркарт вчерашней домохозяйкой (такая была реклама вакансии, в одной крупной компании, в 50ых или 60ых,если верить одной книге о гендерной истории айти) того что ей принесли высокие умы.

В описании указывалось что женщины поэтому куда лучше как программисты чем мужчины

А если к этому ритму добавляется право звонить и постоянно заё****ть,

Как где.
жалобе что перфекционистам инженерам всякий там бизнес и менеджеры мешают работать -сто лет в обед.

Этому лит-кукареку-код вас не учил, не так ли?

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

В смысле, не можешь? Там что, ещё и ответов нет для желающих НЕ решать конкретную задачу, а просто посмотреть как надо?

Или есть, но надо докинуть денежку микротранзакцией в доилочку?

Задача на 200% синтетическая, у неё только описание условий на полстраницы и шесть толкований. О чём я и говорил: ФУФЛО, с классической игрой-доилкой: СНАЧАЛА заставить тратить время, чтобы ПОТОМ продавать способ потратить его меньше, но только в конкретном случае, а по факту с каждой итерацией всё увеличивать ВЫЖИГАНИЕ ВРЕМЕНИ.

Или есть, но надо докинуть денежку микротранзакцией в доилочку?

я понимаю желание обличить проклятый литкод, но прежде чем сочиться сарказмом — стоит всё-таки убедиться, что для него есть повод. к любой задаче есть обсуждение, в котором всегда есть пакованы решений, в том числе с обьяснениями и прочим

Тогда в чём проявляется ТВОЯ неспособность решить (точнее пропустить) задачу, которая тебе больше не понадобится никогда нигде? Просто посмотри, какое решение имелось в виду. Потому что эта задача придумана под готовый ответ, а не наоборот. Соответственно настоящим условием задачи является зубрёжка «правильного» ответа.

PS. Львиную долю незнакомых тебе задач по работе ты почему-то решаешь копипастой правильных решений и не заморачиваешься. Что здесь тебе мешает проявить тот же навык? Да, внезапно, в жизни можно пользоваться шпаргалками.

«ты воюешь не туда»
в смысле — я ничего не говорил про неспособность решить
кровь ярости застилает глаза? :)

кровь ярости застилает глаза

Фейспалм при виде адептов литшизы

Ой, как по себе судишь :)

Рекомендую узнать Bainfuck — прекрасный ЯП, отлично расширяет горизонты. И вот ничем не хуже литкота. И однозначно добавляет счастья.

PS. Если у меня одни и те же мысли, что в этом плохого? Ты ведь называешь «конструктивом» исключительно 100% согласие с твоим мнением, которое нифига не твоё собственное даже, а лишь оправдание твоей траты времени на дешёвый разрекламированный фуфел.

PPS. Доказывать что я знаю буду как-то не тебе. Ты предпочитаешь делу комфорт общения — звони в сєкс по телефону. Заодно и ЧСВ передёрешь.

Появилось решение.

Ура!

class Solution {

    /**
     * @param String $beginWord
     * @param String $endWord
     * @param String[] $wordList
     * @return String[][]
     */
    function findLadders($beginWord, $endWord, $wordList) {
        $maskToWords = [];
        $wordToMasks = [];
        $closestWords = [];
        $allwords = $wordList;
        $allwords[] = $beginWord;
        foreach($allwords as $word){
            for($i=0;$i<strlen($word);$i++){
                $mask = $word;
                $mask[$i] = '_';
                $maskToWords[$mask][$word] = true;
                $wordToMasks[$word][$mask] = true;
            }
        }
        foreach($allwords as $word){
            foreach($wordToMasks[$word] as $mask => $notUsed){
                foreach($maskToWords[$mask] as $linkedWord => $notUsed){
                    $closestWords[$word][$linkedWord] = true;
                }
            }
        }
        unset($maskToWords);
        unset($wordToMasks);
        unset($allwords);
        $queue = new SplQueue();
        $visitedNodes = [];
        return (new Node($beginWord, $visitedNodes))->breadthFirstSearch($queue,$endWord,$closestWords);
    }
}

class Node {
    private $name;
    private $distance;
    private $parent;
    private $visitedNodes;
    function __construct($name, &$visitedNodes, $parent = null, $distance = 1){
        $this->name = $name;
        $this->parent = $parent;
        $this->distance = $distance;
        $this->visitedNodes = &$visitedNodes;
    }
    private function getNextNodes(&$closestWords){
        $nodes = [];
        foreach($closestWords[$this->name] as $linkedWord => $notUsed){
            if(!isset($this->visitedNodes[$linkedWord])){
                $nodes[] = new Node($linkedWord, $this->visitedNodes, $this, $this->distance+1);
            }
        }
        return $nodes;
    }
    private function getPath(){
        $node = $this;
        $path = new SplDoublyLinkedList();
        while($node){
            $path->unshift($node->name);
            $node = $node->parent;
        }
        $pathArray = [];
        foreach($path as $item){
            $pathArray[] = $item;
        }
        return $pathArray;
    }
    function traverse($queue,&$closestWords){
        $this->visitedNodes[$this->name] = true;
        foreach($this->getNextNodes($closestWords) as $node){
            $queue->enqueue($node);
        }
    }
    function breadthFirstSearch($queue,$endWord,&$closestWords){
        $this->traverse($queue,$closestWords);
        $paths = [];
        $bestDistance = null;
        while(!$queue->isEmpty()){
            $nextNode = $queue->dequeue();
            if(!is_null($bestDistance) && $bestDistance < $nextNode->distance)
                break;
            if($nextNode->name===$endWord) {
                if(is_null($bestDistance))
                    $bestDistance = $nextNode->distance;
                $paths[] = $nextNode->getPath();
            }
            $nextNode->traverse($queue,$closestWords);
        }
        return $paths;
    }
}
SplDoublyLinkedList

и

SplQueue

это новые классы для меня.

Афігенна ідея з mask’ами, але, здається, тут це overkill.

function diff($a, $b) {
    $res = 0;
    $n = strlen($a);
    for ($i = 0; $i < $n; $i++)
        if ($a[$i] != $b[$i])
            $res++;
    return $res;
}

class Solution {
    function findLadders($beginWord, $endWord, $wordList) {
        // bfs
        $dist = array($beginWord => 0);
        $prev = array();
        $queue = array($beginWord);
        for ($i = 0; $i < count($queue); $i++) {
            $curWord = $queue[$i];
            foreach ($wordList as $nextWord) {
                if (diff($curWord, $nextWord) != 1)
                    continue;
                
                if (!array_key_exists($nextWord, $dist)) {
                    array_push($queue, $nextWord);
                    $dist[$nextWord] = $dist[$curWord] + 1;
                    $prev[$nextWord] = array($curWord);
                } else if ($dist[$nextWord] === $dist[$curWord]+1) {
                    array_push($prev[$nextWord], $curWord);
                }
            }
        }
        
        if (!array_key_exists($endWord, $dist))
            return array();

        // generate all
        $res = array(array($endWord));
        for ($p = $dist[$endWord]; $p > 0; $p--) {
            $nextRes = array();
            foreach ($res as $seq) {
                $curWord = $seq[count($seq)-1];
                foreach ($prev[$curWord] as $prevWord) {
                    array_push($nextRes, array_merge($seq, array($prevWord)));
                }
            }
            $res = $nextRes;
        }
        
        // reverse all sequences in $res
        $reversedRes = array();
        foreach ($res as $seq)
            array_push($reversedRes, array_reverse($seq));
        return $reversedRes;
    }
}

Мое решение на Rust

use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::rc::Rc;
use std::cell::RefCell;

// #[derive(Clone)]
struct Node<'a> {
    word: &'a str,
    previous: Vec<Rc<RefCell<Node<'a>>>>,
}

impl<'a> Node<'a> {
    fn new(word: &'a str) -> Self {
        Self {
            word: word,
            previous: vec![]
        }
    }
    
    fn to_words(&self) -> Vec<Vec<String>> {
        if self.previous.is_empty() {
            vec![vec![self.word.to_string()]]
        } else {
            let mut result = vec![];
            
            for prev in &self.previous {
                let prefixes = prev.borrow().to_words();
                
                for mut prefix in prefixes {
                    prefix.push(self.word.to_string());
                    result.push(prefix);
                }
            }
            
            result
        }
    }
}

impl Solution {
    pub fn find_ladders(begin_word: String, end_word: String, word_list: Vec<String>) -> Vec<Vec<String>> {
        let mut patterns = HashMap::new();
        
        for word in &word_list {
            let mut chars = word.chars().collect::<Vec<_>>();
            
            for i in 0..chars.len() {
                let mut old_char = '_';
                std::mem::swap(&mut old_char, &mut chars[i]);
                
                let pattern = chars.iter().collect::<String>();
                
                patterns.entry(pattern).or_insert_with(|| HashSet::new()).insert(word);
                
                std::mem::swap(&mut old_char, &mut chars[i]);
            }
        }
        
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        
        visited.insert(&begin_word);
        queue.push_front(Rc::new(RefCell::new(Node::new(&begin_word))));
        
        let mut result_nodes = vec![];
        
        let mut s = 0;
        while !queue.is_empty() && result_nodes.is_empty() {
            // println!("{} {}", s, queue.len());
            s+=1;
            let mut new_visited = HashSet::new();
            
            let mut new_nodes = HashMap::new();
            
            for _ in 0..queue.len() {
                let prefix = queue.pop_back().unwrap();
                
                if prefix.borrow().word == end_word {
                    result_nodes.push(prefix);
                } else {
                    let mut chars = prefix.borrow().word.chars().collect::<Vec<_>>();
                    
                    for i in 0..chars.len() {
                        let mut old_char = '_';
                        std::mem::swap(&mut old_char, &mut chars[i]);
                        
                        let pattern = chars.iter().collect::<String>();
                        
                        if let Some(next_words) = patterns.get(&pattern) {
                            for &next_word in next_words {
                                if !visited.contains(next_word) {
                                    
                                    let new_prefix = new_nodes.entry(next_word).or_insert_with(|| Rc::new(RefCell::new(Node::new(next_word))));
                                    new_prefix.borrow_mut().previous.push(prefix.clone());
                                    new_visited.insert(next_word);
                                }
                            }
                        }
                        
                        std::mem::swap(&mut old_char, &mut chars[i]);
                    }
                }
            }
            
            for (_, node) in new_nodes {
                queue.push_front(node);

            }
            
            
            for word in new_visited.into_iter() {
                visited.insert(word);
            }
        }
        
        let mut result = vec![];
        
        for mut node in result_nodes {
            for seq in node.borrow().to_words() {
                result.push(seq);
            }
        }
        
        result
        
        // result.into_iter().map(|chain| chain.into_iter().map(|word| word.clone()).collect()).collect()
    }
}

який же ж Rust багатослівний
ось коротко на Python, можна вкластися в інтерв’юху
leetcode.com/...​simple-BFS-layer-by-layer

class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):

        wordList = set(wordList)
        res = []
        layer = {}
        layer[beginWord] = [[beginWord]]

        while layer:
            newlayer = collections.defaultdict(list)
            for w in layer:
                if w == endWord: 
                    res.extend(k for k in layer[w])
                else:
                    for i in range(len(w)):
                        for c in 'abcdefghijklmnopqrstuvwxyz':
                            neww = w[:i]+c+w[i+1:]
                            if neww in wordList:
                                newlayer[neww]+=[j+[neww] for j in layer[w]]

            wordList -= set(newlayer.keys())
            layer = newlayer

        return res

Это решение менее эффективно, чем мой вариант.

for c in ’abcdefghijklmnopqrstuvwxyz’:

А это, ***ка, вообще фейспалм. Даже на Rust можно сделать

for c in 'a'..='z'

странный язык, сколько раз в жизни нужны такие вещи чтобы их добавлять в язык ?

В Rust char (как и все целочисленные типы) реализует trait Step, поэтому возможность итераций между двумя char’ами таким синтаксисом получает бесплатно.

Это решение менее эффективно, чем мой вариант.

за 35-40 хв на інтерв‘ю накатаєш ту плахту тексту на Rust без багів?

Очень полезная штука, помогает научится чистому кодингу, который может и не часто, но все равно бывает нужен в работе. Те кто говорят про то что все гуглится видно не сталкивались с задачам которые НЕ гуглятся — да, такие есть, может не в аутсорсе, но в продуктах и стартапах встречаются

Сначала было тяжело, а теперрь по фану трачу 40-120 минут в день на Leetcode или подобные задачи из книжек по алгоритмам, заметил, что мозги в «остром» состоянии поддерживаются от этого.

Угадай, когда тебе реально что-то из этого понадобится, ты по фану вспомнишь, или загуглишь?
Мозги не бывают в остром состоянии. Это просто память, и чистится она весьма занятным алгоритмом, и терять ты эти «знания» будешь не по кусочку, а огромным блоками. И быстрее, чем учишь.

Не веришь? Простой тест: чему равно число e хотя бы до 2 знака после запятой? А ведь когда-то знал. Отвечать не надо, когда реально понадобится, ты просто скопипастишь. А с литкодом... это как если бы тебя число Ейлера спросили :)

Угадай, когда тебе реально что-то из этого понадобится, ты по фану вспомнишь, или загуглишь?

Не-не, это неправильная постановка вопроса. Также 16-летние подснежники говорят «зачем университет, 90% знаний не нужны»
Весь я, мое общение, восприятие, влиянение на людей — это и есть та сумма знаний полученных везде. Какой процент в моей жизни играют знания, которыми я пользуюсь на работе? Минимальный — они нужны только для работы.
Правда в том, что я не могу знать точное влияние полученной информации в моей жизни

число e хотя бы до 2 знака после запятой

тут ты ошибся
2.7[1828] — год рождения Льва Толстого, запоминалка от училки в школе застряла в голове на всю жизнь.

Вот видишь! Хрен бы ты иначе выучил год рождения Льва Толстого. Но читать так и не научили: я ж просил, не отвечать.

А теперь скажи, ЗАЧЕМ ты это знаешь, в смысле год рождения? Почему не год рождения скажем Зеленского? Его тоже довольно просто запомнить.

PS. Дважды ЛевТолстой 2.718281828

Там багато чого йде у довгострокову пам’ять. Підходи, головна теорія — лишаться. Тому хто займався буде набагато легше і швидше потім знову увійти в форму.
Олсо, я ще пам’ятав 4 після двох 1828 у числа е.

Саме довгострокова пам’ять вичищається величезними масивами. Не віриш — згадай себе у 2 роки. А потім як ти виглядав у 12. А потім знайди фотки та подивись :)

Польза от литкода не в решении каких-то конкретных задач и запоминании конкретных фактов или хаков, а в умении после энного количества решенных задач интуитивно видеть шаблоны и понимать где вылезут корнер кейсы.
Эти скиллы помогают экономить довольно много времени в прикладных задачах. А конкретика вроде числа e или какой-то формулы здесь ни при чем и она гуглится, да.

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

А в чём смысл отвечать? Допустим, James S. A. Corey. — Tiamat’s Wrath.

Если техническая — то мне по программированию давно перестали заходить книги. Они полезны новичкам. Этот продукт давно уж не делают эксперты своей области, их пишут «технические писатели», зачастую сами разобравшиеся в теме весьма поверхностно. Экспертам же, чтобы опубликовать информацию, более не требуется помощь книгоиздателей, редакторов, etc.

Книги хороши в фундаментальных науках, там где редко что-то меняется. А там где всё ненадёжно как прогноз погоды — инфу стоит брать непосредственно, и только тогда, когда понадобилась. В противном случае тебе просто промоет мозги поток бесполезной информации, которую ты всё равно забудешь. Но изучая её, ты забудешь то что уже знал.

Ты ж не думал, что знания аккуратно копятся как дерьмо на диске? Это скорее корзина, у которой нет функции «очистить», вернее ты не знаешь как. Не говоря уж о том, чтобы хранить знания за пределами мозга.

Польза от литкода не в решении каких-то конкретных задач и запоминании конкретных фактов или хаков, а в умении после энного количества решенных задач интуитивно видеть шаблоны и понимать где вылезут корнер кейсы.

Внезапно, интуиция здесь вредит. В реальности корнер кейзы случаются совсем уж другими. А интуиция подсунет классическое решение.

Мой совет — смотрите код диетического пепси, у него вы научитесь больше чем ;)

Якщо треба туди, де це питають, можете спробувати. Бо ніде ці умови задач окрім щоб завалити не використовуються, вони суто бюрократичні.

Але літкод осто******ились настільки, що навалили в задачі лайна власного виробництва. Тобто, вас тупо розводитимуть рішати задачі, які ніде більше вам ніколи не знадобляться, а вас тупо шиють в дурні, користуючись тим, що в синдрому Данінга-Крюгера є не тільки пік, але й величезна прірва.

А як вони спамлять, як спамлять, і не тільки на DOU. Звичайно ж розповідаючи легенди про «Васю», який літкод, літкод, літкод, літкод, і одразу в Гугл великою шишкою.

А кто сказал что я не добрый? Просто бюрократическое говно ≠ счастье.

люди решающие литкод статистически более счастливы, и добрее, и не несут негатив в комментариях. Вам стоит попробовать, эксперимента ради.

Мазохисты то же самое говорят. Может вам стоит попробовать, эксперимента ради? К тому же у них просто колоссальное преимущество: ОНИ НЕ СПАМЯТ.

Вот именно! Спамом делиться не надо.

Цікаво те що цю біду захищають якісь непонятні ноунейми

Есть распространенное мнение что большая часть выручки литкода идет с продажи премиум подписок пользователям. На самом деле, премиум подписки дают не более 18% от выручки. 80% выручки идет от геренации электричества из энергии горящих пуканов литкод хейтеров и продажи ее в сеть по экологическому тарифу.

Есть распространённое мнение, что СПАМ — это плохо. Литкод имеет своих дрoчеров — пусть имеет. Просто задрали спамить своим дерьмом. Которое, разумеется, маркетинговый булшит и ничего кроме.

PS. Без премиума, насколько помню, его функционал вообще близок к нулю, и служит исключительно для попытки развести на кота в премиум-мешке.

литкод — это уже стандарт индустрии. В районе бухты сан франциско без него практически невозможно найти приличную работу. Литкод увеличивает общую компенсацию в два раза. Скоро эта тенденция дойдет и до Европы. Тем более что и в Европе БигТек И ФинТек юзают литкод во всю.
ps. Без премиума можно использовать литкод на 80- 90%. Нельзя только фильтровать задачи по компании. и нет встроенного дебага(на интервью его тоже нет). Плюс несколько задач недоступны.

Литкод увеличивает общую компенсацию в два раза.

Чем увеличил? Тем что синьоры вместо изучения тонкостей фреймворков и бест практис, дрочат синтетические задачки, 95% из которых не встречаются на реальных проектах?

99,99999999995%, а те что встречаются, попали в литкод по невнимательности копипастой

Так и увеливается. Сидишь, работаешь меньше чем за 100к, а потом научился литкодить и переходишь на 180k+. А тонкости фреймворков вообще никто на интервью сейчас не спрашивает. Идея в том, что кто способен осилить задачи с литкода,тот любой фреймворк осилит за считанные недели. Часто бывает, что литкодишь на джаве, а потом пишишь на С++(или наоборот).

Дядьку, а scala буде, щоб її лупати?

проходишь такой собеседование в амазон а там оказывается IAM на spring security построен :) как хорошо что учил spring вместо литкода %) sarcasm

поверь от того сколько там платят описанная тобой ситуация практически не зависит и фактически можно прямо говорить об классических 50/50 либо попадёшь либо не попадёшь на

свои фреймворки, которых нет в открытом доступе. Ты не можешь учить их тонкости, не попав вовнутрь.

с другой стороны опыта попадания не отнять коль сколь такой опыт уже научился набирать и каждый новый «свои фреймворки которых нет в открытом доступе» (к) (тм) воспринимается уже как «#никогданебылоивотопять а ну ок пойду сварю кофе»

но тут к.м.к. важный нюанс

Поверь, там не нужны тонкости хайбернейта, его там не будут юзать.

к.м.к. тут сильно зависит от того какие тонкости хибернейта ты (здесь обобщение) знаешь и как именно ты понимаешь эти тонкости как некое абстрактное обобщение принципа вполне более чем распространяемого и применимого на другие тонкости другого хайбирнейта или же ж как на вечно закарбованные инструкции на уровне магического ритуала который работает всегда но никто не знает как почему и вообще даже работает ли оно вообще

ЗЫ: последняя ситуация «и работает ли оно вообще» сильно ближе к реальности чем может казаться )) я проверял а вот другие таки не проверяли

ЗЫ: ну и потом system design interview они будут проводить на некотором обобщённом примере того что есть в открытом доступе здраво полагая что на интервью спроектировать систему систему на том что есть у них ты не сможешь

ЗЫ: хотя мало ли ))

В районе бухты сан франциско без него практически невозможно найти приличную работу

Напишешь то же самое, КОГДА НАЙДЁШЬ работу. Даже неприличную.

Літкод ок, якщо ти джун-студент, поганяти себе, перевірити свій скіл. Але мідл, сініору це нащо?

Чому не законтрібутити в бібліотеку, яку використовуєте в проекті? Чому не попрофайлити якийсь фреймворк і не закинути перфоманс імпрув туди? Та ви просто загляньте в середину любої ліби, там зазвичай такий ад твориться, що просто гріх не законтрібутити.

Від сініора я б очікував якийсь «реальний» вклад. 1 PR в лібу, якою користуються тисячі девів краще 1000 літкод задач.

По фану, тут же пишуть. І та, є проекти, хоч їх і мало, де ці знання допомагають. З останнього, що бачив ще до гугла — оптимальний перерахунок положень об’єктів на мапі та їх лейбочок враховуючи кластеризацію.

Абсолютна більшість наших сіньорів на це подивиться і накатає в лоб і потім буде дивуватись: «А чому перфоманс такий поганий? Я ж відважно скопіпастив зі стековерфлоу, застосував SOLID, DRY, KISS, FISTING, а воно все одно не працює.»

По фану, тут же пишуть.

Хз, я отримую в 10 раз більше фану від перфоманс фіксів в лібу, на якій крутиться половина бекенду епла, наприклад. Бо я знаю, що цей код реально піде в тисячі продакшенів.

З останнього, що бачив ще до гугла — оптимальний перерахунок положень об’єктів на мапі та їх лейбочок враховуючи кластеризацію.

Прикольно. Але ця задача давно вирішена в провайдерів мап апі.

Я це до чого. Задачкі це прикольно і я колись теж любив порозбирати. Але зараз, коли майже все опен-сорс, можна фокуситись на реальних проблемах in the wild.

Хз, я отримую в 10 раз більше фану від перфоманс фіксів в лібу, на якій крутиться половина бекенду епла, наприклад. Бо я знаю, що цей код реально піде в тисячі продакшенів.

Ну кому як

Прикольно. Але ця задача давно вирішена в провайдерів мап апі.

не у всіх. Вирішена задача у дорожчих провайдерів.

Я це до чого. Задачкі це прикольно і я колись теж любив порозбирати. Але зараз, коли майже все опен-сорс, можна фокуситись на реальних проблемах in the wild.

Тобто розгрібати продакшен код на роботі, а потім ще й окремо?) Ну кожен угорає, як хоче. Сенс у тому, що якщо людина хоче повирішувати алгоритмічні задачки, це не значить, що такий самий фан їй доставляє знову розгрібати чиєсь гівно в прод коді.

Від сініора я б очікував якийсь «реальний» вклад.
Літкод ок, якщо ти джун-студент, поганяти себе, перевірити свій скіл. Але мідл, сініору це нащо?

Реальний вклад робиться на роботі за гроші. Очікувати від будь-кого, що він поза роботою ще витрачає час на ту ж роботу, але безкоштовно — то дивно. Це ок якщо ти студент, джун — напрацювати портфоліо. Але мідл, сіньору це нащо?

Реальний вклад робиться на роботі за гроші.

Те що за роботу платиться бабло не означає, що здійснюється якийсь реальний вклад. Той же гугол закриває купу проектів і міліони чоловіко-годин wasted. Попитай там в людей, як вони почуваються, коли їх проект закривають.

Очікувати від будь-кого, що він поза роботою ще витрачає час на ту ж роботу, але безкоштовно — то дивно.

Зовсім не дивно. Я ж кажу. Раптово може виявитись, що там фана більше ніж в літкоді. Але для цього треба спробувати.

Але мідл, сіньору це нащо?

Мідлам і сінорам теж треба портфоліо. Це постійний і нескінченний процес в нашому динамічному АйТі.

Зовсім не дивно. Я ж кажу

Дивись. Робити таке — не дивно. Дивно очікувати такого. Я не котріб’ютив жодного разу в опенсорс, портфоліо як таке в мене відсутнє. За 10 років не мав жодних проблем з цим

Та я й не очікую. Я більше агітую за фікс реальних проблем, а не фейкових :). Але, так. Кожному своє.

а, соррі, я не так зрозумів) Мені просто зустрічались люди, які вимагали обов’язкового контриб’юту у щось таке у вільний час.

Абсолютна більшість наших сіньорів на це подивиться і накатає в лоб і потім буде дивуватись: «А чому перфоманс такий поганий? Я ж відважно скопіпастив зі стековерфлоу, застосував SOLID, DRY, KISS, FISTING, а воно все одно не працює.»

Справедливости ради, если большинство наших сеньйоров на планировании скажет «а сейчас я буду прорабатывать алгоритм кластеризации лейбочек на мапе полтора спринта», то ему просто не дадут этого делать.

Там где действительно есть computer science, а не software engineering, либо очень много денег, либо их практически нет. А большинство украинских работодателей где-то посредине. С моих знакомых, например, подобным на фултайме занимался, в принципе, аж один человек в Самсунге. Хотя, в целом, я оттуда полтора десятка людей знаю, и большинство делало более прикладные задачи.

Та ви просто загляньте в середину любої ліби, там зазвичай такий ад твориться

Це перший аргумент, який викатують компанії, коли їх просять щось викинути в опенсорс

«реальний» вклад. 1 PR в лібу, якою користуються тисячі девів краще 1000 літкод задач.

Коли буде рейтинг по цьому параметру — то будуть і це робити
Якщо дев вже не є відомим контриб’ютором, то його пулреквест можуть взагалі проігнорити

Коли буде рейтинг по цьому параметру — то будуть і це робити

Уяви, що ти роботодавець. Є 2 однакових резюме.
В одному «10 ПР в реакт лібу» в іншому «1000 літкод задач». Кого б ти обрав?

Уявимо, що роботодавець найняв рекрутера...

А якщо «роботодавець» — це людина, якій потрібно швидко найняти і в нього немає часу шукати і аналізувати комміти десятка кандидатів

Коли перед вами тільки два кандидати, то ви проведете співбесіду з обома

.

PS: для прогресу цивілізації, ваш варіант кращий за синтетичний цюцюркометр

PR PR-у рознь :) знаю человека который в Clojure языке чуть ли не комент переименовал — так и стал себе писать — контрибьютор Clojure.

Лично мне показалось, что мой код стал лучше после моей практики на литкод.
Ну и пейчек Х2 тоже :)

Ну... а зачем люди вообще решают головоломки? Почему бы им не пойти и огород не покопать. Цели разные...

Мне непонятна немного другая причина. Я зашёл ради развлечения, посмотрел на задачки. Hard, расставить N ферзей на доске. Серьёзно? Я думал, что чуть ниже Easy. Это как сапёр, для синьора больше работа для спинного мозга.

Поделюсь небольшим опытом phone screen в FB. Cерьезно не готовился, решил попробовать просто для опыта подобных собеседований.

Оказалось, что решить задачу, и объяснить решение — это 2 разных скилла, особенно когда английский не свободный. Мне моей 3-недельной подготовки хватило чтобы набить руку в набрасывании решения в голове и быстром написании кода в блокноте, но я совсем был не готов объяснять это решение. Когда сам кодил, я как бы решение накидывал вместе с кодом, на собеседовании надо было сначала полностью объяснить что ты будешь делать, а только потом делать, при этом уложится в тайм-лимит в ~15 минут. В результате я в первой задаче вылез за время и не успел решить вторую. Xотя, в принципе, обе задачи решались даже с моей подготовкой, я ожидал большего хардкора. Видимо то, чем пугают неофитов было бы уже на onsite серии.

Вывод: если конечная цель — собеседование, стоит так же практиковаться в мок-интервью.

А в какую страну собеседовался?

London, UK.
Рекрутер сам на меня вышел, так что я не выбирал особо.

Видимо в США попасть сложнее будет. Явно не 3 недели на подготовку.

Процесс собеседования и пулл задач одни и те же во всех офисах.

В восточной Европе FAANG-и вроде бы вообще какие-то копейки платят, типа 3-4k$ чистыми. А в США 15-25k$ чистыми, я не поверю что задачи одинаковые, тогда почему куча людей сидит на 3-4k$ если они фактически могу получать 15k$ в Калифорнии?

Это просто факт. Я знаю как процесс устроен, потому что участвую в нем. Впрочем, не верить — ваше право. Причины могут быть:
1. Человека приглашают пособеседоваться в конкретный офис, который сейчас хайрит, например в Варшаву. Человек хочет в компанию X, но другие офисы сейчас не хайрят. Он соглашается на Варшаву в надежде потом релокейтнуться внутри компании (например, в штаты по L-визе).
2. Человек хочет работать в компании Х, но не хочет слишком далеко уезжать из Украины.
3. Внезапно, не все хотят в штаты, даже на большие деньги. Мне, например, нравится в Лондоне и планов ехать туда нету.
4-n. Много других вероятных причин.

3. Внезапно, не все хотят в штаты, даже на большие деньги. Мне, например, нравится в Лондоне и планов ехать туда нету.

А какие в Лодноне плюсы? Не считая наверно того, что тебе сам город нравиться, как и мне. Там же ЗП в 2 раза ниже чем в Долине, а цены на аренду и еду практические такие-же.

База меньше раза в полтора, я бы сказал, стоки в 1.1-1.2 (но налог выше).
Европа рядом, в целом образ жизни намного ближе мне: можно много гулять пешком, город очень зеленый, всё вокруг не крутится вокруг технологий, насыщенная культурная жизнь.

3-4k$ чистыми. А в США 15-25k$ чистыми,

Nope. Разница где-то 2.5 раза грязными между, например Варшавой и MV, никак не в 5-6. Налоги примерно в ту же степь. Разница в цене жизни по намбео в 3 раза. И в чем тогда смысл?

Это же вроде ты писал, что то ли в варшаве, толи в финляднии, короче где-то восточнее Германии синьору в Microsoft 3k$ чистыми платят всего?

Разница в цене жизни по намбео в 3 раза.

Вот это фигня, с 25к$ тебе же раз за aренду или ипотеку платить надо, то есть, даже если 5k$ заплатишь, то у тебя 20k$ останется, которые никак не могут быть равным 2k$

Это же вроде ты писал, что то ли в варшаве, толи в финляднии, короче где-то восточнее Германии синьору в Microsoft 3k$ чистыми платят всего?

майкрософт в эстонии мидлу. Но они даже в аббревиатуру ФААНГ не входят))) С гуглом дело другое, левелс в помощь.

Вот это фигня, с 25к$ тебе же раз за aренду или ипотеку платить надо, то есть, даже если 5k$ заплатишь, то у тебя 20k$ останется, которые никак не могут быть равным 2k$

Откуда ты берешь 2к? Если ты считаешь человеку в Маунтин-вью 25к, то в Варшаве это будет не меньше 8, а скорее всего даже больше, с которых ты за квартиру заплатишь вряд ли больше 1-1.5к, остается 7. Дальше, кушать что ты будешь? Коммуналку какую платить? Развлечения сколько будут стоить? Когда появится ребенок, сколько отдашь за садик и за памперсы или за то, чтобы нанять няню? Расходы «на жизнь» не ограничиваются арендной платой.

7к и в Украине получить можно. А 20+к после аренды это уже большие деньги.
С которыми реально миллион в S&P 500 накопить, и жить за пассивный доход.

7к и в Украине получить можно.

Естественно, но изначально все же 8 с лишним считали чистыми после оплаты налогов, с которых тебе еще норм пенсия насыпется, норм медицина, соцгарантии и так далее.

20+к после аренды это уже большие деньги.

20к после аренды — это неизвестно сколько после остальных расходов.

С которыми реально миллион в S&P 500 накопить, и жить за пассивный доход.

Так какая разница? Ну накопил ты миллион. Средний возврат на дистанции с S&P — 10-11%. 100-110к в год в США имеешь, слезы на которые жить нереально, еще и с семьей. В Варшаве ты накопил 400к, в том же S&P ты имеешь 40-44k, на которые также жить нереально, но уже слегка реальнее.

Но давай предположим, что ты накопил в США сумму X, которой достаточно. С нее ты получаешь 0.1-0.11Х в год. В Польше ты накопил 0.4Х. С них ты получаешь 0.04Х-0.044Х. Открываем стоимость жизни — и видим, что эти суммы позволяют получить примерно одинаковый уровень жизни.

Первый закон экономики — деньги есть нельзя. Если у тебя конечная цель свалить на пенсию в условный Таиланд, Зимбабве или Украину — то да, разница в абсолютных числах имеет значение — накопил ты миллион или 2.5. Но если ты собираешься жить в означенной стране до конца жизни — то разницы практически нет.

100-110к в год в США имеешь, слезы на которые жить нереально

Если есть свой дом, и ты где-то во Флориде или Техасе то жить можно очень даже хорошо. А если снимать квартиру в Долине, то да, тяжко будет.

В США люди просыпают большие ЗП потому что любят жить роскошно. Если экономть, то расходы не в 3 раза выше будут чем в Польше. Потому что еда в США стоит столько же, а одежда, машины, и электроника даже дешевле. Так что если не шиковать специально, то реально потратить чуть больше чем в Варшаве, а накопить в разы больше. Понятно что если есть дети, то денег уйдет больше, я про бездетную пару пишу.

В США люди просыпают большие ЗП потому что любят жить роскошно. Если экономть, то расходы не в 3 раза выше будут чем в Польше. Потому что еда в США стоит столько же, а одежда, машины, и электроника даже дешевле.

Just try) издалека так кажется, что расходов мало. Когда приезжаешь, статьи расхода возрастают и их количество увеличивается по сравнению с планируемым. Тем более для экспата. И экономить можно точно так же и в Польше. В итоге у тебя останется все равно в пропорциях те же деньги и при переезде в глубинку можно на них жить.

Да, под строго определенные условия — без детей, согласие жить в глубинке и желание как можно быстрее уволиться — США наверное подойдет лучше, но то, с чего изначально начинался разговор

почему куча людей сидит на 3-4k$ если они фактически могу получать 15k$ в Калифорнии?

если сделать шаг в сторону от твоих условий и, например, завести двух детей, то картина резко меняется. В этом и прелесть работы в фаанге — ты везде можешь поддерживать примерно одинаковый уровень жизни и ты выбираешь ту страну, которая больше подходит под твои требования. Кому-то важен близкий язык, близкая культура и родственники рядом — едет в Польшу, у кого-то жена финансист и не хочет учить другие языки, кроме английского — едет в Лондон, кто-то хочет высокой соц защищенности — едет в Стокгольм, кто-то хочет иметь большие цифры на счету и возможность встрять в стартапчик — едет в США и т.д.

Кому-то важен близкий язык, близкая культура и родственники рядом — едет в Польшу

Та ну его нафиг, мне американская культура ближе.
И английский я уже знаю лучше чем украинский даже.
В США хоть можно в магазине сигарет и редбула купить, поймут чего ты хочешь, а в Польще не понятно вообще как жить.
А 2-й язык на C2 учить что бы интегрироваться, еще лет 5 по 2 часа в день уйдет. И что бы в результате получить ЗП как в Украине, такое себе удовольствие. Английский учить хоть потенциальные 500к мотивируют.

Та ну его нафиг, мне американская культура ближе.

Ну тебе да. По дефолту поляки ближе.

В США хоть можно в магазине сигарет и редбула купить, поймут чего ты хочешь, а в Польще не понятно вообще как жить.

Ээ в чем прикол? Так же как и в США берешь и заказываешь. Я жил три месяца во Вроцлаве несколько лет назад, проблем не было.

А 2-й язык на C2 учить что бы интегрироваться, еще лет 5 по 2 часа в день уйдет.

так речь же изначально шла о том, что ты не понимаешь зачем люди сидят в польше в гугле, если с теми же задачами можно попасть в сшп. Я не пытаюсь доказать почему тебе должна подходить Польша, а пояснить почему многие сознательно выбирают Европу и даже восточную Европу вместо США, имея возможность свалить туда.

Английский учить хоть потенциальные 500к мотивируют.

Тот момент, когда знаю директора гугловского, который сидит в силиконовой долине и у которого В2 от силы с хорошим таким акцентом))) С2 — это эпичнейший оверкилл. Нет ну естественно, чем лучше язык, тем лучше, но начиная с определенного момента повышение уровня становится непродуктивным.

Тот момент, когда знаю директора гугловского, который сидит в силиконовой долине и у которого В2 от силы

Дороничев?

А как там в принципе ойтишниги зарабатывают? MRP возможно низкий. В тех локациях которые меня привлекают было примерно одинаково. Но конечно ymmv

А что за локация такая экзотическая, если не секрет? Типа Испании-Португалии или Вьетнама что-то?

да ну, странно. Я взял медианную цифру с paycomparison dashboard для Л4 в MTV разделил на 12, засунул в намбео для Сан-Франциско, перевел в токийские, умножил на 12 и получил в точности токийскую медианную Л4 с дешбоарда. Для л5 уже лень было считать, но по идее картина. А ты как-то по-другому считал?

Разница в цене жизни по намбео

Не є тим, чим прямо можна користуватись, порівнюючи ціну проживання. Якщо просто абсолютна відкладаєма сумма є у 2.5 разів більшою — це вже великий плюс.

конечно, просто для такого нам нужен человек, который жил и там, и там и который будет согласен зашарить свой опыт) Поэтому сравниваем то, что есть.

Якщо просто абсолютна відкладаєма сумма є у 2.5 разів більшою — це вже великий плюс.

Это если ты поехал просто заработать и потом вернуться в Украину, а не остаться там до конца жизни. Ну отложил ты 2.5 миллиона в СФ при миллионе в Варшаве. Что это поменяет в плане пенсии? Разве что купленная машина приходит в голову. Потому что на остальное ты будешь тратить пропорционально.

На домік біля теплого моря — теж не пропорційно, наприклад. Не обов’язково в Україну переїжджати.

возникает конечно вопрос, зачем стремиться в цивилизацию, чтобы потом вернуться в какой-нибудь Таиланд. В 60 лет, когда ты уже привык к американской жизни, переезд в гребеня сильно порвет шаблон.

Чому гребеня? Хочу море тепле. Я подивився по нумбео Флоріду проти Варшави. Хавка і рент у Флоріді дорожчий тільки, практично. Навіть проперті десь так само. Є також Іспанії різні. Є рівно та сама Варшава, мінус польска, плюс 1.5 млн.

І можна подробніше, шо там де порве, після СФ із бомжами срущими?

тогда почему куча людей сидит на 3-4k$ если они фактически могу получать 15k$ в Калифорнии?

один з неперечислених і важливих пунктів цього і минулого року — візове питання
якби то було так легко отримати одразу ж робочу візу в США після інтерв’ю

а как же ж местные? местным из штата в штат виза не нужна?

а как же ж местные? местным из штата в штат виза не нужна?

местниє, хто в ФААНГу 3-4к отримує? а є такі?
питання було про ФААНГ у Східній Європі

питання було про ФААНГ у Східній Європі

з урахуванням коригування на cost of living виходить риторично

www.numbeo.com/...​ing=getDispatchComparison

местниє, хто в ФААНГу 3-4к отримує? а є такі?

чи ти зараз на магаєся сказати що фхтанги отримують однаково не залежно від штату локації а ну ок

я нічо не намагаюся сказати, я просто порушив перше правило — не вступати у дискусію з Alex Fogol, все решта — сам висувай і підтверджуй/заперечуй тези, або задавай риторичні питання, і показуй, який ти йопта вумний

ще й блін нумбео притащив до купи, ніби перший день на форумі і в Україні живеш

Вроде бы только H1B на год запретили, но уже разрешили, а L1 никто не запрешал даже в прошлом году.

Вроде бы только H1B на год запретили, но уже разрешили, а L1 никто не запрешал даже в прошлом году.

та нехай
але консульства нєбось із сильними затримками працювали через COVID

Для android и front-end leetcode проще для backenda. Ну и на онсайт задания сложнее, чем на скрининге

Это повальное увлечение leetcode-м создат проблемы для найма в обычные компании. Люди в аутсорс компаниях начнут резко спрашивать leetcode задачи, но при этом платить маленькие зарплаты как обычно.

З.Ы. В США куда бы ты не пошел будут спрашивать leetcode (всякие startup считают, что может себе это позволить), но платить будут посредственно.

Зато быстрее в США все свалим. От FAANG-а же нормального Украинского синьора отделяет только Leetcode этот злощастный.

С твоего сообщения можно подумать что США это страна открытых дверей. Я свою H1B получил с 3-го раза (3 года подавался).

Там якобы FAANG-и тебя сначала могу в Канаду на пару лет повезти, а уже с Канады будешь H1B ждать.

будешь H1B ждать

или через год L1B

Кстати, да. Максимум год в Канаде сидеть придеться.

Значит пора перейти от разговоров к делу. Сколько уже 30? Пока переедешь, пока получишь грин карту будет 35 (уже не фонтан возраст).

если в правильную Канаду попасть потом может и не захочешь уезжать

А сколько потратил на подготовку?
Решить тестовое задание проще, чем подготовиться к интервью аля leetcode.

А что, в Украине еще остались синьоры которые делают тестовые? Это же унижение для разработчика.
Вон я проходил интервью в компанию где реально синьор нужен на вчера, так меня не собеседовали толком даже, пару вопросов спросили чисто, не говоря уже про тестовое.

Я делал тестовое пару раз, мне было скучно. Итог — не задротил алгоритмы, получил сходу оффер на +15% от текущей ставки.

По личному опыту: я регулярно собеседую мастеров решать алгоритмические задачи, ну и в целом они мастера только в этом ;)

В Украине тестовое дают только тогда, когда разработчик не сильно то и нужен. Поэтому даже если тебе не впадлу тестовое делать, то чисто логически его нет смысла делать, так как вероятность что тебя не возьмут при идеальном тестовом очень высокая.

Тут важнее другое: люди, которые будут оценивать, будут оценивать ТОЛЬКО их, сравнивая чисто ВИЗУАЛЬНО, и не понимая ни задачи, ни решения.

Или ещё хуже — для тех.интервью выучат 10 задачек, и будут требовать решать их на бумажке за 5 минут. Хотя сами вылизывали решение месяцами, либо же нашли копипасту и в неё поверили. Разумеется, кандидат будет не в курсе, что там будут спрашивать. И только если рекрутер умный, то даст фидбек отсеянным, и узнает ПОЧЕМУ их завалил 23-летний «синьор».

Літкод допомагає тримати себе в формі. Як зарядка зранку. Зробив задачку-дві на день, кілька разів на тиждень — і знаєш де ти є, що можеш. Допомагає від синдрому самозванця.

і знаєш де ти є, що можеш. Допомагає від синдрому самозванця.

youtu.be/TjXAXnacKMc

оце якраз на трапив ще раз на лінк на відео де чувак пояснює How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively) і тут да дивне враження справляє усе це

ЗЫ: і там ше до цього коментарі штибу „Thanks, finally understand the recursive solution. The explanation of call stack really helps.”

Допомагає від синдрому самозванця.

Допомагає потрапити на днище того самого синдрому. А це набагато гірший прояв.
Спробуй зрозуміти, що найсерйозніші речі на планеті робили люди, які НЕ ЗНАЛИ де вони є і що можуть. Вони просто робили. А не чекали, доки через 40 років по тому це все назвуть лайном мамонта алгоритмами, та будуть сшибати за це капусту, розводячи наївних недокодерів.

Пам’ятаю, як якийсь журналіст тролив прихильників Трампа питаннями «А коли Америка була great, якщо ви хочете зробити її „great again“?».
Так от, які це такі найсерйозніші речі на планеті (в розробці ПЗ) робили люди, які не знали алгоритмів? Я б сказав що навпаки, оті «найсерйозніші речі» якраз робили люди з переважно науковими ступенями в математиці і значно кращим розумінням алгоритмів, ніж у сьогоднішнього середньостатистичного розробника.

Можливо. Але літкод вони б не порішали, це точно. Бо кожен знав СВОЮ ЧАСТИНУ, та вирішив одну задачку. А левова доля того «щастя» що в літкоді взагалі ніде не застосована.

А левова доля того «щастя» що в літкоді взагалі ніде не застосована.

Це, безумовно, правда. Що не відміняє того, що літкод будуть питати на інтерв’ю в фаанг і не тільки. Отож, хочеш, щоб тебе прийняли за качку — вмій крякати, як качка.

Літкод вже переріс навіть цей рівень. Звісно, при тій толерантності дискусіних платформ до СПАМУ, який дозволяє кукарєкукоду срати вигаданими «історіями успіху», вони можуть вплинути на секту недоумків, і задачі з нього легко накопіпастять. Але через ріст маразматичності вгадати що саме візьмуть не є можливим, а вивчити всі «правильні» відповіді неможливо через його роздутість.

Повторюся, ті хто питатиме копіпастою, зазвичай не розуміють ані природи задачі, ані критеріїв якості рішення. Особливо, коли передбачається застосувати якийсь «трюк», який не дає нічого, окрім скорочення коду. Звісно ж ціною тотального знищення його читабельності, і як наслідок, здатності роками приховувати баги.

Повторюся, ті хто питатиме копіпастою, зазвичай не розуміють ані природи задачі

Ну от мене Гугл на співбесіді питав задачки, штуки чотири. І всі чотири я потім знайшов на літкоді. Гугл розумів природу задачі і критерії якості рішення. А от я на останній задачі здорово тупанув і на цьому співбесіда закінчилася. А вклав би зайву сотню годин в літкод тоді — може, діло пішло б і далі.

Але це не значить що гугл брав з літкода. Скоріше що літкод брав де тільки знайде для наповнення помийки, туди могли попасти й класичні задачі на алгоритми.

А гугл — це ті самі звичайні люди. Ліниві. Яким також впадло розбиратися, як їх рекрутинг працює, тому бюрократизація неминуча. Тому якщо тобі саме в гугл — то можешь і скористатися літкодом, але не намагайся проковтнути УСЕ ЛАЙНО, обирай там де умови коротші (а не притягнуті за вуха під готову відповідь).

Замість пробувати вирішувати самому, цікався РІШЕННЯМИ. Бо то лише мізер на тлі реальних задач, які в реалі вирішуються не за один день, а то й рік.

Це взагалі розповсюджена ілюзія, що задачки «на логіку» можна давати на співбесіді. Вони здаються легкими, коли ЗНАЄШ РІШЕННЯ, але без рішення є надзвичайно складними. А тепер запитай себе — а чи той, хто питає, сам пробував те рішати, чи просто поглянув правильні відповіді?

Тому ще одна дуже важлива порада: коли вчиш правильні відповіді (а іншого шляху нема), роби це безпосередньо перед здачею. Бо ти забудеш то лайно за місяць-два більше половини, а за 2 роки — майже все. Бо то лайно.

В реальному житті, зустрівшись з задачею, ти просто візьмеш готову відповідь. А вірогідність, що тобі воно знадобиться бодай щось ⩽ 1%

Все правильно сказали. Та все ж-таки: хтось же мусив колись давно сам порахувати і знайти відповідь-«нульового пацієнта»...

Саме так. Але його б не прийняли на роботу, якщо б запропонували вирішити аналогічної складності задачку 20-річної давнини на співбесіді.

Чи скажімо, назвати на пам′ять 60911 у двійковій системі. Так, прикинь, тоді саме це вимагали вивчати, всю таблицю двійкової системи до 32768, а продвинутими вважалися хто вивчив до 65536 З тією самою користю.

Есть хорошая дока, учитывающая acceptance rate, возраст задачи и заявленную сложность — docs.google.com/...​kiDznHUzhtHbVU/edit#gid=0 и пробующая на этом основании вычислить «реальную» сложность задачи. Тут отсортированы по увеличению сложности.

Кроме того, не стоит забывать, что сложность отдельных задач обусловлена не сложностью алгоритма, а количеством корнер-кейсов и объемом задач. На интервью такие вряд ли встретятся. Для себя можно поугорать

Для себя поугорать возьми ассемблер и embedded — вот где реально алгоритмы понадобятся, и в крайние условия уткнёшься, и в потерю производительности.

Коментар порушує правила спільноти і видалений модераторами.

Вспомнилось выражение dress for the job you want not for the job you have
Мне кажется литкод стал для многих кто не планирует собеседоваться в фаанги чем-то аналогичным этой фразе.
«решайте задачи которые вам понадобятся на собеседовании, а не те что вы сейчас решаете и не те что будут если вас возьмут»

Ну, я смотрю на это проще, задачки с LeetCode позволяют иногда отвлечься минут на 15-30 и размять мозг чем-то, переключить внимание. Плюс ещё когда получается решить — это мотивирует
Ну и часть задач оттуда иногда встречаются в жизни в той или иной форме

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

Спасибо, если тема зайдёт — конечно будет продолжение

Если хотите в FAANGMULA+, премиум подписка must have.

FAANGMULA це ще що за звір)? Хто вигадав цю абревіатуру?

Я бы сказал скорее nice to have.

например FB вообще очень четко вопросы спрашивает по списку с LC, так что вызубрив допустим 100 вопросов затеганых ФБ, вы сильно повышаете шанс пройти phone screen и coding на on-site. Особенно учитывая, что ФБ ожидает от вас решения 2х (!!) задачек уровня медиум-хард за 45 минут.
Заметьте, я нигде не сказал, что это правильно :-)

Списки задач по компаниям гуляют по интернету. В остальном — да, но я бы не сказал, что это необходимое условие. У меня во времена подготовки был премиум, но списками задач я не пользовался, как и (почти) всеми остальными плюшками премиума. Что не помешало мне пройти в ФБ.

хорошо, это возможно, но с премиумом сильно удобнее. я вот не столько даже за список вопросов или решения (часто видео на ютубе сильно лучше), сколько за дебаггер

Дебаггер в подготовке к интервью в фаанги — зло. Нужно уметь дебажить в голове, иначе, привыкнув допиливать ломом и дебагом, на интервью можно выгрести по самое не хочу.

ну, M я бы отдал Microsoft, U... может Uber? L... Linkedin (хотя они уже Microsoft), A... AirBnb?

What’s FAANG?:

FANG — Facebook, Amazon, Netflix and Google
FAANG — Facebook, Amazon, Apple, Netflix and Google
FAAMG — Facebook, Amazon, Apple, Microsoft and Google
FAANGMULA — Facebook, Amazon, Apple, Netflix, Google, Microsoft, Uber, Lyft and Airbnb
FAANGULTAD — Facebook, Amazon, Apple, Netflix, Google, Uber, Lyft, Twitter, Airbnb and Dropbox

то есть когда у меня кот походил по клавиатуре — это он планировал куда резюме засылать, а не просто набор букв нажал

А че Lyft в этот список попал? Вроде же это стартап который не во всех городах США есть еще.

Зато есть (будет?) в Киеве.
Впрочем, у них интервью не по алгоритмам, а систем дизайну.
Дают какую-то задачу, ты ее дизайнишь на одной сессии (45 минут).
Потом имплементируешь ее за ~4 часа, шаря скрин. Пользоваться можно всем. Интервьюер поглядывает на фоне, но в целом над душей не стоит.
Потом еще одна сессия на код ревью.
Где-то между этим еще придет менеджер о behaviour поговорить.

За ЗП без понятия, я собес не проходил, только общался на эту тему.

В Киеве расширяют команду, которая изначально в Минске сидит, и которая была отдельной компанией (Juno), которую Lyft купил. В Киеве решили расширятся то ли из-за бацьки, то ли из-за того, что вся Беларусь по населению как Киев с пригородом, и тупо кадров не хватает, толи все вместе

Это некий подраздел, который в основную кодовую базу не контрибутит. Пилят свой mobile maps SDK, чтобы слезть с google maps, а то им гугл чарджит такие счета, что решили сделать свое.

За стек на беке тоже хз, но я так понимаю, что тут как раз включаются FAANGовские плюшки, и если ты получил offer, то твой опыт с конкретным стеком не столь важен, тебе дадут время за деньги компании выучить их стек. Т.е. ищут не условного Spring/Django/Younameit Developer, а Backend Engineer.

За стек на беке тоже хз, но я так понимаю, что тут как раз включаются FAANGовские плюшки, и если ты получил offer, то твой опыт с конкретным стеком не столь важен, тебе дадут время за деньги компании выучить их стек. Т.е. ищут не условного Spring/Django/Younameit Developer, а Backend Engineer.

Это понятно, за 500к в долине я тебе и на Питоне писать начну.
А за каких-то 8к в Украине переходить на другой язык програмирования, это дурка. Если можно почти столько на своем получать.

Впрочем, у них интервью не по алгоритмам, а систем дизайну.

Интересно, у меня немного другой опыт был. Я апплаился в Lyft в киевский офис зимой, и на техникал скрине интерьювер дал Leetcode задачку medium-hard уровня, еще и ожидал близкого к оптимальному решения. Может правда это от конкретного интервьюера зависит, как повезет.

Может от левела зависит? Дизайном на Стафа трахают, а литкодом на мидла и синьора.

Это ж мобильщики. У меня в Лифте тоже было 2 харда+2 сисдиза

Підписатись на коментарі