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

// 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. На каждой итерации мы проверяем, находится ли текущее значение в объекте остатков. Если да, значит мы уже натыкались в предыдущей итерации на значение, которому не хватало текущего элемента в качестве остатка. Соответственно, мы нашли пару и можем её вернуть.

// 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 группы.

Вариант 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!

// Среднее: 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)
}

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

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