Самая сложная задача которую вы решали

Расскажите про какие-нибудь сложные задачи которые вы решали? (скучно на карантине, а все топики про политику)

Один из кейсов что у меня был, это когда заказчик попросил сделать копию Google Ads, и нужно было сделать все-все от документа с требованиями страниц на 80, до конечной схемы как это реализуем и на чем, какую нагрузку оно выдержит. Сложность там в том чтобы собрать все требования и не промахнуться с эстимейтом. А сам код не сложный.

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

Интересно, у кого какие сложные кейсы были?

LinkedIn

Лучшие комментарии пропустить

1986 Переход с языка Фортран-66 на PL-1.

Фортран был моим первым языком программирования и первые года три я программировал только на нем. Там был примитивный оператор IF и из-за этого приходилось использовать много GOTO. Потом я перешел на PL-1, который уже имел нормальный IF..THEN..ELSE. Переход от старого стиля программирования к новому был очень сложным.

1992 Написание программы расчета зарплаты для Харьковского инструментального завода (на Foxpro).

Это был мой первый большой проект, первый проект, который ушел в production и первый реальный опыт общения с пользователями. Структуру базы данных до сих пор вспоминаю со стыдом. Тем не менее, программу использовали после моего ухода с завода еще как минимум 10 лет.

1998 Сопровождение системы планирования полетов авиакомпании KLM (она была написана на языке PL-1 и работала на мейнфрейме IBM).

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

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

Остальное было делом техники и три строчки кода решили проблему.

2000 Я работал в голландской телефонной компании KPN Telecom и нужно было для одного из проектов создать штук 15 несложных отчетов на основе данных статистики с телефонных станций.

Я подошел к задаче творчески и разработал собственный генератор отчетов с простым языком (DSL) описания отчетов. На все ушло две недели, из которых три дня было потрачено на изучение LEX и YACC. Я разработал сам язык, написал его интерпретатор, который генерировал отчеты в XML-формате, сами 15 отчетов и еще программу для конвертации отчетов с XML в другие форматы. Плюс ко всему еще написал 20 страниц документации.

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

2002 Я участвовал в разработке программы реального времени для управления установкой, которая разматывала рулон бумаги и подавала бумагу в печатный пресс (хорошо хоть это был не hard real-time). Система была написана на C по методологии Хэтли-Пирбхаи.

В этой системе был модуль для выравнивания бумаги на основе сигналов от датчиков положения бумаги, работа которого была основана на конечном автомате с 70 состояниями. Код со временем стал настолько сложным, что к нему боялись подступиться.

Наконец после запроса на изменение этого самого модуля было принято решение произвести его полный рефакторинг, чем мне и пришлось (или посчастливилось?) заняться. В результате удалось разбить его на 3 модуля меньшего размера, которые взаимодействовали между собой.

2003 Доработка веб-приложения для финансовой отчетности для компании по производству штор и гардин.

Это было 4000 строк нечитаемого кода на VBScript, сплошным куском, без единой функции. С операторами IF, у которых было по 300 строк кода в каждой ветке, и огромным количеством Copy-Paste.

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

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

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

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

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

Я стал разбираться, все время общался с аналитиком, но никак не мог понять, в чем дело. Уже и начальство стало на меня недовольно посматривать, а я не мог им объяснить, чем же я занят.

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

2012 Работал я в одной консалтинговой компании в области энергетики. Работал над двумя проектами одновременно: первую половину недели над одним, вторую половину над другим. Один проект — программа планирования рабочего времени сотрудников: Oracle, VB.NET, sqlite и Python. Второй — система автоматизации химической лаборатории: SQL Server, C# и ASP.NET. Работа проходила в двух разных командах в двух разных офисах.

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

И не только проекты отличались, но и культура питья кофе в двух командах. В одной в течение дня кто-нибудь говорил: «Давайте выпьем кофе!», после чего вся команда вставала и шла к кофейному автомату. В другой команде каждый два-три раза в день приносил кофе всем остальным. Сложно было это помнить и не
путать :-)

2014 Я работал в финансовой компании, которая занималась ипотеками. Большая такая компания, со множеством проектов, процессов и всякой бюрократии.

Однажды был период, когда я работал над 4-мя проектами одновременно. У нас был полный Agile. Каждый день у меня было 4 stand-up митинга и пару раз в день ко мне подходил менеджер каждого проекта с вопросом: «Когда же это будет наконец сделано?». И я даже ухитрялся еще и код писать.

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

Но разработчики не имели прав создать базу на тестовом сервере. Эти занимался отдел баз данных. Надо было послать им скрипты и попросить их запустить. Это простое, казалось бы, дело заняло у меня три дня. Три дня переговоров, посылки email’ов, организации митингов и неоднократного привлечения моего начальника проекта.

В конце концов все удалось. Но я был страшно рад, когда через месяц уже там не работал.

Двигал компонент влево на 3 пикселя в Winforms...

Сделать зеркальный фон на лендинге чтобы юзер видел себя как в отражении

Самая сложная задача, которую приходилось решать:

Ехать или не ехать, вот в чём вопрос. Достойно ль
Смиряться под ударами судьбы,
Иль надо оказать сопротивленье
И в смертной схватке с целым морем бед
Покончить с ними?

Менял цвет иконки с синего на красный.

Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Є такий вид змагання — на протязі доби писати ботів до різних ігор. Умову гри публікують в зазначений час. На протязі доби проводять кілька турнірів між всіма предявленими ботами. В кінці доби проводять супер фінал, за який дають найбільше балів.
То завжди було для мене самим цікавим і дуже складним.

Ше студентом пробував зробити генератор сканвордів під замовлення. Не вийшло. Їздив завдаток віддавати. Соромно було дуже. Керівника свого підставив тоді. Власне вдвох з ним і їздили віддавати завдаток.

Зараз може б і зробив, але треба перше книжок і статтей почитати про то.

На мене, яка ніколи крім фб та word ні з чим не стикалася — повісили переробити сайт. Причому через тотал командер та note. Благо карантін додав часу — і за тиждень я подружилася з «ієрогліфами». А далі пішла робота. Надіюсь результат сподобається.

С утра в спешке после душа быстро надеть носки на мокрые ноги.

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

в шостій вечора літак який має повезти мене в довгоочікувану відпустку. а qa в другій половині дня придолбався, шо в моєму тікеті полоска, яка відділяє основний контент від футера в інтернет експлорері розташована на один піксель нижче чим в файрфоксі (what???). а я бекендер...

а я бекендер...

А qa — прибиральниця Галя...

нє. мутний тіп с адєси

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

То ще фігня. До мене один перець лондонський прийшов з подібним багом. Він роздрукував табличку і йому ширина ліній не підходила)) На моніторі все ок було))

Назвать правильно переменную

И как в итоге правильно назвал?

В бытность студентом 4-го курса КПИ, за 2 недели написал чат-бота (задачка на диплом), который на основе английской грамматики проводил лексический анализ предложения и генерировал ответ без использования заготовленных фраз на базе той же грамматики.
Плёвая задачка на сегодняшний день, но на дворе был 2004-й год и вершиной существующих чат-ботов на тот момент были те, кто умели подбирать частично заготовленные фразы (по сути, фраза с параметризированным куском) и реагировали они не на семантику, а на отдельные слова в предложении, выбираемые по маске, т.е., почитать, как это можно было сделать, было негде. Формальная грамматика и алгоритм были придуманы с нуля.

Интересно было бы сравнить с ELIZA::DOCTOR

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

колбасить код любой может. а если владеет слепым методом, то вообще молодец (то есть молодой).
поиск ошибок в чужом коде и правильное исправление — требует более высокой квалифакции.

значит сложнее — второй.

1986 Переход с языка Фортран-66 на PL-1.

Фортран был моим первым языком программирования и первые года три я программировал только на нем. Там был примитивный оператор IF и из-за этого приходилось использовать много GOTO. Потом я перешел на PL-1, который уже имел нормальный IF..THEN..ELSE. Переход от старого стиля программирования к новому был очень сложным.

1992 Написание программы расчета зарплаты для Харьковского инструментального завода (на Foxpro).

Это был мой первый большой проект, первый проект, который ушел в production и первый реальный опыт общения с пользователями. Структуру базы данных до сих пор вспоминаю со стыдом. Тем не менее, программу использовали после моего ухода с завода еще как минимум 10 лет.

1998 Сопровождение системы планирования полетов авиакомпании KLM (она была написана на языке PL-1 и работала на мейнфрейме IBM).

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

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

Остальное было делом техники и три строчки кода решили проблему.

2000 Я работал в голландской телефонной компании KPN Telecom и нужно было для одного из проектов создать штук 15 несложных отчетов на основе данных статистики с телефонных станций.

Я подошел к задаче творчески и разработал собственный генератор отчетов с простым языком (DSL) описания отчетов. На все ушло две недели, из которых три дня было потрачено на изучение LEX и YACC. Я разработал сам язык, написал его интерпретатор, который генерировал отчеты в XML-формате, сами 15 отчетов и еще программу для конвертации отчетов с XML в другие форматы. Плюс ко всему еще написал 20 страниц документации.

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

2002 Я участвовал в разработке программы реального времени для управления установкой, которая разматывала рулон бумаги и подавала бумагу в печатный пресс (хорошо хоть это был не hard real-time). Система была написана на C по методологии Хэтли-Пирбхаи.

В этой системе был модуль для выравнивания бумаги на основе сигналов от датчиков положения бумаги, работа которого была основана на конечном автомате с 70 состояниями. Код со временем стал настолько сложным, что к нему боялись подступиться.

Наконец после запроса на изменение этого самого модуля было принято решение произвести его полный рефакторинг, чем мне и пришлось (или посчастливилось?) заняться. В результате удалось разбить его на 3 модуля меньшего размера, которые взаимодействовали между собой.

2003 Доработка веб-приложения для финансовой отчетности для компании по производству штор и гардин.

Это было 4000 строк нечитаемого кода на VBScript, сплошным куском, без единой функции. С операторами IF, у которых было по 300 строк кода в каждой ветке, и огромным количеством Copy-Paste.

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

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

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

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

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

Я стал разбираться, все время общался с аналитиком, но никак не мог понять, в чем дело. Уже и начальство стало на меня недовольно посматривать, а я не мог им объяснить, чем же я занят.

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

2012 Работал я в одной консалтинговой компании в области энергетики. Работал над двумя проектами одновременно: первую половину недели над одним, вторую половину над другим. Один проект — программа планирования рабочего времени сотрудников: Oracle, VB.NET, sqlite и Python. Второй — система автоматизации химической лаборатории: SQL Server, C# и ASP.NET. Работа проходила в двух разных командах в двух разных офисах.

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

И не только проекты отличались, но и культура питья кофе в двух командах. В одной в течение дня кто-нибудь говорил: «Давайте выпьем кофе!», после чего вся команда вставала и шла к кофейному автомату. В другой команде каждый два-три раза в день приносил кофе всем остальным. Сложно было это помнить и не
путать :-)

2014 Я работал в финансовой компании, которая занималась ипотеками. Большая такая компания, со множеством проектов, процессов и всякой бюрократии.

Однажды был период, когда я работал над 4-мя проектами одновременно. У нас был полный Agile. Каждый день у меня было 4 stand-up митинга и пару раз в день ко мне подходил менеджер каждого проекта с вопросом: «Когда же это будет наконец сделано?». И я даже ухитрялся еще и код писать.

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

Но разработчики не имели прав создать базу на тестовом сервере. Эти занимался отдел баз данных. Надо было послать им скрипты и попросить их запустить. Это простое, казалось бы, дело заняло у меня три дня. Три дня переговоров, посылки email’ов, организации митингов и неоднократного привлечения моего начальника проекта.

В конце концов все удалось. Но я был страшно рад, когда через месяц уже там не работал.

Техническая — разработал архитектуру продукта. Но проблемы с людьми куда сложнее. Как-то в 2012 образовалась у меня первая моя команда из трёх человек. Одного наняли неделю назад и он ничего не знал о платформе с которой мы работали. Второго перевели из мануал в автомейшн тестировщики ( без обучения как вообще, просто сказали — поздравляю ты теперь автомейшн). Пришлось проводить экстренные курсы Java прямо по ходу работы. Диливерить мы конечно не могли, а заказчики наседали, менеджер проекта — девочка год назад закончившая иняз. Нашла способ исправить ситуацию — перестала со мной разговаривать, потом устроила скандал. Мы работали по скетчам, накручивали бекенд к «фронтенду». Фронтенд по контракту делала другая компания — поэтому мы использовали наскоро склепаные мокапы от наших фронтендщиков. Обещали — что как только придет фронтенд, мы его прикрутили — а мокапы поменяйте для автотестов, они мол быстрее отработают ибо картинок и цсс-ок со скриптами нет. Команда была частично в Киеве — а частично в Харькове ( мы в Харькове). И мы конкурировали, хотя — официально это одна компания. Менеджер Киевской команды получил фронтенд, и конечно ничего не сказал — чтобы продемонстрировать заказчику бесполезность конкурентов. В итоге все что мы делали — пошло в корзину. Клиент в ахере с происходящего, овербеджет — проект закрыли. Главный менеджер проекта ( который вмешивался зачем-то в мержинг бранчей) — сказал что это всё потому что мы работали по аджайл

1. Задизайнить замену (редизайн/новое поколение) для высоконагруженного tier-1 сервиса, которому с десяток лет активной разработки, последние года в полузаброшеном состоянии, сотни клиентов (других сервисов), спагетти из разнообразного функционала, атавизмы, нетривиальная интеграция с десятками зависимостей. и все это какбы подразумевается частью платформы, то есть не только нужно было задизайнить сам сервис но и переопределить как весь зоопарк клиентов должен интегрироваться и множится и куча всего...
2. Если рассматривать сугубо техническую задачу, сложно вспомнить, наверное какой-то нетривиальный, жуткий дебагинг... но это не интересно, из интересного — реализация операции как распределенной атомарной транзакции, при этом все должно работать идеально надежно, потеря данных не допустима в принципе.

реализация операции как распределенной атомарной транзакции

Про это было бы интересно почитать подробнее.

