Доброго времени суток, друзья!
Представляю вашему вниманию три задания по JS, предложенные участникам Microsoft’s Online Assessment 2019.
Microsoft’s Online Assessment — предварительный отбор кандидатов в разработчики. Тех, кто прошел предварительный отбор, приглашают на онлайн собеседование. Нашел в сети информацию, что на решение задач отводился ровно один час, но это не точно.
Предлагаю вам ознакомиться с вопросами и попробовать решить их самостоятельно. Развернутые комментарии приветствуются.
За решения огромное спасибо Matt Clark.
Итак, поехали.
Задание № 1
Напишите функцию «solution», удовлетворяющую следующим условиям:
- функция принимает строку S, состоящую из N букв английского алфавита
- функция возвращает строку, которая не содержит трех одинаковых букв подряд
- функция удаляет из строки S минимальное количество букв
Примеры:
- S = «eedaaad», функция возвращает «eedaad». Одна буква «a» удалена.
- S = «xxxtxxx», функция возвращает «xxtxx». Одинаковые буквы могут встречаться в строке более трех раз, но не подряд.
- S = «uuuuxaaaaxuuu», функция возвращает «uuxaaxuu».
Допущения:
- N — целое число в диапазоне [1..200,000]
- S состоит только из строчных букв [a-z]
Решение:
function solution(input) { let result = input.slice(0, 2); for (let i = 2; i < input.length; i++) { if (input[i] !== input[i - 1] || input[i] !== input[i - 2]) { result += input[i]; } } console.log(result); return result; } solution('eedaaad'); // eedaad solution('xxxtxxx'); // xxtxx solution('uuuuxaaaaxuuu'); // uuxaaxuu /* Алгоритм: - создаем переменную result, значением которой являются первые две буквы строки - начинаем итерацию с третьей буквы: - если текущая буква отличается хотя бы от одной из двух предыдущих, добавляем ее в result - иначе если текущая буква такая же, как две предыдущие, ничего не делаем - возвращаем result */
Задание № 2
Напишите функцию «solution», удовлетворяющую следующим условиям:
- функция принимает массив A, состоящий из N целых чисел
- функция возвращает максимальную сумму двух чисел, цифры которых при сложении дают одинаковые суммы
- если таких чисел в массиве нет, функция возвращает -1
Примеры:
- A = [51, 71, 17, 42], функция возвращает 93. Здесь две пары чисел, цифры которых при сложении дают одинаковые суммы: (51, 42) и (17, 71). Сумма первой (наибольшей) пары равняется 93.
- A = [42, 33, 60], функция возвращает 102. Сложение цифр всех чисел в массиве дает одинаковые суммы. 42 + 60 = 102.
- A = [51, 32, 43], функция возвращает -1, поскольку сложение цифр всех чисел дает разные суммы.
Допущения:
- N — целое число в диапазоне [1..200,000]
- Каждый элемент массива A — целое число в диапазоне [1..1,000,000,000]
Решение:
function sumDigits(num) { return String(num).split('').reduce(add); } function add(a, b) { return Number(a) + Number(b); } function descending(a, b) { if (a > b) { return -1; } else if (a < b) { return 1; } else { return 0; } } function extractHighestTwo(arr) { return arr.sort(descending).slice(0, 2); } function solution(arr) { let sums = {}; arr.forEach(function(num) { sum = sumDigits(num); if (sums[sum]) { sums[sum].push(num); } else { sums[sum] = [num]; } }); result = Object.values(sums) .filter(nums => nums.length >= 2) .map(extractHighestTwo) .map(nums => nums.reduce(add)) .sort(descending)[0]; console.log(result || -1); return result || -1; } solution([51, 71, 17, 42]); // 93 solution([42, 33, 60]); // 102 solution([51, 32, 43]); // -1 /* Алгоритм: - создаем пустой объект - перебираем числа в массиве - находим сумму цифр каждого числа - если суммы цифр не существует как свойства объекта: - создаем свойство и присваиваем ему в качестве значения массив, переданный функции - иначе если сумма цифр существует как свойство объекта: - добавляем число из массива, переданного функции, в массив, на который ссылается свойство - получаем массив из значений объекта (которые представляют собой "подмассивы", содержащие числа с одинаковыми суммами цифр) - отфильтровываем подмассивы, содержащие меньше двух чисел - для любого подмассива, содержащего больше двух чисел, находим два наибольших, остальные отбрасываем - заменяем каждый подмассив суммой двух его чисел - находим наибольшее число в массиве и возвращаем его или возвращаем -1, если в массиве нет чисел */ /* Код можно сократить так: function solution(arr) { let sums = {}; arr.forEach(num => { sum = String(num).split('').reduce((a, b) => Number(a) + Number(b)); sums[sum] ? sums[sum].push(num) : sums[sum] = [num]; }); result = Object.values(sums) .filter(nums => nums.length >= 2) .map(nums => nums.sort((a, b) => b - a).slice(0, 2)) .map(nums => nums.reduce((a, b) => a + b)) [0] console.log(result || -1); return result || -1; } solution([51, 71, 17, 42]); // 93 solution([42, 33, 60]); // 102 solution([51, 32, 43]); // -1 */
Задание № 3
Дана строка S, состоящая из N букв «a» и/или «b». За одно действие можно поменять любую букву на противоположную («a» на «b» или «b» на «a»).
Напишите функцию solution, удовлетворяющую следующим условиям:
- функция принимает указанную строку S
- функция возвращает количество действий, необходимых для получения строки, которая не содержит трех одинаковых букв подряд
Примеры:
- S = «baaaaa», функция возвращает 1. Строку, которая не содержит трех одинаковых букв подряд («baabaa»), можно получить за одно действие.
- S = «baaabbaabbba», функция возвращает 2. За два действия можно получить четыре «валидных» строки, например, «bbaabbaabbaa».
- S = «baabab», функция возвращает 0.
Допущения:
- N — целое число в диапазоне [0..200,000]
- строка S содержит только буквы «a» и/или «b»
Решение:
function numberOfMovesForStreak(streak) { let length = streak.length - 2; while (length % 3 !== 0) { length++; } return length / 3; } function solution(input) { const streaks = []; let temp = ''; for (let i = 0; i < input.length; i++) { if (input[i] === input[i - 1]) { temp += input[i]; } else { if (temp.length > 2 && temp.length !== 0) { streaks.push(temp); } temp = input[i]; } } if (temp.length > 2) { streaks.push(temp); } console.log(streaks.map(numberOfMovesForStreak).reduce(((a, b) => a + b), 0)); return streaks.map(numberOfMovesForStreak).reduce(((a, b) => a + b), 0); } solution('baaaaa'); // 1 solution('baaabbaabbba'); // 2 solution('baabab'); // 0 /* Для строки, состоящей из трех и более букв: если строка содержит 3-5 одинаковых букв подряд, необходимо совершить 1 действие если 6-8 таких букв - 2 действия если 9-11 букв - 3 действия Алгоритм: - перебираем буквы в поисках подстроки, состоящей из 3 и более одинаковых букв подряд - добавляем подстроки, состоящие из 3 и более одинаковых букв подряд, в массив - "мапируем" массив с подстроками: - определяем количество букв - извлекаем 2 - округляем до ближайшего целого числа, кратного 3 - делим на 3 и возвращаем частное - возвращаем сумму частных */
Благодарю за внимание.
Счастливого кодинга!
