Вхід і реєстрація
Про роботу · 20 квітня 2020, 15:13 17209
Olena Sharovar, Senior Software Engineer (Billing) in a startup

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

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

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

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

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

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

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

Gregory Bocharov 04.05.2020 14:02

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’ов, организации митингов и неоднократного привлечения моего начальника проекта.

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

Перейти до дискусії
Alex Motovilov 24.04.2020 18:01

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

Перейти до дискусії
Mike Gorchak 21.04.2020 14:34

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

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

Перейти до дискусії
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Andrii Zaiats software engineer/architect в VITech 13.06.2020 02:10

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

Відповісти
Підтримати
Andrii Zaiats software engineer/architect в VITech 13.06.2020 02:07

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

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

Відповісти
Підтримати
Готель-Трембіта Закарпаття 06.05.2020 23:51

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

Відповісти
Підтримати
honeybadger 06.05.2020 19:30

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

Відповісти
Підтримати
Andre --- в none 14.05.2020 04:12

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

Відповісти
Підтримати
Vadim Kopanev
Andrew Kornilov Principal Software Engineer 06.05.2020 14:09

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

Відповісти
Підтримати
Andrew Kornilov Principal Software Engineer 06.05.2020 14:50

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

Відповісти
Підтримати
anonymous
Andrew Kornilov Principal Software Engineer 06.05.2020 15:24

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

Відповісти
Підтримати
anonymous
Віталій Мартиник Senior Software Engineer в United Software 06.05.2020 17:56

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

Відповісти
Підтримати
Andrew Kornilov
Anton Fimin .Net Teamlead 06.05.2020 11:41

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

Відповісти
Підтримати
devv 08.05.2020 07:08

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

Відповісти
Підтримати
Anton Fimin
Дмитрий Мирошник Lead QA Automation Engineer 06.05.2020 02:14

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

Відповісти
Підтримати
Denys Poltorak opentowork: Embedded / C++ 06.05.2020 11:44

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

Відповісти
Підтримати
Дмитрий Мирошник
Victor Mikhaylov junior manual tester 05.05.2020 12:54

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

Відповісти
Підтримати
Sergey Lysak T/T Lead 05.05.2020 15:16

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

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

Відповісти
Підтримати
Victor Mikhaylov
Gregory Bocharov Senior Software Developer 04.05.2020 14:02

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’ов, организации митингов и неоднократного привлечения моего начальника проекта.

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

Відповісти
Підтримати
Vic Programmer 01.05.2020 11:09

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

Відповісти
Підтримати
Mark III 01.05.2020 10:44

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

Відповісти
Підтримати
Андрей Литвинов C Señor 04.05.2020 02:30
реализация операции как распределенной атомарной транзакции

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

Відповісти
Підтримати
Mark III
Mark III 05.05.2020 03:39

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

Відповісти
Підтримати
Андрей Литвинов
Андрей Литвинов C Señor 05.05.2020 08:14

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

Відповісти
Підтримати
DNA Exp
DNA Exp 05.05.2020 10:31

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

Відповісти
Підтримати
Андрей Литвинов
Андрей Литвинов C Señor 05.05.2020 10:46

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

Відповісти
Підтримати
DNA Exp
honeybadger 06.05.2020 19:24
Были ли вовлечены брокеры сообщений в 2PC

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

Відповісти
Підтримати
Андрей Литвинов
Андрей Литвинов C Señor 06.05.2020 19:56

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

Відповісти
Підтримати
honeybadger
honeybadger 06.05.2020 20:10

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

Відповісти
Підтримати
Андрей Литвинов
Андрей Литвинов C Señor 06.05.2020 20:13

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

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

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

Відповісти
Підтримати
honeybadger
honeybadger 06.05.2020 20:35
(которые, кстати тоже могут не уметь в 2PC)

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

Відповісти
Підтримати
Андрей Литвинов
Андрей Литвинов C Señor 06.05.2020 20:42

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

Відповісти
Підтримати
honeybadger
Jaroslav Shkarupilo Верховний Мозкоклюй в NDA 30.04.2020 23:05

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

Відповісти
Підтримати
Мухаммед 28.04.2020 11:42

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

Відповісти
Підтримати
DNA Exp 28.04.2020 19:08

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

Відповісти
Підтримати
Мухаммед
Roman Pavlyuk myself в ELEKS 30.04.2020 22:20

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

Відповісти
Підтримати
anonymous
Oleg Leschinsky Software Engineer 01.05.2020 06:57

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

Відповісти
Підтримати
Roman Pavlyuk
Roman Pavlyuk myself в ELEKS 03.05.2020 21:21

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

Відповісти
Підтримати
Oleg Leschinsky
Дима Дима 03.05.2020 21:28

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

Відповісти
Підтримати
Oleg Leschinsky
Мухаммед 04.05.2020 08:06
Тут зародилось новое популярное мнение «Ой, а когда мне понадобится тот матан, я открою популярные несовковые уроки на стенфорде

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