NDA :( не думаю что могу все рассказать.
может можно обобщить задачу и обфусцировать детали, но на это надо больше времени, а сейчас на это времени нет. может потом как-то и опишу

Там ничего интересного не написано.

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

Eventual Consistency FTW. Или WTF, у кого как. Но интересно было узнать как решилась задача как раз в этом треде. Были ли вовлечены брокеры сообщений в 2PC, если это был 2PC и как это было сделано.

Были ли вовлечены брокеры сообщений в 2PC

Почему это должно быть вообще интересно? Гипотетически с точки зрения абстракций 2PC это вообще детали реализации более низкого уровня.

Потому что большинсво брокеров не поддерживает 2PC 😉.

Мы немного о разных вещах потому что «вовлечены» и «поддерживают» не означает одно и то же. Но опять же сути не меняет: брокер сообщений в понимании поддержки 2PC всего лишь один из множества сценариев использования 2PC, и кстати концептуально не самый удачный.

Очевидно о разных. Я о сценарии, когда для

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

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

(которые, кстати тоже могут не уметь в 2PC)

Тогда это не 2PC.

Вот поэтому и интересно какую задачу и как решал автор треда.

Навчився правильно ставити наголос в словах «договор» та «каталог».

Из комментов я узнал, что O(63*n + sqrt(n)) и O(n/2) это не то же самое, что O(n). Интересно, продолжайте.

Ты тут еще и не такого узнаешь. И когда будешь фэйспалмить, осторожно, тут запросто и фингал себе посадить.

Можно продолжить. У меня вопрос, пускай на правах тролинга. Вот допустим спорят два алгоритмиста, в уме прикидывают сложность алгоритмов. Один говорит, мне нужно N итераций в этом алгоритме. Другой говорит, я придумал оптимизацию, нужно обойти всего N/10 элементов, будет в десять раз быстрее.
Понятно что и там и там O(n), но как тогда грамотно отметить что один алгоритм имеет в десять раз меньшую сложность ? Понятно в Вики написали по дубовому, все O(n). Может кого не устраивает такая дубовая формулировка, между черным и белым есть ещё стопицот оттенков.

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

И если внимательно почитаешь, то узнаешь, что O(n^n) может работать быстрее, чем O(n).

О-нотації входять в курс матану

«Матан нікада нінада» ©

Дрони без матану не літають

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

Тут зародилось новое популярное мнение «Ой, а когда мне понадобится тот матан, я открою популярные несовковые уроки на стенфорде

А это мнение возникло из мифа, что «там» типа лучше рассказывают, а раз так, то в нашем универе не стоит напрягаться и изучать.

это дилема, известна как algorithm analysis vs microbenchmark

как тогда грамотно отметить что один алгоритм имеет в десять раз меньшую сложность ?

Ніяк — складність у них однакова і лінійно залежить від розміру вхідного набору даних.

Складність це не про кількість ітерацій, а про те як кількість ітерацій залежить від розміру.

Тут уже ответили на вопрос
При n это О(n)
При меньше n это o(n)

Понятно что все ещё недостаточно хорошо чтобы четко выделить особенности алгоритма, но уже лучше чем везде писать О(n)

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

При n это О(n)
При меньше n это o(n)

нет
«Big O», «little o» это не функции, а классы функций с некоторыми условиями

Забей. Дал я тут одному стеклянный член (в википедию послал) — он его уже разбил.

в Вики написали по дубовому, все O(n). Может кого не устраивает такая дубовая формулировка, между черным и белым есть ещё стопицот оттенков.

Ймовірно, Вам підійде нотація асимптотичної еквівалентності «~» (означення можна подивитись в таблиці en.wikipedia.org/...​Bachmann—Landau_notations ). Всі решта широко вживані нотації (О, о, тета-велике, тета-маленьке, омега) не достатньо «гранулярні», щоб забезпечити різницю між n та 2n.

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

«O» большое и «o» малое ( O {\displaystyle O} O и o {\displaystyle o} o) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Под асимптотикой понимается характер изменения функции при стремлении её аргумента к определённой точке.

Запустить рекламу в Инстаграм, но что бы клиенту приходило по 2 клиента. и все это за 1 доллар в сутки

Сажал самолётик на авианосец в Top Gun на Nintendo.

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

А слабо боинг 737 на авианосец посадить в MFS? ))

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

Правильный дизайн должен был учитывать такую возможность!

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

не. сложнее объяснить что если так и будете «таски закрывать» — проект закроют и всех уволят

Міграція 30Тб БД Оракле з HP-UX IA64 на Linux x86-64 з 1Гб/с мережею та допустимим простоєм 30хв.

Как такое возможно???

Ssd перекинули между серверами?

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

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

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

вот по дороге подумал )) может даже с ssd будет не оптимально а обычные диски дают 100+ МБ линейной записи и соотв. чтобы просто переписать 30 ТБ нужны 3.5 суток причём это легко масштабируется скажем в 4 раза до 1 суток

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

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

в амазона есть AWS Snowball, они реально предоставляют «грузовик груженный дисками as s service»

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

ЗЫ: по ходу snowball это тот „чемоданчик” а „грузовик груженный” это уже snowmobile ))

AWS Snowmobile
Migrate or transport exabyte-scale data sets into and out of AWS

Неа. У нас був нормальний на той час Fiber Channel до ентерпрайзних сховищ даних, так що досить було перепрезентувати диски, але перекинути дані було не основною проблемою. Біда була в конвертації БД, бо платформи різні за порядком байтів (endianness).

Оптимизация криптоалгоритма с использованием полей Галуа. Сложная, но интересная.

а зачем там конечные поля?

Расчет промежуточных ключей, таблиц, которые позволили ускорить шифрование в 50 раз. Речь идет о старых попытках ДСЗЗІ внедрить нацстандарт шифрования. Уже не слишком актуально.

Захоплення потоку кадрів з колесами, що періодично з’являються в полі зору камери, з індустріальних камер із швидкістю 500МБ/с на HDD з використанням стробоскопу, що може працювати кілька секунд підряд, а потім ймовірно вибухає та/або згоряє.

Поділ захоплених кадрів на осі вантажівок та трейлерів.

Декодировал ACG_DATA файлы. Потратил несколько недель на эту задачу.

github.com/...​rc/main/c/superlnk.c#L463

Діставав ягда з борсучої нори... ;))

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

Реализовал удаление ключей из HArray. Задача требовала написания 2/3 кода, который просто мониторит health памяти пока работает алгоритм. Без этого одни ошибки наслаивались на другие, и раскрутить первопричину в дебаге было фактически невозможно. Но это из тех задач которые оправдано сложные и одновременно интересные. Были и сложнее задачи, но это скорей из разряда неоправдано сложно спроектированных систем, поэтому эти задачи я бы сказал были неспортивно сложные. Типа как пробежать стометровку ... прыгая на левой ноге ... задом .

Єто была учебная задача или промышленная?

Не учебная и не промышленная, просто реализация одной интересной и перспективной идеи

Реализовал удаление ключей из HArray. Задача требовала написания 2/3 кода, который просто мониторит health памяти пока работает алгоритм.

о, це ось той топік 2016 року, де ти упорно ігнорив Warnings і усі зауваження комментаторів
dou.ua/forums/topic/18849

і шо — допиляв таки, і воно кросплатформенне і паше?

Да, эта штука кроссплатформенная, давно допилена. Используется в двух СУБД, одна близкий аналог эластика вторая близкий аналог монги. Близкий аналог по ф-сти, по устройству принципиально другая. Та что аналог монги, надо бы переписать в пользу капитального сжатия json документов на базе Trie. Но это слишком сложная задача для меня, по крайней мере на парт тайм.

Сделать зеркальный фон на лендинге чтобы юзер видел себя как в отражении

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

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

На співбесіді пояснив ідею і нормально обговорили її взагалі. А потім вже з інтересу сам сів писати код і витратив майже цілий день на це :(

20 сек ушло. Какие специальные случаи? Линейный алгоритм. По порядку с одного вставляешь во второй..

треба швидше ніж за O(n)

Лінійний не підійде. Цікаво як це швидше можна написати. Всеодно ж треба створювати новий масив і заливати туди по одному з кожного. Можна при ініціалізації впихнути одразу всі. Ще хз Як AddRange методи працюють.

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

Создаешь новый массив
Пам’ять алоціювати чи модифікувати вхідні параметри не можна
Цікаво як це швидше можна написати

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

какой бинарный поиск? что вы искать то собрались? индекс который уже есть?
этот алгоритм — часть сортировки вставками
два указателя на левый и правый массив
сравниваем текущий элемент с левым и правым массивом, проходя по ним пока p_left + p_right != k
последний элемент и будет результатом
сложность O(k)
20 строчек кода

Бесполезно, я ему этот код прислал, написал ровно за 5 минут. Ответ — существует какойто тайный код который «работает» намного лучше O(n), но я вам его не покажу, «напомните мне потом, через несколько дней». Я сам не понимаю, зачем там бинарный поиск ?

сложность O(k)

Прочитай умови задачі. Треба швидше.

Для тих хто ніяк не може второпати поясню — ці «масиви» можуть бути скажімо файлами які просто в пам’ять не поміщуються. Або їх може бути стільки що вони теж не поміщуються в пам’ять. Проходити їх усі елемент за елементом — це дуже довго. Але нам допомагає те, що послідовності відсортовані — може це можна якось використати?

Але нам допомагає те, що послідовності відсортовані — може це можна якось використати?

Тот алгоритм что я прислал как раз и работает потому что элементы отсортированы.

Для тих хто ніяк не може второпати поясню — ці «масиви» можуть бути скажімо файлами які просто в пам’ять не поміщуються.

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

Тот алгоритм что я прислал как раз и работает потому что элементы отсортированы.

У відсортованих масивах можна шукати швидше ніж послідовним перебором.

func find(k: Int, in lhs: [Int], and rhs: [Int]) -> Int? {

    if lhs.count == 0 && rhs.count > k {
        return rhs[k]
    }

    if rhs.count == 0 && lhs.count > k {
        return lhs[k]
    }

    var l = 0
    var r = 0
    var curr: Int? = nil

    while l + r <= k {
        if lhs.count > l && rhs.count > r {
            
            if lhs[l] <= rhs[r] {
                curr = lhs[l]
                l += 1
            } else {
                curr = rhs[r]
                r += 1
            }
        } else if lhs.count > l {
            curr = lhs[l]
            l += 1
        } else if rhs.count > r {
            curr = rhs[r]
            r += 1
        } else {

            break
        }
    }

    return curr
}
let lhs = [1,22,23,25,1000]
let rhs = [1,2,26,28,500]
let k = 5

print(find(k: k, in: lhs, and: rhs))

Это O(n) в хучшем кейсе, тоже что у меня, только похуже написан код.

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

Мой код работает с разным количеством элементов в массиве. Проверь внимательно

Я могу написать алгоритм со сложностью O (k/2) — просто проходить от конца / начала
27 — это третий с конца в 30 элементах условно

Це послідовний перебір, тобто O(n). Не будь як Бубен, прочитай умови задачі.

Условие — сложность O(n)
O(k) это минимальное условие которое даже в теории можно получить

Ну як би так тобі пояснити... Якщо кількість ітерацій лінійно (забув правильний термін) залежить від розміру вхідних наборів то це O(n). Таким чином O(n/2), або O(n-1) не мають сенсу бо вони просто O(n). Те ж саме стосується і твого O(k) — кількість ітерацій прямо залежить від розміру масивів, а має бути менше ітерацій.

web.mit.edu/...​070/www/lecture/big_o.pdf

Как бы тебе обьяснить, что про хештаблицы пишут везде сложность О(1) хотя по факту там О(N) бо worst case. Я уверен что на твой говнокод, который ты так боишся выкатить, тоже можно найти worst case и он будет О(N) а может и больше. Инфа 100% Хотябы при случае когда в одном массиве 1 элемент а во втором 0.

Как бы тебе обьяснить, что про хештаблицы

Та ніяк не треба — я тебе про хеш-таблиці не питав і відношення вони до моєї задачі не мають.

Я уверен что на твой говнокод, который ты так боишся выкатить

З чого ти взяв що боюся. Повторю в четвертий раз — нагадай мені через кілька днів і я дам лінку на нього.

тоже можно найти worst case и он будет О(N) а может и больше

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

Хотябы при случае когда в одном массиве 1 элемент а во втором 0.

Ти би почитав все ж таки про складність алгоритмів.

я никогда не говорил что у меня не линейно, или что O(n/2) это не O(n)
не увидил возможность сразу оптимизировать через логарифмическую сложность, но это не отменяет того факта что если это самое сложное задание в жизни, то жизнь удалась

Ти ж не зміг знайти рішення — як мінімум для тебе складне.

Согласен. Спасибо, Олександр.

У задачі три параметри, від яких може залежати складність: довжини m та n вхідних списків та k — індекс. Твердження, що

кількість ітерацій прямо залежить від розміру масивів

не вірне: зафіксуйте k та змінюйте m та n, кількість ітерацій від цього не збільшиться. Наведіть, будь ласка, складність правильного рішення.

Якщо зафіксувати k то вийде, що рішення шукаємо для одного конкретного випадку. В загальному ж випадку k буде в діапазоні від 0 до O(n), де n — сумарний розмір вхідних масивів. І таким чином виходить O(k) це теж O(n).

Інакше можна було б «зафіксувати» k зі значенням 0 і написати O(1) алгоритм.

Всеодно ж треба створювати новий масив

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

Линейный алгоритм

Треба швидше

с одного вставляешь во второй

Цього не зрозумів. Що куди вставляти? Вхідні параметри модифікувати не можна.

Так, чи що?))

private static int FindValueByIndex(int[] array1, int[] array2, int targetIndex)
{
       if (targetIndex <= array1.Count() - 1) return array1[targetIndex];
       else return array2[targetIndex - array1.Count()];
}

Тут бінарі сирч не треба по моєму) Або я щось не зрозумів.

там така потреба
SELECT our_value FROM ( SELECT our_value FROM ( SELECT our_value FROM a UNION ALL SELECT our_value FROM b ) merged_tbl ORDER BY our_value ) OFFSET k LIMIT 1

написати щоб не треба було формування merged_tbl та ORDER BY
враховуючи що а та b відсортовані

як такє зробити на SQL?
ну щоб пам’яті потребувало стільки ж, скільки ж
SELECT our_value FROM ab OFFSET k LIMIT 1

на звичайному ЯП не цікаво, зазвичай масиви відносно невеликі.
А великі — лежать десь «у базі данних»
то як зробити такий запит?

Окей, завтра спробую. Сьогодні вже на сон тягне.

UPD Ні, не так. Ви мене валите! Давайте я за шоколадку здам?

просто це та ж сама задача, але наближена до практики ПЗ для бізнесу:
маємо «OLX».
на кожну область України маємо окрему таблицю переглядів, у котру фіксується час, user_id, adver_id
user_id може бути null, якщо не авторізований юзер клікнув

треба знайти кожного 100 000го по всій Україні, щоб надати бонус.
на тому ж серверному обладнанні, на якому працює система (зазвичай середній розмір ОП на сервері з БД менший середнього розміру такої таблиці у 10 разів).
створювати заздалегідь окрему таблицю куди пишемо — не можна

Риторичне питання
зкільки задачок з літкоду треба вирішити, щоб навчитися вирішувати такі, реальні завдання?

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

Давайте я за шоколадку здам?

скільки шоколадок вам дали за вирішення завдання з масивами?

У Вас наверняка есть логирование событий на входе в базу. И нефиг лезть в базу грязными руками и мешать ей работать — напустите питон на лог трансакций и он Вам оттуда выгребет каждого 100000го.

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

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

Не сильно зрозумів написаний код. k-тий елемент може бути в будь-якому з двох масивів.

k-тий елемент може бути в будь-якому з двох масивів.

