18.md

Solution

Submission link - https://bigfrontend.dev/problem/improve-a-function/discuss/549

/**
 * @param {object[]} items
 * @excludes { Array< {k: string, v: any} >} excludes
 */

/**
 * @param {object[]} items
 * @param { Array< {k: string, v: any} >} excludes
 * @return {object[]}
 */
function excludeItems(items, excludes) {

  const excludeItemsMap = new Map(); // to remove duplicate entries from 'excludes' array
  // this will bring the time complexity from m * n * k to m * k

  excludes.map(({
    k: key,
    v: value
  }) => {
    if (!excludeItemsMap.has(key)) excludeItemsMap.set(key, new Set()); // if we encounter 'key' for first time then create a Set as key's value
    excludeItemsMap.get(key).add(value); // then add it in same Set (to prevent duplicates)
  });

  return items.filter((item, idx) => { // run a filter through items
    let shouldExclude = false;
    const keys = Object.keys(item); // run a loop through item's props
    for (let i = 0; i < keys.length; i++) {
      if ((excludeItemsMap.has(keys[i]) && excludeItemsMap.get(keys[i]).has(item[keys[i]]))) { // if item's prop exist in the map then mark flag as true
        shouldExclude = true;
      }
    }
    return !shouldExclude; // only true items are returned by filters
  });
}

Short story

The first impression made me think that it is easy to tackle. Though you need certain thinking to solve such problems and it will come with practice and more practice.

I needed to check different solutions to solve this one. It is inspired by one of the solutions.

Code overview

There were 4 questions asked about this problem. Let's answer them one at a time.

1. What does this function excludeItems do?
It returns items which are not present in the excludes array

2. Is this function working as expected?
Nope. It has 2 issues. 1. The filter will return items which make the condition true, here we need to use !== instead of === 1. item[pair.v] will become pair.v

3. What is the time complexity of this function?
The time complexity looks like O(m * n), where m is items in excludes and n is items in the items array

4. How would you optimize it?
If we have k properties which will be definitely < m. So we can atleast collapse m into k. So the new time complexity will be O(n * k).

1. We first remove duplicates from exludes by using Map and Set
2. We will create a map - excludeItemsMap
3. We will then iterate over excludes keeping all the different values (silver,red, blue, etc.) of the same property (e.g. colors) against a single key i.e k in excludes array
4. We will check if the k from excludes is already there in the excludeItemsMap. If not then we will add it with empty Set as value. i.e. excludeItemsMap.set(key, new Set());
5. If we have k from excludes already in excludeItemsMap we will push its value in Set by retrieving it from Map i.e. excludeItemsMap.get(key).add(value);
6. This way we have collapsed duplicates from excludes. Thanks to Set
7. Our excludeItemsMap will look like something - Map(2) {"color" => Set(1), "type" => Set(1)}
8. Now we will simply apply the filter on the items array and then a loop on each item to check its key in the excludeItemsMap
9. If we find a key then we will return false as we don't want the item that presents in the exclude list else we will return true

That's all. In case something is wrong here, please do reach out to me.

---

I'm excited to improve the solution and code walkthrough. Feel free to drop a comment, or send a PR or send memes @knowkalpesh.