Відповісти
Підтримати
Дима Дима
Oleksandr Golovatyi -`★´- в ☁︎ 28.04.2020 20:07
как тогда грамотно отметить что один алгоритм имеет в десять раз меньшую сложность ?

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 28.04.2020 20:21

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Мухаммед 28.04.2020 21:20
При n это О(n)
При меньше n это o(n)

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

Відповісти
Підтримати
DNA Exp
Tymchyshyn Vitalii Researcher 29.04.2020 03:00
в Вики написали по дубовому, все O(n). Может кого не устраивает такая дубовая формулировка, между черным и белым есть ещё стопицот оттенков.

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

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

Відповісти
Підтримати
DNA Exp
Анастасия Павлова Працює в Фриланс 27.04.2020 23:26

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

Відповісти
Підтримати
Оператор Биореактора 27.04.2020 19:33

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

Відповісти
Підтримати
Дмитрий Мирошник Lead QA Automation Engineer 06.05.2020 02:19

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

Відповісти
Підтримати
anonymous
Igor Kravchenko Software developer 26.04.2020 21:13

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

Відповісти
Підтримати
Left Outer Join 26.04.2020 22:48

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

Відповісти
Підтримати
Igor Kravchenko
Igor Kravchenko Software developer 26.04.2020 21:09

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

Відповісти
Підтримати
Sergey Lysak T/T Lead 26.04.2020 22:25

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

Відповісти
Підтримати
Igor Kravchenko
andriy dmytrenko IT Geek 26.04.2020 18:51

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

Відповісти
Підтримати
Sergiy Zolotaryov .Net developer 28.04.2020 08:42

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

Відповісти
Підтримати
andriy dmytrenko
Alex Fogol Software Developer, C/C++ Expert 28.04.2020 11:51

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

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

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

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

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

Відповісти
Підтримати
Left Outer Join
Alex Fogol Software Developer, C/C++ Expert 28.04.2020 14:17

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

Відповісти
Підтримати
anonymous
Alex Fogol Software Developer, C/C++ Expert 28.04.2020 14:20

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

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

Відповісти
Підтримати
anonymous
andriy dmytrenko IT Geek 28.04.2020 10:57

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

Відповісти
Підтримати
Sergiy Zolotaryov
Oleg Leschinsky Software Engineer 25.04.2020 21:56

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

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

Відповісти
Підтримати
Valentyn K Software Engineer в IT 25.04.2020 12:07

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

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

Відповісти
Підтримати
Yurii Kostiuk Cloud Native Architect в Okta 25.04.2020 11:27

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

Відповісти
Підтримати
Deleted 25.04.2020 08:08

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

Відповісти
Підтримати
DNA Exp 24.04.2020 18:12

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

Відповісти
Підтримати
devv 26.04.2020 10:49

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

Відповісти
Підтримати
DNA Exp
DNA Exp 30.04.2020 19:37

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

Відповісти
Підтримати
devv
Punk Floyd 30.04.2020 19:05
Реализовал удаление ключей из HArray. Задача требовала написания 2/3 кода, который просто мониторит health памяти пока работает алгоритм.

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 30.04.2020 19:32

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

Відповісти
Підтримати
Punk Floyd
Alex Motovilov 24.04.2020 18:01

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

Відповісти
Підтримати
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 06:12

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

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

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

Відповісти
Підтримати
Михаил Кузьмин 24.04.2020 10:27

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

Відповісти
Підтримати
Oleksandr Golovatyi
Михаил Кузьмин 24.04.2020 13:55

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

Відповісти
Підтримати
anonymous
Denis Arharov 24.04.2020 14:05
Создаешь новый массив
Пам’ять алоціювати чи модифікувати вхідні параметри не можна
Відповісти
Підтримати
Михаил Кузьмин
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 21:00

Та прочитай же умови задачі :)

Відповісти
Підтримати
Михаил Кузьмин
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 21:02
Цікаво як це швидше можна написати

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

Відповісти
Підтримати
anonymous
Vitalii Shvetsov 25.04.2020 01:07

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

Відповісти
Підтримати
Oleksandr Golovatyi
DNA Exp 25.04.2020 01:15

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

Відповісти
Підтримати
Vitalii Shvetsov
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 01:16
сложность O(k)

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

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

Відповісти
Підтримати
Vitalii Shvetsov
DNA Exp 25.04.2020 01:19
Але нам допомагає те, що послідовності відсортовані — може це можна якось використати?

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

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 02:31
Тот алгоритм что я прислал как раз и работает потому что элементы отсортированы.

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

Відповісти
Підтримати
DNA Exp
Vitalii Shvetsov 25.04.2020 01:44 
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
}
Відповісти
Підтримати
Oleksandr Golovatyi
Vitalii Shvetsov 25.04.2020 01:45 
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))
Відповісти
Підтримати
Vitalii Shvetsov
DNA Exp 25.04.2020 01:48

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

Відповісти
Підтримати
Vitalii Shvetsov
Vitalii Shvetsov 25.04.2020 01:54

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 01:58

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

Відповісти
Підтримати
Vitalii Shvetsov
Vitalii Shvetsov 25.04.2020 01:55

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

Відповісти
Підтримати
DNA Exp
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 02:27
O (k/2)

Це те ж саме що і O(n).

Відповісти
Підтримати
Vitalii Shvetsov
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 02:26

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

Відповісти
Підтримати
Vitalii Shvetsov
Vitalii Shvetsov 25.04.2020 01:46

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 02:31

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

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

Відповісти
Підтримати
Vitalii Shvetsov
DNA Exp 25.04.2020 02:35

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 02:59
Как бы тебе обьяснить, что про хештаблицы

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

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

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

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

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

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

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

Відповісти
Підтримати
DNA Exp
Vitalii Shvetsov 25.04.2020 02:37

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 02:47

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

Відповісти
Підтримати
Vitalii Shvetsov
Ivan Onyshchenko 25.04.2020 11:21

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

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 26.04.2020 03:03

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

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

Відповісти
Підтримати
Ivan Onyshchenko
Punk Floyd 30.04.2020 10:26
Всеодно ж треба створювати новий масив

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

Відповісти
Підтримати
anonymous
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 20:59
Линейный алгоритм

Треба швидше

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

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

Відповісти
Підтримати
Михаил Кузьмин
Sergey Lysak T/T Lead 24.04.2020 22:05

там така потреба
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

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

Відповісти
Підтримати
anonymous
Sergey Lysak T/T Lead 25.04.2020 09:36

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

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

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

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

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

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

Відповісти
Підтримати
anonymous
Denys Poltorak opentowork: Embedded / C++ 26.04.2020 14:22

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

Відповісти
Підтримати
Sergey Lysak
Sergey Lysak T/T Lead 26.04.2020 22:23

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

Відповісти
Підтримати
Denys Poltorak
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 22:56

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

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

Відповісти
Підтримати
anonymous
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:03
Уявно зєднується перший масив із другим

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

Відповісти
Підтримати
anonymous
Дима Дима 24.04.2020 23:11

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:17
С этого начинать надо было.

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

Відповісти
Підтримати
Дима Дима
Дима Дима 24.04.2020 23:23
масиву який би вийшов зі злиття a та b зі збереженням сортованості

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

Відповісти
Підтримати
Oleksandr Golovatyi
Miroslav Grabinskiy senior node.js 25.04.2020 01:21

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

Відповісти
Підтримати
Дима Дима
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 01:22

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

Відповісти
Підтримати
Дима Дима
DNA Exp 24.04.2020 22:45

Зачем там байнори серч ? о_О

Відповісти
Підтримати
anonymous
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 22:57

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

Відповісти
Підтримати
DNA Exp
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:01

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

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

Відповісти
Підтримати
anonymous
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:10
Але ж це алокація, хіба ні?

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

Відповісти
Підтримати
anonymous
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:25
Тут щоб зааплаїти бінарний пошук, потрібно злити масиви і пересортувати.

Ніт. Умовно кажучи маючи індекс 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], що і буде відповіддю.

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

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

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

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

Відповісти
Підтримати
anonymous
Sergey Lysak T/T Lead 25.04.2020 09:41
І вміння програмувати можна продемонструвати, і вміння розв’язувати задачі.

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

программування буде ось у такому варіанті:
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)

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 26.04.2020 03:10

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

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

Відповісти
Підтримати
Sergey Lysak
Михаил Кузьмин 26.04.2020 07:40
Це насправді цікава тема для розмови і я погоджуся, що в цілому подібні задачі не є гарним способом перевірити кандидата.

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 26.04.2020 08:06

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

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

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Denys Poltorak opentowork: Embedded / C++ 26.04.2020 14:34

Ну ок.

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

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 27.04.2020 02:24
Идешь по индексу k в каждый массив...

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

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

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

Відповісти
Підтримати
Denys Poltorak
Denys Poltorak opentowork: Embedded / C++ 27.04.2020 11:13
На спеціально підібраних наборах даних напевно.

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

Відповісти
Підтримати
Oleksandr Golovatyi
DNA Exp 24.04.2020 22:43

А в чем подвох ? Ровно 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++;
                }
            } 
        }
Відповісти
Підтримати
Oleksandr Golovatyi
DNA Exp 24.04.2020 22:57

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

Відповісти
Підтримати
anonymous
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 22:53
І зробити це треба швидше ніж за O(n).
Відповісти
Підтримати
DNA Exp
DNA Exp 24.04.2020 22:56

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 22:58

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

Відповісти
Підтримати
DNA Exp
DNA Exp 24.04.2020 23:07

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

Відповісти
Підтримати
Oleksandr Golovatyi
Valeriy Shvets Engineer в Phonexa 24.04.2020 23:12
швидше ніж за O(n)

!=

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 24.04.2020 23:18

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

Відповісти
Підтримати
Valeriy Shvets
Valeriy Shvets Engineer в Phonexa 24.04.2020 23:28

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

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

Відповісти
Підтримати
DNA Exp
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 01:02
Потому что быстрее O(n), всегда понимается О(log n) или О(1).

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

Відповісти
Підтримати
Valeriy Shvets
Valeriy Shvets Engineer в Phonexa 25.04.2020 01:43

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

Відповісти
Підтримати
Andriy Kunitsin
Artyom Krivokrisenko 24.04.2020 23:23
Какая-то своя интерпретация, очевидно что хотят за O(log n).

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

Відповісти
Підтримати
Valeriy Shvets
Artyom Krivokrisenko 24.04.2020 23:45
ЛОЛ При некоторых O(log n * log n) будет больше > O(n)

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

Відповісти
Підтримати
DNA Exp
DNA Exp 24.04.2020 23:50

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

Відповісти
Підтримати
Artyom Krivokrisenko
Artyom Krivokrisenko 24.04.2020 23:54

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

Відповісти
Підтримати
DNA Exp
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:32

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

Відповісти
Підтримати
Artyom Krivokrisenko
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:48

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

Відповісти
Підтримати
anonymous
DNA Exp 24.04.2020 23:40
Оскільки у масивів скоріше за все буде різна кількість елементів (m та n) то можна за O(log m log n)

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:44

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

Відповісти
Підтримати
DNA Exp
Artyom Krivokrisenko 24.04.2020 23:46

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

Відповісти
Підтримати
DNA Exp
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:13
Это ты не допонял условия задачи.

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

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

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 24.04.2020 23:21
Але в цілому бінарний пошук швидший за перебір. І в середньому і в найгіршому випадку.

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:33
выкатывай свое решение

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

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

Відповісти
Підтримати
DNA Exp
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:19

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 24.04.2020 23:25

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:30
Автор, от тебя на собеседовании просили простое элегантное решение.

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

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

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

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

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

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 24.04.2020 23:36

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

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 23:46
Интервьювер тебе правильные вопросы задавал.

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

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

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

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

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 24.04.2020 23:56
Пишу і регочу

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 00:02
решение за 5 минут которое решает задачу в среднем за меньше чем а О(n)

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

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

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

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

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

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

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

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

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

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 00:16

День != доба.

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

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

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

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

Як так?

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

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

Відповісти
Підтримати
DNA Exp
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 01:38

Я с вас ору.

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 01:43

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

Відповісти
Підтримати
Andriy Kunitsin
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 01:50

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 01:55

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

Відповісти
Підтримати
Andriy Kunitsin
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 02:00

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

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 02:07
Нет, не ок. Вы не понимаете О-нотацию. O(n/2) — это то же самое, что и O(n).

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

Відповісти
Підтримати
Andriy Kunitsin
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 02:15

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

Відповісти
Підтримати
DNA Exp
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 02:18

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 02:23

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

Відповісти
Підтримати
Andriy Kunitsin
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 02:34
мой алгоритм в среднем бежит только по половине этих элементов

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

Відповісти
Підтримати
DNA Exp
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 02:40

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

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 02:47
Или, боронь Боже, проведёте? Вы можете свою компанию назвать, чтобы я знал, куда точно идти не следует?

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

Відповісти
Підтримати
Andriy Kunitsin
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 02:56

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 02:59

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

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

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

Відповісти
Підтримати
Andriy Kunitsin
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 03:37

А у меня тоже есть опыт, называется „читать уже заботливо скинутую в тред статью”. Попробуйте: 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.
Відповісти
Підтримати
DNA Exp
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 03:00
научитесь писать O(n/2)

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 02:49
это то же самое O(n*63+sqrt(n)-283)

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

Відповісти
Підтримати
Andriy Kunitsin
Valeriy Shvets Engineer в Phonexa 25.04.2020 03:32

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

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 03:38

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

Відповісти
Підтримати
Valeriy Shvets
Artyom Krivokrisenko 25.04.2020 03:47
на то что время работы алгоритмы растет не линейно а значит это не O(n), потому что на графике это не прямая линия

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 03:54

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

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 04:03

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

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

Відповісти
Підтримати
Artyom Krivokrisenko
Artyom Krivokrisenko 25.04.2020 04:27
я привык к точным наукам.

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

Возьми 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.»

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 05:03

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

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

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

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 11:02

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

Відповісти
Підтримати
Artyom Krivokrisenko
Artyom Krivokrisenko 25.04.2020 11:05

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

Повторяю:

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 11:07

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

Відповісти
Підтримати
Artyom Krivokrisenko
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 02:33
Первый алгоритм при передаче массива на 100 элементов вынужден пробежать по всем 100 элементам. Второй только по 50. У одного будет сложность условно O(n) у второго O(n/2).

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

Відповісти
Підтримати
DNA Exp
Artyom Krivokrisenko 25.04.2020 02:39
Мы можем сказать что оба алгоритма имеют линейную сложность O(x), но если хотим сказать более точно, говорим O(n) и O(n/2) где N количество элементов

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

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

Відповісти
Підтримати
DNA Exp
Artyom Krivokrisenko 25.04.2020 02:37
Про хештаблицы кстате тоже говорят что работают за О(1), а по факту их worst case тоже O(n)

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 02:40

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

Відповісти
Підтримати
Artyom Krivokrisenko
Artyom Krivokrisenko 25.04.2020 03:13
Нет, развечто хештаблица редуцирована до обычного массива и ключи целые числа малого диапазона.

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 03:15
Не обязательно, есть куча вариантов свести до O(1) с минимальными ограничениями.

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

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

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

Відповісти
Підтримати
Artyom Krivokrisenko
Artyom Krivokrisenko 25.04.2020 03:21
Не обязательно, есть куча вариантов свести до O(1) с минимальными ограничениями.
в общем случае нельзя, для ключей любой природы, любого количества. Матчасть.

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

Відповісти
Підтримати
DNA Exp
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 03:07

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

Відповісти
Підтримати
Artyom Krivokrisenko
DNA Exp 25.04.2020 03:13

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

Відповісти
Підтримати
Andriy Kunitsin
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 13:08

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

Відповісти
Підтримати
DNA Exp
Artyom Krivokrisenko 25.04.2020 03:17
А где можно про это почитать? O(1) даже в worst case — это как-то too good to be true.

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

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

Відповісти
Підтримати
Andriy Kunitsin
DNA Exp 25.04.2020 03:19
Например, банально: ограничить размер бакета (обычно фиксируют, чтоб он полностью помещался на кеш линию).

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

Відповісти
Підтримати
Artyom Krivokrisenko
Artyom Krivokrisenko 25.04.2020 03:20
Если сканить прийдется несколько элементов в бакете, значит это точно больше O(1)

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 03:23

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

Відповісти
Підтримати
Artyom Krivokrisenko
DNA Exp 25.04.2020 03:32

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

Відповісти
Підтримати
Artyom Krivokrisenko
DNA Exp 25.04.2020 03:32

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

Відповісти
Підтримати
Artyom Krivokrisenko
Artyom Krivokrisenko 25.04.2020 03:51
Во-первых ты не можешь ограничить количество элементов в бакете

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

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

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

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

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

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

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

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

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

Відповісти
Підтримати
Artyom Krivokrisenko
Artyom Krivokrisenko 25.04.2020 03:25
O(k) где k количество элементов в бакете при наибольшей коллизии. Еще раз O(1) это константное время доступа, это означает что у тебя сто что у тебя квинтильен записей, время доступа должно быть константно, причем не аппаратно а алгоритмически

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

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

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

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

Смекаешь?

Відповісти
Підтримати
DNA Exp
Дима Дима 25.04.2020 00:11

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

Відповісти
Підтримати
anonymous
DNA Exp 25.04.2020 00:14

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

Відповісти
Підтримати
anonymous
Дима Дима 25.04.2020 00:18

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 00:22

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

Відповісти
Підтримати
Дима Дима
DNA Exp 25.04.2020 00:31

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

Відповісти
Підтримати
anonymous
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 00:19

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 00:49

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 01:12
Мой код решает твою задачу.

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

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

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

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

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

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

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

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 00:25

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

Відповісти
Підтримати
anonymous
DNA Exp 25.04.2020 05:09

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

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

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

Відповісти
Підтримати
DNA Exp
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 05:53
ПС Бинари серча там не надо, незачем.

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

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

Відповісти
Підтримати
DNA Exp
Artyom Krivokrisenko 24.04.2020 23:22

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

Відповісти
Підтримати
Oleksandr Golovatyi
Vitalii Shvetsov 25.04.2020 01:01

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 01:17

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

Відповісти
Підтримати
Vitalii Shvetsov
Vitalii Shvetsov 25.04.2020 01:47 
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 минут

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 04:34

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

Відповісти
Підтримати
anonymous
Михаил Кузьмин 25.04.2020 04:50
Складність не придумати алгоритм, а написати код — всі оці спеціальні випадки по суті і складають 90% коду.

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 04:54

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

Відповісти
Підтримати
Михаил Кузьмин
Denys Poltorak opentowork: Embedded / C++ 26.04.2020 14:40

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

Відповісти
Підтримати
Михаил Кузьмин
DNA Exp 25.04.2020 05:31
а от коли починаєш писати то вилазить стільки спеціальних випадків, що капєц. Для мене складність була не знайти рішення, а написати код який працює.

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 25.04.2020 05:48

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

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

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

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 10:53

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 26.04.2020 03:13
Код мой есть, да там не хватает чуть чуть

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

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

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

Відповісти
Підтримати
DNA Exp
Artyom Krivokrisenko 25.04.2020 06:42
Подозреваю что ты зарылся изза того что пытался ее решить с неправильным дизайном. Наскоком.Тебе нужно было изначально сразу выделить правильные абстракции, тоесть блок и описать методы мержа блоков. Научив блоки мержится без скана, дальше бы уже код был тривиальным и чистым. Наверное ты пытался в рукопашную выписывать все эти ифы, что сразу выливается в жутчайший говнокод. Эта задача кстате хорошо ложится на ООП

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 10:49

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

Відповісти
Підтримати
Artyom Krivokrisenko
Artyom Krivokrisenko 25.04.2020 11:00

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

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

Відповісти
Підтримати
DNA Exp
DNA Exp 25.04.2020 11:36
Код не будет тривиальны ми чистым

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

Відповісти
Підтримати
Artyom Krivokrisenko
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 14:53

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

Відповісти
Підтримати
DNA Exp
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 14:47

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 15:45

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

Відповісти
Підтримати
Andriy Kunitsin
Андрей Литвинов C Señor 25.04.2020 21:36

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

Відповісти
Підтримати
Oleksandr Golovatyi
Artyom Krivokrisenko 26.04.2020 07:19
А при поиске значения по индексу, все-таки, решение будет линейное.

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

Відповісти
Підтримати
Андрей Литвинов
Oleksandr Golovatyi -`★´- в ☁︎ 26.04.2020 08:22

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

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.