І яка логіка? Тут так і працює: або к в першому або в другому. Уявно зєднується перший масив із другим і повертається валю по к індексу. Якщо перший масив має 4 елементи з останнім індексом 3, а другий 2 елементи то його умовний індекс 4, 5 і якщо к — 4 то поверне перший елемент другого масиву. Або ж якщо к 2 то поврене третій елемент першого масиву.

Уявно зєднується перший масив із другим

Елементи після такого з’єднання будуть перемішані, а не просто один масив дописується в кінець іншого.

Ага, під такий варіант я не писав, хоч і розумів що він можливий.

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

С этого начинать надо было.

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

масиву який би вийшов зі злиття a та b зі збереженням сортованості

То есть эта магическая строчка означает, что результирующий массив, в котором нужно искать по индексу k, являет из себя отсортированный результат объединения элементов массивов a и b? Фух.

результирующий массив создавать не надо, нужно на выход отдать элемент, который бы совпадал с arr[index] результирующего отсортированного массива

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

gist.github.com/...​bfa1343cc9a769760a8dfac97

Ось я зробив 2 методи, щоб цікавіше. В другому заюзав бінарі сирч з вікіпедії(звісно підкорегував під бізнес логіку).

Як навіщо? Щоб заїпатися. Ну і власне розміри масивів різні можуть бути. В літкоді пихають громадні в таких випадках.

В прямому виді ні для чого, але техніка коли звужується діапазон пошуку індексами зліва і зправа та сама.

Чи враховує цей код, що у злитому в купу масиві елементи з двох вхідних масивів будуть перемішані? Бо у тебе усі елементи в array2 можна просто вставити блоком після елементів array1.

Також один з масивів може бути порожнім.

Чи враховує цей код, що у злитому в купу масиві елементи з двох вхідних масивів будуть перемішані?

Ні, це я не враховував, щоб хоча б так вирішити. Завтра візьмуся врахувати.

Бо у тебе усі елементи в array2 можна просто вставити блоком після елементів array1.

Але ж це алокація, хіба ні?

Також один з масивів може бути порожнім.

Так, якщо перший пустий то ламається метод FindValueByIndex. А от FindIndexByValue працює справно.

Але ж це алокація, хіба ні?

Я мав на увазі що якщо створювати злитий масив (але робити ми цього не будемо) то в тебе той випадок коли просто другий масив буде ціляком йти після першого. Але значення можуть бути в масивах будь-які: {1, 10, 100}, {2, 3, 4, 5, 11, 12, 12, 50, 99, 1001, 1002}.

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

Тут щоб зааплаїти бінарний пошук, потрібно злити масиви і пересортувати.

Ніт. Умовно кажучи маючи індекс i в A та індекс j в B можна сказати як розміщують відносно один одного елементи A[i-1], A[i], B[j-1], B[j]. Якщо при цьому додати обмеження як i+j==k то ми можемо сказати в яку сторону треба рухати i та j так щоб знайти A[i-1] < B[j] < A[i], або B[j-1] < A[i] < B[j], що і буде відповіддю.

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

На мою думку задача хороша. І вміння програмувати можна продемонструвати, і вміння розв’язувати задачі.

В реальності просто б злили масиви і пересортували

Коли є час і пам’ять для цього.

І вміння програмувати можна продемонструвати, і вміння розв’язувати задачі.

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

программування буде ось у такому варіанті:
dou.ua/...​rums/topic/30317/#1838219

і. якщо вирішувати такі завдання, то треба починати з тесту
варіанти a та b
[1], [2..31]
[1..30], [31]
[1..15], [16..31]
[1..11], [12..31]
[1..21], [22..31]
[парні з 1..31], [непарні з 1..31]
та на помилкі коли масиви порожні, або скупний розмір менший за 31

та для кожної пари отримати
для k 1, 31, 5, 6,17,18
(тобто масиви індексуються з 1)

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

про такі випадки і кажу, математика не вчить программуванню.

Це насправді цікава тема для розмови і я погоджуся, що в цілому подібні задачі не є гарним способом перевірити кандидата. Якщо дають виключно такі задачі як робить одна компанія назва якої починається на «гу», а закінчується на «гл» (хоча ФБ теж таким страждає).

Мені більше подобається підхід коли кожна година інтерв’ю перевіряє певний конкретний набір вмінь. Ось ця задача конкретно на вміння в алгоритми. В купі з інтерв’ю на ООП/дизайн, рефакторинг та пошук проблем у коді, проектування та оцінка складності і вартості розробки з незнайомими технологіями і будь-якими ще (не значить що саме цей набір має сенс для кожної конкретної позиції), ось з усім цим подібна задача підходить дуже добре ІМО. І в цілому для програмістів має діяти правило no code — no hire незалжно від результатів перевірки інших вмінь та знань.

Це насправді цікава тема для розмови і я погоджуся, що в цілому подібні задачі не є гарним способом перевірити кандидата.

Задача может быть и простой. Проверяющий должен быть способен заценить ход мысли. Решение задачи не цель.

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

Як у нас кажуть he can talk the talk, but can he walk the walk?

В загальному випадку так. Але на позицію дева має бути хоч одне інтерв’ю де очикується правильно і акуратно написаний код

Ключевое слово «правильно». Аккуратно и секретарша перепишет.

Ну ок.

Идешь по индексу k в каждый массив. Сравниваешь значения a[k] <=> b[k]. Если первое больше — отступаешь пол-интервала назад в первом массиве. Если второе больше — во втором массиве. Опять сравниваешь. Повторяешь, пока сумма индексов сравниваемых элементов не станет равна k.

Другой вариант — брать a[k>>1] <=> b[k>>1] и скакать в обе стороны — смотря кто из них больше или меньше.

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

Идешь по индексу k в каждый массив...

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

на практике оно может быть медленнее линейного прохода

На спеціально підібраних наборах даних напевно.

На спеціально підібраних наборах даних напевно.

Там не від даних, а від розміру масивів, мабуть. Міряти треба. (Я не буду)

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

static int f(int[] a, int[] b, int k)
        {
            if (k > a.Length + b.Length)
                throw new InvalidOperationException();

            int i = 0;
            int j = 0;

            while(true)
            {
                if(i >= a.Length)
                {
                    if (i + j >= k)
                        return b[j];

                    j++;
                }
                else if(j >= b.Length)
                {
                    if (i + j >= k)
                        return a[i];

                    i++;
                }
                else if (a[i] < b[j])
                {
                    if (i + j >= k)
                        return a[i];

                    i++;
                }
                else if (a[i] > b[j])
                {
                    if (i + j >= k)
                        return b[j];

                    j++;
                }
                else
                {
                    if (i + j >= k - 1)
                        return a[i];

                    i++;
                    j++;
                }
            } 
        }
if (k > a.Length + b.Length)
throw new InvalidOperationException();

Забув 1 відняти. Я свій код по лінку теж відедітив бо додав лишню одиницю і останній не знаходило.

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

Так, але така дрібниця може змусити подебажити. Завтра осилю весь твій алгоритм і заціню(для себе).

І зробити це треба швидше ніж за O(n).

Там и есть как раз O(n). Допустим в первом массиве 100 элементов, во втором массиве 200 элементов. N = 300. Максимум итераций в цикле будет 300, в среднем 150.

Максимум має бути швидший за O(n).

Это ты не допонял условия задачи. Максимум не должен быть быстрее O(n). Минимум там одна итерация, максимум равно по количеству элементов O(n). Это от тебя и требовали на собеседовании, обычное слияние массивов. Все эти бинарные поиски это говнокод и баловство в этой задаче. Легко доказать что на определенных наборах данных все эти бинари серч с мат функциями будут в разы медленее работать чем тот простой и понятный алгоритм что я привел выше работающий за О(n).

швидше ніж за O(n)

!=

Максимум не должен быть быстрее O(n)

Какая-то своя интерпретация, очевидно что хотят за O(log n).
Ну а практичность и применимость такого решения в реальных кейсах, то уже такое.

Откуда взято O(log n) в условиях задачи, почему не O(1) ?
Обычно пишут то время за которое хотят решение, в данном случае O(n).

O це як я знаю про worst-case. В умові було:

І зробити це треба швидше ніж за O(n)

А значить worst-case має бути швидшим за O(n).

О(1) тоже ок по условию )
Потому что быстрее O(n), всегда понимается О(log n) или О(1).

Но да, всегда можно сказать: my life — my rules.

Потому что быстрее O(n), всегда понимается О(log n) или О(1).

Или O(sqrt(n)). Или O(log n * log n). Или любое другое из бесконечного множества функций от n, асимпотически меньших O(n). Откуда вы это взяли?

Соглашусь, слишком категорично насчёт «всегда», скорее обычно. Имел ввиду общие случаи sublinear time.

Какая-то своя интерпретация, очевидно что хотят за O(log n).

Не думал особо, но не думаю, что O(log n) возможно. Скорее что-то в районе O(log n * log n)

ЛОЛ При некоторых O(log n * log n) будет больше > O(n)

Кто-то не знает как работает O нотация.

Да, здесь ошибся. Но в любом случае. Выкатывайте свое решение с O(log n * log n)

Не треба. Хай кожен хто хоче сам спробує написати. От через декілька днів хай Олександр і викачує, не раніше. Підсказок вже тьма.

У меня аналогичная задачка лежит в todo на литкоде. Решу, когда дойдет очередь.

Оскільки у масивів скоріше за все буде різна кількість елементів (m та n) то можна за O(log m log n)

то можна за O(log m log n)

Це типу 2 рекурсії/(while з поділом на 2) одна після одної?

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

Оскільки у масивів скоріше за все буде різна кількість елементів (m та n) то можна за O(log m log n)

ЛОЛ условия рожаются прямо на лету. С чего ты взял что у массивов будет разное количество элементов ?

З того що ніде не сказано, що кількість елементів в масивах однакова. А значить робити подібне припущення — помилка.

— Напиши код, который возвращает количество элементов в LinkedList
— Вот.
— Но этот код упадет, если LinkedList пустой
— Лол, условия рождаются прямо на лету. С чего вы взяли, что линкедлист может быть пустой?

В ядрі лінукса до речі бачив подібний код в ютубі, Торвальдс коли конференцію проводив. Там не провіряється на пустоту, щоб швидше код працював. Типу провіряти що вставляє має клієнт функції.

Это ты не допонял условия задачи.

ЛОЛ. Тобто те що я обсудив рішення з інетв’юєром і очевидно правильно зрозумів умову ти вирішив проігнорувати?

Ні, задача така і була — швидше за O(n), без додаткової пам’яті і не модифікувати вхідні дані.

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

Але в цілому бінарний пошук швидший за перебір. І в середньому і в найгіршому випадку.

Але в цілому бінарний пошук швидший за перебір. І в середньому і в найгіршому випадку.

ЛОЛ ну выкатывай свое решение. Сейчас его засунем в бенчмарк и замеряем «в найгіршому випадку»

выкатывай свое решение

Дам ще час подумати іншим, може кому цікаво самому зробити. Підказки вище вже дав.

Нагадай через кілька днів як забуду.

До речі ось цей комент ^^^^ якраз демонструє те про що я писав як зверхність і необгрунтовано високу про себе думку українських програмістів.

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

Автор, от тебя на собеседовании просили простое элегантное решение. А ты мутил крутил говнокод который выкатил Вовчок, в котором и LINQ и Math.Cell и еще хрен знает что. Конечно если ты такой код рожал целый день, интервьювер тихонько посмеялся и сказал нет, нам таких кодерков которые элементарную задачу чуть ли не через нейронные сети решают — не нужно. Но это мое мнение. Пускай оно будет субьективно.

Автор, от тебя на собеседовании просили простое элегантное решение.

Для задачі яку я привів, а не тієї яку ти вигадав.

LINQ и Math.Cell и еще хрен знает что

Я на чистому С писав. Бо там специфіка команди така — перформанс, вот ето вот всьо.

Конечно если ты такой код рожал целый день

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

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

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

Так покажи свой код на Си, а не додумывай в «найгиршому випадку буде краще»

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

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

Интервьювер тебе правильные вопросы задавал.

Це які наприклад?

Пишу і регочу — якийсь васян з інтернетів розказує мені, що у мене інтев’юєр питав багато років тому і як я його не так зрозумів :D

мой код масштабируется за 15 минут на любое количество массивов

Але він не виконує умови «швидше ніж на O(n)».

Я бы ровно такой же вопрос задал,

Ти б для початку задачу зрозумів. Питання по коду (до речі якому коду?) потім вже якось.

Пишу і регочу

Ну васян в данном случае ты. Согласись, выкатить решение за 5 минут которое решает задачу в среднем за меньше чем а О(n) все же лучше чем невыкатить ничего, и рожать потом код сутки. Но я всетаки подожду твой код, зря ты сьезжаешь что «потом запощу подожду что ктото решит».

решение за 5 минут которое решает задачу в среднем за меньше чем а О(n)

Це задача яку ти сам собі вигадав і чомусь намагаєшся мене переконати, що саме її я і мав на увазі.

лучше чем невыкатить ничего

Нічим не краще — що так, що інакше задачу не вирішено.

рожать потом код сутки

Звідки ось це «сутки» взялося?

я всетаки подожду твой код

Так, не забудь мені нагадати через кілька днів.

зря ты сьезжаешь что «потом запощу подожду что ктото решит»

І знову ти зі своїми вигадками сперечаєшся. Я ж наче такого не писав, для чого брехати?

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

Если бы я хотел сьехать, именно так бы и написал. Я сделаю, но потом, когдато ...

День != доба.

Ти завжди читаєш те що тобі хочеться, замість того, що написано?

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

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

Если бы я хотел сьехать, именно так бы и написал.

Як так?

Я сделаю, но потом, когдато

Але ж я не так написав. Це ти щойно вигадав і намагаєшся видати за сказане мною.

Я с вас ору.

Потому что мой код масштабируется за 15 минут на любое количество массивов

Да вообще ваш код безумно прекрасен, делает волосы чистыми и шелковистыми и улучшает цвет лица. У него есть только один недостаток — ОН НЕ РАБОТАЕТ ДЛЯ РЕШЕНИЯ ЭТОЙ ЗАДАЧИ, более того, он не может служить stepping stone в итеративном подходе решения задачи (когда для решения задачи X мы решаем похожую на X задачу, только с облегчёнными требованиями, а потом думаем, что там поменять, чтобы решить X). Эта задача — очень хороша в том плане, что проверяет много важных для программиста качеств, и самое первое из них — умение читать и понимать требования. По-видимому, это качество у вас недоразвито (и поэтому и stepping stone из вашего кода не выйдет), поэтому вы не сможете решить эту задачу — что, впрочем, не мешает вам предаваться грёзам, в которых вы кого-то там неделями мучаете.

Его задача решается меньше чем за O(n) с набором определенных эвристик и нетривиальных решений. Это очевидно. Мой посыл — зачем так сложно. А вы прежде чем орать — выкатите свое решение. Почему-то ниодного решения «орунов» не увидели пока что.

