5
\$\begingroup\$

there is a video on life at google about what an interview would be like and so i watched it and decided to go along and come up with a solution to the problem myself and i found it really easy this is the solution i came up with

the question is to make a program to find 2 numbers in an array that add up to a sum return true if two such numbers exists return false if they do not

var gotPair = function(arr, sum) {
  this.data = arr;
  this.sum = sum
  this.check = [];
  this.num = null;
  this.out = false;
  for (var i = 0; i < this.data.length; i++) {
    this.num = this.sum - this.data[i];
    if (check.includes(this.num)) {
      this.out = true;
    }
    this.check.push(data[i]);
  }
  return this.out;
}

did i do a good job? i made sure it always worked so tell me if its good. i currently want to work for google and i am 14 so anyone who can help me get there i would be very grateful

\$\endgroup\$
4
\$\begingroup\$

Danger code!

Did you do a good job?

Well I could not give your function a pass. Your solution works, but I would never use it in any environment apart from the testing environment. The reason is your use of the global scope.

Global scope for the browser is window. It is also referenced via this outside functions, and inside functions it is also referenced by this if the function is not bound to another this.

To put it another way your code is the same as

var gotPair = function(arr, sum) {
  window.data = arr;
  window.sum = sum
  window.check = [];
  window.num = null;
  window.out = false;
  for (var i = 0; i < window.data.length; i++) {
    window.num = window.sum - window.data[i];
    if (check.includes(window.num)) {
      window.out = true;
    }
    window.check.push(data[i]);
  }
  return window.out;
}

And if not in strict mode the code would be the same as

var gotPair = function(arr, sum) {
  data = arr;
  sum = sum
  check = [];
  num = null;
  out = false;
  for (var i = 0; i < data.length; i++) {
    num = sum - data[i];
    if (check.includes(num)) {
      out = true;
    }
    check.push(data[i]);
  }
  return out;
}

Your code would overwrite any global scoped variables, and is completely unsafe for general use.

If on the other hand you had bound a specific object to the function to isolate the variables from the global or containing scope then you still have some problems.

General issues

The function needs to return if any 2 of the array's numbers add up to sum. In the loop you check for the match and set a flag. But the condition has been meet, there is no need to check for any more matched. You should return true at the first match, this saves CPU cycles and memory.


You also create too many variables. If you are using something only once in the same block then it is best to use it in place.

eg

