RECENT INTERVIEW QUESTION: Find Sum-Pairs in an Array that add up to X (JS/Ruby Solutions)

Recently got this question in a technical interview for a junior dev position. It's a pretty straightforward algorithm... still fumbled through it a lil bit to start (nerves). They also asked me to do it in Javascript specifically, which I'm still getting comfortable with (Ruby was language #1 for me). Anyway, check it out below. I'll talk through what I like/dislike about the solution, and I'll include a Ruby solution at the end too.

Given an array of integers, write a function that outputs all the combinations of two elements in the array that add up to x. Assume the array contains all unique values.
ex. if x = 5 and array = [1, 2, 3, 4, 5], the function should return [1, 4] and [2, 3]... bc each pair adds up to 5

My initial pseudocode:

// function(array, X)
  // establish a return collection PAIRS
  // loop through the input array
    // at each value, search the remaining values for a pair that sums to X
    // if that pair value exists
      // push the value and its pair into an array
      // push that array into the PAIRS collection
  // return the PAIRS collection

So it took me a couple mins to devise that strategy and talk through it with the interviewer, and then I started coding. It probably took me 20 mins of tinkering to get to the eventual solution below. I was committed to the algorithm logic (above), so I'd say most of my time was actually spent:

1. sweating
2. figuring out / remembering the return-types of javascript functions I was trying to use (e.g. does .find() return an individual value, or an array... that type of thing)
3. testing/tinkering and debugging it at the end

My eventual solution:

const getSumPairs = (array, x) => {
  let pairs = [];
  
  do {
    let num = array.shift();
    let numPair = array.find(value => value === x - num);
    if (numPair !== undefined) {
      pairs.push([num, numPair]);
    }
  } while (array.length > 1);

  return pairs.length > 0
    ? console.log(...pairs)
    : console.log(`There are no value pairs that add up to ${x}!`);
};


// A coupla test-cases

const array = [1, 2, 3, 4, 5];
const x = 5;
getSumPairs(array, x);
// [ 1, 4] [2, 3]

const array2 = [12, 2, 3, 21, 0, 9, 5, 6, 7, 8, 1, 4, 10, 11, 13];
const y = 12;
getSumPairs(array2, y);
// [ 12, 0 ] [ 2, 10 ] [ 3, 9 ] [ 5, 7 ] [ 8, 4 ] [ 1, 11 ]

--

A quick 'how it works', step-by-step:
The pseudocode above essentially walks through it in plain english, BUT a little more detail:

1. First, declare a function getSumPairs() that takes two arguments: array and x. Remember we're looking to return all pairs of values from the array that add up to x.
2. Declare a variable pairs -- this empty array will eventually hold all of the sub-arrays containing the number-pairs. This is what we will ulitimately have the function return.
3. I use a do... while loop to loop through the following code block until there is only one value left in the array.
4. Inside of the loop, we first declare two variables: num and numPair. The num is set to the first value (index[0]) of the input array -- the shift() function removes the first value from an array (this permanently manipulates the input array, which is not very wise. I'll elaborate on that in the next section). The numPair variable is set to the return value of array.find(value => value === x - num). Basically this little .find() function will search through the array from left-to-right, and it will return the first value it finds that matches the logic on the right-hand side of the =>, i.e. it'll return the first value that is equal to x - num, or the sum-pair of num. If num = 1 and x = 5, numPair will search through the array and return a value of 4 if/when it finds it. If no such value exists, numPair will be undefined, which is import in the next step.
5. If numPair === undefined, nothing will happen, because NO sum-pair exists (in the array) for the current value of num, so the loop will simply restart, setting num to the next number in the array.
6. If numPair does exist, put the two values in an array [num, numPair] and push that array into that pairs array that we established in the first line (step 2). pairs will be an array of arrays, assuming some sum-pairs exist.
7. I love ternary operator statements. Just love em. Idk why. They feel super clean. The return statement logic is: if pairs.length > 0, i.e. if any sum-pairs exist, return them (check the spread operator to make them print a little more cleanly). Otherwise, return a lil sentence that says there aren't any pairs.

---

Something I would change:
Overall I was actualy pretty happy with the logic. But, the thing that screamed at me when I went back to look at it... I would NOT use the .shift() function on the input array. Idk, imagine you're using this function on a set of real user data... if you shift() off the first value in the function, you're permanently manipulating the input array. So say the input dataArray has the values [1, 2, 3, 4, 5]... once your perform this function on it, if you were to try to then access dataArray again, it would return [1], because in the function we manipulated it until there was only one value left. A much, much better way to do this would be to first make a copy of the input array, like so:

let arrayCopy = [...array]

We can then replace EVERY use of the array variable in the rest of the function with arrayCopy, which will return the exact same output, without affecting the original array. e.g.:

let num = arrayCopy.shift();
let numPair = arrayCopy.find(value => value === x - num);

Noice.

Something I like:
Like I said, I was fairly happy with it. One intentional decision that I think is worth pointing out, is the use of the .find() function. There are so many ways to iterate through an array and extract a value (poke around here). I like .find() here because it only performs the work that is necessary. In the question prompt we are told that the array has all unique values... Since the .find() function returns the first element in the array that satisfies the logic, we know that once we find the correct number-pair, the function will stop searching. So we might only need to search through half of the array to find our value. Contrast that with .filter(). I used .filter() initially, and then refactored for two reasons:

1. .filter() will always search through the entire array to find values that match whatever logic we give it... even if it finds the correct value half-way through it'll keep going to the end of the array, looking for more matching values. This is a useful function, and would've been appropriate had we not been told that all of the array values are unique.
2. .filter() returns an array (vs. .find() which returns just the specific value, in this case the integer). So it's just a little less clean.

One other thing I'd like to mention -- There's a way to do this algorithm with nested for-loops. That's where my brain went initially, and I would guess that's how many people might choose to solve this problem... nested for-loops with two different counter-variables i and j, or something like that. I still have a sneaky nested loop structure here, but it's a built-in function loop (.find()) within a do...while loop, which I personally like better for this problem. I find to be easier to comprehend/read. Nested for-loops sometimes throw me for a loop (hahahahah), especially in javascript bc the syntax is less familiar, and I usually end up misplacing a bracket somewhere.

---

As promised, I wrote a little Ruby solution:

def getSumPairs(array, x)
  all_pairs = array.combination(2)
  sum_pairs = []
  all_pairs.each do |pair|
    sum_pairs << pair if pair.reduce(:+) == x
  end

  p sum_pairs
end

# A coupla test-cases
array = [1, 2, 3, 4, 5];
x = 5;
getSumPairs(array, x);
# [[ 1, 4] [2, 3]]

array2 = [12, 2, 3, 21, 0, 9, 5, 6, 7, 8, 1, 4, 10, 11, 13]
y = 12
getSumPairs(array2, y)
# [[12, 0], [2, 10], [3, 9], [5, 7], [8, 4], [1, 11]]

As you can see it's about half the length of the Javascript solution. That's bc I used some Ruby cheat-codes, like .combination and .reduce, and some syntactic sugar (e.g. sum_pairs << pair if pair.reduce(:+) == x) just to make it as compact as possible and play around with a different logical approach.

I'll quickly explain the logic:

1. Define a getSumPairs method that takes array and x as arguments.
2. Establish all_pairs variable and set it equal to array.combination(2), which returns an array of sub-arrays containing ALL possible combinations of 2-values from the input array. (so if array = [1, 2, 3] it'll return [[1, 2], [1, 3], [2, 3]]). As far as I know, there is no magic Javascript function that does this. Just a little Ruby magic. We also establish a sum_pairs empty array here, which is the array we will eventually return.
3. Iterate through every value-pair in the all_pairs array, and if the value-pair adds up to x, shovel it into the sum_pairs array.
4. When that loop is finished, return the sum_pairs array.

K see ya. Thx for reading, love you guys,

noah

view raw SumPairs.md hosted with ❤ by GitHub