Seek and Destroy flyin

Seek and Destroy flyin
0

#21

Now I will ask you another question which could make you rethink your entire algorithm.

What if you were told that the array passed (the first argument) into the function could have a million elements and the number of additional arguments could be 100,000. Would another solution be more efficient in terms of speed? Let’s assume that memory is not a factor, see if you can think of a different solution which does not iterate over the additional arguments (like indexOf, includes or any kind of for or while loops would do) during each iteration of the filter.

Hint: Think lookup table (something you have already learned on FCC) or even better - Memoization


#22

@RandellDawson

So if we use splice to remove the element from the first array then each successive argument would be searching against a continuously shorter first array as the elements are removed?

I read through the Wikipedia link and the intent seems to be to retain data from each operation in the function and each “recursion” would require less time to execute.


#23

Splice is a very expensive operation and should definitely be avoided on large arrays. It does a lot behind the scenes. No recursion is needed.

Hint #2: If I created a “lookup” object which contained the extra arguments as property names, then I could reference the object property and if it existed it would return a value other than undefined. The value undefined would indicate that particular argument value does not exist. The key point here is create the object one time, so that it can be used inside the filter callback in such a way to return true or false. This is much faster, because the arguments only have to be iterated over a single time to create the lookup object.


#24

@RandellDawson I’m not creating the lookup object correctly and I know below isn’t correct. Can you tell me if I’m way off base here?

function destroyer(arr, ...args) {
  let look = [];
  for (let j=0; j<args.length; j++) {
    look.args[j];
  }
  var filtered = [];
  for (let i=0; i<arr.length; i++) {
    if (look[arr[i]]) {filtered.push(arr[i])};
  }
  return filtered;
}

destroyer([1, 2, 3, 1, 2, 3], 2, 3);

#25

@RandellDawson The following solution works. I’m not confident it is fully accomplishing what you are describing above. It’s also probably not the most concise solution.

function destroyer(arr, ...args) {
  let look = {};
  for (let j=0; j<args.length; j++) {
    Object.defineProperty(look, args[j], {value:true});
  }
  var filtered = [];
  for (let i=0; i<arr.length; i++) {
    if (!look[arr[i]]) {filtered.push(arr[i])};
  }
  console.log();
  return filtered;
}

destroyer([1, 2, 3, 1, 2, 3], 2, 3);

#26

I sent you a message.


#27

This is an interesting thread!

I would be most interested to see where this finishes up and get Randell’s solution using a lookup object. Did you work it out for a solution that can handle very large arrays/args?