6
\$\begingroup\$

I recently encountered a front-end interview coding challenge question that required one to create a function which returned an array that excluded numbers that occurred more than n-number of times (i.e. duplicate-removal). In this example it was all numbers repeated >= three (3) times. I managed to submit an answer, but admittedly struggled solving it.

I was looking for any feedback / suggestions on how to make it more concise and efficient (the for loop inside the forEach method is especially repulsive).

Here is what I came up with:

// Remove duplicates that occur 3 or more times in an array
// keeping unique values and those with less than 3
function removeMany(arr) {
  const newArr = Array.from(arr).sort()
  let count = 0;
  let result = []

  newArr.forEach((value, index, ar) => {
    count += 1;
    // refactored afterwards from (ar[index + 1] !== value)
    if (ar.lastIndexOf(value) <= index && count <= 2) {
      for (var i = 0; i < arr.length; i++) {
        if (arr[i] === value) {
          result.push(arr[i])
        }
      }
      count = 0
    } else if (ar[index + 1] !== value) {
      count = 0;
    }
  });

  // +1 is there anyway to return a result that mimicks the original order of `numbers`?
  return result;  // [1, 2, 2, 3, 4, 4]
}

// Ex. 1
const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5];
console.log(removeMany(numbers));

\$\endgroup\$
11
\$\begingroup\$

As you expected, there is a much simpler way to do this.

  1. Create a map where the keys are the numbers in the array and the value is the number of times each number appears in the array.
  2. Filter the input array for any numbers that appear less than X times.

function removeMany(numbers, max) {
    const numberMap = numbers.reduce((map, num) => {
        map[num] = map[num] ? map[num] + 1 : 1;
        return map;
    }, []);
    
    return numbers.filter(num => numberMap[num] < max);
}

const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5];
console.log(removeMany(numbers, 3));

\$\endgroup\$
  • 1
    \$\begingroup\$ The problem specified a single parameter, but this is great stuff and even extends functionality - going to sit at my computer and stare at this for awhile :) Thanks to @Sam as well \$\endgroup\$ – Gavin McLean Sep 7 '17 at 21:56
  • 4
    \$\begingroup\$ You can make it short as map[num] = (map[num] || 0) + 1;. \$\endgroup\$ – Tushar Sep 8 '17 at 4:07
  • \$\begingroup\$ @Tushar I had initially written exactly that but decided that in this case a ternary statement would be more clear -- I'm not sure if I was correct coming back a few hours later though. \$\endgroup\$ – Gerrit0 Sep 8 '17 at 4:15
  • \$\begingroup\$ @GavinHughes you can always add a removeThree function implemented in terms of removeMany. Such solution should score you extra points at an interview. \$\endgroup\$ – janos Sep 10 '17 at 8:57
6
\$\begingroup\$

tl;dr

The code can be re-written to first count the number of occurrences of each number, then return an array filtering out any number that occurs more than 3 times.

// Remove duplicates that occur 3 or more times in an array
// keeping unique values and those with less than 3
function removeMany(arr) {
  let countMappings = arr.reduce(function(carry, item) {
    carry[item] = (carry[item] || 0) + 1;
    return carry;
  }, {});
  return arr.filter(item => countMappings[item] < 3);
}

// Ex. 1
const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5];
console.log(removeMany(numbers));

Suggestions

I was looking for any feedback / suggestions on how to make it more concise and efficient (the for loop inside the forEach method is especially repulsive).

The original code already uses functional techniques - i.e. array.forEach()- for one loop. Perhaps you are already familiar with functional techniques like that and others but if not, I recommend going through these exercises.

That inner for loop can be re-written using array.forEach():

arr.forEach(function(element, i) { //for (var i = 0; i < arr.length; i++) {
    if (element === value) {
        result.push(element);
    }
});