Відповісти
Підтримати
Artyom Krivokrisenko
Андрей Литвинов C Señor 26.04.2020 21:51

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

Відповісти
Підтримати
Artyom Krivokrisenko
Andriy Kunitsin Software Engineer в GlobalLogic 25.04.2020 23:48

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Andriy Kunitsin Software Engineer в GlobalLogic 26.04.2020 18:26

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

Відповісти
Підтримати
anonymous
Andriy Kunitsin Software Engineer в GlobalLogic 26.04.2020 21:24

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

Відповісти
Підтримати
anonymous
DNA Exp 27.04.2020 17:01

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

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 Тесты молодец что дописал. Основательный подход, но тесты однотипные, не покрывают краевые случаи. За это минус. Да и в тестах рандом не нужен, кому нужны тесты которые в случае бага раз проходят раз не проходят ?

Відповісти
Підтримати
Andriy Kunitsin
Oleksandr Golovatyi -`★´- в ☁︎ 26.04.2020 03:16

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

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

Відповісти
Підтримати
anonymous
Andriy Kunitsin Software Engineer в GlobalLogic 26.04.2020 18:23

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

Відповісти
Підтримати
anonymous
Олександр Шпак Oarsman в Self Employed 26.04.2020 11:21
Пам’ять алоціювати чи модифікувати вхідні параметри не можна.

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 27.04.2020 02:25

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

Відповісти
Підтримати
Олександр Шпак
Олександр Шпак Oarsman в Self Employed 27.04.2020 09:51

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

Відповісти
Підтримати
Oleksandr Golovatyi
Андрей Литвинов C Señor 27.04.2020 10:10

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

Відповісти
Підтримати
Олександр Шпак
Олександр Шпак Oarsman в Self Employed 27.04.2020 10:52
Пам’ять алоціювати чи модифікувати вхідні параметри не можна.

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

Відповісти
Підтримати
Андрей Литвинов
Олександр Шпак Oarsman в Self Employed 27.04.2020 18:51

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

Відповісти
Підтримати
Андрей Литвинов
Oleksandr Golovatyi -`★´- в ☁︎ 27.04.2020 21:26

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

