QUIZIO

hasPairWithSum: Google coding interview solution

There is a nice video of two Google engineers demonstrates a mock interview question, and there is simple solutions for this question.


The question goes as follows:

Given a collection of numbers and a number target, find a matching pair that is equal to a given target.
If there is a matching sum, return true, otherwise, return false .

For example:

Input: nums = [1,2,3,9], target = 8
Output: false
Output: No matching pair


Input: nums = [1,2,4,4], target = 8
Output: true
Output: Matching pair found nums[2] + nums[3] = 8

There is a simple solution to this question. In Javascript (as well as in other coding languages) We can use the power of Set() object.
The Set object lets you store unique values of any type, whether primitive values or object references.
Why we are not just using array method such includes()?
The methods an array uses to search for items has a linear time complexity of O(N). In other words, the run-time increases at the same rate as the size of the data increases. By contrast, the methods used by Sets to search for, delete and insert items all have a time complexity of just O(1) — that means the size of the data has virtually no bearing on the run-time of these methods!



Here is the solution:

function hasPairWithSum(nums, sum) { const set = new Set() let sumArr = [] for (let i = 0; i < nums.length; i++) { const complement = sum - nums[i] if (set.has(complement)) { sumArr = [[...set].indexOf(complement), i] } else { set.add(nums[i]) } } return !!sumArr.length }

Similar question on LeetCode:

https://leetcode.com/problems/two-sum/


LeetCode question is slightly different. twoSum function have to return indices of the two numbers such that they add up to target. Here is the solution to Leetcode twoSum question that beats 89.61 % of javascript submissions.

function twoSum(nums, sum) { const set = new Set() let sumArr = [] for (let i = 0; i < nums.length; i++) { const complement = sum - nums[i] if (set.has(complement)) { sumArr = [[...set].indexOf(complement), i] } else { set.add(nums[i]) } } return sumArr }
© 2021, Quizio.io