Условие задачи из предыдущего треда: даётся массив из N чисел и число X. Найти индексы пары элементов (либо всех пар элементов, похуй), которые в сумме дают число X. Лучшее решение прошлого треда в оппике-2
>>258089888 В чем проблема человеку навести курсор на функцию, где будет показан тип возвращаемого значения? Тащемта такая длинная ебанина в 100+ символов инициализации функции и её возвращаемого типа тоже не особо хорошо читается.
>>258089936 Подумай сам, в чем проблема. Можешь водить курсорами сколько угодно. Особенно, когда они у тебя есть. Когда нет, попроси кого-нибудь снять для тебя ролик на ютубе, где любимец молодежи прочтет тебе сигнатуру вслух. Нормальные люди умеют читать, им этого достаточно.
>>258089936 В чем проблема не пользоваться тс-ом совсем? жс не требует (и не позволяет, лол) тебе вовсе какие-то типы указывать. В чем проблема водить курсором и угадывать типы?
>>258089888 В 2к22 код пишет человек для тимлида, ну или если фирма совсем говношлюпка, то для кабанчика. Я видал, как лиды ебучие код в десяток абстракций заворачивали, идею которых только они понимали, и под которые отдельного финансирования ГлавКабаны, понятное дело, не выделяли. Но зато потом эти самые лиды час работать и несколько часов еще списывать на овертаймы дополнительно ежедневно могли, типа как они Дохуя Работают по сравнению со всей остальной командой. Сказочные дегенераты. Типичный хуяндексовский скот, который проникает на лучшее корыто.
>>258089936 > В чем проблема человеку навести курсор на функцию, где будет показан тип возвращаемого значения В том что это нужно делать? В том что это не работает в браузере на код ревью?
>>258089998 Сразу вопрос: а в этом суперкоде тс не предупредит, что функция может вообще ничего не вернуть, и пойди-ка ты на хуй? теоретически я плохо подкован, а хуярить пример и компилить - лень
>>258090034 проиграл) в чем смысл еще названия переменных использовать, если они потом в адреса памяти переведутся. и оп коды в хексе тоже лучше сразу писать
>>258090266 Повторюсь -- Могу себе позволить. Я здесь сидел еще когда 10+ лет назад начинал вкатываться на галеры. Уж извините, состоявшимся программистам автоматически тянка не дается с выселением на пикабу, как бы не думалось окружающим.
>>258090328 >так там функция либо возвращает, либо в цикле крутится бесконечно Ну, у нее же тип возвращаемый указан. Значит, должна эту хуйню вернуть. По моему безграмотному мнению
Ок, я проверил. 1. ты прав. 2. я объебался с явой. если цикл убрать, будет ругаться (как и тс), если цикл вернуть, то не будет. ща жлс перечитаю
>>258089644 (OP) Проиграл с решения, думаю nlogn минимум тут, ну или какой-то хитровыебанный способ с n но в голову не лезет такой без условия на максимальное число.
>>258089644 (OP) >>258089696 Судя по пику из первого треда, у ОПа элементы в массиве могут повторяться. Поэтому проходимся по массиву и строим хэшмапу [число : [массив индексов]]. Потом для каждого числа в мапе находим второе слагаемое и составляем все комбинации индексов между слагаемыми. Время от O(n), если все числа уникальные до O(n2), если в массиве только одно повторяющееся число, которое является половиной суммы. Вроде так?
A while statement can complete normally iff at least one of the following is true:
The while statement is reachable and the condition expression is not a constant expression (§15.28) with value true.
There is a reachable break statement that exits the while statement.
The contained statement is reachable iff the while statement is reachable and the condition expression is not a constant expression whose value is false.
В принципе, можно последний абзац на тянуть на наш иф, конечно. Но я попробовал, и нет. Таким образом while не completes normally/ Хули ему еще надо?
>>258090581 в прошлом треде все обмусолили, nlogn по времени и 1 по месту если отсортировать и двумя поинтерами на встречу шагать. n по времени и n по месту если через хешмеп искать комплемент
>>258089696 def two_sum(nums, target): ____memo = defaultdict(list) ____result = [] ____for i, n in enumerate(nums): ________compliment = target - n ________if compliment in memo: ____________for idx in memo[compliment]: ________________result.append([idx, i]) ________memo[n].append(i) ____return result
код не запускал, проверять лень, наколябал за 3 минуты на коленке. O(n) space complexity, O(n^2) сложность для этой функции, которая возвращает индексы всех пар. Если нужно вернуть любую из пар, то сложность можно уменьшить до O(n)
Есть массив, требуется определить, есть ли подмножество чисел, дающих X в сумме.
У меня если я не облажался получилось решение типа O(n^log(2,X)) и хрен знает что там по памяти, ень прикидывать. знатоки деревьев кучи прочей кнутомагии призываются и приветствуются.
>>258089644 (OP) Где такие задачки дают? Только один раз на собесе дали задачу с числами фибоначи, я прям там орнул, до этого думал это мем. Обычно с лидом за что-то практичное перетирал.
>>258090886 хуй знает, я бы начал с рекурсии (и считал бы, что это нквадрат) потом, в зависимости от констрейнтов можно было бы думать про сортировку, прунинг и мемоизацию
>>258090959 квадрат из-за вложенного цикла, который добавляет индексы всех пар в результат. Актуально, например, для инпута ([1,1,1,1,1,1,1,1,1], 2). Ну и я не питонист, лол. Я на шарпе пишу на работе. Просто питон удобнее для таких задач.
>>258090959 на интервью (нормальных) как раз смотрят на такие вещи, когда пишешь читаемый код типа такого, и за обсуждение хода мысли в слух, а решишь или не решишь это бонус.
>>258091259 Отбрасывание чисел погоды не делает, так то да - согласно вики алгоритм экспоненциальный в любом случаае. У меня получился лучше, и он простой, ошибку пытаюсь вот найти.
>>258090947 Ты бы был больше рад, если бы тебе дали задачку, как обеспечить конкуррентный доступ к одной и той же записи в базе, чтобы ни одно изменение не проебалось (предположим, что изменения не противоречат друг другу)?
>>258091310 так он в обоих случаях изза констант true понимает что он всегда только до первого ретерна дойдет. может я чето упускаю но по мне все логично статик чекер делает.
>>258091454 Ну ответь, раз сталкиваешься. Посмотрим.
10000 тредов апдейтят какие-нибудь энтити-объекты (считай - записи в одной и той же таблице). Как ты сделаешь, чтобы 1. 2000 апдейтов одной и той же записи происходили последовательно (изменения из одного апдейта учитывались бы в другом) 2. все остальные апдейты не встали от твоего решения раком
>>258091474 Вот тебе подсказка, лол: напиши число на бумажке и попробуй подвигать цифры в нем так, чтобы нужное тебе изменение стало бы следующим большим заметь закономерность
>>258091679 >>258091713 Т.е. если ты все изменения хочешь выстроить в очередь, а потом ПО ОДНОМУ хуярить в базу, то ответ неверный. Если ты не этого хочешь, то поясни.
>>258091758 Как они тебе помогут? у тебя из кода приходят 5 апдейтов. База на первом делает блокировку, апдейтит. Оставшиеся 4 апдейта ничего не знают о том, что произошло в первом - данные портятся
Ответ неверный, пока что. Или я тебя не понял.
Давай еще проще: в один момент 10 пользователей жмут дизлайк у одного ролика на ютубе. Как твои блокировки помогут?
>>258091730 >ПО ОДНОМУ По одному на каждую запись. То есть если 3треда паралеьно пишут в базу поменять значения с ключами 1,2 и 2, то 1 и 2 будут выполнены параллельно микросервисами с другого конца очереди асинхроно/конкурентно, а когда обработка ключа 2 закончится, то он ещё раз прочтётся из очереди и снова обработается. И все читающие сервисы как раз синхронизируются через ту самую event sourcing таблицу. Просто в твоём случае она не перед очередью, а после очереди. В этой таблице как раз и пишут те самые паралельные микросервисы с обратной стороны свои локи чтобы 2 миокрсервиса один ключ не обрабатывали паралельно
>>258091835 Ёбаный умник, ты бы хотя бы почитал про уровни транзакций. Если тебе надо "ШОБ НИЧО ТАМ НЕ ПЕРЕЗАПИСАЛОСЬ" - хуярь себе Serializable, наебни всю производительность. А вообще такие вопросы как с ютубом решаются архитектурно, никто не хуячит колонку с "числом лайков", это всегда вычисляемое значение. В базу ты будешь класть по одной записи на каждый лайк от каждого пользователя - ВУАЛЯ, у тебя нет никаких race conditions.
>>258091882 Если у тебя из очереди читает один потоков, то у тебя все встает раком: 1000 тредов хотели одновременно записать по одной записи, но теперь один тред будет записывать 1000 записей. Узкое место.
Если у тебя из очереди читают несколько потоков, как ты добьешься, чтобы два из них опять не взяли одновременно для апдейта записи с одинаковым ид? Вопрос ведь в этом: как не дать одновременно апдейтить записи с одним ИД, но давать апдейтить одновременно записи с разными ИД.
>>258091998 Кек, ты напомнил мне собес, где меня пытался собесить подобный чёрт с очередных вайтишных курсов. На что я резонно отказался, хотя бедная хрюша уговаривала меня потом вернуться на собес с СТО, который "сейчас не может". Надо ли уточнять, что такие псевдо-галеры нахуй не нужны?
Ютуб имеет два режима подсчета лайков: быстрый (считаем приблезительно) и точный (считаем как на выборах). И уж если хочешь блеснуть архитектурой на интервью, ты должен выяснить решаемую проблему и предложить оба варианта, расписав trade-off-ы обоих.
>>258091835 >Оставшиеся 4 апдейта ничего не знают о том, что произошло в первом Как это ничего не знают? Первый тред делает блокировку уровня строки и последующие будут ждать пока первый закончит транзакцию и снимет ее. Макака мейнтейнс проводит?
>>258091927 Не, не понял. Но надеюсь, что ты знаешь, о чем говоришь, и вот-вот мне расскажешь, и я пойму. Потому что пару вариантов я знаю, и ни один не похож на твой. Если твой - рабочий, то буду знать не пару, а тройку.
>>258091986 >Вопрос ведь в этом: как не дать одновременно апдейтить записи с одним ИД, но давать апдейтить одновременно записи с разными ИД. Много потоков. Я же сказал. Через таблицу локов как в event sourcing. Причём классика. Много потоков пишут в очередь. Много потоков читают. Когда микросервис прочитал, то объекта уже в очереди нет и другой его не прочитает. Потом микросервис проверяет по таблице стоит ли на таком объекте лок. Если нет, то пишет в базу. А если стоит, то возвращает в очередь и пробует другой читать.
У этого решения есть пару проблем. 1. Микросервис крашнулся после того как прочитал сообщение из очереди, но не успел обработать. Тогда сообщение потеряется. Тут нужно какие-то коммитменты настраивать с таймаутами, но это уже лишнее усложнение твоей задачи 2. Много одинаковых объектов забило очередь и все микросервисы бусконечно читают их, видят лок и заново пишут обратно. Тут надо какой-то circuit breaker делать, который будет проверять фейлился ли такой ключ недавно и хранить его отдельно не давай микросервисам его прочитать, а потом по истечению времени хранения обратно возвращать в очередь. Тут тоже надо всё атомарно через транзации делать чтобы если вдруг микросервис крашнется до коммита чтобы ретрай транзакции был. Но это тоже за пределами твоего вопроса.
>>258092033 Тут недочеловек выше задавал вопросы про блокировки и "как они помогут", а не про хайлоад. Рисовать на коленке рандомхую на двачах архитектурку высоконагруженного сервиса как-то нет желания. На это и так обычно две трети собеса уходит, со введением дополнительных ограничений/требований от адекватного собеседующего, но это не про /b.
>>258092089 Я что-то проебал, в какой момент у тебя возникли микросервисы. Но мне уже не нравится. Если нам нужны микросервисы для того, чтобы распедалить апдейты, которые нам прислали другие микросервисы, то это пиздец, а не решение.
Короче, не убедил. Обычно делают через оптимистик лок либо на уровне базы, если она поддерживает и может тебе выкинуть ошибку, если оптимизм был напрасным, либо на уровне кода и схемы данных. Никакие особые паттерны для этого не нужны, никакие очереди или посторонние микросервисы.
Наверняка, и другие варианты есть нехитрые. Я бы послушал.
В двух словах consumer потоки и producer потоки общаются через очередь и все consumer потоки используют общую/глобальную таблицу в бд (с консистентность при параллельном доступе конечно типа постгреса, а то редис без параллельности может перфоманс уронить) чтобы писать туда айдишники объектов, которые собирает обрабатывать. Тоже атомарно. Если смог записать, то значит никто это обхект не обрабатывает и можно безопасно объект с этим айдишником в целевой базе менять. А если не получилось, то там кто-то уже меняет такой объект. Его трогать нельзя. Надо вернуть в очередь. Надеюсь понятно
>>258092028 >А если будут float в массиве? Молодой человек, вы усложняете наш продукт! Не отклоняйтесь от ТЗ, пожалуйста. Наши software engineering manager'ы обо всём позаботились. Системные аналитики посчитали, что такая ситуация не возникнет с вероятностью 0.00001
>>258092189 Теперь понятно, но не решает мою задачу. Ты, да, выполнишь апдейты в какой-то последовательности, но каждый следующий апдейт не будет знать, что какой-то предыдущий в этой последовательности уже изменил данные. Ну, или тебе придется усложнять твой алгоритм, чтобы твой консумер не возвращал в очередь, а клал бы в другую, чтобы исходные процессы перечитали бы данные, проапдейтили бы вновь, и прислали бы обратно. Выходит сильно дорого.
>>258092181 Ты наверно джавист судя по 10к потокам. У меня всегда микросервисы. В любом случае неважно. Поток или микросервис.
Но я понял о чём ты. Ты говоришь про механизм самой бд, а я предлагаю универсальный паттерн для любых параллельных действий. Писать параллельно в любою бд, а не только в ту, которая поддерживает ерро чекинг и ролбэк. А можно так и не только в бд писать, но и в s3 объекты слать. Что угодно.
>>258092348 Когда у тебя 10к юзеров, ты же под каждого из них не запускаешь отдельный микросервис? Наверняка твои сервисы все же умеют обращаться с несколькими юзерами одновременно. Каждый юзер, грубо говоря, будет у тебя отдельным потоком.
>>258092393 >Каждый юзер, грубо говоря, будет у тебя отдельным потоком Чет это слишком дорого, когда каждый поток будет простаивать хуеву тучу времени ожидая ответ от бд.
>>258092463 Но у тебя все то же самое - ты читаешь и пишешь в базу. Принимаешь какие-то решения на основании результатов чтения/записи. Только еще они у тебя будут крутиться в отдельных "микросервисах", которые по факту не то, чтобы уж и "микро". У меня потоки, у тебя процессы. Процессы всегда дороже.
>>258092342 >Ты, да, выполнишь апдейты в какой-то последовательности, но каждый следующий апдейт не будет знать, что какой-то предыдущий в этой последовательности уже изменил данные. Это физически невозможно. Когда 2 апдейт запроса приходят с двух разных серверов, то даже при синхронизированном NTP там будет микроскопический рассинхрон
Чтобы такого не было надо сначала прочитать значение из базы, а потом послать команду апдейта, которая выполнить только если значение совпадает. Так если 2 паралельных запроса придёт, то не важно в каком порядке они буду выполняться. Один всегда выполниться первым, а второй отброситься всё равно. И тогда отправителя второго запроса можно будет уведомить об ошибке и попросить снова если надо. В моей схеме всё так же кроме возможности сообщить об ошибке. В твоей схеме нотифай происходит, но тоже не детерминировано какой из паралельных запросов выполниться первым, а какой упадёт.
>>258092393 Нет конечно. Одного микросервиса для начала зхватит. Если он не будет справлять, то лоад балансер его заскелит сколько надо и будет 2, 3, 5 или 10 контейнеров параллельно читать из очереди и обрабатывать запросы. И хоть в 10к потоков пишу в очередь микросервисы схавают. Но я не настаиваю на их использовании. Просто мне так проще описывать и мыслить. Можешь заспавнить сколько хочешь потоков и читать их очереди потоками. Не важно вообще для схемы
>>258092457 Асинхронный код используется там, где потоки никак не ускоряют код. Например, если в потоке есть медленный IO с диска или по сети. Выше вы предлагали 10к потоко создать. Про switch context, я думаю, ты слышал? Ещё, почитай исходники nginx.
>>258092566 >Один всегда выполниться первым, а второй отброситься всё равно. И тогда отправителя второго запроса можно будет уведомить об ошибке и попросить снова если надо. Да, идея оптимистик локов именно в этом.
>В моей схеме всё так же кроме возможности сообщить об ошибке. Поэтому я твою схему и не понял.
>В твоей схеме нотифай происходит, но тоже не детерминировано какой из паралельных запросов выполниться первым, а какой упадёт. Да, но мы не стремимся их упорядочить. Нам главное, что если 2 запроса одновременно хотят что-то одно увеличить на 10, то после их выполнения это что-то увеличится на 20.
Короче, возвращаясь к теме треда: мы, наверное, не самые джуны с тобой, и нам вон сколько времени понадобилось договориться. Теперь представь этот вопрос зададут джуну (да пусть даже и миддлу?)
>>258092520 В этом случае микросервис с горутинами будет так же быстро как и много потоков читать записи из очереди, смотреть локи, писать в базу и пока одна из этих стадий в io блоке, то микросервис переключится второй запрос читать, так же чекать лок и писать в базу. То есть в одном потоке микросервис запустивший один раз может без контекст свитчинга между потоками обрабатывать ассинхронно много запросов не хуже нескольких сотен паралельных потоков. И если одного микросервиса не хватит, то можно другие сванить. Один рах потратился на создание микросервиса и вот уже паралельно 2 асинхроннвх микросервиса.
Но опять же я не настаиваю на микросервисах. Мне так удобней. То ж самое решение может и на потоках работать
>>258092588 Ок, пусть я дурачок и слово "потоки" употребил для упрощения объяснения. Если заменить его на слово "корутины", суть задачи не изменится совершенно никак.
>>258092694 Не, про "процессы дороже потоков" я к тому, что ты отдельно отвел слой микросервисов, которые отдельно пишут в отдельную таблицу блокировок, и т. д. Пусть они супер-быстрые, но они где-то крутятся, до них надо достучаться, они должны достучаться обратно.
>>258092614 Вот точно тебе говорю, что создавать я их не предлагал. А ввел в условие задачи для наглядности. Ты не предлагаешь решение задачи, ты предлагаешь пообсуждать, почему там 10к, и почему там потоки. Да даже и обсуждать не буду, скажу, что ты во всем прав, а я нет, но задача-то не решена.
>>258091830 >>258091662 ой я рот ебал) я до решения сам догадался, но вот писать это пизда, запутался в индексах, в итоге оч долго ковырался с функцией реверса
>>258092786 Какая задача, нахуй?! Я охранником в пяторочке работаю и там же грузчиком подрабатываю. Завтра в 6 хлеб подвозят, мне на электричку пора выходить. Аррривидерчи!