// num is just unneeded noise
num = sum - arr[i];
if (check.includes(num)) {   

// better to do
if (check.includes(sum - arr[i])) {   

This is true in most cases, but if the expression (sum - arr[i]) is a complicated on that would stretch the if statment past 80 chars then it would be best to use the variable.


You are also copying the arguments for no reason. You don't need to do this.


Use function declarations rather than function expressions.

// function declaration good
function gotPar(arr, sum) { ...

// function expression not so good
var gotPair = function(arr, sum) { ...

Why. it has to do with the assignment of the name. A function declaration is available in the entire scope that it is declared in. A function expression is undefined until the expression has been run.

testA(); // Works and outputs "Hi from A"
testB(); // This throws a ReferenceError testB is undefined
         // because testB exists as a variable but as yet 
         // has not been assigned the function

function testA() { console.log("Hi from A") }
var testB = function() { console.log("Hi from B") }

Avoid using more memory than you have to. The array check is a duplicate of the arr data. You can Use the existing arr and use the Array.includes second argument to set the start location of the search.

Rewrite of you solution

As you solved the problem, and the logic is sound I rewrite your code using your logic but with some improvements.

function gotPair1(arr, sum) {
  var i;
  for (i = 0; i < arr.length - 1; i++) {
    if (arr.includes(sum - arr[i], i + 1)) { return true }
  }
  return false;
}
\$\endgroup\$
  • \$\begingroup\$ In your rewrite, check.includes should be arr.includes. \$\endgroup\$ – Gerrit0 Oct 18 '17 at 4:52
  • \$\begingroup\$ @Gerrit0 Thanks I did not see that... \$\endgroup\$ – Blindman67 Oct 18 '17 at 5:05
  • \$\begingroup\$ arr.include would not work if the array had multiple of the same number \$\endgroup\$ – Sylas Cuthill Oct 18 '17 at 20:24
  • \$\begingroup\$ @SylasCuthill I have tested that (not exhaustively) and can't reproduce the error. Do you have example arguments that will cause it to fail? I read your post to mean "if any 2 numbers add up to sum return true, else false" thus gotPair([1,2,3,6,7,6], 12) === true and gotPair([6,6,7,6], 13) === true and gotPair([1,2,3,6,7,6], 14) === false. Or are duplicates considered the same number? \$\endgroup\$ – Blindman67 Oct 18 '17 at 21:12
4
\$\begingroup\$

There are a few problems with the function right now.

  1. gotPair leaks variables to the global scope. When you say this.data, this refers to the global scope so you create a global property called data. See How does the "this" keyword work? on SO.

  2. Instead of storing an out variable, you can just return true when you find a match. This both reduces the complexity of the function and improves the speed. Imagine you have an array of 10 billion elements and you find the match in the first 2 elements. There's no need to go through the rest of the array.

  3. Avoid creating variables you don't need. this.data is just arr, num isn't necessary as the subtraction can be performed in the call to includes, this.sum is the same as sum, and check is not needed as it is just a copy of arr from index 0 to i.

Here are a few alternative implementations.

Similar to your logic, but looping backwards so that we can take advantage of the fromIndex argument of the includes function. I've included type checks in this function to show how they might be done, but some people prefer to leave them out in Javascript and let the function throw "naturally".

function hasSumPair(arr, sum) {
    if (!Array.isArray(arr)) throw new Error('The first argument must be an array')
    if (Number.isNaN(sum)) throw new Error('The second argument must be a number')

    for (let i = arr.length - 2; i >= 0; i--) {
        if (arr.includes(sum - arr[i], i)) {
            return true
        }
    }
    return false
}

Explicitly looping through the array twice. This makes what the function is doing very clear but results in code that is somewhat uglier.

function hasSumPair(arr, sum) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length - 1; j++) {
            if (arr[i] + arr[j] === sum) {
                return true
            }
        }
    }
    return false
}

Here is a one liner that will have some problems with very large arrays since it will copy the array for each run.

function hasSumPair(arr, sum) {
    return arr.some((num1, index) => arr.slice(index + 1).some(num2 => num1 + num2 === sum))
}

This implementation is not the fastest as it has to sort the array first. If you can assume that the array is sorted, this would be the fastest solution (which is often very important at interviews for companies like Google)

function hasSumPair(arr, sum) {
    // .sort() mutates the array, so copy it using .slice() first.
    let sorted = arr.slice().sort()
    for (let i = 0; i < sorted.length - 1; i++) {
        for (let j = i + 1; j < sorted.length && sorted[j] + sorted[i] <= sum; j++) {
            if (sorted[j] + sorted[i] === sum) {
                return true
            }
        }
    }
    return false
}

The same function as above, but making use of some (Note that on the last iteration, arr[i + 1] will be undefined which will result in a NaN result and will work as expected). This is likely the implementation I would use if the array is sorted, and likely even if the array isn't sorted if the speed is not an issue.

function hasSumPair(arr, sum) {
    return arr.slice().sort()
        .some((a, i, sorted) => sorted.slice(i).some(b => a + b == sum))
}

Which of these functions is best is largely a matter of opinion and the case in which it will be used. Most of the time I recommend choosing readability over speed. Speed should only be considered if the time it takes to run the function is creating problems.

\$\endgroup\$
  • 1
    \$\begingroup\$ Ah, good point @insertusernamehere, I completely forgot about that. I'll remove that function, also fixing a couple other mistakes. I clearly wasn't completely with it when I wrote this last night. \$\endgroup\$ – Gerrit0 Oct 18 '17 at 15:04
3
\$\begingroup\$

In addition to other answers, I would like to point out that this implementation has a O(n²) performance, which can be improved by flipping the array to perform an index-lookup instead of calling Array.prototype.includes, which has a O(n) performance.

Here is an implementation which has a better complexity:

function gotPairFlipped(arr, sum) {
  var flipped_arr = [];

  for (var i = 0; i < arr.length; i++) {
    flipped_arr[arr[i]] = (flipped_arr[arr[i]] || 0) + 1;
  }

  for (var j = 0; j < arr.length; j++) {
    if (2 * arr[j] === sum) {
      return flipped_arr[(sum - arr[j])] > 1;
    }

    if (typeof flipped_arr[(sum - arr[j])] !== 'undefined') {
      return true;
    }
  }

  return false;
}

And here is a benchmark on large (100K) arrays: https://jsperf.com/sum2

Beware that while this algorithm's complexity is better, it doesn't mean that it will be faster everytime. It heavily depends on the input size: larger arrays will profite from this optimization, while smaller arrays will take longer to process.

\$\endgroup\$
  • \$\begingroup\$ you don't need that for loop just use arr.reverse \$\endgroup\$ – Sylas Cuthill Oct 18 '17 at 20:38
  • \$\begingroup\$ @SylasCuthill: Array.prototype.reverse just changes the order of the elements, while the loop is to flip the array: keys become values and values become keys. \$\endgroup\$ – Benoit Esnard Oct 19 '17 at 7:58
  • \$\begingroup\$ The function does not work if result should be false but array contains one value that is half the sum. eg gotPairFlipped([1,95],190) returns true but should return false \$\endgroup\$ – Blindman67 Oct 19 '17 at 8:22
  • \$\begingroup\$ @Blindman67: indeed, fixed. Misread the question and assumed the expected result to be true. Thanks for the report! \$\endgroup\$ – Benoit Esnard Oct 19 '17 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.