Y
Published on

BigFrontEnd Category 6 DOM Questions

Authors
  • avatar
    Name
    Yinhuan Yuan
    Twitter

Introduction

This blog post summarizes the DOM related questions found on BigFrontEnd.Dev.

1.get DOM tree height

58.https://bigfrontend.dev/problem/get-DOM-tree-height Height of a tree is the maximum depth from root node. Empty root node have a height of 0.

If given DOM tree, can you create a function to get the height of it?

For the DOM tree below, we have a height of 4.

<div>
  <div>
    <p>
      <button>Hello</button>
    </p>
  </div>
  <p>
    <span>World!</span>
  </p>
</div>

Can you solve this both recursively and iteratively?

Solution: tree.children to get the children of a HTMLElement.

1.1.Recursive Solution with DFS

/**
 * @param {HTMLElement | null} tree
 * @return {number}
 */
function getHeight(tree) {
  if (tree === null) return 0;
  // Use .children instead of .childNodes to ignore TextNodes.
  const heights = [...tree.children].map(getHeight);
  if (heights.length === 0) return 1;
  return Math.max(...heights) + 1;
}

1.2.Iterative Solution using Stack

/**
 * @param {HTMLElement | null} tree
 * @return {number}
 */
function getHeight(tree) {
  if (tree === null) {
    return 0;
  }

  let maxHeight = 0;
  const stack = [[tree, 1]];

  while (stack.length > 0) {
    const [el, height] = stack.pop();
    maxHeight = Math.max(height, maxHeight);

    for (const child of el.children) {
      stack.push([child, height + 1]);
    }
  }

  return maxHeight;
}

1.3.Iterative Solution with BFS

/**
 * @param {HTMLElement | null} tree
 * @return {number}
 */
function getHeight(tree) {
  if (tree === null) {
    return 0;
  }

  let maxHeight = 0;
  const queue = [[tree, 1]];

  while (queue.length > 0) {
    const [el, height] = queue.shift();
    maxHeight = Math.max(height, maxHeight);

    for (const child of el.children) {
      queue.push([child, height + 1]);
    }
  }

  return maxHeight;
}

2.get DOM tags

68.https://bigfrontend.dev/problem/get-DOM-tags Given a DOM tree, please return all the tag names it has.

Your function should return a unique array of tags names in lowercase, order doesn't matter.

Solution: node.tagName

function getTags(tree) {
  const tags = new Set();

  function dfs(node, fn) {
    fn(node);
    for (let child of node.children) {
      dfs(child, fn);
    }
  }

  dfs(tree, (node) => tags.add(node.tagName.toLowerCase()));
  return Array.from(tags);
}

3.Next Right Sibling

89.https://bigfrontend.dev/problem/Next-Right-Sibiling

Given a DOM tree and a target element, please return the next right sibling.

Like above, the next right sibling of <button/> is the blue <a/>. Notice that they don't necessarily have the same parent element.

If no right sibling, then return null.

What is time & space cost of your solution ?

Solution: The next right sibling is the next element in queue in BFS. The only exception is the last node in a layer.

/**
 * @param {HTMLElement} root
 * @param {HTMLElement} target
 * @return {HTMLElement | null}
 */
function nextRightSibling(root, target) {
  const queue = [root, null];

  while (queue.length > 0) {
    const node = queue.shift();

    if (node === target) {
      return queue.shift(); // The next element in the queue.
    }
    // use null to specify that a level has ended.
    if (node === null) {
      queue.push(null);
    } else {
      queue.push(...node.children);
    }
  }

  return null;
}

4.extract all anchor element from HTML string

99.https://bigfrontend.dev/problem/extract-all-anchor-elements-from-HTML-string

Given a HTML string, write a function to extract the anchor tag from it.