// Remove duplicates that occur 3 or more times in an array
// keeping unique values and those with less than 3
function removeMany(arr) {
  const newArr = Array.from(arr).sort()
  let count = 0;
  let result = []

  newArr.forEach((value, index, ar) => {
    count += 1;
    // refactored afterwards from (ar[index + 1] !== value)
    if (ar.lastIndexOf(value) <= index && count <= 2) {
      arr.forEach(function(element, i) { //for (var i = 0; i < arr.length; i++) {
        if (element === value) {
          result.push(element);
        }
      });
      count = 0
    } else if (ar[index + 1] !== value) {
      count = 0;
    }
  });

  // +1 is there anyway to return a result that mimicks the original order of `numbers`?
  return result;  // [1, 2, 2, 3, 4, 4]
}

// Ex. 1
const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5];
console.log(removeMany(numbers));

For that commented line:

// +1 is there anyway to return a result that mimicks the original order of numbers?

One approach to handle that would be to iterate over the elements using array.reduce() (so we can conditionally add values to the output array), counting the occurrences of each element, then in a second iteration, only return elements where there are 2 or less occurrences of that element.

One main advantage here compared to the original is that there is not a nested iteration... the complexity is \$O(n)\$ instead of \$O(n^2)\$.

See the example below. I wanted to compare with jsPerf but that appears to be down. I did find a similar system: measurethat.net - see the comparison here.

// Remove duplicates that occur 3 or more times in an array
// keeping unique values and those with less than 3
function removeMany(arr) {
  let countMappings = arr.reduce(function(carry, item) {
      if (carry[item]!== undefined) {
        carry[item]++;
      }
      else {
        carry[item] = 1;
      }
      return carry;
  }, {});
  return arr.reduce(function(final, item) {
    if (countMappings[item] <3) {
      final.push(item);
    }
    return final;
  }, []);
}

// Ex. 1
const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5];
console.log(removeMany(numbers));

Edit

Bravo to Gerrit0 for using Array.filter() and having very concise code! The performance results appear to be similar.

Utilizing filter() instead of reduce for the second iteration can eliminate a few lines:

return arr.reduce(function(final, item) {
    if (countMappings[item] <3) {
      final.push(item);
    }
    return final;
  }, []);

becomes:

return arr.filter(function(item) {
    return countMappings[item] < 3;
 });

Or if you want to use ES-6 arrow functions:

return arr.filter(item => countMappings[item] < 3);

Additionally, the first iteration, to count the occurrences of each element, could be simplified using a ternary operator:

let countMappings = arr.reduce(function(carry, item) {
    if (carry[item]!== undefined) {
        carry[item]++;
    }
    else {
        carry[item] = 1;
    }
    return carry;
}, {});

becomes:

let countMappings = arr.reduce(function(carry, item) {
    carry[item] = carry[item]? carry[item] + 1: 1;
    return carry;
}, {});

Or as was suggested in comments, use logical OR:

carry[item] = (carry[item] || 0) + 1;

to implicitly check if carry[item] has a value - if not, use 0 before incrementing the count for the value of the given element.

// Remove duplicates that occur 3 or more times in an array
// keeping unique values and those with less than 3
function removeMany(arr) {
  let countMappings = arr.reduce(function(carry, item) {
    carry[item] = (carry[item] || 0) + 1;
    return carry;
  }, {});
  return arr.filter(item => countMappings[item] < 3);
}

// Ex. 1
const numbers = [1, 2, 3, 2, 4, 4, 5, 5, 5, 5];
console.log(removeMany(numbers));

\$\endgroup\$
  • 1
    \$\begingroup\$ Is there any reason you chose to use reduce to create the final array instead of just filtering the input array? Filtering seems to be faster. benchmark \$\endgroup\$ – Gerrit0 Sep 7 '17 at 19:02
  • \$\begingroup\$ I think I was looking for a similar approach and hadn't (yet?) considered filter(). Good job with using that! \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Sep 7 '17 at 19:04
  • 1
    \$\begingroup\$ You can remove if...else by replacing it with carry[item] = (carry[item] || 0) + 1. \$\endgroup\$ – Tushar Sep 8 '17 at 4:10
  • \$\begingroup\$ Yeah ... initially I was going for readability but I have mentioned the single line approach... thanks! \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Sep 8 '17 at 4:42

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.