Вступление

Хотите улучшить свои технические навыки проведения собеседований? Что ж, вы пришли в нужное место. Давайте разберемся с проблемой LeetCode. Я покажу вам свой подход, свои ошибки и выводы. Надеюсь, это поможет вам понять, как решать технические проблемы на собеседовании.

№ 1588. Сумма всех подмассивов нечетной длины

The prompt:
Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.
A subarray is a contiguous subsequence of the array.
Return the sum of all odd-length subarrays of arr.

Мои мысли

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

Side Note: I’m currently using Javascript for a technical interview language. It’s what I’m most familiar with, and I would encourage you to do the same. Interview with what you’re comfortable with, that’s key!

Мысли о суммировании значений

  1. Одно странно: мы должны добавить каждый элемент в массив.
  2. Длина массива: если он нечетный, необходимо добавить всю длину массива!
  3. Подмассивы нечетной длины: необходимо подмассивы или фрагменты из исходного массива,
  4. Длина подмассивов изменится: нам нужно убедиться, что мы получаем все возможные подмассивы нечетной длины в исходном массиве. Длины 3,5,7 и т. Д. все нужно учитывать.

Как это выглядит? Методы и логика

For Loops: Nested For Loops кажется хорошим местом для начала. Возможно, мне удастся как-нибудь улучшить временную сложность. Мне нужно будет это написать и посмотреть…

  1. Добавление материала: нужно сложить значения в каждом массиве, .reduce () отлично подходит для этого.
  2. Создание вложенных массивов: вы можете подойти к этому несколькими способами, я выбрал .slice (), вы можете вырезать массивы, начав и завершив индексы. Это будет играть со структурой For Loops!

МАМА !!! … Я застрял…

Обычно я уделяю себе от 20 до 40 минут. Я рекомендую это; он отлично подходит для адаптации вашего мышления к среде технического собеседования. Это также дает вам хорошую оценку того, на каком этапе вашего мыслительного процесса вы находитесь. Время играет здесь важную роль, лучше работать с ним, чем исключать его из практики.

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

Прежде чем у меня закончится время

  1. Реализованы вложенные циклы For
  2. Настройте переменную, содержащую промежуточную сумму
  3. Настройте переменную, которая содержит нарезанные подмассивы
  4. Настройте редуктор для переменной срезанного подмассива
  5. подключил редуктор к моей переменной текущего итога с помощью оператора «+ =»

Мои ценности были неверными, и я не мог понять, почему за это время. Но что это было? Как я мог разрезать массивы на ЛЮБУЮ нечетную длину и складывать их все? Меня очень беспокоило, почему я не могу этого понять ...

Мой выбор

Почему все ломается и почему вы терпите неудачу, имеет значение. Это важнее ответа (ИМХО). Глядя на простое для понимания решение, я увидел свою вопиющую ошибку. Мне нужно было настроить циклы for так, чтобы моя переменная среза могла вместить ВСЕ переменные нечетной длины.

Этого можно добиться следующим образом:

Outer For Loop

  1. Установите i = 1
  2. Установите i ‹= arr.length
  3. Установите i + = 2.

Внутренний цикл For

  1. Установите обр. длина-i
  2. arr.slice (j, j + i)

Неужели это было не так уж и далеко, правда? Неправильный! Не закрывайте глаза на это; вы увидите почему!

  • Счетчик внешнего цикла перемещается самым медленным, поэтому он должен двигаться следующим образом: с 1 на 3, затем с 3 на 5 и так далее.
Outer Loop's Setup
for (let i = 1; i <= arr.length; i+= 2) {...
i = 1, then... i = 3, then ... i = 5, etc.
  • Счетчик внешнего цикла For должен быть МЕНЬШЕ ИЛИ РАВНО исходной длине массива . Разница между ‹и‹ = в том, что вы не добавляете последние наборы подмассивов, включая весь массив (если он нечетный).
No, Wrong!!!
for (let i = 0; i < arr.length; i++) {...
Correct solution !!!
  for (let i = 1; i <= arr.length; i+= 2) {...
  • Счетчик внутреннего цикла For должен проигрывать внешнему циклу For Loop. Мы вычитаем длину массива на счетчик внешнего цикла, поскольку он пропорционален размеру каждого подмассива. Помните, что эти подмассивы растут на следующее нечетное число!
for(let j = 0; j <= arr.length - i; j++){...
for(let j = 0; j <= arr.length - 1; j++){...
for(let j = 0; j <= arr.length - 3; j++){...
for(let j = 0; j <= arr.length - 5; j++){...
  • .slice () отлично подключается к 2 циклам For на этом этапе; если вы заметили внутренний и внешний счетчики при сложении, дайте вам текущий подмассив нечетной длины. Похоже, что…
arr.slice(i, j+ i)
INNER CYCLE: round 1
arr.slice(0, 0 + 1)
arr.slice(1, 1 + 1)
arr.slice(2, 2 + 1) ...
INNER CYCLE: round 2
arr.slice(0, 0 + 3)
arr.slice(1, 1 + 3)
arr.slice(2, 2 + 3) ...

Заключение

Одна из неприятных вещей в решении новых проблем - это отсутствие накопленного опыта. Это не означает, что вы не можете зарабатывать на жизнь программированием, это означает, что вам нужно больше внимания. Для Loop счетчиками можно управлять несколькими способами. Мне не хватало понимания некоторых базовых техник и того, как их применять в любой ситуации. Отсюда я буду работать над такими же проблемами. Может быть, даже вернусь к этому через несколько недель. Это укрепит то, чего я не знаю. Опыт - невероятный учитель, если вы потратите время на то, чтобы по-настоящему его выслушать. Ознакомьтесь со всем решением ниже и продолжайте кодировать!

Correct Solution:
const sumOddLengthSubarrays = function(arr) {
let result = 0;
    
    for (let i = 1; i <= arr.length; i+= 2) {
        
        for(let j = 0; j <= arr.length - i; j++){
           
            let oddLength = arr.slice(j, j+i)
            result += oddLength.reduce((a,b) => {return a + b})
        }   
    }
    return result
};

Ссылки: