1967 просмотров
От 16 февраля

Задачи с собеседований на JavaScript с решением

1. Бинарный поиск

Бинарный поиск (Binary Search) - это эффективный алгоритм для поиска значения в отсортированном массиве. Принцип алгоритма очень прост. Мы всегда имеем дело с упорядоченным массивом. Это позволяет прибегать к хитрости - на каждой итерации цикла, который мы запускаем, мы вычисляем индекс среднего элемента. Этот элемент сравниваем с искомым. Если элемент из середины массива оказался меньше, чем тот, что мы ищем, значит нужный нам находится правее по массиву, ведь массив упорядочен. Соответственно, нам нужно перейти в следующую итерацию цикла, "оставляя" ей лишь правую часть массива - в ней снова будет найден средний элемент и алгоритм повторится. Если же элемент из середины массива оказался больше искомого, то мы переходим к следующей итерации, отбрасывая правую часть массива, а оставляя левую. Если же элемент совпадает с искомым, мы выходим из цикла. function binarySearch(array, target) { let left = 0; let right = array.length - 1; while (left <= right) { let mid = Math.floor((left + right) / 2); let currentElement = array[mid]; if (currentElement === target) { return mid; } else if (target < currentElement) { right = mid - 1; } else { left = mid + 1; } } return -1; } 1. left и right – это границы массива, которые мы просматриваем в данный момент. 2. mid – это индекс элемента в середине массива, мы используем его для определения, в какую сторону двигаться дальше. 3. currentElement – это элемент в массиве, который сейчас проверяется. 4. if (currentElement === target) – если текущий элемент равен искомому значению, то возвращаем его индекс. 5. else if (target < currentElement) – если искомое значение меньше текущего элемента, то мы перемещаем правую границу влево, так как искомое значение должно находиться слева от текущего элемента. 6. else – в противном случае, если искомое значение больше текущего элемента, мы перемещаем левую границу вправо, так как искомое значение должно находиться справа от текущего элемента. 7. while (left <= right) – цикл повторяется, пока левая граница меньше или равна правой. 8. return -1 – если мы вышли из цикла и не нашли искомое значение, то возвращаем -1, что означает, что элемент не найден. Вот пример использования функции бинарного поиска: const array = [1, 2, 3, 4, 5, 6, 7, 8, 9]; const target = 5; const index = binarySearch(array, target); console.log(index); // Output: 4 1. Создаем массив array с данными, в котором будем искать элемент. 2. Задаем значение target, которое мы хотим найти. 3. Вызываем функцию binarySearch с передачей массива и искомого значения. 4. Результат вызова функции присваиваем переменной index. 5. Выводим index в консоль. Результатом будет индекс 4, так как элемент со значением 5 находится под индексом 4 в массиве. В заключение, бинарный поиск является одним из эффективных алгоритмов поиска, особенно когда используется с отсортированными данными. Также существуют другие похожие алгоритмы, такие как линейный поиск и интерполяционный поиск. Среди всех этих алгоритмов бинарный поиск является самым эффективным и используется, когда необходимо быстро найти конкретный элемент в большом массиве данных. В то время как линейный поиск является более простым и понятным, но медленным при больших объемах данных. Интерполяционный поиск используется, когда есть информация о возможной позиции элемента в массиве, но является менее стабильным по сравнению с бинарным поиском.

2. Проверка на палиндром

Постановка: Палиндром — слово, предложение или последовательность символов, которая абсолютно одинаково читается как в привычном направлении, так и в обратном. К примеру, “Anna” — это палиндром, а “table” и “John” — нет. Дана строка; нужно написать функцию, которая позволяет вернуть значение true, если строка является палиндромом, и false — если нет. При этом нужно учитывать пробелы и знаки препинания. palindrome('racecar') // true palindrome('table') // false Разбираем задание Основная идея здесь — перевернуть строку в обратном направлении. Если «реверсная» строка полностью идентична исходной, значит, мы получили палиндром и функция должна вернуть значение true. Если же нет — false. Решение: Вот код, который позволяет решить задачу: const palindrome = str => { str = str.toLowerCase() return str === str.split('').reverse().join('') } Первый шаг — преобразование символов исходной строки в нижний регистр. Это гарантия того, что программа будет сравнивать символы без учета регистра. Второй шаг — реверс строки. Это сделать несложно: необходимо преобразовать ее в массив посредством метода .split(). Потом мы переворачиваем массив, используя .reverse(). Последний этап — преобразование обратного массива в строку при помощи .join(). Теперь все, что нужно, — сравнить «обратную» строку с исходной, вернув результат true или false.

3. Проверка на анаграмму