Відповісти
Підтримати
Олександр Шпак
Олександр Шпак Oarsman в Self Employed 28.04.2020 14:24

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

Відповісти
Підтримати
Oleksandr Golovatyi
De Money 28.04.2020 16:08

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

Відповісти
Підтримати
Олександр Шпак
Oleksandr Golovatyi -`★´- в ☁︎ 28.04.2020 20:09

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

Відповісти
Підтримати
Олександр Шпак
Andriy Kunitsin Software Engineer в GlobalLogic 27.04.2020 13:42

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

Відповісти
Підтримати
Олександр Шпак
Олександр Шпак Oarsman в Self Employed 27.04.2020 18:54
Виділяти змінні ≠ виділяти пам’ять
вже виділена сторінка зі стеком

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

Відповісти
Підтримати
Andriy Kunitsin
Oleksandr Golovatyi -`★´- в ☁︎ 28.04.2020 20:10
Піду краще за бабло порішаю як одну сраку інтегрувати в іншу

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

Відповісти
Підтримати
anonymous
Tymchyshyn Vitalii Researcher 26.04.2020 23:21

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

Код:

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. Насправді я не дуже впевнений, що воно працює, але тести проходять, то може воно й ок.

Відповісти
Підтримати
Oleksandr Golovatyi
Tymchyshyn Vitalii Researcher 26.04.2020 23:36

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

Відповісти
Підтримати
anonymous
Oleksandr Golovatyi -`★´- в ☁︎ 27.04.2020 02:18

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

Відповісти
Підтримати
Tymchyshyn Vitalii
Oleksandr Golovatyi -`★´- в ☁︎ 27.04.2020 02:20

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

Відповісти
Підтримати
Tymchyshyn Vitalii
Tymchyshyn Vitalii Researcher 27.04.2020 02:23

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 28.04.2020 20:12

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

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

Відповісти
Підтримати
anonymous
Oleksandr Golovatyi -`★´- в ☁︎ 28.04.2020 20:29
Сводить k к n или m не есть корректно. Понимаешь почему?

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

Відповісти
Підтримати
anonymous
Oleksandr Golovatyi -`★´- в ☁︎ 29.04.2020 20:19

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

Відповісти
Підтримати
anonymous
serg freelance 28.04.2020 15:48

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

Відповісти
Підтримати
Oleksandr Golovatyi
De Money 28.04.2020 16:11

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 28.04.2020 20:05
моє рішення запросто можна адаптувати для індексу k, от тільки воно на 140 строк

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

Відповісти
Підтримати
De Money
Artyom Krivokrisenko 29.04.2020 09:39

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

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Yaroslav Shevchuk Senior Software Engineer в Google 29.04.2020 10:16
Скорее всего, поиск k-ого элемента пошел бы немного проще, так как с медианой еще разная логика в зависимости от того, четное или нечетное ко-во элементов.

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

Відповісти
Підтримати
Artyom Krivokrisenko
Oleksandr Golovatyi -`★´- в ☁︎ 29.04.2020 20:17
Задача по сути и есть — написать поиск k-ого

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

Відповісти
Підтримати
Yaroslav Shevchuk
Yaroslav Shevchuk Senior Software Engineer в Google 29.04.2020 23:01

зашел в свои 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;
}
Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 29.04.2020 23:06

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

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

Відповісти
Підтримати
Yaroslav Shevchuk
Yaroslav Shevchuk Senior Software Engineer в Google 29.04.2020 23:09

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

Відповісти
Підтримати
Oleksandr Golovatyi
Alex Koshterek погромизд 29.04.2020 23:07

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

Відповісти
Підтримати
Oleksandr Golovatyi
Oleksandr Golovatyi -`★´- в ☁︎ 29.04.2020 20:15
До куда ты смог дойти во время собеседования?

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

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

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

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

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

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

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

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

Відповісти
Підтримати
Oleksandr Golovatyi
Mark III 01.05.2020 10:25

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

Відповісти
Підтримати
Oleksandr Golovatyi
Anatoliy 23.04.2020 20:54

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

Відповісти
Підтримати
anonymus ps 24.04.2020 08:21

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

Відповісти
Підтримати
Anatoliy
Anatoliy 24.04.2020 13:55

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

Відповісти
Підтримати
anonymus ps
flyman 23.04.2020 12:50

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

Відповісти
Підтримати
Natali UI/UX Designer в Playvalve 23.04.2020 12:32

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

Відповісти
Підтримати
anonymus ps 24.04.2020 08:23

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

Відповісти
Підтримати
Natali
Андрей Литвинов C Señor 25.04.2020 21:44
завдання було заставити всіх юзати стайлдгайд, який ніхто не хотів юзати
результат бьорн аут і звільнення

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

Відповісти
Підтримати
Natali
Natali UI/UX Designer в Playvalve 25.04.2020 21:55

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

Відповісти
Підтримати
Андрей Литвинов
Андрей Литвинов C Señor 25.04.2020 22:08

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

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

Відповісти
Підтримати
Natali
Andriy Kunitsin Software Engineer в GlobalLogic 26.04.2020 01:24
Навязывать им какие-то coding standards говорит об полном непонимании тонкой душевной организации.

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

Відповісти
Підтримати
Андрей Литвинов
Андрей Литвинов C Señor 26.04.2020 07:53

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

Відповісти
Підтримати
Andriy Kunitsin
Andriy Kunitsin Software Engineer в GlobalLogic 26.04.2020 18:37

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

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

Відповісти
Підтримати
Андрей Литвинов
Andriy Kunitsin Software Engineer в GlobalLogic 27.04.2020 01:45

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

Відповісти
Підтримати
anonymous
Андрей Литвинов C Señor 26.04.2020 19:56

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

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

Відповісти
Підтримати
Andriy Kunitsin
Oleksandr Golovatyi -`★´- в ☁︎ 26.04.2020 03:18

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

Відповісти
Підтримати
Natali
Андрей Литвинов C Señor 26.04.2020 07:56

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

Відповісти
Підтримати
Oleksandr Golovatyi
Grez 21.04.2020 22:54

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

Відповісти
Підтримати
Sergey Lysak T/T Lead 21.04.2020 20:27

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

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

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

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

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

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

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

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

Відповісти
Підтримати
Sergey Lysak T/T Lead 21.04.2020 21:34
И сложность внезапно пропадет.

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

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

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

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

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

Відповісти
Підтримати
anonymous
Sergey Lysak T/T Lead 21.04.2020 22:00
Мало пороха понюхал.

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

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

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

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

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

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

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

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

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

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

Відповісти
Підтримати
anonymous
Sergey Lysak T/T Lead 21.04.2020 22:25
описанная тобой задача перестает быть сложной и становится типичной

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

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

то же и здесь.

Во. Я об этом

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

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

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

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

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

Відповісти
Підтримати
anonymous
Михаил Кузьмин 22.04.2020 06:24
они не сильные — если не могут решать — реальные задачи разработки
им бы в математику, компьютер сайенс, или еще какой ресерч. подальше вобщем от программирования.

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

Відповісти
Підтримати
Sergey Lysak
Sergey Lysak T/T Lead 22.04.2020 07:20

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

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

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

Відповісти
Підтримати
Михаил Кузьмин
Михаил Кузьмин 22.04.2020 08:04
так что у меня все впереди — выровняю свои перекосы :)

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

Відповісти
Підтримати
Sergey Lysak
Артем Перекресний WTF over SSH 21.04.2020 17:39

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

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

Відповісти
Підтримати
Vladimir Kovrigin Теоретик 21.04.2020 22:29

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

Відповісти
Підтримати
Артем Перекресний
John Appleseed 22.04.2020 11:50

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

Відповісти
Підтримати
Артем Перекресний
Valeriy Shvets Engineer в Phonexa 21.04.2020 17:02

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

Відповісти
Підтримати
Mike Gorchak Graphics Device Driver Developer в QNX Software Systems 21.04.2020 14:34

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

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

Відповісти
Підтримати
Євген Лесько Competency manager в ELEKS 21.04.2020 17:40

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

Відповісти
Підтримати
Mike Gorchak
Dmytro Shchurov Frontend/React Developer в KAJO s.r.o. 21.04.2020 12:42

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

Відповісти
Підтримати
Фрэнк Сайдботтом 21.04.2020 13:42

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

Відповісти
Підтримати
anonymous
Фрэнк Сайдботтом 21.04.2020 13:51

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

Відповісти
Підтримати
anonymous
Anatoliy Rentgenovich 21.04.2020 12:02

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

Відповісти
Підтримати
Vitalii Davyskyba Frontend Engineer 21.04.2020 11:33

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

Відповісти
Підтримати
Михаил Кузьмин 21.04.2020 13:24

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

Відповісти
Підтримати
Vitalii Davyskyba
Фрэнк Сайдботтом 21.04.2020 14:03

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

Відповісти
Підтримати
Михаил Кузьмин
Andrii Sevastianov Senior Developer в HCLTech 21.04.2020 14:08

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

Відповісти
Підтримати
Фрэнк Сайдботтом
Seven Berg 22.04.2020 03:19

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

Відповісти
Підтримати
Tymchyshyn Vitalii
Artyom Krivokrisenko 22.04.2020 04:11

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

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

Відповісти
Підтримати
Tymchyshyn Vitalii
Мавпа программиста 21.04.2020 13:45

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

Відповісти
Підтримати
anonymous
minodvesP Vasya 24.04.2020 12:32
Двигал компонент влево на 3 пикселя

На этих словах я вспомнил Pixel Perfect (для верстки страницы по макету пиксель в пиксель, геморрой еще тот). :-) В Winforms небось аналогичный геморрой))))

Відповісти
Підтримати
anonymous
Igor Kravchenko Software developer 26.04.2020 21:11

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

Відповісти
Підтримати
anonymous
Yegor Chumakov founder в startup 21.04.2020 10:31

В чем смысл жизни.

Відповісти
Підтримати
Oleksandr Golovatyi -`★´- в ☁︎ 24.04.2020 05:57

