Программирование, Путешествия, Покер

Немного оффтопа, может кому интересно будет.
Наткнулся на вступительный курс по программированию (на Java) от Стенфорда:
https://www.youtube.com/view_play_list?p=84A56BC7F4A1F852

я бы ещё уколол :

каждая строка содержит целое положительное число....
0 11
0 12
11 12

Метод вернет список...

ничего не вернёт список.

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

Спустя 2 недели пришел ожидаемый ответ от "Одноклассников"
Я потом еще раз подумал над своими ответами на вопросы теста и нашел ошибку, может в этом дело было. Если верить тому, что написано, то видимо моя вариация решета не пошла. Боевой слон верно подметил тогда, что моя реализация не очень похожа :)

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

Неожиданно, опять же спустя 2 недели, получил письмо от Grid Dynamics с дефолтным предложением пройти тест по джаве. Большой плюс, что там были более сложные вопросы, занимает он максимум 15 минут и проходится онлайн. Фидбека пока не было.

Завтра схожу еще на одно внутреннее собеседование.

По задаче со списком цифр - в файле более 16 миллионов строк, дельфи тут явно придется попотеть.

Galax @ 23.5.2017
объект TList имеет ограничение (по-моему 16380 элементов)

Каким образом можно сделать более длинный список? 16к элементов это как-то совсем несерьезно. Или надо делать цепочку из таких листов?

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

ChillLEO @ 17.5.2017
В чем кайф от работы, ты как я понимаю, его получаешь?

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


Что касается второго типа - багов. Именно те, которые доставляют неудобства и не решаются шаблонно (к примеру, которые трудно или просто невозможно воспроизвести), или связаны не с вашим кодом, тоже приносят большое удовлетворение от решения.
Опять же, пример из жизни:


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

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

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

Как-то так.
P.S. задавайте вопросы, они вдохновляют на написание лонгридов :)

Я больше по С++, но думаю в данном случае с Джавой не должно быть разницы.
Лучшего алгоритма, чем предложил Galax, мне в голову не приходит. C парой уточнений:

Galax @ 23.5.2017
1. Проверяем весь список и ищем Номера задачи, где счетчик равен 0 - это искомые номера задач для данной итерации, выводим их.
...
3. Удаляем из списка все записи с только-что найденными номерами.

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

На счёт структуры хранения - я сторонник использования обычных динамических массивов (std::vector в С++, в Java видимо ArrayList) везде, где только можно :).

То бишь я бы делал так:
1) Сначала нужно сопоставить каждой задаче уникальный индекс от 0 до N без пропусков. Для этого использовал бы TreeMap (std::map в С++). В качестве альтернативы можно записывать всё в вектор и потом его отсортировать. При отсутствии повторов это должно работать быстрее, но у нас повторы есть, поэтому не знаю как лучше.

2) Затем создаём и заполняем массив таких структур:
struct TaskInfo {
int taskNumber; //Соответствует дереву из пункта 1.
std::vector<int> childTasks; //Здесь мы уже храним индексы этого массива, а не "настоящие" номера задач!
int numberOfParentTasks;
};

3) А дальше реализуем алгоритм Galax'а с указанными уточнениями. Благодаря массиву нам теперь не нужно "искать" зависимые задачи по их номеру - просто используем индексы и всё. Только в самом конце, уже при выводе результата, вместо индексов выводим значения taskNumber.

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

Upd. В 1 Гб вроде тоже должны вписаться.

БоевойСлон, на самом деле, мне кажется что тут вообще трудно придумать другой алгоритм :)
Касательно написанного тобой -

БоевойСлон @ 24.5.2017
Сначала нужно сопоставить каждой задаче уникальный индекс от 0 до N без пропусков. Для этого использовал бы TreeMap (std::map в С++). В качестве альтернативы можно записывать всё в вектор и потом его отсортировать. При отсутствии повторов это должно работать быстрее, но у нас повторы есть, поэтому не знаю как лучше.

Зачем тут использовать какую-то дополнительную структуру данных для каких-то индексов. Номер задачи (в виде стринги или инта) уже является индексом, разве нет?
В сортировке я тоже смысла не вижу.

Я написал следующее.
Парсим файл и запихиваем данные в хэш-мапу (HashMap в джаве), где ключом является номер таски (для простоты оставил их текстом, ибо в парсинге числа из строки смысла не увидел), а значением - структура, похожая на указанную тобой. Выглядит он следующим образом:
class Node {
int counter;
List<Node> nodes = new ArrayList<>();
boolean visited;
}
флаг visited нужен для удобства поиска (видно будет ниже)

Когда парсим, мы увеличиваем счетчик у второй ноды, а в список первой добавляем вторую. Например, при добавлении "2 22" будет одна нода со списком из одного значения "22" , значением "2" и счетчиком 0, а другая со значением "22", пустым списком и счетчиком = 1.

Затем просто итерируемся по мапе. Проверяем флаг visited и счетчик. Если visited = false и счетчик = 0, то мы добавляем значение в список результатов, и для всех зависимых нод меняем флаг на true (чтобы пропускать их, т.к. все равно на этом прогоне их не будем обрабатывать) и уменьшаем их счетчик на один. Затем текущая пара ключ-значение удаляется.

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

