-1
\$\begingroup\$

I was given this question during an interview. It is similar to two sum problems and I would like to ask for feedback for my solution.

Merging 2 Packages

Given a package with a weight limit limit and an array arr of item weights, implement a function getIndicesOfItemWeights that finds two items whose sum of weights equals the weight limit limit. Your function should return a pair [i, j] of the indices of the item weights, ordered such that i > j. If such a pair doesn’t exist, return an empty array.

Example:

input: arr = [4, 6, 10, 15, 16], lim = 21

output: [3, 1] # since these are the indices of the # weights 6 and 15 whose sum equals to 21 Constraints:

[time limit] 5000ms

[input] array.integer arr

0 ≤ arr.length ≤ 100 [input] integer limit

[output] array.integer

function getIndicesOfItemWeights(arr, limit) {  
  let weights = {};
  let result = []
  for ( let i = 0; i < arr.length; i++){
    let compliment = limit - arr[i];
    if (typeof weights[compliment]!= "undefinded"){
      if (i > (weights[compliment])){
        result.push(weights[compliment], i);
        //return [i, weights[compliment]];
      } else {
        return [weights[compliment] , i];
      }
    } else {
      weights[arr[i]] = i; // put new weight into weight obj
     
    }
  }
  return [];

}

let arr = [4, 6, 10, 15, 16];
let limit = 21;
console.log(getIndicesOfItemWeights(arr, limit))


// output: [3, 1] # since these are the indices of the
// weights 6 and 15 whose sum equals to 21

\$\endgroup\$
  • 2
    \$\begingroup\$ Your code logs [undefined, 0] - should it actually log [3, 1]? \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Jan 30 '19 at 0:08
  • \$\begingroup\$ Is the array of weights sorted? \$\endgroup\$ – vnp Jan 30 '19 at 4:08
  • 1
    \$\begingroup\$ As Sam Onela pointed out, the code doesn't work as intended, returning [undefined, 0] instead of [3, 1]. The commented out return statement looks suspicious, so is the typo "undefinded" (instead of undefined) \$\endgroup\$ – janos Feb 10 '19 at 16:59
1
\$\begingroup\$

there are many ways to aproach this, somehow i find your solution alittle bit difficult to read but i like the idea of using compliment = limit - arr[i];

a simpler way would be either using nested for loops :

const getIndicesOfItemWeights = (arr, limit) => {
  let result = [];

  for (let i = 0; i < arr.length; i++) {
    if (result[0] && result[1]) break; // break out of the loop if the result is full.

    for (let j = i; j < arr.length; j++) {
      if (arr[i] + arr[j] === limit) { // if the sum of two elements is eqaul to the limit.
        result.push(i, j); // push the indices to the result array.        
        break; // break out of the second loop
      }
    }
  }

  return result.sort((a, b) => b - a);
}

const arr = [4, 6, 10, 15, 16];
const limit = 21;

const x = getIndicesOfItemWeights(arr, limit);
console.log(x)

or take the shortcut of using the compliment = limit - arr[i];

const arr = [4, 6, 10, 15, 16];
const limit = 21;

const getIndicesOfItemWeights = (arr, limit) => {
  let result = [];

  arr.forEach(e => {
    const a = arr.find(x => x === limit - e);
    if (a && result.length === 0) { // if the element is found and the array is empty, push the indices to the result array
      result.push(arr.indexOf(e), arr.indexOf(a));
      return;
    }
  })

  return result.sort((a, b) => b - a);
}

const x = getIndicesOfItemWeights(arr, limit);
console.log(x)

\$\endgroup\$
0
\$\begingroup\$

this is my updated solution after the code review:

let getIndicesOfItemWeights = function(arr, limit) {
  let map = new Map()
  let indices = []
  for(let i = 0; i < arr.length; i++){
    let difference = limit-arr[i]
    if(map.has(difference)){
      indices.push(i, map.get(difference))
      return indices
    } else {
      map.set(arr[i], i)
    }
  }
  return indices
}
\$\endgroup\$

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