Потому что решение быстрее чем за O(n) является частью требований поставленной задачи. Мы делаем эти нетривиальные штуки для того, чтобы решить эту задачу. Решение за O(n) или медленнее не будет подходящим решением этой задачи. Поэтому и сложно. Вы не согласны?

Если бы вы внимательно читали то поняли, что предложено решение которое в среднем работает О(n/2). В худшем кейсе (worst case) оно только показывает O(n). Так что формально по условиям все Ок.
Про хештаблицы кстате тоже говорят что работают за О(1), а по факту их worst case тоже O(n)

Нет, не ок. Вы не понимаете О-нотацию. O(n/2) — это то же самое, что и O(n).

В худшем кейсе (worst case)

Спасибо вам (thank you).

Нет, не ок. Вы не понимаете О-нотацию. O(n/2) — это то же самое, что и O(n).

Не совсем так. У вас есть два алгоритма. Первый алгоритм при передаче массива на 100 элементов вынужден пробежать по всем 100 элементам. Второй только по 50. У одного будет сложность условно O(n) у второго O(n/2). Мы можем сказать что оба алгоритма имеют линейную сложность O(x), но если хотим сказать более точно, говорим O(n) и O(n/2) где N количество элементов

Это всё прекрасно, но ваш алгоритм всё ещё работает за линейное время. O(n). Не быстрее.

Где N это сумма количеств элементов в первом и втором массивах.

Если это сумма элементов, то мой алгоритм в среднем бежит только по половине этих элементов. Поэтому это и N/2. Еще раз внимательно прочитай мой пример выше с двумя алгоритмами у них сложность не одинакова (!). Вообще определение сложности алгоритмов, это нетривиальная задача, если конечно это не делать так по дубовому как ты типа O(1) O(n) O(log n) и больше ничего нет

мой алгоритм в среднем бежит только по половине этих элементов

Це лише означає, що кількість ітерацій лінійно залежить від кількості елементів. Тобто O(n).

Асимптотическая сложность — одинакова. Они оба линейны. Они оба O(n). Я не виноват, что вы этого не понимаете.

Вообще определение сложности алгоритмов, это нетривиальная задача

Поэтому люди когда-то сели и подумали: а как вообще сложность посчитать? Что это вообще такое? И придумали такую штуку, «асимптотическое описание вычислительной сложности», или «асимптотическая сложность» по-простому. Очень полезный инструмент. И именно этот инструмент, в котором O(n) — это то же самое, что O(n/2), и O(n/5), и O(n*63+sqrt(n)-283), вас просили использовать в требованиях к обсуждаемой задаче, и вы, чтобы оправдать своё решение, которое для требований задачи явно не работает, начали этот инструмент переделывать. Зачем вы так? Вы точно уверены, что так вы пройдёте собеседования?

Или, боронь Боже, проведёте? Вы можете свою компанию назвать, чтобы я знал, куда точно идти не следует?

Не беспокойтесь на этот счет. Одним из основных черт хорошего специалиста — способность видеть область в которой он работает детально и многогранно. Людей которые видят эту область однообразно и по «книжному» отличает малый опыт работы в этой области. Ну знаете, если механик авто видел устройтво авто только на картинках, то для него что там такого. Руль да четыре колеса. О(1) да О(n). А механик который работает с этим подробно то и зазоры увидит и крыло не в цвет двери ... Вообщем не беспокойтесь. Поднаберетесь опыта, научитесь писать O(n/2) и различать алгоритмы между собой более подробно. Удачи.

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

Этот опыт позволяет по крайней мере не писать несусветную чушь что формула

O(n*63+sqrt(n)-283)

это тоже что O(n), график там не линейный. Напомните, это 5й или 6й класс школьного курса алгебры ? Вроде бы карантин идет не так долго, должни же помнить ...

А у меня тоже есть опыт, называется „читать уже заботливо скинутую в тред статью”. Попробуйте: en.wikipedia.org/...​Big_O_notation#Properties Английский там простой, как раз для пятого класса.

If the function f can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n). For example,
f(n)=9log n+5log^4 n+3n^2+2n^3=O(n^3) as n->inf.
научитесь писать O(n/2)

Правильно писати O(n).

это то же самое O(n*63+sqrt(n)-283)

А это тебе нужно уже математику подучить.
Эта формула не даст линейный график, там квадратный корень есть ...

Эти формулы сокращаются.
1. O(n*63+sqrt(n)-283)
2. Отбрасываются константы: O(n+sqrt(n))
3. Так как плюс, оставляем наибольшее: О(n)

А потом уже и график можно строить.
Естественно они дают просто общее представление как работает алгоритм, без деталей, например, что есть какой-то множитель 10^50, который отбросили, потому что константа.

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

Спасибо, посмеялся. График не линейный. Константы действительно можно отбросить, но корень или логарифм никуда не отбрасывается. Он влияет на то что время работы алгоритмы растет не линейно а значит это не O(n), потому что на графике это не прямая линия

на то что время работы алгоритмы растет не линейно а значит это не O(n), потому что на графике это не прямая линия

docs.google.com/...​rlLLczyQ/edit?usp=sharing

Выглядит как прямая линия.

И тем не менее это не прямая. Подвох в масштабе. Возьми N как 1, 2, 3 и тд

И тем не менее это не прямая. Подвох в масштабе. Возьми N как 1, 2, 3 и тд

Приложи линейку к экрану и покажи где там не прямая.

Неодинаковые дельты между вершинами тебе о чем то говорят ?
63.19626157
63.18267581
63.17157288
63.16227766

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

я привык к точным наукам.

Если любишь точные науки, то перестань позориться и писать ерунду типа

Возьми N как 1, 2, 3 и тд
63.19626157
63.18267581
63.17157288
63.16227766

Открой en.wikipedia.org/wiki/Big_O_notation

Дочитай до

we are interested in the growth rate as the variable x goes to infinity

In typical usage the O notation is asymptotical, that is, it refers to very large x

the contribution of the terms that grow «most quickly» will eventually make the other ones irrelevant

посмотри примеры, которые там приводят и прозрей.

Это долбаный text book, все это было написано в позапрошлом столетии, здесь нет места для интерпретации, как бы тебе этого не хотелось.

Если ты пойдешь на собеседование и начнешь нести такую ерунду, то ты никого не впечатлишь своим богатым внутренним миром, только получишь заметку в фидбеке «Candidate was not able to correctly identify time and space complexity.»

Ты мне только что рассказывал что O(k) = O(1). Потомучто кеш процессора. Успокойся уже. Такую формулировку к тебе можно применить. Лучше операционку дописал бы и процессор свой.

Ты мне только что рассказывал что O(k) = O(1). Потомучто кеш процессора. Успокойся уже. Такую формулировку к тебе можно применить. Лучше операционку дописал бы и процессор свой.

Цитирую что я тебе доказывал:

k — константа, следовательно, O(k) == O(1)

Prove me wrong. Конкретно с фактами и ссылками на авторитетные источники и без своей отсебятины.

Да какие пруфы. Ты начал делать волны что твоя хештаблица работает железно О(1), тебе изначально сказали что это возможно только в особом случае с сильной привязкой к природе ключей и количеству данных. Дальше ты начал нести ахинею что если бакет влезет в линию Кеша проца то типа О(1) == О(к) где к это количество элементов в бакете, на что тебе ответили что ты несёшь бред. Скучно. Если тролишь придумай что-то интересней

Мне не нужно пересказывать историю.

Повторяю:

k — константа, следовательно, O(k) == O(1)

Согласен или нет? Если нет, то приведи доказательство своей точки зрения.

Я на глупые манипуляции не отвечаю. Пузырек работает 1 час на моих данных. 1 час это константа. Там где меньше чем час я добавил Sleep. Значит пузырек работает за О(1). Согласен или нет ?

Множитель 63 получается без проблем отбросить, а n + sqrt(n) уже нельзя :-)? Типа n + sqrt(n) больше чем 63 * n? И «нелинейный».

Первый алгоритм при передаче массива на 100 элементов вынужден пробежать по всем 100 элементам. Второй только по 50. У одного будет сложность условно O(n) у второго O(n/2).

У обох буде O(n) тому що кількість ітерацій залежить від розміру вхідних наборів даних лінійно.

Мы можем сказать что оба алгоритма имеют линейную сложность O(x), но если хотим сказать более точно, говорим O(n) и O(n/2) где N количество элементов

Так говорят только безграмотные кодерки, которые прогуляли уроки computer science.

Читай и просвещяйся: en.wikipedia.org/wiki/Big_O_notation

Про хештаблицы кстате тоже говорят что работают за О(1), а по факту их worst case тоже O(n)

Зависит от хеш таблицы. Есть реализации, у которых даже в худшем случае O(1)

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

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

Не обязательно, есть куча вариантов свести до O(1) с минимальными ограничениями.

Даже в «обычной» хеш таблице можно свести worst case to O(log n), если сильно нужно.

Не обязательно, есть куча вариантов свести до O(1) с минимальными ограничениями.

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

Даже в «обычной» хеш таблице можно свести worst case to O(log n), если сильно нужно.

этим никто не занимается, потому что хештаблица в которой много коллизий плохая хештаблица, а точней ее хешфункция.

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

Прикинь, есть реализации хеш таблиц, которые заточены не для общего случая, а для конкретного случая.

А где можно про это почитать? O(1) даже в worst case — это как-то too good to be true.

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

Ну, куда уж мне до вашего дана использовать О-нотацию, даже не зная её :)

А где можно про это почитать? O(1) даже в worst case — это как-то too good to be true.

Например, банально: ограничить размер бакета (обычно фиксируют, чтоб он полностью помещался на кеш линию).

Cuckoo hash table развивает эту идею дальше, позволяя добиться очень высокого load factor, сохраняя lookup O(1), но insert будет страдать, load factor высокий.

Например, банально: ограничить размер бакета (обычно фиксируют, чтоб он полностью помещался на кеш линию).

Опять несешь чушь. Сложность алгоритмов не имеет отношения к кешам процессора. Если сканить прийдется несколько элементов в бакете, значит это точно больше O(1)

Если сканить прийдется несколько элементов в бакете, значит это точно больше O(1)

Более конкретно. Больше O(1) это сколько?

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

Сортировка пузырьком сортирует за О(1) где константа это 100 лет или меньше. Смекаешь ? Что за бред ты несешь.
Во-первых ты не можешь ограничить количество элементов в бакете. Это невозможно в общем случае. Если ты закачаешь 1К ключей коллизий может и не быть, при 1М их будут сотни, при 1G сотни тысяч. А значит и время не константно, оно поплывет в сторону увеличения.

Короче это так не работает, я спать.

Во-первых ты не можешь ограничить количество элементов в бакете

Могу. У меня в продакшене хеш таблицы, в которых количество элементов в бакете ограничено.

Это невозможно в общем случае.

Спасибо, кэп, про общий случай речь не идет.

Если ты закачаешь 1К ключей коллизий может и не быть, при 1М их будут сотни, при 1G сотни тысяч. А значит и время не константно, оно поплывет в сторону увеличения.

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

Во-первых ты не можешь ограничить количество элементов в бакете
Могу. У меня в продакшене хеш таблицы, в которых количество элементов в бакете ограничено.

Это невозможно в общем случае.
Спасибо, кэп, про общий случай речь не идет.

Если ты закачаешь 1К ключей коллизий может и не быть, при 1М их будут сотни, при 1G сотни тысяч. А значит и время не константно, оно поплывет в сторону увеличения.
Есть формулы, которые позволяют рассчитать потенциальное количество коллизий, и есть способы ими управлять в ту или иную сторону. Умные люди делают это за большие $$$$.

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

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

Теперь еще раз внимательно читаем:

Например, банально: ограничить размер бакета

... O(k) где k количество элементов в бакете ..

k — константа, следовательно, O(k) == O(1)

Смекаешь?

За LINQ метод Count сорі, протупив. Я до нього звик просто. Формошльопер...

Разница между Count() и Length в этом случае, если не ошибаюсь ничтожна, если вообще есть.

Можливо. Але зайва бібліотека використана, це біда.

Там не зайва библиотека. Там весь код в муссор. Решительно непонятно какую задачу он вообще решает. Меня вообще удивляет, как у людей мозги иногда работают, что такую простую задачу они настолько витеевато и нелогично пытаются решить ? Неужели им потом не лень в этом говне ошибки ловить ?

Сидеть после работы писать изящный код в предвосхищении апплодисментов юзеров доу. Вот оказывается где счастье зарыто.) Тут бы отдохнуть, чтобы завтра с новыми силами грести.

Я его написал только потому что это 5 минут работы. Смотреть на код Вовчка, и подозреваю в скором Головатого это будет суцильна боль. Головатый правда трошки умнее Вовчка, свой «код» не показывает, понимает чем закончится =) Лил

Чувак, якщо у тебе виникає

суцильна боль

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

Путаешь, перебор и слияние. Разные вещи. Слияние сортированных массивов — классика жанра в разных сортировках типа Шела, типа джоинов в базах данных, обхода курсором больших обьемов данных без их копирования и тд. А ты думал в гугле хотят твою вундервафлю с линкью и мath библиотеками в НЕ математической задаче увидеть ?

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

А ты думал в гугле хотят твою вундервафлю с линкью и мath библиотеками в НЕ математической задаче увидеть ?

Я в гугл не цілюся. Ще рано.

Не можна так реготати — сусідів через дорогу лякаю.

Яку задачу по твоєму я намагаюся розв’язати? Напиши своїми словами, щоб було зрозуміло для якої задачі твій код.

Мой код решает твою задачу. Причем делает акцент на двух вещах.
1. Решает твою задачу максимально просто и элегантно, за время в среднем меньшее O(N)
2. Использует приемы которые крайне хорошо ложатся на архитектуру ЭВМ, в частности на конвеер предсказания комманд в процессоре и последовательный доступ к памяти. Причем второе учитывает как и работу с памятью в кешах процессора Л1\Л2 так и памятью к которой доступ через шпиндельные головки винчестверов.

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

Мой код решает твою задачу.

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

1. Решает твою задачу максимально просто и элегантно, за время в среднем меньшее O(N)

Таких умов не було, ти їх вигадав.

2. Использует приемы которые крайне хорошо ложатся на архитектуру ЭВМ,

Яких саме ЕВМ? Ти вже й архітектуру на якій буде працювати цей код за мене знаєш?

Другими словами, это

«Ето» не те що я просив написати, якби я звісно був би інтев’юером.

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

Яке «моє чудо»? Ти і код мій собі напевно вже вигадав. Ну покажи його тоді.

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

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

Я ничего не понял что ты написал. Даже по украински.

Короче этот алгоритм легко дорабатывается до меньше O(n). Суть в том что последовательно скипаем блоки которые можно легко скипнуть не сканируя полностью и в конце хвостик добиваем уже этим алгоритмом. Размер блока нужно взять примерно k/2 или меньше. Поскольку там работы на час, а не на 5 мин то мне лень писать, но алгоритм четко формализуется. По сути это эвристика к этому алгоритму, все достаточно просто и код будет таким же элегантным, ну немного сложнее

