每日十題 金三銀四面試題（五）
一、快速排序（算法）
參考解答：
算法步驟如下：
1. 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）;
2. 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；
3. 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)退出，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。
function quickSort(arr, left, right) {var len = arr.length,partitionIndex,left = typeof left != 'number' ? 0 : left,right = typeof right != 'number' ? len - 1 : right;if (left < right) {partitionIndex = partition(arr, left, right);quickSort(arr, left, partitionIndex-1);quickSort(arr, partitionIndex+1, right);}return arr;}function partition(arr, left ,right) { // 分區(qū)操作var pivot = left, // 設(shè)定基準(zhǔn)值（pivot）index = pivot + 1;for (var i = index; i <= right; i++) {if (arr[i] < arr[pivot]) {swap(arr, i, index);index++;}}swap(arr, pivot, index - 1);return index-1;}function swap(arr, i, j) {var temp = arr[i];arr[i] = arr[j];arr[j] = temp;}function partition2(arr, low, high) {let pivot = arr[low];while (low < high) {while (low < high && arr[high] > pivot) {--high;}arr[low] = arr[high];while (low < high && arr[low] <= pivot) {++low;}arr[high] = arr[low];}arr[low] = pivot;return low;}function quickSort2(arr, low, high) {if (low < high) {let pivot = partition2(arr, low, high);quickSort2(arr, low, pivot - 1);quickSort2(arr, pivot + 1, high);}return arr;}
二、說一下 vue 組件之間的傳值通信
參考解答：
組件傳值可分為父子組件傳值和非父子組件傳值（兄弟組件傳值）
父組件給子組件傳值：使用props
子組件給父組件傳值：使用$emit觸發(fā)事件
兄弟組件：使用Bus.js, 兩個(gè)組件引入同一個(gè)Bus.js
使用vuex可以處理上述情況的傳值問題。
四、說說 Vue 雙向綁定的原理
參考解答：
vue.js 是采用數(shù)據(jù)劫持結(jié)合發(fā)布者-訂閱者模式的方式，通過Object.defineProperty()來劫持各個(gè)屬性的setter，getter，在數(shù)據(jù)變動(dòng)時(shí)發(fā)布消息給訂閱者，觸發(fā)相應(yīng)的監(jiān)聽回調(diào)。
當(dāng)把一個(gè)普通 Javascript 對(duì)象傳給 Vue 實(shí)例來作為它的 data 選項(xiàng)時(shí)，Vue 將遍歷它的屬性，用 Object.defineProperty 都加上 setter和getter 這樣的話，給這個(gè)對(duì)象的某個(gè)值賦值，就會(huì)觸發(fā)setter，那么就能監(jiān)聽到了數(shù)據(jù)變化
compile解析模板指令，將模板中的變量替換成數(shù)據(jù)，然后初始化渲染頁面視圖，并將每個(gè)指令對(duì)應(yīng)的節(jié)點(diǎn)綁定更新函數(shù)，添加監(jiān)聽數(shù)據(jù)的訂閱者，一旦數(shù)據(jù)有變動(dòng)，收到通知，更新視圖
Watcher訂閱者是Observer和Compile之間通信的橋梁，主要做的事情是: 1、在自身實(shí)例化時(shí)往屬性訂閱器(dep)里面添加自己 2、自身必須有一個(gè)update()方法 3、待屬性變動(dòng)dep.notice()通知時(shí)，能調(diào)用自身的update()方法，并觸發(fā)Compile中綁定的回調(diào)，則功成身退。
MVVM作為數(shù)據(jù)綁定的入口，整合Observer、Compile和Watcher三者，通過Observer來監(jiān)聽自己的model數(shù)據(jù)變化，通過Compile來解析編譯模板指令，最終利用Watcher搭起Observer和Compile之間的通信橋梁，達(dá)到數(shù)據(jù)變化 -> 視圖更新；視圖交互變化(input) -> 數(shù)據(jù)model變更的雙向綁定效果
節(jié)選自: https://juejin.cn/post/6844903858804621325
五、介紹下虛擬 DOM，對(duì)虛擬 DOM 的理解
參考解答：
我對(duì)Virtual DOM 的理解：
首先對(duì)我們準(zhǔn)備插入文檔中的DOM樹結(jié)構(gòu)進(jìn)行分析，使用js對(duì)象數(shù)據(jù)類型表示出。Virtual DOM 算法是有三個(gè)核心實(shí)現(xiàn)。一是用JS對(duì)象模擬DOM樹，可以理解組合VNode。二是diff算法，比較新舊VNode的差異。三是打補(bǔ)丁patch，將差異應(yīng)用到真正的DOM樹上。
六、談?wù)勀銓?duì) webpack 的看法
參考解答：
我認(rèn)為webpack的主要原理是將所有的資源都看成一個(gè)模塊，并且把頁面邏輯當(dāng)成一個(gè)整體，通過給定入口文件，找到所有依賴，將各個(gè)依賴經(jīng)過loader和plugins處理后，打包在一起，最后輸出瀏覽器可識(shí)別的js文件。
webpack的核心概念：
Entry: 入口文件，Webpack 會(huì)從該文件開始進(jìn)行分析與編譯；
Output: 出口路徑，打包后創(chuàng)建 bundler 的文件路徑以及文件名；
Module: 模塊，在 Webpack 中任何文件都可以作為一個(gè)模塊，會(huì)根據(jù)配置的不同的 Loader 進(jìn)行加載和打包；
Chunk: 代碼塊，可以根據(jù)配置，將所有模塊代碼合并成一個(gè)或多個(gè)代碼塊，以便按需加載，提高性能；
Loader: 模塊加載器，進(jìn)行各種文件類型的加載與轉(zhuǎn)換；
Plugin: 拓展插件，可以通過 Webpack 相應(yīng)的事件鉤子，介入到打包過程中的任意環(huán)節(jié)，從而對(duì)代碼按需修改；
七、手寫一個(gè)Promise
參考解答：
const PENDING = "pending";const RESOLVED = "resolved";const REJECTED = "rejected";function MyPromise(fn) {// 保存初始化狀態(tài)var self = this;// 初始化狀態(tài)this.state = PENDING;// 用于保存 resolve 或者 rejected 傳入的值this.value = null;// 用于保存 resolve 的回調(diào)函數(shù)this.resolvedCallbacks = [];// 用于保存 reject 的回調(diào)函數(shù)this.rejectedCallbacks = [];// 狀態(tài)轉(zhuǎn)變?yōu)?resolved 方法function resolve(value) {// 判斷傳入元素是否為 Promise 值，如果是，則狀態(tài)改變必須等待前一個(gè)狀態(tài)改變后再進(jìn)行改變if (value instanceof MyPromise) {return value.then(resolve, reject);}// 保證代碼的執(zhí)行順序?yàn)楸据喪录h(huán)的末尾setTimeout(() => {// 只有狀態(tài)為 pending 時(shí)才能轉(zhuǎn)變，if (self.state === PENDING) {// 修改狀態(tài)self.state = RESOLVED;// 設(shè)置傳入的值self.value = value;// 執(zhí)行回調(diào)函數(shù)self.resolvedCallbacks.forEach(callback => {callback(value);});}}, 0);}// 狀態(tài)轉(zhuǎn)變?yōu)?rejected 方法function reject(value) {// 保證代碼的執(zhí)行順序?yàn)楸据喪录h(huán)的末尾setTimeout(() => {// 只有狀態(tài)為 pending 時(shí)才能轉(zhuǎn)變if (self.state === PENDING) {// 修改狀態(tài)self.state = REJECTED;// 設(shè)置傳入的值self.value = value;// 執(zhí)行回調(diào)函數(shù)self.rejectedCallbacks.forEach(callback => {callback(value);});}}, 0);}// 將兩個(gè)方法傳入函數(shù)執(zhí)行try {fn(resolve, reject);} catch (e) {// 遇到錯(cuò)誤時(shí)，捕獲錯(cuò)誤，執(zhí)行 reject 函數(shù)reject(e);}}MyPromise.prototype.then = function(onResolved, onRejected) {// 首先判斷兩個(gè)參數(shù)是否為函數(shù)類型，因?yàn)檫@兩個(gè)參數(shù)是可選參數(shù)onResolved =typeof onResolved === "function"? onResolved: function(value) {return value;};onRejected =typeof onRejected === "function"? onRejected: function(error) {throw error;};// 如果是等待狀態(tài)，則將函數(shù)加入對(duì)應(yīng)列表中if (this.state === PENDING) {this.resolvedCallbacks.push(onResolved);this.rejectedCallbacks.push(onRejected);}// 如果狀態(tài)已經(jīng)凝固，則直接執(zhí)行對(duì)應(yīng)狀態(tài)的函數(shù)if (this.state === RESOLVED) {onResolved(this.value);}if (this.state === REJECTED) {onRejected(this.value);}};
八、手寫一個(gè)觀察者模式
參考解答：
var events = (function() {var topics = {};return {// 注冊(cè)監(jiān)聽函數(shù)subscribe: function(topic, handler) {if (!topics.hasOwnProperty(topic)) {topics[topic] = [];}topics[topic].push(handler);},// 發(fā)布事件，觸發(fā)觀察者回調(diào)事件publish: function(topic, info) {if (topics.hasOwnProperty(topic)) {topics[topic].forEach(function(handler) {handler(info);});}},// 移除主題的一個(gè)觀察者的回調(diào)事件remove: function(topic, handler) {if (!topics.hasOwnProperty(topic)) return;var handlerIndex = -1;topics[topic].forEach(function(item, index) {if (item === handler) {handlerIndex = index;}});if (handlerIndex >= 0) {topics[topic].splice(handlerIndex, 1);}},// 移除主題的所有觀察者的回調(diào)事件removeAll: function(topic) {if (topics.hasOwnProperty(topic)) {topics[topic] = [];}}};})();
九、手寫一個(gè)jsonp
參考解答：
function jsonp(url, params, callback) {// 判斷是否含有參數(shù)let queryString = url.indexOf("?") === "-1" ? "?" : "&";// 添加參數(shù)for (var k in params) {if (params.hasOwnProperty(k)) {queryString += k + "=" + params[k] + "&";}}// 處理回調(diào)函數(shù)名let random = Math.random().toString().replace(".", ""),callbackName = "myJsonp" + random;// 添加回調(diào)函數(shù)queryString += "callback=" + callbackName;// 構(gòu)建請(qǐng)求let scriptNode = document.createElement("script");scriptNode.src = url + queryString;window[callbackName] = function() {// 調(diào)用回調(diào)函數(shù)callback(...arguments);// 刪除這個(gè)引入的腳本document.getElementsByTagName("head")[0].removeChild(scriptNode);};// 發(fā)起請(qǐng)求document.getElementsByTagName("head")[0].appendChild(scriptNode);}
十、實(shí)現(xiàn)一個(gè)淺拷貝和一個(gè)深拷貝
參考解答：
// 淺拷貝的實(shí)現(xiàn);function shallowCopy(object) {// 只拷貝對(duì)象if (!object || typeof object !== "object") return;// 根據(jù) object 的類型判斷是新建一個(gè)數(shù)組還是對(duì)象let newObject = Array.isArray(object) ? [] : {};// 遍歷 object，并且判斷是 object 的屬性才拷貝for (let key in object) {if (object.hasOwnProperty(key)) {newObject[key] = object[key];}}return newObject;}// 深拷貝的實(shí)現(xiàn);function deepCopy(object) {if (!object || typeof object !== "object") return;let newObject = Array.isArray(object) ? [] : {};for (let key in object) {if (object.hasOwnProperty(key)) {newObject[key] =typeof object[key] === "object" ? deepCopy(object[key]) : object[key];}}return newObject;}