Постановка: Так называют слово, которое содержит все буквы другого слова в том же количестве, но ином порядке. Нужно написать функцию, которая проверяет, являются ли две строки анаграммами, причем регистр букв не имеет значения. Учитываются лишь символы; пробелы или знаки препинания в расчет не берутся. anagram('finder', 'Friend') --> true anagram('hello', 'bye') --> false Разбираем задание Здесь важно учитывать, что необходимо проверять каждую букву в обеих строках и количество ее вхождений в каждую из них. finder --> f: 1 friend --> f: 1 i: 1 r: 1 n: 1 i: 1 d: 1 e: 1 e: 1 n: 1 r: 1 d: 1 Для хранения данных анаграммы стоит выбрать такую структуру, как объект. Ключ в этом случае — символ буквы, значение — количество ее повторений в текущей строке. Есть и другие условия: Нужно убедиться в том, что регистр букв при сравнении не учитывается. Просто преобразуем обе строки в нижний или верхний регистр. Исключаем из сравнения все не-символы. Лучше всего работать с регулярными выражениями. Решение: // Вспомогательная функция для создания объекта // хранящего пары вида <символ>:<кол-во повторений> const buildCharObject = (str) => { const charObj = {} for (let char of str.replace(/[^\w]/g).toLowerCase()) { // Поисходит первичная запись свойства в объект, // либо инкрементирование, если оно уже имеется charObj[char] = charObj[char] + 1 || 1 } return charObj } // Основная функция const anagram = (strA, strB) => { const aCharObject = buildCharObject(strA) const bCharObject = buildCharObject(strB) // Если в объектах разное кол-во символов, это не анаграмма if(Object.keys(aCharObject).length !== Object.keys(bCharObject).length) { return false } // Так же возвращаем false, если кол-во вхождений // не совпадает для какого-либо символа for(let char in aCharObject) { if(aCharObject[char] !== bCharObject[char]) { return false } } return true } Обратите внимание на использование Object.keys() в сниппете выше. Этот метод возвращает массив, содержащий имена или ключи в таком же порядке, в каком они встречаются в объекте. В этом случае массив будет таким: ['f', 'i', 'n', 'd', 'e', 'r'] Таким образом, мы получаем свойства объекта без необходимости выполнять объемный цикл. В задаче можно использовать этот способ со свойством .length — для проверки того, есть ли в обеих строках одинаковое количество символов — это важная особенность анаграмм.

4. Техника двух указателей (поиск пары чисел по сумме)