Пример скипанья.
Блоки 1 2 5 7 10 и 3, 7, 8 можно смержить не сканируя как блок размером в 7 начало 1 и конец 8 (поскольку один блок входит в другой). Другие кейсы нахлест влево, нахлест право, пересечение, что тоже легко мержится.

ПС Бинари серча там не надо, незачем.

ПС Бинари серча там не надо, незачем.

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

Звісно можна і інші способи знайти. Просто розказую той навколо якого побудував своє рішення.

Скажи мне, что в массивах нет дубликатов.

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

Покажи рішення, раз воно таке просте. Може ти і правда геній, а може теж з тих хто читає не те що написано.

func find(k: Int, in lhs: [Int], and rhs: [Int]) -> Int? {

    if lhs.count == 0 && rhs.count > k {
        return rhs[k]
    }

    if rhs.count == 0 && lhs.count > k {
        return lhs[k]
    }

    var l = 0
    var r = 0
    var curr: Int? = nil

    while l + r <= k {
        if lhs.count > l && rhs.count > r {
            
            if lhs[l] <= rhs[r] {
                curr = lhs[l]
                l += 1
            } else {
                curr = rhs[r]
                r += 1
            }
        } else if lhs.count > l {
            curr = lhs[l]
            l += 1
        } else if rhs.count > r {
            curr = rhs[r]
            r += 1
        } else {

            break
        }
    }

    return curr
}

вот вам код написанный на коленке за 10 минут

Ну все, зробив я його: gist.github.com/...​5184b210d98737b1cba7cd4b4

АПД на граничній вилітає. 10 хв пофікшу.

Блін, здаюсь. На даний момент дійшов лише до того що порівнює перший менший масив з початком другого допоки не знайдено таргет або не закінчився і потім уявно конкатенується другий і решта з таргет індексу туди вписується. Що є явно хибним, бо потрібні додаткові світчі назад в перший масив, і потім щоб в другий заглядало якщо щось. Важко мені це придумати не знаючи достатньо алгоритмів =) Це з бінарі сирчем, щоб задовільнити швидкість. І все норм працює допоки не треба світчитися назад в перший.

Так, там саме в тому щоб правильно міняти індекси і проблема. І треба враховувати що вони можуть вилізти вліво чи вправо з масивів. До того ж коли їх соваєш треба уникати нескінченого цикли.
Складність не придумати алгоритм, а написати код — всі оці спеціальні випадки по суті і складають 90% коду.

Складність не придумати алгоритм, а написати код — всі оці спеціальні випадки по суті і складають 90% коду.

Код можно не писать. Есть декларативные языки. И в моем языке достаточно сформулировать подписки на события определяющие порядок в массиве результате. машина все сделает сама.

Як це приблизно буде виглядати? Щось типу Prolog?

А сколько времени оно будет работать? Какая сложность в О-нотации?

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

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

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

Так, для мене це була складна задача щоб розв’язати її на інтерв’ю. І в цілому я вважаю цю задачу складною.

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

І так, цей код не ідеально майже напевно, і його можна покращити.

Але все це другорядне — спочатку треба зрозуміти саму задачу.

Задачу я зрозумив, она не сложная. Код мой есть, да там не хватает чуть чуть чтобы формально опустится ниже О(n) нужна небольшая эвристика, скипать блоки без скана, но алгоритм я расписал. Чтобы это сделать нужен час времени, мне его жаль, 5 мин мог потратить на базовое решение.

Код мой есть, да там не хватает чуть чуть

Це те саме що кода нема. Тому що задача не написати POC, а знайти рішення яке задовольняє умовам.

Чтобы это сделать нужен час времени

Якраз довжиною в одне інтерв’ю. Але ти провів 45 хвилин намагаючись переконати мене, що насправді мені потрібно рішення для іншої задачі.

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

Можно пример чистого кода на ООП, который бы прошел тесты на leetcode.com/...​ian-of-two-sorted-arrays ?

Можно, но потом. До своего алгоритма который я уже выкатил могу дописать копеечную эвристику с которой время опустится ниже O(n). Но принципиально подожду ваш обещанный код, поскольку пока что один трёп.

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

Я хочу увидеть чистое решение на ООП.

Код не будет тривиальны ми чистым

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

Эта задача не простая. Даже так: возможно, для кого-то она простая, но точно не для вас, потому что вы её даже не понимаете.

Специальная олимпиада ещё не закончилась? Вот мой подход к шпагату, метод FindIndexByValue: gist.github.com/...​17771fa4ec5c8b169017eef41

Прощу прощения за возможно неровный почерк, я не настоящий шарпист.

Охрана, отмена. Я тоже не прочитал нормально задание.

Увлекательная дискуссия получилась. Только вот кажется, что binary search подошел бы для поиска индекса по значению. А при поиске значения по индексу, все-таки, решение будет линейное.

А при поиске значения по индексу, все-таки, решение будет линейное.

Не линейное. Аналогичная задача на литкоде, там выложены решения, которые «быстрее O(N)»
leetcode.com/...​ian-of-two-sorted-arrays

О, клас, моє рішення проходить всі тести. Це при тому що я свою функцію викликаю двічі бо ліньки модифікувати код.

Success
Details
Runtime: 40 ms, faster than 6.28% of C++ online submissions for Median of Two Sorted Arrays.
Memory Usage: 7.3 MB, less than 100.00% of C++ online submissions for Median of Two Sorted Arrays.

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

Мой второй подход к снаряду: gist.github.com/...​1c4da8e2a2b6d08fc151d02c3

Работает, и насколько я могу судить, за O(log n).

Херасє коду. У мене набагато менше і теж працює

за O(log n)

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

в ній трохи більше магії

Магия рулит?

В олимпиадных задачках — рулит и педалит. Это же не настоящее программирование.

Плюс за серйозне тестування. Застосував у себе і зламалося після другого довгого арею =(

АПД, вже пофіксив. Ще раз дякую за тести!

Дауж, код чуток получше чем у Вовчка, но в целом если такое попадет на ревью, то сходу получит ну пять комментариев минимум

1. Во-первых чего оно падает при определенных наборах данных с IndexOutOfRange ?
2. Что за наименование даже не переменных, а функций в стиле «e» и «p». Кодинг от Элочки-Людоедки однако.
3. Что за наименования переменных аля int minCount1 int maxCount1. А куда minCount2 подевал ? А если его нет то зачем приставка 1 ?
4. Что за int minCount1 = Math.Max(0, index — array2.Length); Почему array2 а не array1 ? Нет эстетики.
5. Почему код пытается делать какието циклы, в случае очевидных решений типа [1,2] [3,4]

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

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

gist.github.com/...​171b1ffca52765bc2c9f5229d

Ну чуваки, зробив я. Тепер точно. Потративши ще декілька годин але вже на свіжішу голову. Усі валю протестовані, індекси від 0 до 9, усі виключення виловлені. Можете у себе запустити в айдішці і перевірити. Коментарі до коду будуть завтра. А поки що накидайте мені лайків, і скажіть яка тут складність, а то я не експерт =(.

Додай різних тестів як запропоновано в dou.ua/...​ign=reply-comment#1838221. Бо дуже важко вгадати на якій комбінації даних та індексів подібний код може зламатися.

Виглядає наче норм з першого погляду.

Так. Добре б додати більше різних даних для тестування. Хоча я й так в масивах вписав такі значення, щоб декілька переходів було в обробці. В будь-якому разі алгоритм вірний. Якщо і вистрілить якийсь едж кейс(а вистрілювало багато), то не прийдеться заново придумовувати, а лише підфіксити. ІМХО.

ibb.co/0szS1tB

От блін. Злітає при даному тесті:

array2 = new int[] { 0, 0, 1, 3, 4, 4, 7, 7, 10, 10, 11, 11, 11, 12, 13, 16, 16 };
array1 = new int[] { 2, 2, 2, 4, 5, 5, 6, 7, 8, 9, 9, 10, 10, 10, 11, 13, 13, 15, 16, 16, 17, 17, 18, 18, 18, 18, 20, 20, 20, 21, 21, 22, 24, 26, 26, 27, 29, 32, 33, 35, 36, 42, 42 };

і видає дублікати. Знову я злився. Але вже близько йопта.

Я так розумію, код ще недороблений (я його у себе запустив, і на деяких тестах він вилітає), і я його не повністю осягнув, але таке питання — чи може у вас бути вироджений випадок, коли на ітераціях зовнішнього циклу array1Index та array2Index будуть зростати на 1 за ітерацію? Бо якщо так, тоді у worst case (підкреслюю — у worst case, в задачі не написано, чи повинні ми бути швидше лінійного пошуку у worst case чи average case) це не швидше за лінійний пошук, це O(k) чи навіть O(k * log n+m) (бо в кожній ітерації зовнішнього циклу ви робите ще log n або log m ітерацій в циклі BinarySearchIndexForLessOrEqual). Дисклеймер — я теж не експерт.

Я так розумію, код ще недороблений

Нажаль так =(

чи може у вас бути вироджений випадок, коли на ітераціях зовнішнього циклу array1Index та array2Index будуть зростати на 1 за ітерацію?

От це добре підмічено. І воно не має так бути. Піду шукати як виправити. Тому що При пошуку індексу 9 чомусь робить 9 ітерацій, а має робити 5. Через це може й вилітати при інших тестах.

я його не повністю осягнув

Якби ж я його повністю осягнув)))

П.С. на «ти» давай)

Та шоб йому =( Схоже я ніколи і не дороблю його. А може дороблю, але завтра. Мені соромно. Але вже не крешить, це ж майже як і виконати поставлене завдання!

Пам’ять алоціювати чи модифікувати вхідні параметри не можна.

Задача не має рішення при таких умовах.

Вже більше одного рішення написали з дотриманням цих умов.

Всі ці рішення виділяють пам’ять. Умова не дотримується.

Память под переменные-то выделять можно. Суть в том, чтобы память не зависила от n.

Пам’ять алоціювати чи модифікувати вхідні параметри не можна.

Думаю, що задача описана доволі чітко.

Дякую, але ваша компанія й так не підходила мені.

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

Стек магічним чином з’являється? Без алокації?

Насправді правильно казати O(1) по пам’яті.

На момент початку роботи функції в практично усіх сучасних мовах програмування стек вже алоковано. Або нема стеку — нема і функцій (це як варіант «нема ніжок — нема і варення»). Це якщо з такої точки зору легше зрозуміти.

Опять-таки, что есть стек? Initialized Low-level? Дык он кроме яну (asm, C да остальное с габридным подходом, если вообще есть) ниде не доступен. Да и маниуляция с ним ни для чего кроме sp:ip не должны производиться. Да и то, всё это не имеет отношения к нормальному обособленному кодингу

Виділяти змінні ≠ виділяти пам’ять. Це, звісно, залежить від мови програмування/енвайронменту, але в C у програми після запуску є вже виділена сторінка зі стеком, і якщо просто робити нові змінні на стеку, то нова пам‘ять не виділяється.

ну зазвичай після запуску тільки кусок віртуальної пам’яті розмічається під стек, а фізична пам’ять таки виділяється при першому зверненні

Виділяти змінні ≠ виділяти пам’ять
вже виділена сторінка зі стеком

Одне одному суперечить.

Доучани! Тепер то я не лише написав вірний алгоритм, а ще й коментував в процесі(що сильно допомогло самому зрозуміти що пишу).

gist.github.com/...​171b1ffca52765bc2c9f5229d

Закидайте мене помідорами, якщо цей алгоритм зламається хоча б на одному тесті. І так! Тепер ітерацій в циклі рівно K!

Насправді можливо! при одинакових трохи більше К, бо тут:

if (secondArrayHasNext) targetForBinarySearch = array1UndergoingSearch ? array2[array2Index + 1] : array1[array1Index + 1];

Наче треба шукати в ідеалі не +1 а +н де н це кількість подібних елементів до останнього теперішнього, але я вже конкретно підзаїпався, і головне що воно працює. От в тому тесті що в репо, робить 13 ітерацій для останнього індексу. Хз кароче, не можу сказати на даний момент, іду поїм і відпочину. Це триндець такі таски рішати. Краще в грузчики!

Ну цей рядом можна заапдейтити для пошуку індексу н звісно. Тоді буде залізне К. Ой!!! Так воно вже К один хрін. Якщо К це індекс то там більше К не буде точно.

Цей комент туфта. Ітерацій <= k. Потім в кожній ітерації(або в кожній мінус одна) є бінарісирч, який являється O(log n). В результаті складність виходить O(k log n)? Навіть в тесті на купу чисел в масивах що я в репо закинув, останній індекс береться за 13 ітерацій, а це точно швидше O(n). Завдання виконане, начальнике. Якщо звісно хтось не завалить це якимось тестом. Не думаю що завалить, бо тепер кожен рядок розумів що робить.

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

Піду краще за бабло порішаю як одну сраку інтегрувати в іншу

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

На двох шістандцятках(валю) зупиняється, і далі не рахує.А дві 16 це край array2. Може якось звязано з кінцем арею ПЛЮС одинаковими числами в другому ареї.

О, та тут просто свято якесь, — я теж хочу причаститись :)

Код:

def get_elem(l1, l2, idx):
  clamp = lambda l, i: l[i-1] if 0 < i <= len(l) else float(("inf", "-inf")[i < 1])
  f = lambda i: clamp(l1, i) > clamp(l2, idx-i+1)
  g = lambda i: max(clamp(l1, i), clamp(l2, idx-i+1))
  ind = [idx - min(idx+1, len(l2)), min(idx+1, len(l1)) + 1]
  flg = f(ind[1])

  while ind[1] - ind[0] > 1.0:
    ind[f(round((ind[1] + ind[0]) / 2.0)) == flg] = round((ind[1] + ind[0]) / 2.0)

  return min(g(ind[0]), g(ind[1]))

Використання:

L1 = [1,2,3,17]
L2 = [4,5,6,22]
get_elem(L1, L2, 3)

Тестики:

def test_lists(L1, L2):
  my_list = [get_elem(L1, L2, x) for x in range(len(L1) + len(L2))]
  L = L1 + L2; L.sort()
  return my_list == L

# manual tests
assert test_lists([1,2,3], [4,5,6])
assert test_lists([1,2,3,22,45], [4,5,6])
assert test_lists([], [4,5,6])
assert test_lists([1,2,3], [])
assert test_lists([4,5,6],[1,2,3])
assert test_lists([4,5,6], [1,2,3,22,45])
assert test_lists([1,3,5,7], [2,4,6,8])
assert test_lists([1,3,3,3,3,3,7], [2,4,4,4,4,6,8])
assert test_lists([3,3,3,3,3], [4,4,4,4])

# random tests
import random
for _ in range(1000):
  start, stop, limit = -20, 20, 50
  L1 = [random.randint(Start, Stop) for iter in range(limit)]; L1.sort()
  L2 = [random.randint(Start, Stop) for iter in range(limit)]; L2.sort()
  assert test_lists(L1, L2), "test failed"