Може не всі знають, але 42 — не випадкове число і насправді означає щось цілком конкретне.

Відповісти
Підтримати
anonymous
Denys Poltorak opentowork: Embedded / C++ 26.04.2020 14:52

скоріше
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”).

Відповісти
Підтримати
Oleksandr Golovatyi
Мавпа программиста 21.04.2020 09:30

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

Відповісти
Підтримати
Мавпа программиста 21.04.2020 21:53

А с такими цветовыми условиями — задача вообще не решаема :(

Відповісти
Підтримати
Alex Fogol
Nik Ospnko 21.04.2020 11:33

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

Відповісти
Підтримати
anonymous
Nickolay Maletsky Senior Software Engineer в EPAM 21.04.2020 12:51
автоматический клининг задней части туловища коров

на изображении?

Відповісти
Підтримати
Nik Ospnko
Фрэнк Сайдботтом 21.04.2020 13:49

В пocтcoвкe фермерство остается во многом не автоматизированным.

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

Фермерство Финляндии, по сравнению с пocтcoвкoм, выглядит пришельческим:
1) youtu.be/ekP_L2k5FgI
2) youtu.be/q81w201PNUM

Відповісти
Підтримати
anonymous
Фрэнк Сайдботтом 21.04.2020 16:34

Там не совсем роботы, и даже не квадрокоптеры какие-нибудь.

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

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

Відповісти
Підтримати
anonymous
Denys Poltorak opentowork: Embedded / C++ 26.04.2020 15:37

От автодоилок молоко за 2 дня скисает. А если руками — до недели стоит в холодильнике.

Відповісти
Підтримати
anonymous
Denys Poltorak opentowork: Embedded / C++ 26.04.2020 16:47

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

Відповісти
Підтримати
anonymous
Andrii Sevastianov Senior Developer в HCLTech 21.04.2020 08:55

Если на собеседовании, то для данного числа uint64_t а, найти наименьшее число b, такое что b > a && pop_count(b) == pop_count(a). Максимально эффективно с точки зрения призводительности, без циклов и условий вообще . Функция pop_count возвращает число установленных в единицу бит.

Відповісти
Підтримати
Valeriy Shvets Engineer в Phonexa 21.04.2020 09:41

Сдвинуть первую младшую единичку (в двоичном представлении) влево, у которой там стоит 0. Но без условий и циклов, чёт мне никакие xor|or с масками в голову не приходят.

А вообще странный вопрос для собеса.

Відповісти
Підтримати
Andrii Sevastianov
code monkey 21.04.2020 09:48
Сдвинуть первую младшую единичку

алгоритм немного сложнее, но в целом согласен, вопрос для интервью странный

www.geeksforgeeks.org/...​-same-number-of-set-bits

Відповісти
Підтримати
Valeriy Shvets
Andrii Sevastianov Senior Developer в HCLTech 21.04.2020 11:22
алгоритм немного сложнее, но в целом согласен, вопрос для интервью странный

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

Відповісти
Підтримати
code monkey
Andrii Sevastianov Senior Developer в HCLTech 21.04.2020 11:34

Обычно в битах, хотя возможно будут и исключения :)

Відповісти
Підтримати
anonymous
Дима Дима 21.04.2020 17:25

Вот таким образом народ и палится)

Відповісти
Підтримати
anonymous
Дима Дима 21.04.2020 20:48
Я формошльоп

я тоже

В чому?

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

Відповісти
Підтримати
anonymous
Andrii Sevastianov Senior Developer в HCLTech 21.04.2020 13:54

Угу, расскажи разработчикам шахматных движков :) Хранить позицию в виде битовых масок — самый эффективный путь. Например, берём битовую маску наших пешек, сдвигаем на восемь, делаем & с маской всех свободных клеток и моментально получаем маску всех возможных ходом. И если замаскировать пешки на вертикали «a», сдвинуть на семь и сделать & с маской всех вражеских фигур плюс поле взятия на проходе мы сразу же получаем все взятия пешками влево.

Не говоря о том, что у нас позиции храняться в регистрах, и нам даже в память лезть не надо.

Відповісти
Підтримати
anonymous
Andrii Sevastianov Senior Developer в HCLTech 21.04.2020 11:15

110 -> 1001 а не 1010
Ну и понимание битов там требуется немного больше xor/or/масок.

Відповісти
Підтримати
Valeriy Shvets
Andrii Sevastianov Senior Developer в HCLTech 21.04.2020 11:33

101100 -> 110001, как-то не получает просто заменить

Відповісти
Підтримати
Михаил Кузьмин
Nik Ospnko 21.04.2020 11:39

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

Відповісти
Підтримати
Andrii Sevastianov
Andrii Sevastianov Senior Developer в HCLTech 21.04.2020 11:41

Ну... 64 маски для нахождения первой единицы? Долго, быстрее выполнится a & (-a) Далее тоже неоптимально, нам надо установить первый нуль после последовательности единиц в единицу, а остальные сдвинуть вправо.

Відповісти
Підтримати
Nik Ospnko
Nik Ospnko 21.04.2020 11:50
a & (-a)

а как получается что такой хак дает младшую единицу?

Відповісти
Підтримати
Andrii Sevastianov
Andrii Sevastianov Senior Developer в HCLTech 21.04.2020 12:26

Надо понимать, что минус это инверсия всех бит плюс один. Например, 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.

Відповісти
Підтримати
Nik Ospnko
Олексій Пєніє 21.04.2020 10:34

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

Объясняю почему: такие задачи в реальной работе ставятся раз в никогда. А если когда и попадается что подобное (разумеется сильно далёкое от того что дали на собесе), то оно делается с RTFM, несколько раз проверяется, включая возможные крайние условия, а потом ещё и тестами покрывается дабы потом какой оптимизатор делов не натворил. А сверху ещё 1.5-2 килознака комментов, почему так, зачем так надо, и что пробовали до этого и не сработало.

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

Чисто на логику — это в любом случае условие, и неважно через какую жопу его заменили, это всё равно достаточно тяжёлые с точки зрения современных процов операции сдвига бит. То есть производительность здесь будет чисто ТЕОРЕТИЧЕСКАЯ, на практике же придётя понимать, есть ли у тебя ПАРАЛЛЕЛЬНЫЙ процессор, или ПОСЛЕДОВАТЕЛЬНЫЙ конвейр тебя устроит. Результат будет сильно зависеть от того, на чём выполняется код.

Решение в лоб — просто добавлять 1 к a покуда условие не выполнится (вероятностно это самый быстрый вариант). Но тут же «без условий»... а значит через жопу. Ну и разумеется, как же вы без условий намерены ловить исключение переполнения??

Відповісти
Підтримати
Andrii Sevastianov
Andrii Sevastianov Senior Developer в HCLTech 21.04.2020 10:57
Ну и потом, с точки зрения производительности первой нужно выкинуть функцию, заменив её куском ассемблерного кода.

Ой, какой смысл заменять шесть операторов С на шесть асемблерных команд?

Решение в лоб — просто добавлять 1 к a покуда условие не выполнится (вероятностно это самый быстрый вариант).