extract(`
<div>
    <a>link1< / a><a href="https://bfe.dev">link1< / a>
    <div<abbr>bfe</abbr>div>
    <div>
<abbr>bfe</abbr><a href="https://bfe.dev" class="link2"> <abbr>bfe</abbr>   <span class="l">l</span><span  class="i">i</span>   nk2   </a>
    </div>
</div>
`)
// [
//    '<a>link1< / a>',
//    '<a href="https://bfe.dev">link1< / a>',
//    '<a href="https://bfe.dev" class="link2"> <abbr>bfe</abbr>   <span class="l">l</span><span  //class="i">i</span>   nk2   </a>'
 //]

Solution: Use state machine to judge whether it is within a tag and an anchor element.

/**
 * @param {string} str
 * @return {string[]}
 */
function extract(str) {
  const n = str.length;
  const ans = [];
  let start = -1;
  let inTag = false;
  let inTagA = false;
  for (let i = 0; i < n; i++) {
    if (str[i] === "<") {
      inTag = true;
      start = i;
    } else if (str[i] === ">") {
      inTag = false;
      const tag = str.slice(start, i + 1);
      if (tag.slice(0, 3) === "<a>" || tag.slice(0, 3) === "<a ") {
        inTagA = true;
        tagAStart = start;
      } else if (tag.replaceAll(" ", "") === "</a>") {
        inTagA = false;
        ans.push(str.slice(tagAStart, i + 1));
      }
    }
  }
  return ans;
}
console.log(
  extract(`
<div>
    <a>link1< / a><a href="https://bfe.dev">link1< / a>
    <div<abbr>bfe</abbr>div>
    <div>
<abbr>bfe</abbr><a href="https://bfe.dev" class="link2"> <abbr>bfe</abbr>   <span class="l">l</span><span  class="i">i</span>   nk2   </a>
    </div>
</div>
`),
);

5.Traverse DOM level by level

104.https://bigfrontend.dev/problem/Traverse-DOM-level-by-level

Given a DOM tree, flatten it into an one dimensional array, in the order of layer by layer, like below.

/**
 * @param {HTMLElement | null} root
 * @return {HTMLElement[]}
 */
function flatten(root) {
  const ans = [];
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift();
    if (node === null) {
      continue;
    }
    ans.push(node);
    queue.push(...node.children);
  }
  return ans;
}

6.create your own Cookie

134.https://bigfrontend.dev/problem/create-your-own-Cookie

We can get and set cookie by document.cookie.

document.cookie = 'bfe=dev'
// "bfe=dev"
document.cookie = 'bfe1=dev1'
// "bfe1=dev1"
document.cookie
// "bfe=dev; bfe1=dev1"

Please create your own myCookie.

it should support get and set.

document.myCookie = 'bfe=dev'
// "bfe=dev"
document.myCookie = 'bfe1=dev1'
// "bfe1=dev1"
document.myCookie
// "bfe=dev; bfe1=dev1"

there a few options to cookie, but in this problem, you only need to support max-age which means the cookie should be deleted after certain time(in seconds).

document.myCookie = 'bfe=dev; max-age=1'
// "bfe=dev; max-age=1"
document.myCookie
// "bfe=dev"

after 1 second

document.myCookie
// ""

in your code, please enable myCookie in install() and remove the logic in uninstall(), these are used in judging.

Solution: Object.defineProperty(obj, prop, descriptor); descriptor: value, writable, enumerable, configurable, get, set

// Function to install the myCookie functionality
function install() {
  Object.defineProperty(document, "myCookie", {
    get() {
      return Object.entries(document.cookie_)
        .map(([key, value]) => `${key}=${value}`)
        .join("; ");
    },
    set(cookieStr) {
      // Parse the cookie string
      const [cookiePart, ...optionsParts] = cookieStr
        .split(";")
        .map((part) => part.trim());
      const [cookieName, cookieValue] = cookiePart
        .split("=")
        .map((part) => part.trim());
      // Handle max-age option
      const maxAgeOption = optionsParts.find((part) =>
        part.startsWith("max-age="),
      );
      if (maxAgeOption) {
        const maxAge = Number(maxAgeOption.split("=")[1]);
        if (!isNaN(maxAge)) {
          if (maxAge === 0) {
            return;
          }
          setTimeout(() => {
            delete document.cookie_[cookieName];
          }, maxAge * 1000);
        }
      }
      if (!document.cookie_) {
        document.cookie_ = {};
      }
      document.cookie_[cookieName] = cookieValue;
    },
    configurable: true,
  });
}

