Задачи по JavaScript от Microsoft

  • Tutorial


Доброго времени суток, друзья!

Представляю вашему вниманию три задания по JS, предложенные участникам Microsoft’s Online Assessment 2019.

Microsoft’s Online Assessment — предварительный отбор кандидатов в разработчики. Тех, кто прошел предварительный отбор, приглашают на онлайн собеседование. Нашел в сети информацию, что на решение задач отводился ровно один час, но это не точно.

Предлагаю вам ознакомиться с вопросами и попробовать решить их самостоятельно. Развернутые комментарии приветствуются.

За решения огромное спасибо Matt Clark.

Итак, поехали.

Задание № 1


Напишите функцию «solution», удовлетворяющую следующим условиям:

  • функция принимает строку S, состоящую из N букв английского алфавита
  • функция возвращает строку, которая не содержит трех одинаковых букв подряд
  • функция удаляет из строки S минимальное количество букв

Примеры:

  1. S = «eedaaad», функция возвращает «eedaad». Одна буква «a» удалена.
  2. S = «xxxtxxx», функция возвращает «xxtxx». Одинаковые буквы могут встречаться в строке более трех раз, но не подряд.
  3. 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

Примеры:

  1. A = [51, 71, 17, 42], функция возвращает 93. Здесь две пары чисел, цифры которых при сложении дают одинаковые суммы: (51, 42) и (17, 71). Сумма первой (наибольшей) пары равняется 93.
  2. A = [42, 33, 60], функция возвращает 102. Сложение цифр всех чисел в массиве дает одинаковые суммы. 42 + 60 = 102.
  3. 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
  • функция возвращает количество действий, необходимых для получения строки, которая не содержит трех одинаковых букв подряд

Примеры:

  1. S = «baaaaa», функция возвращает 1. Строку, которая не содержит трех одинаковых букв подряд («baabaa»), можно получить за одно действие.
  2. S = «baaabbaabbba», функция возвращает 2. За два действия можно получить четыре «валидных» строки, например, «bbaabbaabbaa».
  3. 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 и возвращаем частное
    - возвращаем сумму частных
*/


Благодарю за внимание.

Счастливого кодинга!
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 18

    +2
    В чём прикол? Банальные прямолинейные задачи — упражнения для работы с массивами для первого семестра. Особенности Javascript тоже никак не используются. Решения почти дословно можно перевести на любой другой алгоритмический язык.
      +2
      Видимо, для тех, у кого не было и не может быть первого семестра, а есть потребность начать с чего-то.
      К тому же, JS есть вообще на любой платформе, в которой есть графический режим и браузер.
        0
        видимо это предварительный скрининг что-бы отфильтровать людей и уменьшить нагрузку на интервьюверов.
          0
          Это задачи с Codility, там обычно можно выбрать язык для решения. Возможно у автора был ограничен выбор из-за роли, на которую подавал. У Microsoft почему-то online assessment достаточно легкий, мб на on-site отыгрываются :)
            0
            Ну да. Прямо на их главной странице логотип MS.
            0
            Да, наверное, и нет прикола никакого. Просто задачки на понимание самых основ. Автор же написал, что потом только онлайн собеседование :)

            А вообще, спасибо автору, помог с утра вкатиться в работу после больших выходных:)
            0
            кажется, тут много ошибок/опечаток в коде. Залейте куда-нибудь типа JSFiddle и дайте ссылку, чтобы каждый мог проверить как это работает.
              +3
              P.S. примеры ошибок: в функции descending стоит два раза if (a > b) — наверное, во второй ветке должно было быть a < b? Одни переменные объявляются с let, другие (sum, result) почему-то без. Сама функция solution в её первом варианте вообще не возвращает значение, а только пишет результат в консоль. Ну и так далее.
              +2
              хм, по поводу первой задачи как то сложно, есть же регулярки
              regexr.com/4v19n
                0
                Тссс, пацанам не сказали, что регулярные выражения завезли. Третья задача тоже решается в одну строчку:
                var str = "abbbaaaaaaabbbaabaaabbb";
                console.log( str.match( /a{3}|b{3}/g ).length );  // 6

                По условию достаточно подсчитать число замен. Впрочем и выполнить замены не намного сложнее.
                  0
                  Согласно моей женской логике замены делаются так:
                  //  Сначала итеративно заменяем патерны из 5-ти букв. Итерации необходимы, т.к. после первого раунда замен могут появиться новые 5-буквенные патерны, например (с пробелом для ясности) aaaaa aaa => aabaa aaa — в конце вылез новый 5-буквенный патерн. Поэтому выполняем "подходы к снаряду", пока новые такие патерны не перестанут появляться, т.е. до тех пор, пока строка, получающаяся после замены (temp), не будет совпадать со строкой до замены (str):
                  while ( !( str === ( temp = str.replace( /aaaaa/g, 'aabaa' ) ) ) ) str = temp;
                  //  С патернами из 3-х букв уже просто. Тут итерации не нужны, тупо реплэйсим:
                  str = str.replace( /aaa/g, 'aba' );
                  // + Аналогично с буквой b
                  0
                  Справедливости ради, регулярки при использовании capturing groups проседают в производительности (по очевидным причинам), и едва ли будут прям сильно лучше посимвольного перебора строки.
                  +1

                  Offtopic: отличная кпдв, прям дышит Microsoft ;)

                    0
                    Что то легко. Пойду ка я работать в к ним -_-
                      0
                      Там потом собеседование с HR по телефону и только после этого on-site интервью на пол-дня :)
                      0
                      Люблю такие штуки, первую задачку ещё можно решить так:
                      'uuuuxaaaaxuuu'.replace(/((.)\1)\1+/g, '$1$2');

                      Остальные так коротко не решаются, по этому лень)))
                        +1
                        В решении для второй задачи сложность O(N logN) из-за сортировки. Там можно сделать лучше O(N logK) (K — максимальное значение элемента), сохраняя одно максимальное число для отдельной суммы.

                        function solution(arr) {
                          let sums = {};
                        
                          let result = -1;
                          arr.forEach((num) => {
                            const sum = sumDigits(num);
                            if (sums[sum]) {
                              const pair_num = sums[sum];
                              sums[sum] = Math.max(pair_num, num);
                              result = Math.max(result, num + pair_num);
                            } else {
                              sums[sum] = num;
                            }
                          });
                          return result;
                        }
                        


                          0
                          Зачем эти упражнения и эта статья если есть codewars.

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

                          Самое читаемое