18.improve-a-function.md

18. improve a function

Problem

https://bigfrontend.dev/problem/improve-a-function

Problem Description

// Given an input of array,
// which is made of items with >= 3 properties

let items = [
  {color: 'red', type: 'tv', age: 18},
  {color: 'silver', type: 'phone', age: 20},
  {color: 'blue', type: 'book', age: 17}
]

// an exclude array made of key value pair
const excludes = [
  {k: 'color', v: 'silver'},
  {k: 'type', v: 'tv'},
  ...
]

function excludeItems(items, excludes) {
  excludes.forEach( pair => {
    items = items.filter(item => item[pair.k] === item[pair.v])
  })

  return items
}

1. What does this function excludeItems do?
2. Is this function working as expected ?
3. What is the time complexity of this function?
4. How would you optimize it ?

note

we only judge by the result, not the time cost. please submit the best approach you can.

Solution

Answers to the questions:

1. The function excludeItems returns items that match the conditions in excludes array.
2. No. Because the function is called excludesItems, it should exclude items that match the conditions.
3. O(n * m)
4. We should also handle duplicate keys in excludes array.

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

  for (const { k, v } of excludes) {
    if (!excludesMap.has(k)) {
      excludesMap.set(k, new Set());
    }
    excludesMap.get(k).add(v);
  }

  return items.filter((item) =>
    Object.keys(item).every(
      // Time complexity of V8's Set.has() is practically O(1).
      (key) => !excludesMap.has(key) || !excludesMap.get(key).has(item[key])
    )
  );

Reference

https://www.youtube.com/watch?v=EC_M8LlguC0&ab_channel=JSer