// Function to uninstall the myCookie functionality
function uninstall() {
  delete document.cookie_;
  delete document.myCookie;
}

7.localStorage with expiration

135.https://bigfrontend.dev/problem/localStorage-with-expiration

localStorage is a simple and handy client-side storage, but you should avoid using it because it is synchronous.

Also Safari's ITP actually deletes client-side script-writable storage after 7 days of Safari use without interacting on your website, and localStorage is included.

Unlike Cookie, localStorage doesn't expire.

In this problem, please create a localStorage wrapper with expiration support

myLocalStorage.setItem('bfe', 'dev', 1000)
myLocalStorage.getItem('bfe')
// 'dev'

after 1 second:

myLocalStorage.getItem('bfe')
// null

FYI

localStorage is replaced with our own implementation to avoid security error. But the interface is the same, actually you don't need to care :)

window.myLocalStorage = {
  getItem(key) {
    return window.localStorage.getItem(key);
  },

  setItem(key, value, maxAge) {
    if (maxAge === 0) {
      return;
    }
    window.localStorage.setItem(key, value);
    if (!!maxAge) {
      setTimeout(() => {
        window.localStorage.removeItem(key);
      }, maxAge);
    }
  },

  removeItem(key) {
    window.localStorage.removeItem(key);
  },

  clear() {
    window.localStorage.clear();
  },
};

8.Previous Left Sibling

158.https://bigfrontend.dev/problem/previous-left-sibling

Given a DOM tree and a target element, please return the previous left sibling.

Like above, the previous left sibling of green <a/> is the blue <button/>. Notice that they don't necessarily have the same parent element.

If no left sibling, then return null.

What is time & space cost of your solution ?

Solution: The previous left sibling is the previous element in queue in BFS. The only exception is the first node in a layer.

/**
 * @param {Element} root
 * @param {Element} target
 * @return {Elemnt | null}
 */
function previousLeftSibling(root, target) {
  const queue = [null, root];
  let node = null;
  let preNode = null;
  while (queue.length > 0) {
    preNode = node;
    node = queue.shift();

    if (node === target) {
      return preNode; // The previous element in the queue.
    }
    // use null to specify that a level has started.
    if (node === null) {
      queue.push(null);
    } else {
      queue.push(...node.children);
    }
  }

  return null;
}

9.implement your own URLSearchParams

80.https://bigfrontend.dev/problem/implement-your-own-URLSearchParams When we want to extract parameters from query string, URLSearchParams could be very handy.

Can you implement MyURLSearchParams which works the same ?

const params = new MyURLSearchParams('?a=1&a=2&b=2')
params.get('a') // '1'
params.getAll('a') // ['1', '2']
params.get('b') // '2'
params.getAll('b') // ['2']
params.append('a', 3)
params.set('b', '3')
params.toString() // 'a=1&a=2&b=3&a=3'

There are a few methods on URLSearchParams, please implement them all.

Constructor URLSearchParams(): Returns a URLSearchParams object instance.

Instance properties size Read only: Indicates the total number of search parameter entries.

Instance methods URLSearchParams[Symbol.iterator](): Returns an iterator allowing iteration through all key/value pairs contained in this object in the same order as they appear in the query string.

URLSearchParams.append(): Appends a specified key/value pair as a new search parameter.

URLSearchParams.delete(): Deletes search parameters that match a name, and optional value, from the list of all search parameters.

URLSearchParams.entries(): Returns an iterator allowing iteration through all key/value pairs contained in this object in the same order as they appear in the query string.

URLSearchParams.forEach(): Allows iteration through all values contained in this object via a callback function.

URLSearchParams.get(): Returns the first value associated with the given search parameter.

URLSearchParams.getAll(): Returns all the values associated with a given search parameter.

URLSearchParams.has(): Returns a boolean value indicating if a given parameter, or parameter and value pair, exists.