print("ALL TESTS PASSED")

P.S. Насправді я не дуже впевнений, що воно працює, але тести проходять, то може воно й ок.

P.S. Насправді я не дуже впевнений, що воно працює, але тести проходять, то може воно й ок.

Можна спробувати цей клятий тест ще:

{ 0, 0, 1, 3, 4, 4, 7, 7, 10, 10, 11, 11, 11, 12, 13, 16, 16 }
{ 2, 2, 2, 4, 5, 5, 6, 7, 8, 9, 9, 10, 10, 10, 11, 13, 13, 15, 16, 16, 17, 17, 18, 18, 18, 18, 20, 20, 20, 21, 21, 22, 24, 26, 26, 27, 29, 32, 33, 35, 36, 42, 42 }

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

П.С. твій код крутий, такий лаконічний. Ось де матеметика потрібна.

дякую за тест! спробував — проходить

Трошки вище наведено лінк на майже цю саму задачу на leetcode, можна спробувати їх тести.

Хитрість в тому що замість int використувується float, а як індекси виходять за межі то значення приймається відповідно -inf/+inf?

Так, цим я суттєво спростив собі життя :) Я зводив задачу до розв’язку рівняння F(x)=0 і цим гарантував собі, що така точка завжди існує.

Мне кажеться, стоит сделать паузу, и попросить автора ответить на вопрос, справедливо ли, что O(k) < O(n) в контексте сугубо данной задачи? :)

При певних значення k.

Як би правильно було сформувати умову іншим способом? Якщо написати одразу O(log(n+m)) то це вже половина рішення.

Ну вот. Это называется bias. Видишь ли, тут только носорог не догадался про древовидный поиск, не стоит сотый раз на этом фокусироваться. Скажи лучше, why the earth ты в оценке не оперируешь k? Сводить k к n или m не есть корректно. Понимаешь почему?

Сводить k к n или m не есть корректно. Понимаешь почему?

Ні, поясни чому.

Ок, поясню. Прости, но придётся делать case разбивку, иначе мне самому сложно будет, я увы не гуру:

1. k << min(n,m): алгоритмы O(k) сильно выгоднее 
чем O(f(m,n)), стало быть не сравнимо на практике 
(при теоретической линейой эквивалентонсти 
О-большого для обоих)
2. k ~= min(n,m) Справедливо полагать O(k) ~ O(f(m,n)) 
при условии что n~=m

Зізнаюся — не зрозумів пояснення. Як на мене такі аргументи можна навести до будь-якого алгоритму перебором і сказати що він тепер O(k), а не O(n). Що я не так розумію?

без основания нельзя свести о(n) к. о(k)

Интересная задачка, в голове придумал решение. Может на досуге напишу код, закину

Ога, загрузив спін-оффом leetcode.com/...​ian-of-two-sorted-arrays =) Вона є першою серед хард на літкоді. Мені здається моє рішення запросто можна адаптувати для індексу k, от тільки воно на 140 строк, тому мабуть не буду його краще показувати %) Але може там у рішенні є більш притомний код.

моє рішення запросто можна адаптувати для індексу k, от тільки воно на 140 строк

В моєму десь 80 (gist.github.com/...​1c5077991e1a93e8d95cb74c5), але для подібних алгоритмів особливо я би надав перевагу такому коду який легше читати, ніж компактному заради компактності.

Короче фп***у. Попробовал, 3 часа убито, и я так и не смог сформулировать по каким критериям решать куда двигаться при бинарном поиске. От балды пытался пофиксить код ,чтоб проходили примеры в итоге старые примеры начали ломаться. На собеседовании я бы не осилил.

Скорее всего, поиск k-ого элемента пошел бы немного проще, так как с медианой еще разная логика в зависимости от того, четное или нечетное ко-во элементов.

До куда ты смог дойти во время собеседования? Нужны ли были подсказки?

Скорее всего, поиск k-ого элемента пошел бы немного проще, так как с медианой еще разная логика в зависимости от того, четное или нечетное ко-во элементов.

Задача по сути и есть — написать поиск k-ого. Если четное найти сначала n/2, потом n/2+1, сложить и поделить на два, если нечетное — найти только ceil(n/2) и вернуть.

Задача по сути и есть — написать поиск k-ого

Я саме такий код і залив на leetcode і він швидше лише 6% правильних рішень. Виходить не так швидко якщо знайти медіану з першого заходу. Почав був правити алгоритм, але коли побачив що з моїх 80 рядків вийде усі 300 здався :)

зашел в свои submissions — и правда. 30ms у моего против топовых на 2-3ms с бинарным поиском, но поиск правильно на интервью точно бы не осилил написать.
Забавно что когда кликнул посмотреть что там на 3ms — вообще nlogn submission показало:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] arr = new int[nums1.length + nums2.length];
System.arraycopy(nums1, 0, arr, 0, nums1.length);
System.arraycopy(nums2, 0, arr, nums1.length, nums2.length);
Arrays.sort(arr);
double med = 0.0;
int length = arr.length;
if(length % 2 == 0){//even
int middle = length/2;
int middle1 = arr[middle-1];
int middle2 = arr[middle];
med = ((double)(middle1 + middle2))/2;
}else{//odd
int val = length/2;
med = (double)(arr[val]);
}
return med;
}

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

І друге — у них там надзвичайно маленькі вхідні масиви, та і тестів мало. Як подати на вхід кілька Гб даних то вже не так все добре буде.

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

попробуйте пересабмитить) Не знаю, как с С++ кодом, но с джавой показатели сильно гуляют.
Особенно забавно, когда объявил пару локальных переменных типа int i,j и показатели по памяти сразу на дне.

До куда ты смог дойти во время собеседования?

Дійшов до «математичного» рішення про i+j==k і що після порівняння елементів індекси треба відповідно рухати вліво/вправо. Написав простий код без усіх необхідних перевірок виходів за межі масиву (які в моєму фінальному рішення займають 80% обсягу усього коду). Рішення інтерв’юера задовольнило і ми провели залишок часу обговорюючи усі спеціальні випадки.

Нужны ли были подсказки?

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

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

Дійшов до «математичного» рішення про i+j==k і що після порівняння елементів індекси треба відповідно рухати вліво/вправо.

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

i+j = k я допер относительно быстро, но через час начал сомневаться в этом выводе, отбросил, и еще час убил непонятно над чем, в итоге вернулся к i+j = k.

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

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

Признаться, что пишу на java.

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

У меня было приблизительно так с родными youtu.be/tVl2fkUY5PI?t=74

зробити так щоб всім було добре

Impossible. Тому треба робити так, щоб добре було собі!

завдання було заставити всіх юзати стайлдгайд (design style guide), який ніхто не хотів юзати, а і ще щоб його оновлювали з своїми фічами теж. Без підтримки керівництва, якому було на це посрати, ну окрім мого менеджера, який це завдання придумав — результат бьорн аут і звільнення.

стайдгайд

Англійською можна? Щоб я і ще дехто зрозуміли що це.

А всем всегда на все по ***, главное чтобы часы были вписаны и задачи закрывались

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

Зато команда вам безмерно благодарна, я уверен. За то, что уволились.

дуже жаль що у вас видався поганий день, удачі

Хмм, занимательный вывод, я бы спросил на чем он основан, но мне не очень интересно.

А вообще разработчики они такие, очень чувствительные мальчики Томми. Навязывать им какие-то coding standards говорит об полном непонимании тонкой душевной организации. Или полном игнорировании срачей на подобии tabs vs. spaces.

Навязывать им какие-то coding standards говорит об полном непонимании тонкой душевной организации.

О чём это вы? Все coding standards в топку, или что?

Я о том, что навязывать и заставлять — это такой себе подход, особенно с девелоперами. А тем более если у команды уже был какой-то coding standard и их пытались заставить писать в новом, в котором никто писать не хотел.

Вы за ласковое уговаривание? «Ну программистик, ну пожалуйста, ставь фигурные скобки на новой строке»? :)

В репу не должен попадать код, который нарушает стандарты уже существующего окружающего его кода и текущий coding standard (и если они конфликтуют, существующий код выигрывает), крапка. Какими средствами это будет достигнуто — вопрос уже второй.

Играть в игра в инете ты меньше не пробовал? Оно работает

Пробовал, в результате постарел на 5 лет. Теперь больше не буду.

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

А куда ставить скобочку должно быть сконфигурено в IDE.

В моїй конторі зараз для коду запускається аналізатор і не дає комітити зміни якщо порушено правила. Можна фіксати вручну, а можна запустити авто-форматери для усіх мов якими ведеться розробка.

Вообще считаю контр-продуктивным вводить стили кодирования, которые нельзя пофиксить автоматическими инструментами. В адекватных IDE вообще можно автоматически запускать code-cleanup перед коммитом еще до всех проверок на сервере.

Встретил употребление зависимых типов (шейплес) в продакшене (с багой которую нужно было както пофиксить) — мозг тогда сильно помутнел...

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

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

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

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

Анализ — НЕ синтез.
На какие простые подзадачи не разбивай — в прод то должны пойти — все эти подзадачи, в рамках той самой одной задачи — сложной.

Хотя, сложнее, конечно добиться командной работы :) С кодом, бизнес логикой, намного проще.

Сложность там в том чтобы собрать все требования и не промахнуться с эстимейтом

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

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

И сложность внезапно пропадет.

работа с неполной информаций с ограничением по времени — никуда не пропадет.

будешь не спеша пилить

то так и останешься «вечным джуном», еще и крайним — первым кандидатом на увольнение :)

Но, если не будешь спорить и бузить,

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

то так и останешься «вечным джуном», еще и крайним — первым кандидатом на увольнение :)

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

С остальным ты таки еще джун. Мало пороха понюхал. Потихоньку научишься.

З.Ы. Тут в ленте была статейка на эту тему от одного из топов крупной какой-то галеры. Его слова «Он был не сильным программистом, он был хитрым программистом» и стал топом. А вот сильные таки до сих пор кодят в уголках и молятся богу, чтобы их не выкинули на мороз, когда хитрому они наскучат.

Мало пороха понюхал.

уж лет 25 как нюхаю :)

Потихоньку научишься.

спасибо, обнадежили.

А ты не будь джуном

да как бы давно не.

Он был не сильным программистом, он был хитрым программистом" и стал топом

естественно.
решать реально сложные задачи — это не битики в задачках с литкода двигать.

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

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

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

а в разработке ПО — нужно быть хитрым, ленивым, предусмотрительным, и т.п.

Во. Я об этом. И если ты вот это всё, то описанная тобой задача перестает быть сложной и становится типичной.

описанная тобой задача перестает быть сложной и становится типичной

типичность не является синонимом простоты

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

то же и здесь.

Во. Я об этом

ты не об этом.
знание правил игры в шахматы не делает простым решение завернутого этюда.
а тем более победу в соревновании.

а правила Го — еще проще шахматных. Скачай на смарт программку, их полно, порешай типичные задачки, простые правила — значит же и задачи простые?

Одним из простых критериев сложности в разработке ПО является — количество человекочасов для реализации.

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

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

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

У тебя перекос в другую сторону от критикуемого.

ну, так как мне было

ты таки еще джун. Мало пороха понюхал. Потихоньку научишься.

так что у меня все впереди — выровняю свои перекосы :)

так что у меня все впереди — выровняю свои перекосы :)

Даже немного завидую. Удачи!

За допомогою циркуля та лінійки знайти діаметр кулі.

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

Проткнуть шарик циркулем. Дальше при использовании линейки задача сводится к уже известным.

Хорошая задача с легким налётом инженерной графики

Брать 0.7 или литр.
(но решение быстро находится)

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

Самая сложная задача, которую приходилось решать:

Ехать или не ехать, вот в чём вопрос. Достойно ль
Смиряться под ударами судьбы,
Иль надо оказать сопротивленье
И в смертной схватке с целым морем бед
Покончить с ними?

справедливости ради, у большинства и тут находится быстрый и несложный ответ: пох-нах :)

... спизив сраный трактор

Вот это была-таки самая сложная задача (вернее — две): 1) как взять авто в кредит в уе официально, когда долларовых кредитов уже не было, а гривневые азиров ФОПам не давал. 2) как взять ипотеку без первого взноса, если есть запрет нацбанка на ипотеки с 0% первым взносом, а кредитов физлицам-иностранцам без истории нет вообще.
Первая была решена успешно, а последняя обломалась в самом конце на местном поручителе.
Ну, а сократить время запроса в базу в 5 раз или отучить программу от жадности — это ерунда.

Какой самый сложный трюк на скейте?

Жить отдельно от родителей.

Самый сложный трюк — чтобы родители от тебя съехали.
Не на кладбище, нет.

Господь с Вами, в свою квартиру, в многоэтажном доме с жителями от 0 и старше.

как свалить из этого бантустана

написать калькулятор/компилятор на курсах (токены, стейт машина, «стек машина» и тд. по книге пурпурного дракона)

А я написал)) И даже просили пользоваться. Удобный оказался. Можно было несколько строчек выражений написать и сохранять и редактировать. Со скобками. Ну и по шагам и автоматически считать все выражения. Своего рода Эксель

То есть у всех прочитавших эту книгу такой же неиллюзорный шанс eбaнyтьcя на отличненько?

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

Компиляторы: принципы, технологии и инструменты

www.amazon.com/...​0?_encoding=UTF8&qid=&sr=

Кто-то может объяснить почему она стоит 150 баксов? О_О

Двигал компонент влево на 3 пикселя в Winforms...

Возьму на заметку
«Я твой компонент вокруг оси вращал»

Двигал компонент влево на 3 пикселя

На этих словах я вспомнил Pixel Perfect (для верстки страницы по макету пиксель в пиксель, геморрой еще тот). :-) В Winforms небось аналогичный геморрой))))

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

В чем смысл жизни.

Може не всі знають, але 42 — не випадкове число і насправді означає щось цілком конкретне.

скоріше
Harlock is the archetypical Romantic hero, a space pirate with an individualist philosophy of life. He is as noble as he is taciturn, rebellious, stoically fighting against totalitarian regimes, whether they be Earth-born or alien. In his own words, he „fight[s] for no one’s sake... only for something deep in [his] heart.” He does not fear death, and is sometimes seen wearing clothing with the number 42 on it. In Japanese culture, the number 42 is associated with death (the numbers, pronounced separately as „four two,” sound like the word "shini„—meaning „dying/death”).

Менял цвет иконки с синего на красный.

А с такими цветовыми условиями — задача вообще не решаема :(

Голосовой замок в 1995 году. Стоял на двери в лаборатории и впускал только своих по произнесению парольной фразы.
Треккер людей в магазинах по видео с камеры, причем для случая быстрых и не очень качественных моделей детекций недавно.

Еще чего-то много было за 25 лет — уже и не вспомню.

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

автоматический клининг задней части туловища коров

на изображении?

А вот некоторым таки лучше уроки делать, а не нести чушь здесь.

В пocтcoвкe фермерство остается во многом не автоматизированным.

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

Фермерство Финляндии, по сравнению с пocтcoвкoм, выглядит пришельческим:
1) youtu.be/ekP_L2k5FgI
2) youtu.be/q81w201PNUM

