Блог

Любите решать задачи на интервью?

6 февр. 2025 г.

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

Поэтому когда я увидела афишу лекции «Красивые математические задачи с айтишных собеседований» с преподавателем математики Бориса Трушина (известен своим youtube-каналом, где доходчиво объясняет математику), собралась и пошла.

Было интересно, разобрали 7 задач (парочка из них никогда не была замечена на собеседованиях, но и пусть). Записываю задачи и то, что может помочь найти решение в других задачах будущей мне :)

Красные и белые колпаки

Царь решил сыграть в игру со своими мудрецами: собрал 30 мудрецов, на каждого надел красный или белый колпак. Каждый мудрец видит все остальные колпаки, но не знает цвета своего колпака. Мудрецы не могут никак подавать сигналы другим о цвете их колпаков. Они сидят в комнате, и каждую минуту туда заходит проверяющий: как только хоть один мудрец правильно назовет цвет своего колпака — все будут свободны. Если называешь неправильно — казнь. Если ни один мудрец не назовет правильно цвет своего колпака в течение дня — все будут казнены.

Пока мудрецы сидели, мимо двери проходил человек и сказал: “О, среди вас как минимум 1 белый колпак!”. Через какое-то время все люди в белых колпаках встали и правильно назвали свой цвет.

Как так получилось?

Подход

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

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

Когда разобьётся яйцо?

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

(если яйцо не разбилось — его можно продолжать использовать; если разбилось — нельзя использовать, естественно)

Подход

Когда одно яйцо разбилось, вторым мы можем только перебирать подряд этажи. Можно попробовать разделить более-менее равномерно этажи на одинаковые диапазоны, и так проверять.

Но при одинаковом диапазоне (проверили сначала n, затем 2n, затем 3n) — для второго яйца количество попыток не сокращается (n - 1). Это хотелось бы оптимизировать.

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

Как доехать с пустым баком?

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

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

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

(очевидно, заливая бензин из всех встреченных по пути канистр)

Подход

Рекомендуется рисовать. Я в такие задачки не очень умею, если что, объяснение вот здесь.

Бесконечный поезд

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

Подход

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

Тюрьма и лампочка

В тюрьме 100 заключённых сидят по одиночным камерам. Начальник тюрьмы решил организовать такую игру. Их по одному иногда будут приводить в комнату, где нет ничего, кроме одной лампочки, которую заключённому разрешается включить или выключить. Гарантируется, что рано или поздно каждый из заключенных побывает в комнате с лампочкой сколько угодно раз. В любой момент заключённый, приведённый в комнату с лампочкой, может объявить, что все заключенные уже побывали в комнате хотя бы по одному разу. Если он прав, то всех отпустят, если нет — казнят. Заключенных собрали вместе в этой комнате, объявили правила, разрешили договориться, придумать стратегию, и, уходя, оставить выключатель в том положении, в котором захотят. Придумайте стратегию, которая позволит им освободиться

Подход

Объяснение, две вещи над которым надо подумать:

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

Как у вас с памятью?

5 янв. 2025 г.

Часто ли вы занимаетесь утечками памяти? Честно говоря, я — нет, но тема мне интересна. Каждый раз, когда я копаюсь в проблемах, связанных с памятью в веб-приложениях, я обнаруживаю, что надо задействовать мозг по максимуму: вспомнить, как устроена работа с памятью в JS, разобраться со всеми этими данными из Memory вкладки в DevTools, четко представлять, какие данные и когда нужны для приложения.

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

Посмотрите Memory Leaks в гайдах — это отобранные ссылки со статьями, как работает GC, как лучше отлаживаться в DevTools. Также планирую со временем добавить практические советы.

0 дней без ошибок с SVG background

20 дек. 2024 г.

У нас SVG в качестве фона сверху нашего сайта, основной фон — просто серый. Для картинки у нас такой css:

.container {
    background-image: url(path/to/our.svg);
    background-repeat: no-repeat;
    background-size: 100% 144px;
}

Всех всё устраивает, однако подкрались праздники и дизайнерка предложила обновить картинку на более праздничную (и, конечно, добавить снег, но с ним как раз проблем не было). Дизайнерка попросила не растягивать новую картинку (как мы делаем обычно, просто растягивая её до 100%), так что обновила css:

.container {
    background-image: url(path/to/holiday.svg);
    background: no-repeat;
    background-size: auto 144px;
    background-position: left top;
}

Тестировщики протестировали, и всё улетело в предпраздничный релиз.

Пару дней спустя мне написал коллега: можем ли мы что-то сделать с нашим праздничным фоном на широких экранах? Я проверила, и это была катастрофа: на широких экранах (более чем 2500px) наш фон заканчивался на 2000px, и дальше справа было просто серое пятно.

Фикс был быстрый и простой:

.container {
    background-image: url(path/to/holiday.svg);
    background: repeat-x;
    background-size: auto 144px;
    background-position: left top;
}

Просто не забывайте: либо 100%, либо repeat.

HOC или не HOC?

10 дек. 2024 г.

В наборе кат для изучения паттернов попалась одна про Higher-Order Component(HOC) в React — truncate paragraph with HOC in React. Плюс недавно разбиралась с паттерном Декоратор, и примером применения для React как раз считается HOC.

И вот я задумалась: а действительно ли хоки актуальны?

Чаще всего я вижу хоки, когда работаю с кодом, написанным 3-4 года назад, но в новом коде я практически их не вижу. Опять же, в старой документации React есть целая страница, посвященная HOC и примерам использования, а вот в новой классной документации ничего нет.

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

Лично я предпочитаю кастомные хуки или даже классы с вынесенной в них бизнес-логикой. Для меня это более очевидный и поддерживаемый подход.

Boxes in boxes, Или что застряло у меня в голове

27 нояб. 2024 г.

Я периодически решаю задачи на leetcode или codewars, и недавно наткнулась на кату “Boxes in boxes”.

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

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

После двух вечеров размышлений, я была вынуждена посмотреть чужие решения (эта задача просто сводила меня с ума). И знаете что? Даже после того, как я увидела код и поняла, что он должен делать, я так и не могла осознать, а каким же образом это приводит нас к нужному результату.

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

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

function draw(n) {
    // all for one box, our start
    let res = [" _ ", "|_|"];

    for (let i = 1; i < n; i++) {
        res = [
            // top line - just add tops of boxes
            ' _' + res[0],
            // draw existing boxes without left border (top 1/2 part is repeat existing but partially)
            ...res.slice(1).map(str => '|  ' + str.slice(1)),
            // draw existing with left border and without bottom
            ...res.slice(1, -1).map(str => '| ' + str),
            // draw bottom
            '|_' + res[res.length-1],
        ]
    }

    return res.join('\n');
}

Остаётся только надеяться, что на интервью мне эта задача не попадётся 🤪