URLSearchParams.keys(): Returns an iterator allowing iteration through all keys of the key/value pairs contained in this object.

URLSearchParams.set(): Sets the value associated with a given search parameter to the given value. If there are several values, the others are deleted.

URLSearchParams.sort(): Sorts all key/value pairs, if any, by their keys.

URLSearchParams.toString(): Returns a string containing a query string suitable for use in a URL.

URLSearchParams.values(): Returns an iterator allowing iteration through all values of the key/value pairs contained in this object.

Solution:

class MyURLSearchParams {
 constructor(init = '') {
   this.params = new Map();

   if (typeof init === 'string') {
     init = init.startsWith('?') ? init.slice(1) : init;
     const pairs = init.split('&');
     for (const pair of pairs) {
       const [key, value] = pair.split('=');
       this.append(decodeURIComponent(key), decodeURIComponent(value));
     }
   } else if (init instanceof MyURLSearchParams) {
     init.forEach((value, key) => this.append(key, value));
   } else if (Array.isArray(init)) {
     for (const [key, value] of init) {
       this.append(key, value);
     }
   } else if (typeof init === 'object' && init !== null) {
     for (const [key, value] of Object.entries(init)) {
       this.append(key, value);
     }
   }
 }

 get size() {
   return [...this.params.values()].reduce((acc, arr) => acc + arr.length, 0);
 }

 [Symbol.iterator]() {
   return this.entries();
 }

 append(name, value) {
   if (!this.params.has(name)) {
     this.params.set(name, []);
   }
   this.params.get(name).push(String(value));
 }

 delete(name, value) {
   if (value === undefined) {
     this.params.delete(name);
   } else {
     const values = this.params.get(name);
     if (values) {
       const index = values.indexOf(String(value));
       if (index !== -1) {
         values.splice(index, 1);
       }
       if (values.length === 0) {
         this.params.delete(name);
       }
     }
   }
 }

 *entries() {
   for (const [key, values] of this.params) {
     for (const value of values) {
       yield [key, value];
     }
   }
 }

 forEach(callback, thisArg) {
   for (const [key, value] of this) {
     callback.call(thisArg, value, key, this);
   }
 }

 get(name) {
   const values = this.params.get(name);
   return values ? values[0] : null;
 }

 getAll(name) {
   return this.params.get(name) || [];
 }

 has(name, value) {
   const values = this.params.get(name);
   if (value === undefined) {
     return values !== undefined && values.length > 0;
   }
   return values !== undefined && values.includes(String(value));
 }

 *keys() {
   for (const [key] of this) {
     yield key;
   }
 }

 set(name, value) {
   this.params.set(name, [String(value)]);
 }

 sort() {
   this.params = new Map([...this.params].sort());
   for (const [key, values] of this.params) {
     this.params.set(key, values);
   }
 }

 toString() {
   return [...this].map(([key, value]) =>
     `${encodeURIComponent(key)}=${encodeURIComponent(value)}`
   ).join('&');
 }

 *values() {
   for (const [, value] of this) {
     yield value;
   }
 }
}

10.Two-way binding

153.https://bigfrontend.dev/problem/two-way-binding

Let's do some simple two-way binding.

Please create a function model(state, element), to bind state.value to the HTMLInputElement element.

const input = document.createElement('input')
const state = { value: 'BFE' }
model(state, input)

console.log(input.value) // 'BFE'
state.value = 'dev'
console.log(input.value) // 'dev'
input.value = 'BFE.dev'
input.dispatchEvent(new Event('change'))
console.log(state.value) // 'BFE.dev'

Solution:

  1. First, we check if the provided element is indeed an HTMLInputElement. If not, we throw an error.

  2. We set the initial value of the input element to match the state's value.

  3. We use Object.defineProperty() to create a custom getter and setter for state.value:

    • The getter returns the current value of the input element.
    • The setter updates the input element's value when state.value is assigned.

  4. We add an event listener to the input element for the 'input' event. This event fires whenever the user types or modifies the input's value. When this happens, we update state.value, which triggers the setter we defined.