Ну... от (1 << 50) до (1 << 51) долго прибавлять придёться. Вообще, практический смысл такой. Есть 52 карты, по битику на карту. Мы хотим быстро перебрать все варианты флопа/тёрна/ривета (пять карт) итого 52 choose 5 = 2598960 вариантов. Ты же предлагаешь по единичке перебирать 2^52 = 4.5e+15...

Відповісти
Підтримати
Олексій Пєніє
Олексій Пєніє 23.04.2020 02:04

Объясни, что не так с добавлением? Задача — получить НАИМЕНЬШЕЕ b, которое больше a (читай, начиная от a+1), число 1 в битах такое же.
С гарантией 50% это случится после первого же сложения, то есть ОДНА операция. Из оставшихся — гарантия 50% что после второго, и так далее. Задача поддаётся параллелизации.

Учитывая условие задачи, вангую что для сохранения числа бит нужны весьма специфические числа, например 100 + 1 = 101, не подходит, а 101 + 1 — подходит. Итого, атаковать нулевые биты НЕЛЬЗЯ поодиночке, нужно целиться только в единичные. Но так мы имеем УСЛОВИЕ, которые нельзя ставить. Следовательно, придётся использовать суррогаты условий.

Суть условия — просто вычитание, оно же по сути сложение. Потому единственное, почему в условии появился запрет — это задача не на производительность, а на ВЫЗУБРИВАНИЕ «правильного» ответа. Я больше скажу, если окажется тот же ответ, но по-разному записанный, в двух разных версиях той же книги — на собесе это окажется ПРОВАЛОМ, потому что собеседующие не понимают смысла задачи.

PS. Многие задачи кажутся логичными, когда знаешь правильный ответ. Но в реальном мире даже самые элементарные решения вырабатывались СТОЛЕТИЯМИ всем человечеством, а здесь требуют за 1-2 минуты на собеседовании. Соответственно, собес пройдёт кто? Студенты собственных курсов, где предупредили, что будут спрашивать. И тем самым оправдают ФИНАНСИРОВАНИЕ этих курсов — потому что со стороны не наймёшь, одни идиёты.

И казалось бы, причёт тут EPAM, нанимающий >98% штата ITшников со своих же курсов?

Відповісти
Підтримати
Andrii Sevastianov
Andrii Sevastianov Senior Developer в HCLTech 23.04.2020 10:52
С гарантией 50% это случится после первого же сложения, то есть ОДНА операция. Из оставшихся — гарантия 50% что после второго, и так далее. Задача поддаётся параллелизации.

Во-первых, 25%. Только если число оканчивается на 01b мы получим правильный ответ. Во-вторых, мы получаем экспоненциальную сложность. Посчитай, сколько добавлений нам надо сделать, чтобы из 0x1000000000000000ull получить 0x2000000000000000ull.

Відповісти
Підтримати
Олексій Пєніє
Олексій Пєніє 23.04.2020 12:21
мы получаем экспоненциальную сложность.

C той же экспоненциальной вероятностью, что она случится. Иначе говоря, задачу следует решать ТОЛЬКО ЕСЛИ она имеет сколь-либо реальную нагрузку. Например, это какая-то функция контроля и т.д. В этом случае анализ покажет, что добавлять надо не 1, 2, 3 и так далее, а только заранее предусмотренный набор констант и их комбинаций. Более того, так можно решать задачу грубой прикидкой с последующим уточнением — это экспоненциально снижает мат.ожидание, вплоть до 1 операции если это может быть сделано в параллель.

В данном случае, повторюсь, ЗАДАЧУ ПОДОГНАЛИ под красивое решение. С тем же успехом можно на собесе мерять письку, заранее зная кого хочешь принять и сколько у него и при каких условиях. Прям золушка современности.

Как результат — ПОИСК СОТРУДНИКА стал задачей с экспоненциальной сложностью. Хотя задача решается с обратной экспонентой вероятности: ЕСЛИ такая задача попадётся в реальности [с мат.ожиданием раз в миллион человеко-лет], можно найти 1 раз эксперта, который её решит за вменяемую цену, а то и бесплатно.

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

Відповісти
Підтримати
Andrii Sevastianov
Олексій Пєніє 23.04.2020 12:35

Не слышал о таком в реале.
Правило 34 доказывает, что его не существует.

Відповісти
Підтримати
anonymous
Олексій Пєніє 24.04.2020 11:16

Правило 34: обо всём есть прон.

Соответственно, если прона нет — этого не существует. Обратное утверждение не есть истинно, прон может быть и о несуществующих вещах, если они кому-то зашли как фантастика. Но вот о гендерном балансе прона нет :)

Відповісти
Підтримати
anonymous
Sergey Lysak T/T Lead 23.04.2020 14:20
анализ покажет, что добавлять надо не 1, 2, 3 и так далее, а только заранее предусмотренный набор констант и их комбинаций.

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

вспомнилась история, еще с 70ых, как один молодой да «крутой бывший математик» пришел в контору которая пишет ПО для эмбедеда.
глянул код расчета косинусов-синусов, ахнул, и ловко переписал.

А лид глянул, и так лукаво:
ну, красивее конечно чем наши таблицы коэфов, по которым происходит мудреный поиск...
но понимаешь, это ПО часто будет работать на процессорах где норальных ни деления, ни умножения нет.
поэтому твоя красота — на порядки медленнее будет работать.
а зашить в ПЗУ таблицу коэфов — не проблема, на этом особо незачем экономить.
И да, конечно, в твоем алгоритме точность выше, но понимаешь, на практике такая точность не нужна, чтобы тратить на нее ценные такты...

Відповісти
Підтримати
Олексій Пєніє
Олексій Пєніє 24.04.2020 11:40
на практике такая точность не нужна, чтобы тратить на нее ценные такты...

Это точно не я писал? Обычно мне приходится разъяснять эти простые вещи — что оптимизировать нужно финансы, а не понты.

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

Відповісти
Підтримати
Sergey Lysak
Олексій Пєніє 23.04.2020 01:42

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

Відповісти
Підтримати
anonymous
Олексій Бессараб Програміст 1С 21.04.2020 12:23

Перепроверил имя, думал — Владимир.

Відповісти
Підтримати
Олексій Пєніє
flyman 23.04.2020 12:56

а через наслідування можна? бажано ромбічне

Відповісти
Підтримати
Олексій Пєніє
Serhii Symonenko Software Engineer 21.04.2020 16:06

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;
}
Відповісти
Підтримати
Andrii Sevastianov
Andrii Sevastianov Senior Developer в HCLTech 21.04.2020 18:37

Да, так. 

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 если есть инстрикт).

У Д. Кнута этот трюк называется хаком Госпера, там в упражнении обратная задача, по искхонику определить, что делает код.

Відповісти
Підтримати
Serhii Symonenko
Serhii Symonenko Software Engineer 21.04.2020 18:54

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

Відповісти
Підтримати
Andrii Sevastianov
Serhii Symonenko Software Engineer 21.04.2020 18:58

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

Відповісти
Підтримати
Andrii Sevastianov
Михаил Кузьмин 21.04.2020 20:34
позволяет выиграть вычислительную сложность (вместо линейной — константная).

Решение красивое, но проверка в лоб с проверкой условий и сдвигами в цикле это тоже константа.

Відповісти
Підтримати
Serhii Symonenko
Serhii Symonenko Software Engineer 21.04.2020 20:48

Как бы не совсем так.
Линейная всё же, от числа бит зависит (решение в лоб).

Відповісти
Підтримати
Михаил Кузьмин
Olena Sharovar Senior Software Engineer (Billing) in a startup 21.04.2020 21:26

Константная сложность это когда для любого количества бит нужно например 20 операций (одно и то же количество хоть для 1 бита хоть для 1 миллиона битов).
Линейная сложность это когда для 5 бит нужно 5 операций, для 10 — 10, для 20 — 20, для 1 млн — 1 млн.

Відповісти
Підтримати
Михаил Кузьмин
De Money 22.04.2020 01:55

У рамках uniform cost model — ні. І якщо у вас інти стандартні, а не бігінт якийсь (як, наприклад, у кріптографії трапляється) — то використовується саме вона. Інакше виходить, що робота із числом n, взагалі будь-яка робота — це log(n). Бо шоб записати/прочитати це n — треба log(n) біт. Ну, тобто взяття елементу масиву по індексу n — не константа, а log(n). A+B додати — щось log(A+B) складність має ітд. Але вважають число біт у інті константним. І тому перебор хоч 1, хоч усіх біт — обмежено константою і тому має константну складність.

Відповісти
Підтримати
Olena Sharovar
Михаил Кузьмин 22.04.2020 06:56
Константная сложность

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

Відповісти
Підтримати
Olena Sharovar
Olena Sharovar Senior Software Engineer (Billing) in a startup 22.04.2020 08:33

В контексте алгоритмов — сложность это хорошо изученная и оцененная штука, все алгоритмы задолго до нас разбили на классы сложности en.m.wikipedia.org/...​ist_of_complexity_classes и linear time complexity это один из классов сложности алгоритмов — DTIME(f(n)) я ж и перевожу «linear time complexity» как «линейная [временная] сложность» а не зависимость

