Algorithms Coursera Part II Programming Assignment 4.js

Algorithms Coursera Part II Programming Assignment 4.js

/* eslint-env node */

/**
* The goal of this problem is to implement a variant of the 2-SUM algorithm
* covered in this week's lectures.
*
* The file contains 1 million integers, both positive and negative (there
* might be some repetitions!).This is your array of integers, with the ith
* row of the file specifying the ith entry of the array.
*
* Your task is to compute the number of target values t in the interval
* [-10000,10000] (inclusive) such that there are distinct numbers x,y in
* the input file that satisfy x + y = t. (NOTE: ensuring distinctness
* requires a one-line addition to the algorithm from lecture.)
*
* Clarification from the forums: What you are trying to find is number of
* values in range [-10000,10000] (20001 max,) that have AT LEAST ONE PAIR
* that would add to that number. (NOT the number of distinct pairs)
*
* Write your numeric answer (an integer between 0 and 20001) in the space
* provided.
*
* OPTIONAL CHALLENGE: If this problem is too easy for you, try implementing
* your own hash table for it. For example, you could compare performance
* under the chaining and open addressing approaches to resolving collisions.
*/

/**
* -------------------------- FILE I/O -----------------------------
*/

const fs = require("fs");

const input = [];

/**
* Parse the text file and store it as an array where the number value of each
* row is its own element in the array.
*/
(function getInput() {
  const data = fs.readFileSync("2sum.txt", "utf8");
  const rows = data.split("\n");
  for (let row of rows) {
    // Get rid of empty row at EOF
    if (row === "") {
      continue;
    }
    // Remove excess white space at the end of the line
    row = row.trim();
    input.push(Number(row));
  }
}());

// console.log(input);

/**
* -------------------------- 2-SUM Algorithm -----------------------------
*/

/**
* De-Duplication Pseudocode
* - When new object x arrives,
*   - Look up if x is in hash table H
*   - If not found, insert x into H
*
* 2-Sum Pseudocode
*   1. Insert elements of A into hash table H
*   2. For each x in A, lookup t - x in H
*/


/**
* Takes in an inclusive range of target, t, values and returns the
* number of target values for which there are two distinct elements
* that sum to those values.
*/
function twoSum(tRange) {
  const tMin = tRange[0];
  const tMax = tRange[1];

  // Insert elements of A into hash table H
  const H = new Map();
  for (const num of input) {
    // de-dupe check
    if (H.has(num)) continue;
    H.set(num, num);
  }

  // Get number of target values of t for which there is an x + y = t
  let numTargetValues = 0;
  for (let t = tMin; t <= tMax; t++) {
    // For each x in A, lookup t - x in H
    for (const x of input) {
      if ((x !== (t - x)) && H.has(t - x)) {
        numTargetValues++;
        // you don't have to find all pairs of (x,y) that can be summed to
        // a value t. As soon as you can find a pair of distinct (x,y),
        // you can increase the count.
        break;
      }
    }
  }
  return numTargetValues;
}

const tRange = [-10000,10000];
console.log(twoSum(tRange));
// NOTE: TRY USING CHROME DEVTOOLS DEBUGGER:
// https://medium.com/@paul_irish/debugging-node-js-nightlies-with-chrome-devtools-7c4a1b95ae27

// Solutions:
//  - testCase1.txt (range for t = [3, 10]): 8
//  - testCase2.txt (range for t = [0, 4]): 2
//  - 2sum.txt (range for t = [-10000,10000]): 427

testCase1.txt

3
-1
1
2
9
11
7
6
2

testCase2.txt

-2
0
0
4