Затем проверяем, остались ли записи в мапе. Если они остались, это означает что у нас есть цикл и кидается исключение.

Вроде как должно быть правильно :) По крайней мере, на меньшей выборки из самого текста задания отработало правильно. На моей машине с хипом в 1 Гб выдало 20 секунд и 32 листа в итоговом списке. Понятно, что результат это очень примерный (я про время) и может быть заметно больше при первом запуске кода. Да и способ замера не лучший.

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

Если кому интересно, код выложил сюда.

strkk @ 25.5.2017
Зачем тут использовать какую-то дополнительную структуру данных для каких-то индексов. Номер задачи (в виде стринги или инта) уже является индексом, разве нет?

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

Написал на шарпе, получился расход по памяти около 500МБ без оптимизаций (можно еще сильно допилить), время выполнения тоже очень шустрое, правда не имею ни малейшего понятия как это проверять на таком диком наборе данных (результат на большом файле выглядит странновато, хотя тестовый набор данных отрабатывает корректно )

strkk @ 25.5.2017
и 32 листа в итоговом списке.

Походу это правильно ) Радует )

strkk, Сколько народу было в java-школе всего и сколько из них взяли на работу (если кого-то не взяли, у тебя есть мысли почему)? Можешь оценить свой скилл на момент поступления в школу(если можно в покерном эквиваленте, типа бил в ноль nl50, так будет понятнее), после окончания, и на сегодняшний день? Как считаешь у тебя была предрасположенность к программированию или ты "как все"? И еще одни, возможно не очень понятный вопрос: у человека не знакомого с программирование, задания, которые тут тут выкладываешь, должны вызывать сложности с логикой? Т.е. понятно, что я не знаю команд, методов каких-то и тд, но у меня в голове должно это как-то решатся на логическом уровне, или это придет с опытом (или не придет)?

Реализовал свою версию решения этой задачи с одним проходом по дереву задач.
В итоге это заняло у меня 670 Мб памяти (heap не ограничивал, просто посмотрел через Task Manager сколько памяти выжралось), чтение из файла 37.149 seconds, собственно решение 5.42 seconds, число групп 32.

P.S. Единственное, чего я не понял, это какие сроки выделялись на решение данной задачи? Я так понял, ее давали на дом...

Привет,
по задаче, самое корректное будет использовать паттерн "Стратегия", Fork/Join + Stream Api ( + распараллеливание, но тут аккуратнее, если тебе нужно нативное упорядочивание, то лучше не распараллеливать поток), так же я бы сделал отдельный таск на groovy в gradle который тоже выполнял бы распараллелив и ранил бы через batch файл.
Так как не указано, какой тип GC можно использовать, я бы насильно подрубил G1 или Shenandoah, что невероятно поможет сократить время на collection без всяких stop the world.
Если будет время на работе, сделаю таск по такому принципу, архитектура с этим паттерном будет вполне себе отвечать SOLIDу.
UPDATE:
если будешь писать на JDK1.8+, то OutOfMemory словишь, только когда убьёшь все ресурсы на компе, т.к. в 8ушке нет перма, а вместо него метаспэйс, который динамически может расширяться.
UPDATE2:
помогай JVM инлайнить и скалиризовать данные.

Снова про собеседования.

Завтра пойду общаться с Grid Dynamics, вроде как неплохая компания, куда ушли несколько моих бывших коллег. Видимо, их тест я прошел успешно. Также из плюсов - это расположение.

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

Доброго дня снова.

Может все-таки побеседуем у нас в офисе, если Вы уже не нашли железно новое место, почему нет?

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

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

Решать задачи проектирования баз данных, в составе Scrum-команды, разрабатывающей Web-
приложения.

Участвовать в разработке Web и Java кода (при условии наличия желания и навыков).

Сопровождать создаваемый продукт.

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

На мою просьбу добавить хоть какой-то конкретики (что за проект, какой стек технологий и т.п.) ответ жду уже 5 дней.

Так же в пятницу общался с одним нашим внутренним проектом, который пилит бэкенд для швейцарских железных дорог. По технологиям там все очень круто, однако график работы это полный швах - начало рабочего дня в 10.30 и заканчивать никак не раньше 19. Про этот проект и их переработки слухи ходят по всей компании, ну и я в этом убедился :) В итоге, несмотря на очень привлекательный стек, отказался. Из-за такого графика работы (даже без учета переработок) придется завязать с теннисом и обучением, а это минус деньги (пусть и небольшие), да и просто некрасиво по отношению к ученикам.

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

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

fragaLY, твое сообщение мне показалось немного странным. Во-первых, задачу уже решили (причем не только я и не только на джаве - см. посты выше), поэтому твои советы в принципе выглядят немного out of date. Пятью постами выше твоего я кидал ссылку на свой код.

fragaLY @ 29.5.2017
самое корректное будет использовать паттерн "Стратегия", Fork/Join + Stream Api ( + распараллеливание, но тут аккуратнее, если тебе нужно нативное упорядочивание, то лучше не распараллеливать поток)

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

