I saw somewhere that this question was asked in a faang interview and I cannot come up with an optimized solution or find it anywhere. So the question basically wants us to write a function that receives an input like this:

Input: findAllEle('color', '#fff');

and produces an output like this:

Output: Array of elements matching this color

by going through the DOM tree! The solution probably is using a BFS or DFS but then the edge case is what if the color selector is white or #ffffff instead of #fff for which I think we should use a Trie!

Can anyone implement Trie solution using javascript for those edge cases (having multiple different selector)?

CodePudding user response：

I've managed to do it, but, although the trie works in my version, it's kinda useless because it seems getComputedStyle always returns the color's rgb representation (which is why I had to include it in the trie).

I tried to make it as generic as possible so that you can use this with other dfs problems

class Trie {
  value = ''
  children = []

  constructor(...keys) {
    const firstLetters = Array.from(new Set(keys.map(k => k[0])))
    this.children = firstLetters.map(l => {
      return {
                ...new Trie(...keys.filter(k => k.startsWith(l)).map(k => k.substring(1))),
                value: l,
            }
    })
  }
}

const whiteColorTrie = new Trie('white', '#fff', '#ffffff', 'rgb(255, 255, 255)')

const existsInTrie = (trie, search, initialValue = '') => {
    const { value } = trie

    const acc = initialValue   (value ?? '')

    if (!search.startsWith(acc)) return false

    if (search === acc && acc.length !== 0) return true

    return trie.children.some(node => existsInTrie(node, search, acc))
}

const dfs = (root, getChildNodes, predicate) => {
    const children = getChildNodes(root)
    const matches = []

    if (predicate(root)) matches.push(root)

    children.forEach(child =>
        matches.push(...dfs(child, getChildNodes, predicate))
    )

    return matches
}

const elements = dfs(
    document.body,
    node => [...node.children],
    node => existsInTrie(whiteColorTrie, getComputedStyle(node).color)
)

CodePudding user response：

I think I understand the goal to be a recursive search through the dom, starting at some given node, seeking all descendants who have a given color.

The catch is that both the color given to the function and the colors expressed in the dom can be in several formats, like a name, rgb, 3-digit hex, or 6-digit hex.

The catch is solved by "normalizing" colors to the value returned by getComputedStyle (see here). When comparing, compare normalized input and node colors.

// turn any color into a standard-formatted rgb string
const normalizeColor = color => {
  const d = document.createElement("div");
  d.style.color = color;
  document.body.appendChild(d)
  const result = window.getComputedStyle(d).color;
  d.remove();
  return result;
}

// recursive search for descendant nodes with color
function childrenWithColor(el, color) {
  let result = [];
  let targetColor = normalizeColor(color);
  let elColor = normalizeColor(el.style.getPropertyValue('color'));
  if (elColor === targetColor) result.push(el);

  for (let i = 0; i < el.children.length; i  ) {
    let child = el.children[i];
    result = [...result, ...childrenWithColor(child, color)];
  }
  return result;
}

// chose "red" for this example
let el = document.getElementById('parent')
let results = childrenWithColor(el, 'red');
// expect: grandchild-a, grandchild-b, child-b, grandchild-d
console.log('red ones:', results.map(el => el.id).join(', '));

<div id="parent">
  parent has no style at all

  <div id="child-a" style="border: 1px solid black;">
    child-a has a style that isn't a color

    <div id="grandchild-a" style="color: rgb(255,0,0);">
      grandchild-a has rgb red
    </div>

    <div id="grandchild-b" style="color: rgb(255, 0, 0);">
      grandchild-b has rgb red formatted with whitespace
    </div>
  </div>

  <div id="child-b" style="color: #f00;">
    child-b has single digit hex red

    <div id="grandchild-c" style="color: rgb(0,0,255);">
      grandchild-c isn't red
    </div>

    <div id="grandchild-d" style="color: #ff0000;">
      grandchild-d has double digit hex red
    </div>
  </div>
</div>