Обложка: Собеседование на позицию Middle JavaScript разработчика: примеры задач и необходимые знания

Собеседование на позицию Middle JavaScript разработчика: примеры задач и необходимые знания

Дмитрий Шостак

Дмитрий Шостак

ведущий Frontend-разработчик IT-компании MediaSoft

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

Какие знания понадобятся:

  • JavaScript;
  • базовые структуры данных;
  • большое O.

Как подойти к решению задач:

  • размышляйте вслух;
  • не торопитесь и не сдавайтесь;
  • работайте с энтузиазмом.

JavaScript

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

Ресурсы для изучения:

  • «Современный учебник JavaScript» (перевод Ильи Кантора);
  • Eloquent JavaScript («Красноречивый JavaScript») (автор Marijn Haverbeke);
  • JavaScript Ninja (автор John Resig).

Структуры данных

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

  • массивами;
  • объектами/Хэш-мапами;
  • связанными списками;
  • стеками;
  • очередями;
  • деревьями;
  • графами.

Большое О

О большое описывает эффективность выполнения кода — то есть то, насколько быстро выполняется алгоритм с учётом входных данных (time complexity).

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

Большое О к задаче пишется комментарием над решением.

Пример:

// O(n) time | O(1) space

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

Размышляйте вслух

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

Не торопитесь и не сдавайтесь

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

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

Работайте с энтузиазмом

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

Задачи уровня Middle

Сумма двух чисел

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

Пример входных данных:

array = [3, 5, -4, 8, 11, 1, -1, 6]
targetSum = 10

На выходе:

[-1, 11] или [11, -1], так как -1 + 11 = 10 = targetSum

// O(n^2) time | O(1) space
function twoNumberSum(array, targetSum) {
 for (let currentIndex = 0; currentIndex < array.length; currentIndex++) {
	 const currentNumber = array[currentIndex];
	 
	 for (let currentCompareIndex = currentIndex + 1; currentCompareIndex < array.length; currentCompareIndex++) {
		 const currentCompareNumber = array[currentCompareIndex];
		 
		 if (currentCompareNumber + currentNumber === targetSum) {
			 return [currentNumber, currentCompareNumber];
		 }
	 }
 }
	
	return [];
}

Итерируем по массиву и на каждом элементе делаем итерацию по всем последующим элементам, проверяя текущую сумму со следующими на сумму из аргумента.

// O(n) time | O(n) space
function twoNumberSum(array, targetSum) {
	const nums = {};
	for (const currentNum of array) {
		const potentialMatch = targetSum - currentNum;
		
		if (potentialMatch in nums) {
			return [currentNum, potentialMatch];
		} else {
			nums[currentNum] = true;
		}
	}
	return [];
}

Мы итерируем по массиву единожды, сохраняя в новом объекте недостаток текущего элемента, нужный для получения targetSum. На каждой итерации мы проверяем, находится ли текущее значение в объекте остатков. Если да, значит мы уже натыкались в предыдущей итерации на значение, которому не хватало текущего элемента в качестве остатка. Соответственно, мы нашли пару и можем её вернуть.

Преобразование массива в объект с группировкой и фильтрацией элементов

Напишите функцию, которая на вход принимает массив из студентов, где студент — это объект с полями «имя», «возраст» и «номер группы» {name: string, age: number, groupId: number}, а на выходе возвращает объект, где ключ — это номер группы, а значение — массив из студентов старше 17 лет.

// O(n) time | O(n) space
function groupOnlyMatureStudentsByGroup(students) {
  return students.reduce((acc, student) => {
    const { groupId, age } = student;

    if (age < 18) {
      return acc;
    }

    if (groupId in acc) {
      acc[groupId].push(student);
    } else {
      acc[groupId] = [student];
    }

    return acc;
  }, {});
}

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

// O(n) time | O(n) space
const groupOnlyMatureStudentsByGroup = (students) =>
  students.reduce(
    (acc, student) =>
      student.age < 18
        ? acc
        : acc[student.groupId]
        ? acc[student.groupId].push(student) && acc
        : (acc[student.groupId] = [student]) && acc,
    {}
  );

Фирменное решение в одну строчку. Куда же без него!

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

Проверка строки на палиндром

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

Палиндром — слово или текст, одинаково читающееся в обоих направлениях.

Вариант 1

// O(n^2) time | O(n) space
function isPalindrome(string) {
  let reversed = "";
  for (let i = string.length - 1; i >= 0; i--) {
    reversed += string[i];
  }
  return string === reversed;
}

Вариант 2

function isPalindrome(string) {
  let reversed = [];
  for (let i = string.length - 1; i >= 0; i--) {
    reversed.push(string[i]);
  }
  return string === reversed.join("");
}
  1. Заводим переменную для хранения результата.
  2. Проходим циклом по строке с конца, каждый раз конкатенируя текущую букву c ранее заведенной переменной.
  3. Сравниваем входную строку с перевернутой.

Почему у первого решения time complexity O(n^2), а у второго O(n)?

Причина заключается в том, как JS хранит значения на низком уровне. Из-за того, что строка является примитивным значением, при конкатенации в каждом цикле она заново пересоздается с новым местом в памяти.

function isPalindrome(string) {
  let leftPointer = 0;
  let rightPointer = string.length - 1;

  while (leftPointer < rightPointer) {
    if (string[leftPointer] !== string[rightPointer]) {
      return false;
    }
    leftPointer++;
    rightPointer--;
  }

  return true;
}
  1. Заводим два пойнтера — для конца и начала строки.
  2. Идём циклом while до тех пор, пока левый пойнтер не пересек правый.
  3. В цикле делаем проверку на несоответствие букв строки по пойнтерам. Если находим неравенство, данная строка не может быть палиндромом, следовательно, мы выходим из функции, возвращая false.
  4. Если условие не прошло, то мы сдвигаем оба пойнтера ближе к центру и продолжаем идти по циклу.
  5. Если мы вышли из цикла, значит строка является палиндромом, и мы возвращаем true.
// O(n) time | O(n) space
const isPalindrome = (string) => string === string.split("").reverse().join("");

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

  1. Разбиваем строку на массив из букв.
  2. Меняем порядок элементов на обратное направление.
  3. Соединяем элементы обратно в целую строку.
  4. WIN!

Найти ближайшее значение в бинарном дереве

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

Node = { value: number | null, left: Node | null, right: Node | null }

// Среднее: O(log(n)) time | O(1) space
// Худшее: O(n) time | O(1) space

function findClosestValueInBst(tree, target) {
	let currentNode = tree;
	let currDifference = Math.abs(currentNode.value - target);

	function findClosest(node) {
		const difference = Math.abs(node.value - target);
		if (difference === 0) return node.value;
		if (difference <= currDifference) {
			currentNode = node;
			currDifference = difference;
		}
		if (target < node.value) {
			if (node.left === null) {
				return currentNode.value;
			}
			return findClosest(node.left);
		} else if (target >= node.value) {
			if (node.right === null) {
				return currentNode.value;
			}
			return findClosest(node.right);
		}
	}
	return findClosest(currentNode)
}

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

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

Итог

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

Поэтому дерзайте и удачи на собеседовании 🙂