Facebook 面試考什麼 — DOM Tree 篇
重新認識最基本的瀏覽器 Document 新增修改遍歷 DOM的方法
雖然自知能力還不足,但能有機會跟 Facebook 電話面試 (美國面試 6–8 關,電話面試只是第 2 關而已 ),也可以算是人生成就了吧! 覺得大家應該會好奇國外面試除了演算法/資料結構還會考些什麼有趣題目。
不過這篇只會介紹其中一題而已,因為題目背後的相關知識太多需要說明了。
🔖 文章索引
1. 開始之前先看題目
2. 來去自如遍歷 DOM
3. 搜尋 node : getElement*, querySelector*
4. 新增刪除修改 node
5. 如何解題
寫這篇動機
第一眼看到面試題目其實有傻眼到,不過後來細細想來其實並沒有那麼難 (如果對 DOM 掌握度夠熟的話)。問題來了,自己對於用 “jQuery” 操作 DOM 還算熟 (eg()
、parent()
、siblings()
...) 但面試是不允許用任何框架的,而我對原生 DOM 真的不太行,所以此篇文章就誕生了~
看完這篇你應該要會
- 來去自如遍歷 DOM Tree 與搜尋 node
- 新增刪除修改 node
- 知道如何解 Facebook 的這一題
圖片出處
這篇用到很多 The Modern JavaScript Tutorial 裡的圖,我只能說他的教學跟圖都太棒了 ,這一篇也算是擷取其中 Document 精華,非常建議大家上去看原文.
開始之前先看題目
Given two identical DOM tree structures, A and B, and a node from A, find the corresponding node in B
翻譯: 給 A 跟 B 兩個一模一樣的 DOM Tree 結構,輸入 A 裡面的 child node,請找出對應在 B 裡面的 child node
解題很重要就是要知道輸入 input 跟輸出 ouput (return),所以我這邊直接整理一下
/**
* @param {DOM} A
* @param {DOM} B
* @param {node} node in A
* @return {node} corresponding node in B
*/
<body>
<div id="rootA">
<div>
<div>a</div>
</div>
<div></div>
<div>
<div>A
<div id="nodeA">A</div>
<div></div>
</div>
</div>
</div>
<div id="rootB">
<div>
<div>b</div>
</div>
<div></div>
<div>
<div>B
<div id="nodeB">B</div>
<div></div>
</div>
</div>
</div>
</body>
若已經知道怎麼解就可以關掉這篇了,接下來我會先介紹操作 DOM 基本操作最後再來解這題。
來去自如遍歷 DOM
DOM 的最上層 (root) 就是 document [延伸閱讀: Browser environment, specs],nodes 包含
- element node (所有 HTML tag 都是 element node,例如
<div>
、<h1>
) - text nodes (純 string),甚至連 comment 都會出現在 node 上 [延伸閱讀: DOM tree]
這篇會把重點放在 element-only 上,因為我們比較常針對 element nodes 去找東西.而 element only 的 Tree 通常會由 document.body
開始 (廢話 你 HTML code 一定會寫在 body
裡)
<body>
<div id="root">爸媽
<h1>我姊姊</h1>
<ul>我
<li>大寶</l1>
<li>二寶</l1>
<li>三寶</l1>
</ul>
<p>我弟弟</p>
</div>
</body>
<script>
let target = document.querySelector('ul')
// 下一個跟自己同層級的兄弟姊妹 node
target.nextElementSibling; // <p>我弟弟</p>
// 前一個跟自己同層級的兄弟姊妹 node
target.previousElementSibling; // <h1>我姊姊</h1>
// 上一層的爸媽 node
target.parentElement; // <div id="root">爸媽...</div>
// 下一層的小孩們 nodeList
target.children; / HTMLCollection(3) [li, li, li]
// 下一層的第一個小孩
target.children[0] // <li>大寶</a>
target.firstElementChild; // <li>大寶</a>
// 總小孩數
target.children.length // 3
// 下一層的最後一個小孩
target.children[target.children.length - 1] // <li>三寶</a>
target.lastElementChild; // <li>三寶</a>
</script>
搜尋 node : getElement*, querySelector*
假如每次搜尋 node 都去算是第幾個 index 然後 children[index]
或 previosElementSiblings
豈不很麻煩,所以 DOM 提供一些快速抓取特定 node 的方法
getElementById(‘id’)
回傳 “一個” 特定 node。基本上這個方法是 Big O(1),搜尋速度相當快.記得一個 id 是唯一的一個頁面只能有一個相同 id 名,不然你抓到的很有可能不是預期中的 node
<div id="elem">
<div id="elem-content">Element</div>
</div>
<script>
// get the element
let elem = document.getElementById('elem');
// make its background red
elem.style.background = 'red';
</script>
querySelectorAll
回傳 nodeList 。所以假如要針對抓到的 nodeList 做事需要 forEach 或 for of
<ul>
<li>The</li>
<li>test</li>
</ul>
<ul>
<li>has</li>
<li>passed</li>
</ul>
<script>
let elements = document.querySelectorAll('ul > li:last-child');
for (let elem of elements) {
alert(elem.innerHTML); // "test", "passed"
}
</script>
querySelector
回傳 “第一個” 抓到的 node,所以 elem.querySelectorAll(css)[0]
其實會等於 elem.querySelector(css)
getElementsBy*
回傳 NodeList。記得是 Elements
有 s
,常見的有下列幾種
elem.getElementsByTagName(tag)
elem.getElementsByClassName(className)
elem.getElementsByName(name)
你可以能會想說 elem.querySelector*
完全可以取代以上三種方法,沒錯! 但是他們有一個最大不一樣就是 Live collections
Live collections ?
Live 意思就是會自動更新,基本上 getElementsBy*
都是 live,但 querySelector
是 static 所以不會自動更新.直接來看範例比較好理解
<div id="outer">
<div id="inner">inner</div>
</div>
<script>
// <div id="outer">
var outerDiv = document.getElementById('outer');
// 所有的 <div> 標籤
var allDivs = document.getElementsByTagName('div');
console.log(allDivs.length); // 2
// 清空 <div id="outer"> 下的節點
outerDiv.innerHTML = '';
// 因為清空了<div id="outer"> 下的節點,所以只剩下 outer
console.log(allDivs.length); // 1
// 若 allDivs 改成 querySelectorAll 那這裡 length 會是 2
</script>
There are 6 main methods to search for nodes in DOM
可以來這邊測試是不是都理解了
matches
前面都是查找 DOM,這個方法是會回傳 Boolean,告訴你這個 Node 是否符合搜尋條件
<a href="http://example.com/file.zip">...</a>
<a href="http://ya.ru">...</a>
<script>
// can be any collection instead of document.body.children
for (let elem of document.body.children) {
if (elem.matches('a[href$="zip"]')) {
alert("The archive reference: " + elem.href );
}
}
</script>
新增刪除修改 node
如何用純 js 動態產生以下呢
<div class=“alert” test=”123”/>
Hi there!
</div>
新增 nodes
有兩種方式可以新增 DOM nodes
// Element node
let div = document.createElement('div')
// Text node
let textNode = document.createTextNode('Here I am')
所以結合以上答案就是
let div = document.createElement('div');
div.className = "alert"
div.setAttribute('Test', 123) // setAttribute 不分大小寫,所以最後呈現在頁面賞都是小寫
div.innerHTML = "Hi there!"
新增完你會發現頁面上看不到啊,因為我們只是先 “產生” 這個 tag 並給他內容而已,並沒有 “插入” 到現有網頁上。
插入頁面方法
先來看圖,因為他的圖實在畫得太好.我都不用再畫一次
<ol id="ol">
<li>0</li>
<li>1</li>
<li>2</li>
</ol>
<script>
ol.before('before'); // insert string "before" before <ol>
ol.after('after'); // insert string "after" after <ol>
let liFirst = document.createElement('li');
liFirst.innerHTML = 'prepend';
ol.prepend(liFirst); // insert liFirst at the beginning of <ol>
let liLast = document.createElement('li');
liLast.innerHTML = 'append';
ol.append(liLast); // insert liLast at the end of <ol>
</script>
Node removal
node.remove()
let div = document.createElement('div');
div.className = "alert";
div.innerHTML = "<strong>Hi there!</strong> You've read an important message.";
document.body.append(div);
setTimeout(() => div.remove(), 1000);
複製 nodes: cloneNode
node.cloneNode([Boolean]);
複製現有 node 比一個一個新增要快上許多,後面的參數 Boolean 可以是 true
或 false
- node.cloneNode(true): 深層複製,代表連他所有屬性以及子層都會被複製到
- node.cloneNode(false): 淺層複製,並不會連子層一起複製
<div class="alert" id="div">
<strong>Hi there!</strong> You've read an important message.
</div>
深層複製
let div = document.getElementById('div')
let div2 = div.cloneNode(true)
div2.querySelector('strong').innerText = 'hello';
div.after(div2)
/* HTML 會長這樣
<div class="alert" id="div">
<strong>Hi there!</strong> You've read an important message.
</div>
<div class="alert" id="div">
<strong>hello</strong> You've read an important message.
</div>
*/
淺層複製
let div = document.getElementById('div')
let div2 = div.cloneNode(false)
div.after(div2)
/* HTML 會長這樣
<div class="alert" id="div">
<strong>Hi there!</strong> You've read an important message.
</div>
<div class="alert" id="div"></div>
*/
[延伸: 印出文字]
//HTMl
<div id="elem1"></div>
<div id="elem2"></div>
<div id="elem3"></div>
<div id="elem4"></div>
// js
let text = '<b>text</b>';
elem1.append(document.createTextNode(text));
elem2.innerHTML = text;
elem3.textContent = text;
elem4.innerText = text;
/*
<b>text</b>
text
<b>text</b>
<b>text</b>
*/
如何解題
看完以上應該要可以獨立解題了
- 首先必需要知道輸入的 node 層級,假如輸入的 node 是 document.getElementById(‘#nodeA’),以肉眼先觀察,你會知道 nodeA 是在從 root 數來第 3 個 child, 下面第 1 個 child ,再下面第一個 child 位置
<div id="rootA">
<div>
<div>a</div>
</div>
<div></div>
<div><!-- 3. 這邊是 parentElements 下的 "第三個 node" -->
<div>A <!-- 2. 這邊是 parentElements 下的 "第一個 node" -->
<div id="nodeA">A</div> <!-- 1. 這邊是 parentElements 下的 "第一個 node" -->
<div></div>
</div>
</div>
</div>
把層級由”裡而外” 存進某個 array [1, 1, 3]’
const rootA = document.getElementById('rootA');
const rootB = document.getElementById('rootB');
const nodeA = document.getElementById('nodeA');
const nodeB = document.getElementById('nodeB');
function getPath(root, node){
const path = []; // [node index, 上一層 index, 再上一層 index...]
while(node !== root){
// 從當下這層一層層往上找
const parent = node.parentElement;
const children = Array.from(parent.children)
const nodeIndex = children.indexOf(node)
path.push(nodeIndex);
node = parent;
}
return path;
}
- 回到 DOM tree B 依照第一步驟的層級輸出相對應的 Node
function getNodeFromPath(node, path){
while(path.length > 0){
node = node.children[path.pop()]
}
return node;
}
console.log(getNodeFromPath(rootB, getPath(rootA, nodeA)) === nodeB) // true
補充
其實這題也是有小小用到 stack 觀念 [延伸閱讀: 堆疊 Stack]
- 從當下 node 開始存所在層級
- 然後之後再從最上面拿出來
其實本來還想講一題很有趣的題目但礙於篇幅(每次都不小心寫好多)所以就請讀者自行練習啦!
題外話
找工作過程心裡真的很煎熬,但轉念把這些過程都變成練習與進步心態就變得輕鬆許多! 從中真的看到太多自己的不足需要更努力啊!
這裏也想分享 Facebook 提供給面試者的一些資源,對我很受用也提供給大家
- (這不用說了 大家都知) Learn JavaScript | MDN
- A re-introduction to JavaScript | MDN
- (超推) The Modern JavaScript Tutorial
- (也很推) JavaScript Garden
- Eloquent JavaScript
- Understanding ES6
- Learning Advanced JavaScript
- 5 Typical JavaScript Interview Exercises
- book helpful for CS fundamentals (please note this book in free pdf version is available through Google search).
(此篇於 2019–11–26 同步刊登於 w3hexschool)