Как на фронтенд-собеседовании превратить сложный вопрос в лёгкий

Рассказывает Алекс Паттисон

За последние пару месяцев я активно проводил собеседования фронтенд-разработчиков. Каждый, кто когда-либо бывал на подобных собеседованиях, знает, что вопросы могут быть совершенно разные, а вот уровень знаний необходимо демонстрировать неизменно высокий. Вас могут спросить о чём угодно, начиная со структур данных/алгоритмов и заканчивая нюансами CSS. При подготовке к очередному собеседованию возникает чувство, будто нас просят вызубрить всю информацию с MDN. Тем более, что большинство тренировочных материалов для собеседований сконцентрированы на CS, поэтому фронтенд-разработчику приходится особенно туго. В этой статье я собираюсь объяснить мой подход к подготовке к интервью.

Суть подхода

Суть в том, чтобы научиться сводить каждый вопрос по структурам данных/алгоритму к DOM. DOM — это дерево узлов. Оно очень органично соединяет друг с другом как определённые структуры данных: графы (родительский класс), связные списки (подкласс дерева и, в частности, унарное дерево), — так и сами деревья. Немного креатива, и любой вопрос можно подстроить под фронтенд-тематику.

Все примеры будут рассматриваться для Vanilla JS. На собеседованиях довольно часто спрашивают о DOM-манипуляциях, а времени пробежаться по любимому фреймворку (и всему встроенному инструментарию) не остаётся. Перед соискателями ставится трудная задача, ведь специалисты, как правило, мало пишут на Vanilla JS. Они предпочитают React, Angular, Vue и т. д. Но попрактиковаться в работе с чистым JS заранее всё-таки нужно: так вы гарантированно облегчите свою жизнь на следующем собеседовании. А учитывая тот факт, что почти все проблемы с кроссбраузерностью остались в прошлом, лишний козырь в виде умения писать на чистом JS явно не помешает.

Преобразование вопроса

Задача: Верните значение k-тому с конца элементу односвязного списка.

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

Фронтенд-вопрос: Измените цвет фона k-того с конца среди сестринских элементов. Вы стараетесь смоделировать связный список, поэтому необходимо ограничение: в каждом узле может быть доступ только к nextElementSibling (и встроенным стилям).

Решения

Теперь задачу можно решить по-разному. Для начала проанализируйте возможные варианты. Не садитесь сразу за написание кода, ведь первое пришедшее на ум решение не всегда оказывается самым правильным. Варианты действий:

1. Пройдитесь по списку и сделайте его двусвязным. Затем сделайте k шагов с конца.
2. Пройдитесь по списку и вычислите его длину. Повторите ещё раз и остановитесь на length - k.
3. Изначально в связных списках заложена рекурсивная структура. Можно ли как-нибудь рекурсивно дойти до хвоста списка, а потом, поднимаясь назад по стеку вызовов, увеличивать счётчик?

Давайте разберём каждый вариант по порядку:

1. Первое пришедшее на ум решение, однако лучше всё-таки избегать любых изменений значений на входе. Кто-то может возразить, сказав, что в каждом узле уже есть previousElementSibling, поэтому входное значение останется неизменным. С этим никто не спорит, однако, как уже говорилось ранее, данный подход противоречит решению задачи. Не будем выходить за исходные условия и не станем добавлять ничего нового в DOM.
2. Вполне разумный вариант. Но можно обойтись без лишнего повторения цикла.
3. А вот этот вариант я лучше оставлю для размышлений. Как можно отследить количество ссылок до конца списка, если мы задействуем стек вызовов? Ответ на этот вопрос вы найдёте в конце статьи.

Как оказалось, можно немножко схитрить во втором варианте, взяв из него самое лучшее и избежав лишних действий в виде повторной итерации по длине списка. Мы просто добавим к нему сразу два указателя. Пока главный указатель движется к концу списка, а разница между указателями равна k -1, следующий указатель остаётся в узле, который мы выделим цветом. На картинке всё смотрится более понятно:

Представим, что у нас есть HTML, который выглядит как-то так:

			0⟹
  1⟹
  2⟹
  3⟹
  4⟹
  5⟹
  6⟹
  7⟹
  8⟹
  9
		

Как именно использовать последний указатель для закрашивания k из последнего элемента красным? Посмотрим внимательнее на код:

			const turnKthFromLastRed = (head, k) => {
  let leader = head;
  let follower = head;

  while (leader.nextElementSibling) {
    if (k > 1) {
      k--;
    } else {
      follower = follower.nextElementSibling;
    }

    leader = leader.nextElementSibling;
  }

  if (k === 1) {
    follower.style.background = 'red';
  }
}
		

Сначала мы инициализируем наши указатели leader и follower (2–3 строки) — оба они указывают на начало списка. Задаём выполнение цикла до тех пор, пока первый указатель не достигнет следующего сестринского элемента. Это будет индикатором окончания списка. Строка 12 перенаправляет наш главный указатель в сторону родственного элемента. Теперь посмотрим на строки 6–10. Здесь указано, нужно ли нам также перенаправлять и follower. Нам нужно, чтобы при k = 1 оба указателя двигались вперёд. Логика тут немного хромает, но мы вынуждены действовать так в рамках стандартного использования языка. Если я говорю «сделать вторую с конца ссылку красной», то это значит поменять цвет ссылки под номером 8. При наших текущих условиях входное значение k = 2 как раз и будет «второй ссылкой с конца».
Выставим дополнительное условие в строке 15 — так мы случайно не покрасим первую ссылку, если значение k превысит количество узлов в списке.

Наконец, вызываем наш метод:

			const head = document.querySelector('.link');
turnKthFromLastRed(head, 2);
		

Проверяем рабочий пример:

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

Заключение

Если вас заинтересовал третий вариант, то, как я и обещал, даю подсказку:

			const recTurnKthToLastRed = (head, k) => {
  if (!head.nextElementSibling) return 1;
  const countAhead = recTurnKthToLastRed(head.nextElementSibling, k) + 1;

  if (k === countAhead) {
    head.style.background = 'red';
  }

  return countAhead;
}
		

Нам нужно просто поменять цвет узла, а возвращаемое значение функции здесь не важно. countAhead — это количество узлов перед текущим значением (включительно). То есть при вызове верхнего уровня метод recTurnKthToLastRed() вернёт длину нашего списка.

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

Написанный код, который ещё не оптимизировали, — это ВСЕГДА лучше, чем оптимизированный код, который ещё не написали.

Смотрите также: Хочу стать frontend разработчиком: базовые знания и план обучения