This implementation creates a two-way binding:

  • When state.value is changed programmatically, it updates the input element's value.
  • When the user types in the input element, it updates state.value.
/**
 * @param {{value: string}} state
 * @param {HTMLInputElement} element
 */
function model(state, element) {
  if (!(element instanceof HTMLInputElement)) {
    throw new Error('Element must be an HTMLInputElement');
  }

  // Initial set of input value from state
  element.value = state.value;

  // Define a getter and setter for state.value
  Object.defineProperty(state, 'value', {
    get() {
      return element.value;
    },
    set(newValue) {
      element.value = newValue;
    }
  });

  // Listen for changes on the input element
  element.addEventListener('input', function() {
    // This will trigger the setter defined above
    state.value = element.value;
  });
}

11.Generate CSS Selector for target element

170.https://bigfrontend.dev/problem/generate-selector

Given a DOM tree and a target element, generate a valid selector to target it.

For example, for a DOM tree like below

<div>
  <p>BFE.dev</p>
  <div>
    is
    <p>
      <span>great. <button>click me!</button></span>
    </p>
  </div>
</div>

There could be more than 1 answer.

let selector = generateSelector(root, target) // 'button'
expect(root.querySelector(selector)).toBe(target)
selector = generateSelector(root, target) // 'div > div > p > button'
expect(root.querySelector(selector)).toBe(target)

Solution:

To generate a valid selector for a target element within a DOM tree, we can create a function that traverses up the DOM tree from the target element, building a selector string as it goes.

function generateSelector(root, target) {
  if (!root.contains(target)) {
    throw new Error('Target element is not a descendant of root');
  }

  let path = [];
  let element = target;

  while (element !== root) {
    let selector = element.tagName.toLowerCase();

    // Add id if present
    if (element.id) {
      selector += '#' + element.id;
      path.unshift(selector);
      break; // ID is unique, so we can stop here
    }

    // Add classes if present
    if (element.className) {
      selector += '.' + element.className.trim().replace(/\s+/g, '.');
    }

    // Add nth-child if needed
    let siblings = element.parentNode.children;
    if (siblings.length > 1) {
      let index = Array.from(siblings).indexOf(element) + 1;
      selector += `:nth-child(${index})`;
    }

    path.unshift(selector);
    element = element.parentNode;
  }

  return path.join(' > ');
}

This function does the following:

  1. First, it checks if the target is actually a descendant of the root. If not, it throws an error.

  2. It initializes an empty array path to store the selector parts, and sets element to the target.

  3. It then enters a loop that continues until we reach the root element:

    a. It starts building the selector with the element's tag name.

    b. If the element has an ID, it adds it to the selector and breaks the loop, as IDs should be unique.

    c. If the element has classes, it adds them to the selector.

    d. To ensure uniqueness, it adds an :nth-child() pseudo-class if the element has siblings.

    e. It adds this selector to the beginning of the path array.

    f. It moves up to the parent element.

  4. Finally, it joins the selector parts with ' > ' to create a child combinator selector.

This function will generate a unique selector in most cases. Here are some examples of how it works:

// For the given HTML:
// <div>
//   <p>BFE.dev</p>
//   <div>
//     is
//     <p>
//       <span>great. <button>click me!</button></span>
//     </p>
//   </div>
// </div>

let root = document.querySelector('div');
let target = document.querySelector('button');

let selector = generateSelector(root, target);
console.log(selector); // 'div:nth-child(2) > p > span > button'

// If we add an id to the button:
target.id = 'myButton';
selector = generateSelector(root, target);
console.log(selector); // 'button#myButton'

// If we add a class to the span:
target.parentNode.className = 'highlight';
selector = generateSelector(root, target);
console.log(selector); // 'span.highlight > button#myButton'

This implementation provides a balance between specificity and brevity. It uses IDs when available for brevity, includes classes for more specific targeting, and falls back to structural selectors (tag names and nth-child) when needed for uniqueness.

Discuss on Twitter • View on GitHub