fragaLY @ 29.5.2017
я бы сделал отдельный таск на groovy в gradle который тоже выполнял бы распараллелив и ранил бы через batch файл.

Звучит круто, однако опять же встает вопрос - какой в этом смысл? В задании написано, что нужен класс Planner, которому на вход подается путь к файлу с задачами. В моем понимании, это означает упаковку в jar файл и запуск через "java -jar Planner.jar /path/to/file.txt"

fragaLY @ 29.5.2017
помогай JVM инлайнить и скалиризовать данные.

Как например?
К тому же, помогать JVM в оптимизациях можно написанием хорошего чистого кода с использованием best practices. Делать какую-то фигню, полагая что это "поможет" JVM, чревато появлением говнокода.
Ну и да, JVM бывают разные и оптимизации у всех свои, поэтому подобный подход может выйти боком.

Боюсь, ты не понял одного: что требовалось не только решить задачу, а решить её так, чтобы она соответсвовала принципам ООП, SOLID, а так же некоторым критериям, которые были указаны дополнительно.
Ведь при использовании "стратегии" добавить новую реализацию проще простого, у тебя же придётся писать ещё столько же строк кода, который будет совсем неподдерживаем, и чтобы это доказать, просто попробуй написать Unit test на это добро.

Ребята, ну вы блин даете! Я раньше думал, что я не совсем далекий человек от программирования, но я ничего не понял с ваших последних постов. Я думал это какой-то стеб).
По-поводу последней задачки, хотя она уже и не актуальна. Применение хеш-таблицы очень упрощает написание кода и здесь идеально подходит. Но у меня нет поддержки хеш-таблиц и я решил "изобрести" что-то свое и сравнить эффективность.
Мой результат - 12 сек на загрузку файла и 1 сек на решение задачи (комп довольно слабенький). Так что на будущее я буду иметь под рукой довольно эффективный метод работы с большими объемами данных.

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

Galax @ 1.6.2017
Применение хеш-таблицы очень упрощает написание кода и здесь идеально подходит.

В этом плане в джаве проще, хэш таблица доступна с момента создания языка :)

Мы какие-то космические вещи не обсуждаем, просто они более джава-специфичные.

Мерять перфоманс вообще проблематично, а в данном случае (разные языки, машины и условия работы) вообще некорректно, как мне кажется. Тут скорее результат вписались/не вписались в заданный промежуток (1 минута)

Galax @ 1.6.2017
продолжай выносить на обсуждение различные задачи, каждый может почерпнуть для себя что-то полезное.

Да, конечно :)

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

Сегодня иду на еще один собесед. Обо всех своих похождениях расскажу подробно ближе к выходным.

strkk @ 1.6.2017
На позавчерашнем собеседовании получил довольно простую задачу - написать гарантированный дедлок (которому не сможет помешать даже идеальный планировщик задач ОС), используя только примитивы синхронизации (synchronized и volatile) и затупил. В спокойной обстановке решение заняло около минуты, а там не смог сосредоточиться и сделать все как надо (написал негарантированный)

типа такого? wait это вызов synchronized функции (wait and lock). единственное, мне не нравится поллинг

volatile i = 0, j = 0;

f1() {
wait_x();
i = 1;
while (j == 0);
wait_y();
}

f2() {
wait_y();
j = 1;
while(i == 0);
wait_x();
}

FlySoHigh @ 24.5.2017
Немного оффтопа, может кому интересно будет.
Наткнулся на вступительный курс по программированию (на Java) от Стенфорда:
https://www.youtube.com/view_play_list?p=84A56BC7F4A1F852

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

don_eric, да, как раз что-то подобное.

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

ChillLEO, я постараюсь развернуто ответить в выходные. Пока могу отослать к своему старому блогу на стратеджи (ссылка в первом посте), там на последних 5-7 страницах я писал об этом.

fragaLY @ 31.5.2017
Боюсь, ты не понял одного: что требовалось не только решить задачу, а решить её так, чтобы она соответсвовала принципам ООП, SOLID, а так же некоторым критериям, которые были указаны дополнительно.

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

fragaLY @ 31.5.2017
у тебя же придётся писать ещё столько же строк кода, который будет совсем неподдерживаем, и чтобы это доказать, просто попробуй написать Unit test на это добро

Содержимое метода main нажатием трех кнопок выделяется в отдельный инстансный метод, который принимает файл и возвращает список списков задач. К нему добавляется документация-контракт метода (опционально). Юнит тесты для такого пишутся безо всяких проблем. Или это тоже не по SOLID?
Добавление различных паттернов я вижу в данном случае бесмысленным, как и попытки угадать то, что от меня хотят увидеть. Очень странно просить написать 1 класс с 1 методом, чтобы кандидат мог продемонстрировать знание ООП.

P.S. Классическая статья из серии "Паттерны vs ленивое программирование" - Как два программиста хлеб пекли

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

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

Содержимое метода main нажатием трех кнопок выделяется в отдельный инстансный метод, который принимает файл и возвращает список списков задач.

а потом такое поддерживать...