Leetcode Interview Question 1: Две суммы

Достигли ли вы точки в своей карьере, когда «когда-то так легко» проблемы кодирования стали сложными? Любой, кто занимается разработкой программного обеспечения, знает, что раунды программирования отличаются от традиционных повседневных методов работы. Со временем и разным жизненным циклом разработки программного обеспечения вы можете столкнуться с другим видом «стресса и напряжения». Но в тот момент, когда вы решите измениться, вам нужно вернуться к старым добрым временам программирования. Вам нужно выучить определения. Вы должны согласовать определение с вашим повседневным образом работы. Прежде всего, вам нужно взломать этот раунд кодирования. А тем, кто стремится к крупным брендам, придется пройти пару раундов программирования. Просьба о «временной сложности» и «наилучшем возможном решении» не исчезнет. По крайней мере, в ближайшие несколько лет, если вы разработчик программного обеспечения, вам придется надеть обувь более свежего и освоить массивы, стеки, связанные списки, деревья и битовые манипуляции.

С учетом вышесказанного, последние 6 лет мое путешествие было прекрасным. Спасет ли меня полувековой опыт от алгоритмов? Конечно, нет! Мне все еще нужно знать, как решать проблемы как можно быстрее. И эти 40 минут с интервьюером и один алгоритм могут сделать или сломать мои следующие несколько лет.

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

Итак, приступим.

Постановка задачи

Учитывая массив целых чисел nums и целого числа target, верните индексы двух чисел, чтобы они в сумме составляли target.

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

Вы можете вернуть ответ в любом порядке.

Пример 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Пример 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Пример 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Решение

Вот решение, написанное на Javascript, которое решает все возможные тестовые случаи в LeetCode.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
 let output = [];
 for(let index in nums){
  let item = nums[index];
  let diff = target — item;
  let found = nums.indexOf(diff);
  if(found != -1 && found != index){
    output.push(found);
    output.push(Number(index));
    return output;
  }
} 
};

Сделай или умри момент в интервью

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

Псевдокод для двух сумм

  1. Итерировать по каждому элементу в массиве
  2. Найдите разницу между ожидаемой целью и текущим элементом
  3. Проверьте индекс ожидаемой цели. Если цель присутствует, indexOf вернет позицию элемента. И, если элемент отсутствует в массиве, он вернет -1. С помощью этой логики мы можем перейти к поиску пары, которая добавляется к цели.
  4. Если разница обнаружена, и если текущий индекс равен индексу разницы, мы игнорируем этот элемент. Почему? Пример 3 не принесет ожидаемого результата.

JavaScript в решении

Чтобы решить проблему «Две суммы», мы использовали несколько методов, которые являются «специальными» для Javascript. Теперь, в реальном интервью, есть вероятность, что вас спросят больше об этих нативных методах. И всегда было бы хорошо их лучше освоить.

Два ключевых вывода из решения: t способ итерации массива && использование indexOf

Цикл FOR

Если вы пишете код в течение года, то наверняка знаете, что цикл for широко используется. Было бы сложно взломать программное решение без зацикливания. А в Javascript у вас есть три интересных способа перебора массива.

Метод 1

let array = ['a','b','c','d','e'];
for(let i=0; i<array.length; i++){
  console.log(array[i]); // this will print the item in index i
}

В приведенном выше методе вы будете использовать «итератор» i для идентификации элемента в каждом индексе массива. Длина массива используется, чтобы решить, нужно ли остановить или продолжить итерацию. Результатом выше будет: a b c d e

Способ 2

let array = ['a','b','c','d','e'];
for(let item of array)
  console.log(item);
let obj = {a:1, b:2, c:3}
for(let item of obj)
  console.log(item) // throws an error

В методе 2 вы должны использовать for… of.

for… of интересуются значениями итерируемого объекта. Это устраняет необходимость в подсчете и логике выхода в цикле for. Этот метод можно использовать для любых повторяемых данных. Это означает, что вы не можете использовать for..of для объектов. Но он хорошо работает с массивами, наборами и т. Д. Результат метода 2: a b c d e

Способ 3

let array = ['a','b','c','d','e'];
for(let index in array)
  console.log(array[index]); // prints a b c d e
let obj = {a:1, b:2, c:3}
for(let item in obj)
  console.log(obj[item]) // prints 1 2 3

В методе 3 вы должны использовать for… in.

for… in используется для перебора перечислимых ключей структуры данных. Как и for..of, этот метод также устраняет необходимость в подсчете или логике выхода. В отличие от метода 2, вы можете использовать for… in для итерации по объектам. Когда for… in используется с объектом, он возвращает перечислимые ключи свойств объекта. Когда for..in используется с массивом, он фокусируется на индексе, и этот индекс можно использовать для выборки элементов из массива.

индекс

indexOf - широко используемый метод в JavaScript. Он используется, чтобы определить, присутствует ли элемент в массиве. Как упоминалось ранее, если элемент присутствует в массиве, он вернет позицию элемента в массиве. И, если элемент отсутствует в массиве, он вернет -1.

Если вы проходите собеседование на должность фронтенд-разработчика в любом из крупных брендов, вас, скорее всего, попросят полифилл. Мне всегда интересно, почему. И я предполагаю, что покупателю, живущему в самых глубоких переулках средневековья, случается, что он нравится и использует ваш продукт. Несмотря на то, что все современные браузеры поддерживают самые последние изменения - этот клиент использует специально настроенный браузер, который не поддерживает код, который вы пишете! Как бы удручающе это ни звучало, ваш код теперь запускается этим клиентом в его настроенном браузере. Что случилось бы? Ваш код не компилируется. Почему? Его браузер не поддерживает ваш код! Итак, как сделать так, чтобы он поддерживал? Напишите пару проверок, а затем создайте полифиллы для каждого метода, который он не поддерживает.

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

Полифилл для indexOf может показаться кошмаром. Момент, когда начинаешь терять уверенность и даже паниковать. Но это не обязательно должна быть игра «сделай или умри». Вместо этого расшифруйте роль, которую играет метод indexOf, и начните писать. Именно этим мы и займемся в следующих двух строках.

Псевдокод: полифилл для IndexOf

  1. Если indexOf вызывается значением null или undefined, генерировать TypeError
  2. Преобразование вызываемого объекта в объект.
  3. Оцените длину вызываемого
  4. Если вызываемый пуст, вернуть -1
  5. Итерируйте по вызываемому, используйте перечислимое свойство объекта, чтобы проверить, является ли цель значением объекта или нет
  6. Клавиша возврата, если объект найден
  7. Вернуть -1, если объект не найден
Array.prototype.myIndexOf = function(target, from){
let obj = Object(this);
if(obj == undefined || obj == null)
   throw new TypeError("Incompatible Type");
let len = obj.length;
if(len == 0)
   return -1;
let start = from | 0;
for(; start<len; start++)
{
   if(obj[start] === target)
     return start;
}
return -1;
}

Заключение

К настоящему времени вы решили проблему «двух сумм» наизнанку для цикла внешнего программирования. Вы придумали точное решение, поняли основы Javascript, используемого кодом, и даже написали полифилл для одного из собственных методов.