Category: IT-заметки

Про собеседования по программированию. Часть 2.

Часть 1

Телефонное собеседование

Я намеренно опустил момент знакомства с менеджером по найму: они всегда сами находили меня через LinkedIn и предлагали поговорить. Чтобы обратить на себя внимание, кроме писем рекрутёрам могу предложить решение задач, опубликованных на сайте компании. Например, Facebook Programming Challenge или Spotify’s Tech Puzzles.

Также мы не будем говорить о диалоге с hiring manager по телефону и почте, потому что говорить особо не о чем. Разве что будьте готовы к вопросам о своей личности и по пунктам из резюме. Continue reading “Про собеседования по программированию. Часть 2.” →

Про собеседования по программированию. Часть 1.

Я собирался написать большой пост про процесс собеседования в большие иностранные IT конторы, но оказалось, что это довольно хорошо описано в книгах. Например, в первых главах книги «Cracking the Coding Interview: 150 Programming Questions and Solutions, 5th ed», которую мне на днях показали. Поэтому я написал большой пост про то, как это происходило конкретно у меня, и какие полезные выводы я сделал.

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

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

Continue reading “Про собеседования по программированию. Часть 1.” →

Вычислительная геометрия

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

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

Очевидно, нужно найти расстояние между центрами и сравнить его с суммой радиусов:

Continue reading “Вычислительная геометрия” →

Об анализе хеш-функций

Тут относительно недавно пробегали две статьи, в которых авторы затрагивали тему анализа хеш-функций с целью определить, какая лучше: Заметки о реализации hashCode() в Java и Changes to String internal representation made in Java 1.7.0_06 (перевод). В обеих статьях анализ проводился очень простой: генерировалось большое множество объектов нужного типа, для них вычислялись хеш-коды и среди хеш-кодов искалось количество коллизий (совпадений).

Я считаю, что такой анализ недостаточно хорош. Главное применение хеш-функций в Java — это в основанных на хешировании коллекциях, куда объекты складываются, распределяясь по ячейкам (бакетам, bucket) согласно своим хеш-кодам. Количество ячеек ограниченно, поэтому чтобы определить, в какой из них место объекту, берётся остаток от деления хеш-кода этого объекта на количество ячеек, которое из соображений производительности выбирается из степеней двойки. Так вот, равномерность распределения объектов по бакетам играет решающую роль в производительности коллекции, а значит очень важно, помимо количества коллизий, анализировать и её.

Легко показать, что малое число коллизий хеш-функции не всегда коррелирует с равномерным распределением объектов внутри хеш-таблицы. Достаточно взять любую хорошую хеш-функцию f(x) и получить из неё новую: h(x)=2*f(x). Количество коллизий у новой функции будет ровно таким же (для простоты забудем про переполнение), но при этом все её значения будут чётными, и распределение получится очень неравномерным.

Как избегать deadlock’и

Этот вопрос мне задали года полтора назад на первом телефонном собеседовании в Майкрософт. Я ответил что-то невнятное типа «ну концентрировать весь concurrency-related код в как можно меньшем числе классов, чтобы удобнее было разбираться в проблеме». Это собеседование я не прошёл.

Java Concurrency in Practice для решения проблемы дедлоков предлагает, по крайней мере в главе про дедлоки, следующее решение:
If you must acquire multiple locks, lock ordering must be a part of your design: try to minimize the number of potential locking interactions, and follow and document a lock ordering protocol for locks that may be acquired together.

Однако более полный ответ на этот вопрос я увидел, как ни странно, в Чистом коде Боба Мартина, в той главе, которая там вроде как ни к месту. Там приводятся следующие обязательные условия возникновения дедлока:

  • Mutual Exclusion
  • Lock and Wait
  • No Preemption
  • Circular Wait

И предлагаются способы исключить каждое условие:

Mutual Exclusion:

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

От Lock and Wait избавиться можно так: проверяем ресурс перед захватом; если он занят, то освобождаем все захваченные ресурсы. Этот подход может привести к новым проблемам: Livelock и Starvation.

No Preemption: разрешаем потокам запрашивать ресурсы друг у друга. Я никогда в жизни такого не видел и не представляю, как это хорошо реализовать. Пишут, что это непросто.

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

* * *

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

Managing Technical Debt

Годная и подробная статья про технический долг. Основные идеи:

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

Про собеседования

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

  • Проходить собеседования полезно, чтобы быть готовым к чёрному дню. Сюда относится как углубление знаний в предметной области (на интервью задали сложный вопрос → почитал дома что-нибудь по этому вопросу и вокруг него → получил новые знания → повторил), так и общее понимание того, чего на собеседованиях от тебя хотят и что из этого стоило бы подтянуть.
  • С каждым собеседованием всё сильнее привыкаешь, страх постепенно уступает уверенности. Это особенно важно, если собеседования проходят на английском языке: постепенно перестаёшь задумываться о том, как понятно формулировать свои мысли.
  • Если собеседуешься в иностранную компанию, то есть шанс дойти до очного этапа и съездить в другую страну за их счёт. Например, я таким образом побывал в Лондоне и Тель Авиве, куда сам в ближайшее время точно не поехал бы.
  • Понимание текущего состояния рынка труда и своего положения в нём.
  • Возможность в конечном итоге пройти собеседование и получить хорошую работу.

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

Я помню своё первое собеседование (в Microsoft), как был уверен успехе, как негодовал по поводу отказа и, наконец, каким наивным чувствовал себя после подробного изучения заданных вопросов. Время прошло чрезвычайно плодотворно.

Для тех, кто собирается встать на этот нелёгкий путь, я порекомендовал бы начать со следующуей литературы:

  • книга Programming Interviews Exposed: Secrets to Landing Your Next Job;
  • Hacking a Google Interview: сборник типичных задач и паззлов с собеседований.

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

Успехов.

Чистый код

Дочитал наконец «Чистый код» Роберта Мартина (Clean Code: A Handbook of Agile Software Craftsmanship by Robert C. Martin). Книга является сборником советов и правил написания хорошего и улучшения плохого кода. Она может быть интересна в первую очередь программистам на Java.

Миша про эту книгу говорил, что она какая-то капитанская (то есть в ней написаны очевидные вещи — от Капитана Очевидность). Так оно на самом деле и есть, но это не делает её плохой или бесполезной. По мере прочтения я несколько раз осознавал, что некоторые правила хорошего кода я нарушал и продолжаю нарушать. Поэтому считаю, что, несмотря на малость полученных знаний, перечитывать что-нибудь подобное время от времени очень даже полезно.

Ещё хотел заметить, что Appendix A: Concurrency II совсем не раскрывает темы чистого многопоточного кода. Такое ощущение, что это выдранная глава про concurrency из учебника Java для начинающих.

Понравилось заключение к одной из глав:

It is not enough for code to work. Code that works is often badly broken. Programmers who satisfy themselves with merely working code are behaving unprofessionally. They may fear that they don’t have time to improve the structure and design of their code, but I disagree. Nothing has a more profound and long-term degrading effect upon a develop- ment project than bad code. Bad schedules can be redone, bad requirements can be rede- fined. Bad team dynamics can be repaired. But bad code rots and ferments, becoming an inexorable weight that drags the team down. Time and time again I have seen teams grind to a crawl because, in their haste, they created a malignant morass of code that forever thereafter dominated their destiny.

Of course bad code can be cleaned up. But it’s very expensive. As code rots, the mod- ules insinuate themselves into each other, creating lots of hidden and tangled dependen- cies. Finding and breaking old dependencies is a long and arduous task. On the other hand, keeping code clean is relatively easy. If you made a mess in a module in the morning, it is easy to clean it up in the afternoon. Better yet, if you made a mess five minutes ago, it’s very easy to clean it up right now.

So the solution is to continuously keep your code as clean and simple as it can be. Never let the rot get started.