Відповісти
Підтримати
Михаил Кузьмин
Olena Sharovar Senior Software Engineer (Billing) in a startup 22.04.2020 09:29

Осталось разбить все жизненные вопросы на классы сложности, найти решения и дело в шляпе! :DD

Відповісти
Підтримати
anonymous
Михаил Кузьмин 22.04.2020 11:47

Осталось мелочи. Начать и кончить. Пока там конь не валялся.

Відповісти
Підтримати
Olena Sharovar
Михаил Кузьмин 22.04.2020 11:46
В контексте алгоритмов — сложность это хорошо изученная и оцененная штука,

Само понятие алгоритм за последние года 3 изменилось.
ru.wikipedia.org/wiki/Алгоритм
Попрошу обратить внимание на следующее: «В старой трактовке вместо слова „порядок“ использовалось слово „последовательность“, но по мере развития параллельности в работе компьютеров слово „последовательность“ стали заменять более общим словом „порядок“. Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.» Дело в том, что обычно имеются в виду детерминированная машина Тьюринга в качестве исполнителя. Имея в виду именно детерминированность программы формулируется и сложность по Колмогорову. Однако физический мир не детерминированный. И возникают и новые архитектуры и языки в которых вопросы сложности и работы вообще по другому формулируются. Во всяком случаем я этим и занимаюсь. Весьма удачно в смысле практического результата и не удачно в смысле финансов))

Відповісти
Підтримати
Olena Sharovar
Andrii Sevastianov Senior Developer в HCLTech 22.04.2020 08:24

Константа, только коэффициент при ней может отличаться на два порядка.

Відповісти
Підтримати
Михаил Кузьмин
Михаил Кузьмин 22.04.2020 11:49
Константа, только коэффициент при ней может отличаться на два порядка.

У меня вообще сомнения что вы правильно применяете понятие «на два порядка», что по любому константа. Хоть на 3 порядка.

Відповісти
Підтримати
Andrii Sevastianov
Олексій Пєніє 23.04.2020 01:48

То есть РЕДКОЕ решение НИКОГДА не встречающейся задачи кроме как в ОДНОМ учебнике?
Прекрасный вопрос для собеседования! В таком случае нужно потребовать ответить на встречный вопрос: ПОКАЖИТЕ где вы это применили, хоть кто-то из вас.

PS. Это — не решение. Код не читабельный. Объяснения что и почему — нет. А значит никакой гарантии, что он не содержит ошибок. Протестировать его тоже невозможно. Следовательно, этот код подлежит уничтожению и переписыванию заново — что время. За такое и уволить недолго, ибо диверсия.

Відповісти
Підтримати
Andrii Sevastianov
Andrii Sevastianov Senior Developer в HCLTech 23.04.2020 11:27
В таком случае нужно потребовать ответить на встречный вопрос: ПОКАЖИТЕ где вы это применили, хоть кто-то из вас.

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

Объяснения что и почему — нет.

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

Протестировать его тоже невозможно.

Элементарно, один тест более чем справится:

uint64_t mask = 0x7f;
uint64_t counter = 0
while (mask < (1 << 52)) {
    ++counter;
    mask = next_combination_mask(mask)
}
assert(counter == 133784560); // 52 choose 7
Відповісти
Підтримати
Олексій Пєніє
Олексій Пєніє 23.04.2020 12:27

Вот именно. Для написания теста НУЖНО ЗНАТЬ решение и его узкие места. В реальном мире так не работает, ты не знаешь где грабли.

Відповісти
Підтримати
Andrii Sevastianov
Олексій Пєніє 23.04.2020 12:33

Насчёт применения — ты можешь ОБЪЯСНИТЬ СУТЬ хака обычными словами, ЧТО ИМЕННО хакается, какая общая проблема (только без магических слов и сам-догадайся)? И лучше так объяснить, чтобы даже июнь понял, потому что с огромной вероятностью читать код будет именно он.

Я вижу только узкоспецифическую одну задачу и её чисто теоретические вариации.

Відповісти
Підтримати
Andrii Sevastianov
Artyom Krivokrisenko 21.04.2020 03:20

После того, как в новойо команде обновил приложение, чтоб оно работало с новой версией сетевого драйвера, начались kernel panic. Разработчики драйвера говорят — «Хз, у всех все работает, ты первый, кто пожаловался. Иди разбирайся в своем приложении». Разработчики приложения — «Сам подумай, как приложение может вызвать kernel panic? Это какая-то хрень в драйвере». В итоге за 3 недели ковыряния с кентами в потрохах всего, что можно было, героически выяснили в чем проблема, но все это время в голове витала мысль «фак, надо было оставаться в старой команде»

Відповісти
Підтримати
Left Outer Join 21.04.2020 03:21

а что в итоге пропатчили, ядро или приложение

Відповісти
Підтримати
Artyom Krivokrisenko
Olena Sharovar Senior Software Engineer (Billing) in a startup 21.04.2020 09:38

Жаль, а то бы миллиончик usd получил

Відповісти
Підтримати
code monkey
Ruslan Teliuk Software Engineer 21.04.2020 10:49

А что тут сложного? Либо P=0 либо N=1

Відповісти
Підтримати
code monkey
Seven Berg 21.04.2020 02:52

Вот вспомнил задачу, которую мне задала хрюша, сколько кошек в вашем городе?Кто то знает ответ?

Відповісти
Підтримати
code monkey 21.04.2020 03:16

ну эта простая, для начала надо выснить сколько заправок в юса и сколько настройщиков роялей в Сиэтле, и дальше станет понятно:

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

Відповісти
Підтримати
Seven Berg
John Appleseed 21.04.2020 18:45

Вот ещё немного его маразмов:

....
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.

Сейчас вместе с этим и задачами про рояли маразм масштабировался на всё айти.

Відповісти
Підтримати
code monkey
John Appleseed 21.04.2020 09:45
Вот вспомнил задачу, которую мне задала хрюша, сколько кошек в вашем городе?

Длинное объяснение:
1. Кошек примерно столько же, сколько и котов, с поправкой, что кошки погибают при родах, а коты — в котячьих драках.
Проигравший кот с выцарапанным глазом имеет шансы по неосторожности угодить под спешающую на работу октавию в родном дворе.
Победитель — потратит силы на оплодотворение кошки и на заплетающихся ногах не успеет перебежать дорогу. Итог — тот же.

Короткое объяснение:
2. Покрытие кошками моего города выше, чем покрытие тестами вашего проекта.

Відповісти
Підтримати
Seven Berg
Dmytro Shchurov Frontend/React Developer в KAJO s.r.o. 21.04.2020 12:26

Это уже отсебятина. В оригинале было: «месячное потребление бензина автомобилями в городе».

Відповісти
Підтримати
Seven Berg
Seven Berg 21.04.2020 02:50

Объяснить РМ-ке почему программы не пишутся за 15 минут...

Відповісти
Підтримати
Seven Berg 21.04.2020 17:57

у неё выражение такое было- это задача на 15 минут...

Відповісти
Підтримати
anonymous
Ciemna noc 20.04.2020 23:49

на литкоде есть раздел hard и там обычно не выше 25%^^’, а еще ничего их на время решать

Відповісти
Підтримати
Олексій Пєніє 21.04.2020 01:40

а еще почему инфоцыгане литкода не пользуются вазелином
[но это не точно]

Відповісти
Підтримати
Ciemna noc
Ciemna noc 21.04.2020 02:05

Саша, ничто не стоит так дёшево и не ценится так дорого, как вежливость. Это не я, это Чехов)

Відповісти
Підтримати
Олексій Пєніє
Олексій Пєніє 21.04.2020 05:28

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

Аналогия: «фдыовгвчыяш» — как поймёт это японец?

PS. Это эталон инфоцыганства: сами ни в зуб ногой, зато учить аж бегом. И я считаю, за попытку спама инфоцыганщиной бан должен прилетать моментально. Равно как и бан всех ссылок и регистрация их в базах для ЭдБлока.

PPS. И верни «цитату чехова» Дон Кихоту

Відповісти
Підтримати
Ciemna noc
Ciemna noc 21.04.2020 15:39

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

Відповісти
Підтримати
Олексій Пєніє
Bot Bot 20.04.2020 23:14

Задача про два стула! Очевидно же! :-))

Відповісти
Підтримати
Victor Mikhaylov junior manual tester 06.05.2020 11:36

про реакт точеный и ангуляр др*ченый?

Відповісти
Підтримати
Bot Bot
Tymchyshyn Vitalii Researcher 20.04.2020 22:02

В мене самого трохи специфічні задачі: в основному я стараюсь займатись я̶к̶о̶ю̶с̶ь̶ ̶ф̶і̶ґ̶н̶ь̶о̶ю̶ чимось, де треба хоч трохи «писати формули на папері», і з них важко виділити найскладнішу. Проте, все одно розкажу про найбільш прикольну задачу, щоб хоч трохи розбавити це нескінченне порівняння кефіро-метрів квадратних з розміром податків в США.

