Pergunta de entrevista da empresa Capital One

Given an array of integers, find the two integers whose sum is closest to zero (not necessarily zero). Then, optimization of code.

Resposta da entrevista

Sigiloso

2 de fev. de 2022

brute force way is to iterate over every pair of integers in the array. this is O(n^2) better way is to sort the array and then use two pointers, one that goes from left to right and one that goes from right to left. then track the max of nums[left] + nums[right]. if the sum 0 then decrement right pointer cuz you want sum to get smaller. sorting is O(n log(n)) and two pointer approach is O(n). complexity is therefore O(n log(n) + n) but since we drop non-dominant terms it's just O(n log(n))

4