Для автоматизации оного нужен спрос на нее и деньги.
Пока сильно дешевле выгнать толпу на поле или на ферму, чем оплачивать покупку робота, не говоря уже о его разработке.
Вот когда тут зарплата колхозника сравниться с запрлатой колхозника в Финляндии (или Норвегии) тогда тут и будут покупать и юзать роботы, что в Финляндии уже производят.
Здесь вкладывать деньги в разработку подобных роботов не будут, потому что дешевле купить 10 роботов, чем потратить на их разработку в 100 раз больше.

Но есть одна ниша — сделать робота тут в 10 раз дешевле финского со стоимостью разработки в 10-20 раз меньше.

Ну может можешь заменить 10 на 3 (и считать в этих порядках).

А да инвесторы тут и в Штатах тоже отличаются на порядки. Здесь для инвестора 10000 баксов аналогичны 1000000 в штатах.

Вот только комплетуху ни интел, не нвидия не хотят продавать здесь в 10 раз дешевле, чем продают ее в шататах.

Там не совсем роботы, и даже не квадрокоптеры какие-нибудь.

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

У финов с этой автоматизацией и компьютеризацией не сократилась работа.
С этим всем у них увеличилась работа на качество продукции, в итоге. Иначе не смогут продать то, что там понавыращивали.

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

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

От автодоилок молоко за 2 дня скисает. А если руками — до недели стоит в холодильнике.

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

А если руками

Сам корову доил и вымя подмыл?

Если на собеседовании, то для данного числа uint64_t а, найти наименьшее число b, такое что b > a && pop_count(b) == pop_count(a). Максимально эффективно с точки зрения призводительности, без циклов и условий вообще . Функция pop_count возвращает число установленных в единицу бит.

Сдвинуть первую младшую единичку (в двоичном представлении) влево, у которой там стоит 0. Но без условий и циклов, чёт мне никакие xor|or с масками в голову не приходят.

А вообще странный вопрос для собеса.

Сдвинуть первую младшую единичку

алгоритм немного сложнее, но в целом согласен, вопрос для интервью странный

www.geeksforgeeks.org/...​-same-number-of-set-bits

алгоритм немного сложнее, но в целом согласен, вопрос для интервью странный

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

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

Обычно в битах, хотя возможно будут и исключения :)

Неа, кроме некоторых исключений в словах быстрее уже давно, если мы не говорим о 1848 и более ранних.

Вот таким образом народ и палится)

В чому? Я формошльоп, а не асемблер гуру. Хз що там нижче високорівневої мови програмування.

Я формошльоп

я тоже

В чому?

В отсутствии профильного ВО. Термины «слово», «двойное слово», «тетрада» на уровне подсознания вбиваются за годы учебы.

Аа. І як Вам ці знання знадобилися в формошльопстві? Якщо я захочу поглибитися — відкрию браузер і за хвилину знайду купу матеріалу різних форматів і на різний смак. Для цього необов’язково йти в український ВУЗ. Так само, як тепер я вчу css3, html5 і reactjs, щоб можна було фулстьочити. А ще Cloud computing сервіси, веб сервери, бази даних і купу іншого, що мені потрібно. Тепер зрівняємо ці знання з знаннями «програмістів», яких випускають українські навчальні заклади, серед яких абсолютна більшість людей не знаходить себе в високооплачуваній айті сфері і працює різноробочими за зп менше 1к дол. Тому ці виєпони псевдо елітарності залиште при собі.

Угу, расскажи разработчикам шахматных движков :) Хранить позицию в виде битовых масок — самый эффективный путь. Например, берём битовую маску наших пешек, сдвигаем на восемь, делаем & с маской всех свободных клеток и моментально получаем маску всех возможных ходом. И если замаскировать пешки на вертикали «a», сдвинуть на семь и сделать & с маской всех вражеских фигур плюс поле взятия на проходе мы сразу же получаем все взятия пешками влево.

Не говоря о том, что у нас позиции храняться в регистрах, и нам даже в память лезть не надо.

110 -> 1001 а не 1010
Ну и понимание битов там требуется немного больше xor/or/масок.

101100 -> 110001, как-то не получает просто заменить

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

Ну... 64 маски для нахождения первой единицы? Долго, быстрее выполнится a & (-a) Далее тоже неоптимально, нам надо установить первый нуль после последовательности единиц в единицу, а остальные сдвинуть вправо.

a & (-a)

а как получается что такой хак дает младшую единицу?

Надо понимать, что минус это инверсия всех бит плюс один. Например, 0001, инверсия 1110, плюс один 1111. Значит a & (-a) == a & (~a + 1). Далее xxxx1000, инверсия x́x́x́x́0111, плюс один x́x́x́x́1000, далее x & x́ = 0, получаем xxxx1000 & x́x́x́x́1000 == 00001000.

Никакой сложности не вижу. Удар в челюсть за потраченное время, можно сверху стулом приложить.

Объясняю почему: такие задачи в реальной работе ставятся раз в никогда. А если когда и попадается что подобное (разумеется сильно далёкое от того что дали на собесе), то оно делается с RTFM, несколько раз проверяется, включая возможные крайние условия, а потом ещё и тестами покрывается дабы потом какой оптимизатор делов не натворил. А сверху ещё 1.5-2 килознака комментов, почему так, зачем так надо, и что пробовали до этого и не сработало.

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

Чисто на логику — это в любом случае условие, и неважно через какую жопу его заменили, это всё равно достаточно тяжёлые с точки зрения современных процов операции сдвига бит. То есть производительность здесь будет чисто ТЕОРЕТИЧЕСКАЯ, на практике же придётя понимать, есть ли у тебя ПАРАЛЛЕЛЬНЫЙ процессор, или ПОСЛЕДОВАТЕЛЬНЫЙ конвейр тебя устроит. Результат будет сильно зависеть от того, на чём выполняется код.

Решение в лоб — просто добавлять 1 к a покуда условие не выполнится (вероятностно это самый быстрый вариант). Но тут же «без условий»... а значит через жопу. Ну и разумеется, как же вы без условий намерены ловить исключение переполнения??

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

Ой, какой смысл заменять шесть операторов С на шесть асемблерных команд?

Решение в лоб — просто добавлять 1 к a покуда условие не выполнится (вероятностно это самый быстрый вариант).

Ну... от (1 << 50) до (1 << 51) долго прибавлять придёться. Вообще, практический смысл такой. Есть 52 карты, по битику на карту. Мы хотим быстро перебрать все варианты флопа/тёрна/ривета (пять карт) итого 52 choose 5 = 2598960 вариантов. Ты же предлагаешь по единичке перебирать 2^52 = 4.5e+15...

Объясни, что не так с добавлением? Задача — получить НАИМЕНЬШЕЕ b, которое больше a (читай, начиная от a+1), число 1 в битах такое же.
С гарантией 50% это случится после первого же сложения, то есть ОДНА операция. Из оставшихся — гарантия 50% что после второго, и так далее. Задача поддаётся параллелизации.

Учитывая условие задачи, вангую что для сохранения числа бит нужны весьма специфические числа, например 100 + 1 = 101, не подходит, а 101 + 1 — подходит. Итого, атаковать нулевые биты НЕЛЬЗЯ поодиночке, нужно целиться только в единичные. Но так мы имеем УСЛОВИЕ, которые нельзя ставить. Следовательно, придётся использовать суррогаты условий.

Суть условия — просто вычитание, оно же по сути сложение. Потому единственное, почему в условии появился запрет — это задача не на производительность, а на ВЫЗУБРИВАНИЕ «правильного» ответа. Я больше скажу, если окажется тот же ответ, но по-разному записанный, в двух разных версиях той же книги — на собесе это окажется ПРОВАЛОМ, потому что собеседующие не понимают смысла задачи.

PS. Многие задачи кажутся логичными, когда знаешь правильный ответ. Но в реальном мире даже самые элементарные решения вырабатывались СТОЛЕТИЯМИ всем человечеством, а здесь требуют за 1-2 минуты на собеседовании. Соответственно, собес пройдёт кто? Студенты собственных курсов, где предупредили, что будут спрашивать. И тем самым оправдают ФИНАНСИРОВАНИЕ этих курсов — потому что со стороны не наймёшь, одни идиёты.

И казалось бы, причёт тут EPAM, нанимающий >98% штата ITшников со своих же курсов?

С гарантией 50% это случится после первого же сложения, то есть ОДНА операция. Из оставшихся — гарантия 50% что после второго, и так далее. Задача поддаётся параллелизации.

Во-первых, 25%. Только если число оканчивается на 01b мы получим правильный ответ. Во-вторых, мы получаем экспоненциальную сложность. Посчитай, сколько добавлений нам надо сделать, чтобы из 0x1000000000000000ull получить 0x2000000000000000ull.

мы получаем экспоненциальную сложность.

C той же экспоненциальной вероятностью, что она случится. Иначе говоря, задачу следует решать ТОЛЬКО ЕСЛИ она имеет сколь-либо реальную нагрузку. Например, это какая-то функция контроля и т.д. В этом случае анализ покажет, что добавлять надо не 1, 2, 3 и так далее, а только заранее предусмотренный набор констант и их комбинаций. Более того, так можно решать задачу грубой прикидкой с последующим уточнением — это экспоненциально снижает мат.ожидание, вплоть до 1 операции если это может быть сделано в параллель.

В данном случае, повторюсь, ЗАДАЧУ ПОДОГНАЛИ под красивое решение. С тем же успехом можно на собесе мерять письку, заранее зная кого хочешь принять и сколько у него и при каких условиях. Прям золушка современности.

Как результат — ПОИСК СОТРУДНИКА стал задачей с экспоненциальной сложностью. Хотя задача решается с обратной экспонентой вероятности: ЕСЛИ такая задача попадётся в реальности [с мат.ожиданием раз в миллион человеко-лет], можно найти 1 раз эксперта, который её решит за вменяемую цену, а то и бесплатно.

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

Не слышал о таком в реале.
Правило 34 доказывает, что его не существует.

5 последних лет на ДОУ тут о нем рассказывали.

Правило 34: обо всём есть прон.

Соответственно, если прона нет — этого не существует. Обратное утверждение не есть истинно, прон может быть и о несуществующих вещах, если они кому-то зашли как фантастика. Но вот о гендерном балансе прона нет :)

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

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

вспомнилась история, еще с 70ых, как один молодой да «крутой бывший математик» пришел в контору которая пишет ПО для эмбедеда.
глянул код расчета косинусов-синусов, ахнул, и ловко переписал.

А лид глянул, и так лукаво:
ну, красивее конечно чем наши таблицы коэфов, по которым происходит мудреный поиск...
но понимаешь, это ПО часто будет работать на процессорах где норальных ни деления, ни умножения нет.
поэтому твоя красота — на порядки медленнее будет работать.
а зашить в ПЗУ таблицу коэфов — не проблема, на этом особо незачем экономить.
И да, конечно, в твоем алгоритме точность выше, но понимаешь, на практике такая точность не нужна, чтобы тратить на нее ценные такты...

на практике такая точность не нужна, чтобы тратить на нее ценные такты...

Это точно не я писал? Обычно мне приходится разъяснять эти простые вещи — что оптимизировать нужно финансы, а не понты.

Конкретно эта задача имеет конкретное решение, весьма быстрое. Но только потому, что она сама за уши притянута под это решение.

Але це ж перевірка алгоритмичного, тобто математичного мислення і інтелекту.

Особливо коли завчають на пам’ять реалізацію алгоритму.

І лише одного. Для вирішення лише однієї задачі. Яка можливо за останні 10 років взагалі ніким не була вирішена... бо не було потреби.

Перепроверил имя, думал — Владимир.

а через наслідування можна? бажано ромбічне

Next binary permutation:

uint64_t next(uint64_t n) {
  // Find the first unset bit (pivot).
  uint64_t pivotBit = __builtin_ctz((n | n - 1) + 1);

  // Set the first unset bit (pivot).
  uint64_t step1 = n | (1<<pivotBit);

  // Unset the first set bit (successor).
  uint64_t step2 = step1 & (step1 - 1);

  // Extract the part after the pivot.
  uint64_t suffixMask = (1 << pivotBit) - 1;
  uint64_t suffix = step2 & suffixMask;

  // Zero out the suffix, and only keep the 1's around.
  uint64_t final = (step2 & ~suffixMask) | (suffix >> __builtin_ctz(suffix));
  return final;
}

Да, так.

static inline uint64_t next_combination_mask(uint64_t x)                
{                           // xxxx011100                                                                    
    uint64_t a = x & -x;    // 0000000100                                            
    uint64_t b = x + a;     // xxxx100000                                            
    uint64_t c = b ^ x;     // 0000111100                                            
    c /= a;                 // 0000001111 ; shift left by log2(a)                                           
    a <<= 2;                // 0000000011 ; skip extra two bits
    return b | c;           // xxxx100011                                                       
}

Понятно, что если у нас есть __builtin_ctz(x), то деление можно заменить сдвигом на это значение. Итого 7 команд (или 8 если есть инстрикт).

У Д. Кнута этот трюк называется хаком Госпера, там в упражнении обратная задача, по искхонику определить, что делает код.

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

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

позволяет выиграть вычислительную сложность (вместо линейной — константная).

Решение красивое, но проверка в лоб с проверкой условий и сдвигами в цикле это тоже константа.

Как бы не совсем так.
Линейная всё же, от числа бит зависит (решение в лоб).

Константная сложность это когда для любого количества бит нужно например 20 операций (одно и то же количество хоть для 1 бита хоть для 1 миллиона битов).
Линейная сложность это когда для 5 бит нужно 5 операций, для 10 — 10, для 20 — 20, для 1 млн — 1 млн.

У рамках uniform cost model — ні. І якщо у вас інти стандартні, а не бігінт якийсь (як, наприклад, у кріптографії трапляється) — то використовується саме вона. Інакше виходить, що робота із числом n, взагалі будь-яка робота — це log(n). Бо шоб записати/прочитати це n — треба log(n) біт. Ну, тобто взяття елементу масиву по індексу n — не константа, а log(n). A+B додати — щось log(A+B) складність має ітд. Але вважають число біт у інті константним. І тому перебор хоч 1, хоч усіх біт — обмежено константою і тому має константну складність.

Константная сложность

Я за чистоту формулировок. Во-первых, линейная зависимость, а не сложность. Сложность это вообще трудно оцениваемая штука. Обычно под ней подразумевают либо использование ресурсов, либо время выполнения относительно какого-то параметра, который называется входными данными. А может быть и затраченное время или денег на разработку. В нашем примере это конкретный тип данных. Т.е. константа. Никакие другие входные параметры не предполагаются.

В контексте алгоритмов — сложность это хорошо изученная и оцененная штука, все алгоритмы задолго до нас разбили на классы сложности en.m.wikipedia.org/...​ist_of_complexity_classes и linear time complexity это один из классов сложности алгоритмов — DTIME(f(n)) я ж и перевожу «linear time complexity» как «линейная [временная] сложность» а не зависимость

This is a list of complexity classes in computational complexity theory.

И вот так мир свернулся до элементарной одной теории. Завидую таким людям.

Осталось разбить все жизненные вопросы на классы сложности, найти решения и дело в шляпе! :DD

Осталось мелочи. Начать и кончить. Пока там конь не валялся.

В контексте алгоритмов — сложность это хорошо изученная и оцененная штука,

Само понятие алгоритм за последние года 3 изменилось.
ru.wikipedia.org/wiki/Алгоритм
Попрошу обратить внимание на следующее: «В старой трактовке вместо слова „порядок“ использовалось слово „последовательность“, но по мере развития параллельности в работе компьютеров слово „последовательность“ стали заменять более общим словом „порядок“. Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.» Дело в том, что обычно имеются в виду детерминированная машина Тьюринга в качестве исполнителя. Имея в виду именно детерминированность программы формулируется и сложность по Колмогорову. Однако физический мир не детерминированный. И возникают и новые архитектуры и языки в которых вопросы сложности и работы вообще по другому формулируются. Во всяком случаем я этим и занимаюсь. Весьма удачно в смысле практического результата и не удачно в смысле финансов))

Константа, только коэффициент при ней может отличаться на два порядка.

Константа, только коэффициент при ней может отличаться на два порядка.

У меня вообще сомнения что вы правильно применяете понятие «на два порядка», что по любому константа. Хоть на 3 порядка.

То есть РЕДКОЕ решение НИКОГДА не встречающейся задачи кроме как в ОДНОМ учебнике?
Прекрасный вопрос для собеседования! В таком случае нужно потребовать ответить на встречный вопрос: ПОКАЖИТЕ где вы это применили, хоть кто-то из вас.

PS. Это — не решение. Код не читабельный. Объяснения что и почему — нет. А значит никакой гарантии, что он не содержит ошибок. Протестировать его тоже невозможно. Следовательно, этот код подлежит уничтожению и переписыванию заново — что время. За такое и уволить недолго, ибо диверсия.

В таком случае нужно потребовать ответить на встречный вопрос: ПОКАЖИТЕ где вы это применили, хоть кто-то из вас.

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

Объяснения что и почему — нет.

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

Протестировать его тоже невозможно.

Элементарно, один тест более чем справится:

uint64_t mask = 0x7f;
uint64_t counter = 0
while (mask < (1 << 52)) {
    ++counter;
    mask = next_combination_mask(mask)
}
assert(counter == 133784560); // 52 choose 7

Вот именно. Для написания теста НУЖНО ЗНАТЬ решение и его узкие места. В реальном мире так не работает, ты не знаешь где грабли.

Насчёт применения — ты можешь ОБЪЯСНИТЬ СУТЬ хака обычными словами, ЧТО ИМЕННО хакается, какая общая проблема (только без магических слов и сам-догадайся)? И лучше так объяснить, чтобы даже июнь понял, потому что с огромной вероятностью читать код будет именно он.

Я вижу только узкоспецифическую одну задачу и её чисто теоретические вариации.

Вибір bugtracking системи для open source проекту на ~500 розробників. Намагайтеся не ставати між програмістом і його улюбленой тулзою.

А з технічних — додати підтримку нової платформи в підсистему віртуальної пам’яті операційної системи. Для мене досі люди, які працюють над цією частиною ОС — магістри білої і чорної магії.

После того, как в новойо команде обновил приложение, чтоб оно работало с новой версией сетевого драйвера, начались kernel panic. Разработчики драйвера говорят — «Хз, у всех все работает, ты первый, кто пожаловался. Иди разбирайся в своем приложении». Разработчики приложения — «Сам подумай, как приложение может вызвать kernel panic? Это какая-то хрень в драйвере». В итоге за 3 недели ковыряния с кентами в потрохах всего, что можно было, героически выяснили в чем проблема, но все это время в голове витала мысль «фак, надо было оставаться в старой команде»

а что в итоге пропатчили, ядро или приложение

Жаль, а то бы миллиончик usd получил

А что тут сложного? Либо P=0 либо N=1

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

ну эта простая, для начала надо выснить сколько заправок в юса и сколько настройщиков роялей в Сиэтле, и дальше станет понятно:

In the past, I’ve used „impossible questions,” also known as „back of the envelope questions.” Classic examples of this are „How many piano tuners are there in Seattle?” The candidate won’t know the answer, but smart candidates won’t give up and they’ll be happy to try and estimate a reasonable number for you.

www.joelonsoftware.com/...​-interviewing-version-30

Вот ещё немного его маразмов:

....
Even if you have a candidate that would be brilliant at doing your particular task, but wouldn’t be very good in another team, that’s a No Hire.
In software, things change so often and so rapidly that you need people that can succeed at just about any programming task that you throw at them.
If for some reason you find an idiot savant that is really, really, really good at SQL but completely incapable of ever learning any other topic, No Hire. You’ll solve some short term pain in exchange for a lot of long term pain.

Never say „Maybe, I can’t tell.” If you can’t tell, that means No Hire. It’s really easier than you’d think. Can’t tell? Just say no! If you are on the fence, that means No Hire. Never say, „Well, Hire, I guess, but I’m a little bit concerned about...” That’s a No Hire as well. Mechanically translate all the waffling to „no” and you’ll be all right.

Why am I so hardnosed about this? It’s because it is much, much better to reject a good candidate than to accept a bad candidate.

Сейчас вместе с этим и задачами про рояли маразм масштабировался на всё айти.

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

Длинное объяснение:
1. Кошек примерно столько же, сколько и котов, с поправкой, что кошки погибают при родах, а коты — в котячьих драках.
Проигравший кот с выцарапанным глазом имеет шансы по неосторожности угодить под спешающую на работу октавию в родном дворе.
Победитель — потратит силы на оплодотворение кошки и на заплетающихся ногах не успеет перебежать дорогу. Итог — тот же.

Короткое объяснение:
2. Покрытие кошками моего города выше, чем покрытие тестами вашего проекта.

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

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

Количество кошек в городе равняется количеству одиноких сильных и независимых женщин, умноженное на 40.

Это уже отсебятина. В оригинале было: «месячное потребление бензина автомобилями в городе».

Объяснить РМ-ке почему программы не пишутся за 15 минут...

у неё выражение такое было- это задача на 15 минут...

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

на литкоде есть раздел hard и там обычно не выше 25%^^’, а еще ничего их на время решать

а еще почему инфоцыгане литкода не пользуются вазелином
[но это не точно]

Саша, ничто не стоит так дёшево и не ценится так дорого, как вежливость. Это не я, это Чехов)

Идите в пизу со своим спамом говнолиткодом.
Для тех кто вдруг не в курсе что это — объясняю: это задачки из серии «что выведет наыкран этот кусок черезжопу написсаного счястья», разумеется никогда в реальном коде не встречающегося.

Аналогия: «фдыовгвчыяш» — как поймёт это японец?

PS. Это эталон инфоцыганства: сами ни в зуб ногой, зато учить аж бегом. И я считаю, за попытку спама инфоцыганщиной бан должен прилетать моментально. Равно как и бан всех ссылок и регистрация их в базах для ЭдБлока.

PPS. И верни «цитату чехова» Дон Кихоту

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

Задача про два стула! Очевидно же! :-))

про реакт точеный и ангуляр др*ченый?

В мене самого трохи специфічні задачі: в основному я стараюсь займатись я̶к̶о̶ю̶с̶ь̶ ̶ф̶і̶ґ̶н̶ь̶о̶ю̶ чимось, де треба хоч трохи «писати формули на папері», і з них важко виділити найскладнішу. Проте, все одно розкажу про найбільш прикольну задачу, щоб хоч трохи розбавити це нескінченне порівняння кефіро-метрів квадратних з розміром податків в США.

Давним-давно, в сусідній команді для чогось треба було відображати текст на фоні довільного кольору; колір тексту треба було вибирати на льоту і так, щоб його було добре видно. Вони попросили дизайнерів підібрати кілька добрих прикладів кольорів текст-фон, а потім написали функцію, що інтерполює між ними. Іншими словами: є функція, що приймає трійку чисел RGB і видає трійку чисел RGB — для певних фіксованих значень RGB вона видає вибрані руками результати, а для всіх інших якось інтерполює між тими фіксованими. Так от проблема: чомусь яким методом не інтерполюють — завжди десь щось в тестах не проходить. Що не так?

Чому ця задача прикольна? Це був перший (і поки що останній) раз, коли мені довелось застосувати щось більше лінійної алгебри рівня першого курсу — теорему Брувера про непорушну точку (en.wikipedia.org/...​ouwer_fixed-point_theorem ). Простими словами: якщо неперервно відобразити кубик [0;1]x[0;1]x[0;1] в кубик [0;1]x[0;1]x[0;1], то котрась точка перейде сама в себе — функція видасть для тексту колір, що в точності співпадає з кольором фону (ясно, що такого тексту видно не буде і відповідні тести попадають). Що робити в такій ситуації? Ну я порадив їм «порвати» функції — інтерполювати чимось розривним, щоб теорема стала непримінимою.

странно. банаха слыхал. брювера єтого не слыхал.

тих теорем про непорушну точку так багато, що я не впевнений, чи їх всі хоч хтось знає )) (en.wikipedia.org/...​t_of_fixed-point_theorems ).

Продовжу розбавляти політику темою прикольних задач і потравлю ще трохи «байок зі склепу» ))

Задача, яку мені задавали два рази підряд

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

Наступного дня я прийшов на роботу... і мене попросили розв’язати точно таку ж задачу, тільки для 3D (нейронка давала ключові точки, а треба було відновити поворот об’єкта). ЛОЛ )) Я з розумною міною заявив, що вгадаю розв’язок з першого разу без розрахунків і виписав по аналогії такий самий детермінант лише більшої матриці. Чи вгадав?.. ну майже )) З точністю до знака мінус, так що театральний ефект трохи не вдався ))

P.S. Кому цікаво як ті формули виглядають, то збереглись замітки на ResearchGate (www.researchgate.net/...​apping_simplexes_affinely ), задачник (www.researchgate.net/...​apping_simplexes_affinely ), а товариш навіть написав невеликий огляд на Хабр (habr.com/ru/post/463349 ).

P.P.S. Стільки всього, бо задача виявилася дійсно класною, хоча спочатку так не здавалось.

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

Раз уже тему підняли, то я ще одну прикольну згадав: відрізнити ліву руку від правої )) Доки руки свої, то все просто, а от коли це 3D точки, що символізують суглоби пальців, то не зразу зрозуміло що робити (більше того, є позиції, коли розрізнити неможливо).

Скинути на фріланс циганці. Рішить 100%.

Самое сложное это думать.. Остальные сложности решаются деньгами и толпой. Я б даже не назвал это сложностями.

от ща у меня такая — построить реальную кросс-проектную команду

Про кроссфункциональные слышала, а кросспроектная это как? Люди парт-тайм на нескольких проектах?

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

Вголосинушку! Вы б ещё хирургов во время операции ротировали.

Львиная доля времени уходит на банальнейшее чтение кода и изучение через жопу написанных материалов, щедро смешанных с информационным мусором. И всё это множится на нолик при смене проекта. Конечно, если это реальные проекты, сложные, а не формошлёпка с CRUDом.

Была бы формошлёпка — не приходилось бы ротацию делать.

Ясен красен что тебя из-за монитора там виднее

У них agile и cross-functionality, а так же t-shape & flat hierarchy.

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

Ну как бы я такой задачи и не ставил ;)

а хирургов во время операции иногда таки ротируют

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

Нет, потому что предыдущий хирург устал

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

Правильно инициализировать контроллер памяти DDR2

Це ж не в сучасному ibm pc ? Там, я так підозрюю, cpu і без вас, і без ос ініціалізує )

в ibm pc память тоже не сама по себе заводится

организовать отпуск с семьей и отдохнуть

сколько отдыхал от отпуска?

Как назвать переменную

... а также когда инвалидировать кэш

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

Во времена 2000-ной винды помнится обязали Майкрософт к какому-то там пониманию формата файлов для Applе. Так вот, системная библиотека обеспечения совместимости, которая работала разумеется как попало, носила имя файла avothui.exe

В последующих апдейтах это разумеется потёрли.

А пруфы за давностью лет протухли? Речь о QuickTime’овских форматах или других каких-то?

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

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

Печально. Надо тогда больше подробностей: годы, какая винда (таки Win2K или другая), какой программе мешало...

Я и прецедентов-то таких найти не могу пока, чтобы Microsoft с Apple в те времена как-то вздорили, или чтобы антитрасты прикапывались к M$ за неподдержку чего-то Apple’овского... За тёрки с Novell знаю, за Netscape знаю, за Microsoft JVM знаю, за более позднее выпиливание WMP для Европы знаю, но такого...

Может, это и вовсе не в M$ похулиганили, а просто вирус-приколист в C:\WINNT\ нагадил? :)

Тоже сначала так подумал, но проверка файла показала что таки M$ признаёт его контрольную сумму.

или квартиру

А чего в муравейнике привлекательного-то?
За стенами соседи могут кутить и выносить мозг, чьи-то дети могут бегать в верхней квартире часами и топотом будить посреди выходных, в час дня. Как выйдешь на балкон, так рожа соседа вот она, только руку протяни, еще и курит, собака, а ты хотел воздухом подышать и на закат/рассвет полюбоваться.

3. Дом на возвышенности.
Но, вроде как, именно это и может задирать цены в Штатах, потому что виды многих точно так же привлекают.

HOA в сердце нежно ударит тебя через кошелек

HOA может и будет, но на дом она до 200 баксов в месяц, на таунхоум чуть больше, хоа на кондо в новом доме со бассейнами и тренажерками будет стремиться к 1k.

ты по прежнему еб**ся со всей утварью в доме

хз что ты под этим понимаешь, если расходы на поддержание дома то эта концепция на доу сильно овверрейтед, в новом доме первые 5 лет вообще ничего делать не надо, гарантия bumer-to-bumper на первые 3, structural на 10.

С домиком в годах можно попасть на дорогой ремонт, типа крышу поменять, но это один раз 30-40k на следующие 20-40 лет. Все остальное не так страшно, можно делать сомому, можно по надобности кого-то нанимать.

Все остальное не так страшно

Особенно когда на третьем этаже лопнет труба и зальёт до подвала.

а что ты хотел за $200? Семь прекрасных наложниц?

У меня HOA $400 и мне понятно за что. Они всё время чистят что-то, сейчас дизенфицируют, бассейн поддерживают в чистоте, перекладывают асфальт на парковке, недавно всё перекрасили. Поменяли лампочки на LED. Бесплатно почистили камин, чистят снег на парковке зимой.

HOA для частного дома это развод чистой воды.

Вот-вот, самые сложные задачи не технические

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

Не послать начальника-самодура, пока был на л1 визе

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

кстати годный поинт таки реально сложная задача

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