Давним-давно, в сусідній команді для чогось треба було відображати текст на фоні довільного кольору; колір тексту треба було вибирати на льоту і так, щоб його було добре видно. Вони попросили дизайнерів підібрати кілька добрих прикладів кольорів текст-фон, а потім написали функцію, що інтерполює між ними. Іншими словами: є функція, що приймає трійку чисел 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], то котрась точка перейде сама в себе — функція видасть для тексту колір, що в точності співпадає з кольором фону (ясно, що такого тексту видно не буде і відповідні тести попадають). Що робити в такій ситуації? Ну я порадив їм «порвати» функції — інтерполювати чимось розривним, щоб теорема стала непримінимою.

Відповісти
Підтримати
Yuriy Zaliznyak regular pizza delivery officer 22.04.2020 22:42

странно. банаха слыхал. брювера єтого не слыхал.

Відповісти
Підтримати
Tymchyshyn Vitalii
Tymchyshyn Vitalii Researcher 22.04.2020 22:51

тих теорем про непорушну точку так багато, що я не впевнений, чи їх всі хоч хтось знає )) (en.wikipedia.org/...​t_of_fixed-point_theorems ).

Відповісти
Підтримати
Yuriy Zaliznyak
Tymchyshyn Vitalii Researcher 23.04.2020 01:03

Продовжу розбавляти політику темою прикольних задач і потравлю ще трохи «байок зі склепу» ))

Задача, яку мені задавали два рази підряд

Один мій товариш захопився 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. Стільки всього, бо задача виявилася дійсно класною, хоча спочатку так не здавалось.

Відповісти
Підтримати
Tymchyshyn Vitalii
Andre --- в none 27.04.2020 00:57

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

Відповісти
Підтримати
Tymchyshyn Vitalii
Tymchyshyn Vitalii Researcher 04.05.2020 02:40

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

Відповісти
Підтримати
Tymchyshyn Vitalii
Михаил Кузьмин 20.04.2020 20:59

Самое сложное это думать.. Остальные сложности решаются деньгами и толпой. Я б даже не назвал это сложностями.

Відповісти
Підтримати
anonymus ps 20.04.2020 19:41

от ща у меня такая — построить реальную кросс-проектную команду

Відповісти
Підтримати
Olena Sharovar Senior Software Engineer (Billing) in a startup 20.04.2020 22:11

Про кроссфункциональные слышала, а кросспроектная это как? Люди парт-тайм на нескольких проектах?

Відповісти
Підтримати
anonymus ps
anonymus ps 20.04.2020 22:38

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

Відповісти
Підтримати
Olena Sharovar
Олексій Пєніє 21.04.2020 05:33

Вголосинушку! Вы б ещё хирургов во время операции ротировали.

Львиная доля времени уходит на банальнейшее чтение кода и изучение через жопу написанных материалов, щедро смешанных с информационным мусором. И всё это множится на нолик при смене проекта. Конечно, если это реальные проекты, сложные, а не формошлёпка с CRUDом.

Была бы формошлёпка — не приходилось бы ротацию делать.

Відповісти
Підтримати
anonymus ps
anonymus ps 21.04.2020 08:11

Ясен красен что тебя из-за монитора там виднее

Відповісти
Підтримати
Олексій Пєніє
Мавпа программиста 21.04.2020 09:29

У них agile и cross-functionality, а так же t-shape & flat hierarchy.

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

Відповісти
Підтримати
Олексій Пєніє
Left Outer Join 21.04.2020 14:42

а хирургов во время операции иногда таки ротируют

Відповісти
Підтримати
Олексій Пєніє
Олексій Пєніє 23.04.2020 03:15

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

Відповісти
Підтримати
Left Outer Join
Left Outer Join 23.04.2020 03:35

Нет, потому что предыдущий хирург устал

Відповісти
Підтримати
Олексій Пєніє
Andrey MK 20.04.2020 19:35

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

Відповісти
Підтримати
Left Outer Join 20.04.2020 18:59

Правильно инициализировать контроллер памяти DDR2

Відповісти
Підтримати
Left Outer Join 21.04.2020 03:24

в ibm pc память тоже не сама по себе заводится

Відповісти
Підтримати
anonymous
Рахіт Срінавасович Кумар 20.04.2020 18:57

организовать отпуск с семьей и отдохнуть

Відповісти
Підтримати
Olena Sharovar Senior Software Engineer (Billing) in a startup 20.04.2020 21:28

... а также когда инвалидировать кэш

Відповісти
Підтримати
Олексій Пєніє
Олексій Пєніє 21.04.2020 01:38

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

Відповісти
Підтримати
Olena Sharovar
Олексій Пєніє 21.04.2020 05:38

Во времена 2000-ной винды помнится обязали Майкрософт к какому-то там пониманию формата файлов для Applе. Так вот, системная библиотека обеспечения совместимости, которая работала разумеется как попало, носила имя файла avothui.exe

В последующих апдейтах это разумеется потёрли.

Відповісти
Підтримати
anonymous
Bohdan Horbeshko 12.06.2020 23:27

А пруфы за давностью лет протухли? Речь о QuickTime’овских форматах или других каких-то?

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

Відповісти
Підтримати
Олексій Пєніє
Олексій Пєніє 13.06.2020 11:11

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

Відповісти
Підтримати
Bohdan Horbeshko
Bohdan Horbeshko 13.06.2020 15:02

Печально. Надо тогда больше подробностей: годы, какая винда (таки Win2K или другая), какой программе мешало...

Я и прецедентов-то таких найти не могу пока, чтобы Microsoft с Apple в те времена как-то вздорили, или чтобы антитрасты прикапывались к M$ за неподдержку чего-то Apple’овского... За тёрки с Novell знаю, за Netscape знаю, за Microsoft JVM знаю, за более позднее выпиливание WMP для Европы знаю, но такого...

Может, это и вовсе не в M$ похулиганили, а просто вирус-приколист в C:\WINNT\ нагадил? :)

Відповісти
Підтримати
Олексій Пєніє
Олексій Пєніє 13.06.2020 19:27

Тоже сначала так подумал, но проверка файла показала что таки M$ признаёт его контрольную сумму.

Відповісти
Підтримати
Bohdan Horbeshko
Фрэнк Сайдботтом 20.04.2020 15:51
или квартиру

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

Відповісти
Підтримати
anonymous
Фрэнк Сайдботтом 20.04.2020 15:58

3. Дом на возвышенности.
Но, вроде как, именно это и может задирать цены в Штатах, потому что виды многих точно так же привлекают.

Відповісти
Підтримати
anonymous
Рахіт Срінавасович Кумар 20.04.2020 18:58

HOA в сердце нежно ударит тебя через кошелек

Відповісти
Підтримати
anonymous
code monkey 20.04.2020 22:53

HOA может и будет, но на дом она до 200 баксов в месяц, на таунхоум чуть больше, хоа на кондо в новом доме со бассейнами и тренажерками будет стремиться к 1k.

Відповісти
Підтримати
anonymous
code monkey 20.04.2020 23:30
ты по прежнему еб**ся со всей утварью в доме

хз что ты под этим понимаешь, если расходы на поддержание дома то эта концепция на доу сильно овверрейтед, в новом доме первые 5 лет вообще ничего делать не надо, гарантия bumer-to-bumper на первые 3, structural на 10.

С домиком в годах можно попасть на дорогой ремонт, типа крышу поменять, но это один раз 30-40k на следующие 20-40 лет. Все остальное не так страшно, можно делать сомому, можно по надобности кого-то нанимать.

Відповісти
Підтримати
anonymous
anonymous 20.04.2020 23:39
Все остальное не так страшно

Особенно когда на третьем этаже лопнет труба и зальёт до подвала.

Відповісти
Підтримати
code monkey
anonymous 20.04.2020 23:40

а что ты хотел за $200? Семь прекрасных наложниц?

Відповісти
Підтримати
anonymous
anonymous 20.04.2020 23:56

У меня HOA $400 и мне понятно за что. Они всё время чистят что-то, сейчас дизенфицируют, бассейн поддерживают в чистоте, перекладывают асфальт на парковке, недавно всё перекрасили. Поменяли лампочки на LED. Бесплатно почистили камин, чистят снег на парковке зимой.

Відповісти
Підтримати
anonymous
anonymous 21.04.2020 00:45

HOA для частного дома это развод чистой воды.

Відповісти
Підтримати
anonymous
Olena Sharovar Senior Software Engineer (Billing) in a startup 20.04.2020 15:59

Вот-вот, самые сложные задачи не технические

Відповісти
Підтримати
anonymous
Alex Fogol Software Developer, C/C++ Expert 21.04.2020 15:54
Не послать начальника-самодура, пока был на л1 визе

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

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

Відповісти
Підтримати
anonymous

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

Не підписуватись
Скористайтесь акаунтом
×
з умовами використання сайту і політикою конфіденційності.