Метод двух указателей - это популярный шаблон решения задач, используемый в JavaScript и других языках программирования, особенно полезный при работе с массивами и строками. Основная идея Основная идея метода двух указателей заключается в использовании двух указателей, которые движутся по массиву или строке в разных направлениях или со скоростями. Этот метод часто используется для решения задач оптимизации, так как он может сократить необходимость вложенных циклов и уменьшить сложность алгоритма. Пример использования Возьмем для примера задачу поиска пары чисел в отсортированном массиве, которые в сумме дают заданное число. Можно использовать метод двух указателей для решения этой задачи. function findPair(arr, target) { let left = 0; let right = arr.length - 1; while (left < right) { let sum = arr[left] + arr[right]; if (sum == target) { return [left, right]; } else if (sum < target) { left++; } else { right--; } } return [-1, -1]; // возвращаем, если пара не найдена } В этом примере мы инициализируем два указателя, один указывает на начало массива, а другой на конец. Затем мы двигаем указатели в зависимости от суммы текущих элементов. Если сумма равна целевому числу, мы нашли пару. Если сумма меньше целевого числа, мы двигаем левый указатель вправо. Если сумма больше целевого числа, мы двигаем правый указатель влево. Заключение Метод двух указателей - это мощный инструмент, который может значительно улучшить производительность вашего кода при правильном использовании. Он особенно полезен при работе с массивами и строками, и может быть использован для решения широкого спектра задач.

5. Техника двух указателей (поиск уникальной подстроки)

Постановка: Напишите функцию для нахождения длины самой длинной подстроки без повторяющихся символов в строке. Решение: Использование двух указателей для отслеживания подстроки: function longestSubstringWithoutRepeating(s) { let leftPointer = 0; // Левый указатель начала подстроки let maxLength = 0; // Максимальная длина подстроки const charIndexMap = {}; // Хранит индексы символов в текущей подстроке for (let rightPointer = 0; rightPointer < s.length; rightPointer++) { const currentChar = s[rightPointer]; // Если символ уже встречался в текущей подстроке, обновляем левый указатель if (charIndexMap[currentChar] !== undefined && charIndexMap[currentChar] >= leftPointer) { leftPointer = charIndexMap[currentChar] + 1; } // Обновляем индекс символа в текущей подстроке charIndexMap[currentChar] = rightPointer; // Обновляем максимальную длину подстроки maxLength = Math.max(maxLength, rightPointer - leftPointer + 1); } return maxLength; } // Пример использования: const strExample = 'abcabcbb'; console.log(longestSubstringWithoutRepeating(strExample)); // Вернет 3. 1. Правый указатель rightPointer движется вперед, проверяя каждый символ. 2. Если символ уже встречался в текущей подстроке, обновляем leftPointer до индекса следующего символа после повторения. 3. Обновляем индекс символа в charIndexMap. 4. Обновляем maxLength с учетом текущей длины подстроки. В конце прохода возвращаем максимальную длину подстроки без повторений. Объяснение подхода с двумя указателями: 1. Использование двух указателей (leftPointer и rightPointer) позволяет эффективно отслеживать текущую подстроку без повторений. 2. Обновление leftPointer после повторения символа гарантирует, что мы рассматриваем только уникальные символы. Проход по строке выполняется за линейное время O(n), где n - длина строки. Этот алгоритм эффективно решает задачу нахождения длины самой длинной подстроки без повторяющихся символов и является одним из классических примеров использования двух указателей.

6. Каррирование

Каррирование – продвинутая техника для работы с функциями. Она используется не только в JavaScript, но и в других языках. Каррирование – это трансформация функций таким образом, чтобы они принимали аргументы не как f(a, b, c), а как f(a)(b)(c). function curry(f) { // curry(f) выполняет каррирование return function(a) { return function(b) { return f(a, b); }; }; } Использование: function sum(a, b) { return a + b; } let curriedSum = curry(sum); alert( curriedSum(1)(2) ); // 3 Более продвинутые реализации каррирования, как например _.curry из библиотеки lodash, возвращают обёртку, которая позволяет запустить функцию как обычным образом, так и частично. function sum(a, b) { return a + b; } let curriedSum = _.curry(sum); // используем _.curry из lodash alert( curriedSum(1, 2) ); // 3, можно вызывать как обычно alert( curriedSum(1)(2) ); // 3, а можно частично Чтобы понять пользу от каррирования, нам определённо нужен пример из реальной жизни. Например, у нас есть функция логирования log(date, importance, message), которая форматирует и выводит информацию. В реальных проектах у таких функций есть много полезных возможностей, например, посылать логи по сети, здесь для простоты используем alert: function log(date, importance, message) { alert(`[${date.getHours()}:${date.getMinutes()}] [${importance}] ${message}`); } А теперь давайте применим к ней каррирование! log = _.curry(log); После этого log продолжает работать нормально: log(new Date(), "DEBUG", "some debug"); // log(a, b, c) Но также работает вариант с каррированием: log(new Date())("DEBUG")("some debug"); // log(a)(b)(c) Давайте сделаем удобную функцию для логов с текущим временем: // logNow будет частичным применением функции log с фиксированным первым аргументом let logNow = log(new Date()); // используем её logNow("INFO", "message"); // [HH:mm] INFO message Теперь logNow – это log с фиксированным первым аргументом, иначе говоря, «частично применённая» или «частичная» функция. Мы можем пойти дальше и сделать удобную функцию для именно отладочных логов с текущим временем: let debugNow = logNow("DEBUG"); debugNow("message"); // [HH:mm] DEBUG message Итак: Мы ничего не потеряли после каррирования: log всё так же можно вызывать нормально. Мы можем легко создавать частично применённые функции, как сделали для логов с текущим временем. В случае, если вам интересны детали, вот «продвинутая» реализация каррирования для функций с множеством аргументов, которую мы могли бы использовать выше. Она очень короткая: function curry(func) { return function curried(...args) { if (args.length >= func.length) { return func.apply(this, args); } else { return function(...args2) { return curried.apply(this, args.concat(args2)); } } }; } Примеры использования: function sum(a, b, c) { return a + b + c; } let curriedSum = curry(sum); alert( curriedSum(1, 2, 3) ); // 6, всё ещё можно вызывать нормально alert( curriedSum(1)(2,3) ); // 6, каррирование первого аргумента alert( curriedSum(1)(2)(3) ); // 6, каррирование всех аргументов

7. Обход дерева

Поддержи проект и получи доступ ко всему контенту всего за 290

8. Сжатие строки

Поддержи проект и получи доступ ко всему контенту всего за 290

9. Развернуть все слова в строке

Поддержи проект и получи доступ ко всему контенту всего за 290

10. Подсчёт количества гласных в строке

Поддержи проект и получи доступ ко всему контенту всего за 290

11. Сортировка символов в строке по кол-ву вхождений

Поддержи проект и получи доступ ко всему контенту всего за 290

12. Определить, являются ли строки изоморфными

Поддержи проект и получи доступ ко всему контенту всего за 290

13. Найти уникальный элемент в массиве

Поддержи проект и получи доступ ко всему контенту всего за 290

14. Удалить из массива дубликаты значений

Поддержи проект и получи доступ ко всему контенту всего за 290

15. Найти пропущенное число за время O(n)

Поддержи проект и получи доступ ко всему контенту всего за 290

16. Найти максимальную разницу между двумя элементами массива

Поддержи проект и получи доступ ко всему контенту всего за 290

17. Найти наибольшее произведение трех элементов массива

Поддержи проект и получи доступ ко всему контенту всего за 290

18. Реализация flat() для массива

Поддержи проект и получи доступ ко всему контенту всего за 290

19. Найти пересечение массивов

Поддержи проект и получи доступ ко всему контенту всего за 290

20. Алгоритм Кадане

Поддержи проект и получи доступ ко всему контенту всего за 290

21. FizzBuzz

Поддержи проект и получи доступ ко всему контенту всего за 290

22. Факториал

Поддержи проект и получи доступ ко всему контенту всего за 290

23. Последовательность Фибоначчи

Поддержи проект и получи доступ ко всему контенту всего за 290

24. Счётчик через замыкание

Поддержи проект и получи доступ ко всему контенту всего за 290

25. Аналог Promise.all

Поддержи проект и получи доступ ко всему контенту всего за 290

26. Аналог Function.prototype.bind

Поддержи проект и получи доступ ко всему контенту всего за 290

27. Проверка на целое число

Поддержи проект и получи доступ ко всему контенту всего за 290

28. Является ли число степенью двойки?

Поддержи проект и получи доступ ко всему контенту всего за 290

29. Двоичное представление числа

Поддержи проект и получи доступ ко всему контенту всего за 290

30. Реализация аналога Array.prototype.map

Поддержи проект и получи доступ ко всему контенту всего за 290

31. Реализация аналога Array.prototype.filter

Поддержи проект и получи доступ ко всему контенту всего за 290

32. Реализация аналога Array.prototype.reduce

Поддержи проект и получи доступ ко всему контенту всего за 290

33. Определить сбалансированность скобок

Поддержи проект и получи доступ ко всему контенту всего за 290
Хочешь стать частью сообщества Девстанции?
Вступай в наш чат в Telegram

Также в этой категории

Шпаргалка
  58 вопросов

60 вопросов для собеседования по JavaScript

Вопросы для собеседования JavaScript-разработчика

930 просмотров
От 16 февраля
Викторина
  21 вопрос

Промисы, async/await и Event Loop

Вопросы про Promise API, async/await и цикл событий

188 просмотров
От 7 февраля
Викторина
  33 вопроса

Подковыристые основы JavaScript

Типичные и не очень вопросы с собеседования по JavaScript

164 просмотра
От 7 февраля
Викторина
  19 вопросов

Про прототипы: __proto__, prototype

Викторина по вопросам о прототипах в JavaScript

58 просмотров
От 9 октября 2023
Викторина
  21 вопрос

Вопросы от пьяного интервьюера

Викторина с самыми странными вопросами

108 просмотров
От 9 октября 2023

Вам может быть интересно

Шпаргалка
  21 вопрос

Шпаргалка по вопросам о TypeScript

TypeScript - то, что могут спросить на собеседовании

491 просмотр
От 19 июня 2023
Викторина
  32 вопроса

Большой тест по CSS

Большая викторина по вопросам о CSS

40 просмотров
От 2 июня 2023
Шпаргалка
  24 вопроса

Полезные хуки на React.js

Сборник пользовательских хуков на React.js

288 просмотров
От 17 февраля
Викторина
  12 вопросов

Вопросы по CSS Grid и FLEX

То, что могут спросить про CSS Grid и Flex на собеседовании

34 просмотра
От 9 октября 2023
Шпаргалка
  25 вопросов

Шпаргалка по вопросам о React.js

Вопросы для собеседования React.js-разработчика

439 просмотров
От 30 мая 2023
Викторина
  10 вопросов

Сложные вопросы по HTML

Вопросы про HTML для опытных разработчиков

57 просмотров
От 4 октября 2023

Топ тредов

Gravatar for 9tokio
Tokio:
то что раньше было бесплатным теперь платное - вот это я понимаю

Последнее сообщение:
Логотип Девстанции
Девстанция:
Спасибо за поддержку проекта :) Повышение качества контента - один из важнейших приоритетов. Этому м...
3 сообщения
212 просмотров

Логотип Девстанции
Девстанция:
Поиск людей для совместной разработки IT-стартапов

Последнее сообщение:
В этом треде пока нет сообщений
0 сообщений
107 просмотров

Логотип Девстанции
Девстанция:
Какой язык программирования выбрать в качестве первого?

Последнее сообщение:
Gravatar for 2kokke
Kokke:
Python или JS - универсально. Но по уму надо бы с чего-то строгого начинать и достаточно низкоуровне...
1 сообщение
139 просмотров

Все категории