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

Голям въпрос за интервю за кодиране на технологии — Проблем с две суми

Подробно внедряване за решаване на проблем с две суми като софтуерен инженер

Преглед

Това е статия от поредицата големи въпроси за интервю за кодиране на технологии и тази статия е за проблема с две суми. Проблемът с две суми е много често срещан въпрос за интервю за ролята на софтуерен инженер във всяка технологична компания. Това се категоризира като лесен проблем в сесия на интервю за кодиране. След като разберете добре тази задача с две суми, ще ви помогне много да решавате по-трудни проблеми с ниво като Три суми, която по някакъв начин е продължение на проблема с две суми.

Проблем

Даден е масив от цели числа „nums“ и цяло число „target“, връща индекси на двете числа, така че сумата им да дава цел. Може да приемете, че всеки вход ще има точно едно решение и не можете да използвате един и същи елемент два пъти. Можете да върнете отговора в произволен ред.

Например

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

Ограничения

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Решаване на задача с две суми

Първо, нека се опитаме да разберем проблема. Даден ни е масив от цели числа и целева сума. Нашата работа е да напишем функция, която връща индекси на два елемента в този масив, когато добавим тези два елемента, тя трябва да бъде равна на дадената целева сума. Има забележка от проблема:

Ако има няколко такива двойки, трябва да върнем индексите на първата двойка, която намерим отляво.

Това означава, че не трябва да се тревожим за реда на изхода. Например, можем да върнем [0, 1] или [1, 0] от горния пример.

Дефинирайте тестови случаи

Второ, ние дефинираме тестови случаи за този проблем, за да сме сигурни, че разбираме добре този проблем. Това са пет тестови случая, включително щастливи случаи и крайни случаи. Тестовите случаи по-долу обхващат както щастлив случай, така и крайни случаи като отрицателна, положителна, нулева стойност и не може да намери целта от входния масив:

testCase1nums[] = {5, 7, 12,1};
testCase1Target = 12;
expectedResult1 = [0, 1]
testCase2nums[] = {3, 5, 0};
testCase2Target = 6;
expectedResult2 = null
testCase3nums[] = {0, 3};
testCase3Target = 3;
expectedResult3 = [0, 1]
testCase4nums[] = {0, -1, 2, -3, 1};
testCase4Target = -2;
expectedResult4 = [3, 4]
testCase5nums[] = {4, -11, 22, -23, 31};
testCase5Target = -20;
expectedResult5 = null

Трябва да приемете тази стъпка като добра практика преди кодиране, защото помага да сте сигурни, че вие ​​и интервюиращият имате еднакво разбиране за проблема. Като дефинира тестовите случаи и очаквания резултат за всеки случай, ако не сте разбрали, интервюиращият може да ви помогне да коригирате разбирането си, за да разрешите проблема, като избягвате да губите време.

Решение 1: Груба сила

След това, как първо да решите този проблем с директен подход? Интервюиращият се интересува как мислите, така че просто му говорете на глас за вашия мисловен процес.

Един наистина груб подход би бил да търсите всички възможни двойки числа, като използвате два вложени for цикъла. Въпреки че това решение е бавно, най-добре е първо да изпробвате решения с груба сила само за пълнота на проблема. Именно от тези груби решения можете да измислите оптимизации по-късно.

За даден входен масив nums[], трябва да направим следните стъпки:

  1. Изпълнете два цикъла for и проверете за всяка комбинация в дадения масив nums[].
  2. Задръжте външния цикъл на конкретен индекс и преместете вътрешния цикъл, за да получите всички възможни двойки.
  3. Във всяка итерация на вътрешния цикъл откриваме дали числата, представени от индексите на външния и вътрешния цикъл, се равняват на целевата сума.
  4. Ако nums[outerIndex] + nums[innerIndex] е равно на входната целева променлива, върнете масива {outerLoopIndex, innerLoopIndex} като резултат. В противен случай продължаваме итерацията, за да проверим за следващата двойка.
  5. Повторете горните стъпки, докато намерите комбинация, която се добавя към дадената целева променлива.

Това е кодът на Java за подхода с груба сила, следвайки стъпките по-горе:

Функция FindTwoSumSolution1:

static int[] findTwoSumSolution1(int nums[], int target) {
    int length = nums.length;
    for (int i = 0; i < (length - 1); i++) {
      for (int j = (i + 1); j < length; j++) {
        if (nums[i] + nums[j] == target) {
          int result[] = { i, j };
          return result;
        }
      }
    }
    return null;
  }

В основния метод можете да извикате тази функция и да проверите изхода с вашите тестови случаи по-горе:

public static void main(String [] args) {
    int testCase1nums[] = {5, 7, 12,1};
    int testCase1Target = 12;

    int testCase2nums[] = {3, 5, 0};
    int testCase2Target = 6;

    int testCase3nums[] = {0, 3};
    int testCase3Target = 3;

    int testCase4nums[] = {0, -1, 2, -3, 1};
    int testCase4Target = -2;

    int testCase5nums[] = {4, -11, 22, -23, 31};
    int testCase5Target = -20;
    System.out.println(Arrays.toString(findTwoSumSolution1(testCase1nums,testCase1Target)));
    System.out.println(Arrays.toString(findTwoSumSolution1(testCase2nums,testCase2Target)));
    System.out.println(Arrays.toString(findTwoSumSolution1(testCase3nums,testCase3Target)));
    System.out.println(Arrays.toString(findTwoSumSolution1(testCase4nums,testCase4Target)));
    System.out.println(Arrays.toString(findTwoSumSolution1(testCase5nums,testCase5Target)));
  }

Времева сложност: O(n²)
Пространствена сложност:O(1)

В най-лошия случай функцията по-горе има времева сложност на изпълнение O(n²). Кога ще се случи най-лошият случай? Най-лошият случай би възникнал, когато необходимата комбинация е последната комбинация, която ще бъде проверена от нашия вложен цикъл.

Можете да видите пълния код на това решение в Github.

Решение 2: HashMap

След като решите проблема с първия подход, трябва да помислите как да подобрите логиката си, така че да може да работи по-бързо и по-ефективно, това е важно, ако искате да разбиете вашето интервю за кодиране, особено когато интервюирате с компании от FAANG.

Този проблем може да бъде решен по-оптимално чрез използване на подхода за хеширане. Идеята е да използваме HashMap за съхраняване на индексите на елементите, които вече сме посетили:

  • Ключът на HashMap е числото в дадения входен масив.
  • Стойността на HashMap е индексът на числото в масива, представен от ключа HashMap.

Това са стъпки за прилагане на тази логика:

  1. Инициализирайте Integer HashMap както за ключ, така и за стойност.
  2. Повтаряне през всеки елемент в дадения масив nums[], започвайки от първия елемент.
  3. При всяка итерация намираме дали временното число присъства в HashMap. temp number= (target — nums[i]) с i като текущ индекс на итерация.
  4. Ако е налице, върнете {необходим номер индекс, текущ номер индекс} като резултат за функцията.
  5. В противен случай добавете текущия номер на итерация като ключ и неговия индекс като стойност към HashMap.
  6. Повтаряйте тази логика, докато намерите резултата, който да върнете. Ако не можем да намерим резултата, върнете null

Функция FindTwoSumSolution2:

static int[] findTwoSumSolution2(int[] nums, int target) {
    HashMap<Integer,Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
      Integer temp = (target - nums[i]);
      if(map.containsKey(temp)){
        int result [] = { map.get(temp), i };
        return result;
      }
      map.put(nums[i], i);
    }
    return null;
  }

Извикайте функцията в основния метод:

public static void main(String [] args) {
    int testCase1nums[] = {5, 7, 12,1};
    int testCase1Target = 12;

    int testCase2nums[] = {3, 5, 0};
    int testCase2Target = 6;

    int testCase3nums[] = {0, 3};
    int testCase3Target = 3;

    int testCase4nums[] = {0, -1, 2, -3, 1};
    int testCase4Target = -2;

    int testCase5nums[] = {4, -11, 22, -23, 31};
    int testCase5Target = -20;
    System.out.println(Arrays.toString(findTwoSumSolution2(testCase1nums,testCase1Target)));
    System.out.println(Arrays.toString(findTwoSumSolution2(testCase2nums,testCase2Target)));
    System.out.println(Arrays.toString(findTwoSumSolution2(testCase3nums,testCase3Target)));
    System.out.println(Arrays.toString(findTwoSumSolution2(testCase4nums,testCase4Target)));
    System.out.println(Arrays.toString(findTwoSumSolution2(testCase5nums,testCase5Target)));
  }
}

Времева сложност: O(n)
Пространствена сложност:O(n)

Тъй като трябва да посетим всички елементи на масива nums[], времевата сложност на този подход е O(n). Най-лошият случай е, когато необходимата комбинация е последната комбинация, която трябва да бъде проверена в for цикъла.

Можете да видите пълния код на това решение в Github.

Резюме

В тази статия споделих често срещан проблем Two Sum в интервю за кодиране на софтуерен инженер и как да го разреша както с брутална сила, така и с оптимални решения. Благодаря ви за отделеното време!

Ако имате проблеми с предизвикателствата, за които се нуждаете от помощ, моля, уведомете ме в коментара.

Препратки

Проблемът в тази статия е от Leetcode.

Ако ви харесва тази история, можете да последвате, да се абонирате за мен, за да бъдете първият човек, който получава следващите ми статии!

„Можете да станете член на Medium тук“, за да имате неограничен достъп до всяка история на платформата Medium. Ако използвате връзката по-горе, това също ме подкрепя, защото имам малка комисионна от Medium. Благодарим ви за вашата подкрепа!