别害怕前端手写,真没想象的难

📝 主包近期面试手写题记录

🌟 观察发现

对于前端实习生岗位,对算法要求并不是很高 主要考察Js Api的熟悉程度与基础算法(hot100)

📊 小结论

前端岗位中，大公司的约面概率远大于小公司～

💡 小建议

如果暂时约不到面试，不妨大胆投递大公司试试呀（字节除外哦～）😉

• 大写转驼峰(24.9.11百度日常实习一面)
• 合并两个有序数组(24.9.25 蔚来日常实习一面)
• 最佳观景台(24.12.26 小米日常一面)
• 两字符字符串的回文对计数(24.12.27 小米日常二面)
• 控制并发数 (24.12.27 不知名小公司)
• 子树添加父ID (4.28 滴滴暑期一面)
• 扑克牌找顺子 (5.19 字节飞书一面)
• 反转链表 (5.19 字节飞书一面 最最最高频)
• 手写reduce (5.20 美团二面)
• 解析URL query (5.20 美团二面)
• 反转链表 (5.20 美团二面)
• ReplaySubjec (5.20 字节二面)
• 防抖 (6.3 网易一面)
• 数组转树 (6.10 滴滴一面)
• 科里化 (6.11 快手一面)
• Promise.all与Promise.any (7.03 百度一面)
• 数组分类 (7.03 百度一面)
• 反转链表 (7.08 快手一面)
• 两个无重复子数组的最大值 (7.14 快手二面)

驼峰转大写

题目要点:熟悉jsApi,如字符串分割Spilt,字符串转大小写Api,字符串转数组Api

• 按 - 分割字符串成数组
• 遍历数组,将除第一个数组外的,首字母转为大写
• 字符串转数组join

 // 'get-element-by-id ' => 'getElementById'
function foo(str){
    let string=str.split('-')
    let ans=string.map((item,index)=>{
        if(index==0){
            return item
        }else{
            return item.at(0).toUpperCase()+item.slice(1)
        }
    }).join('')
    return ans
}

合并两个有序数组高频

• 逆向填充：从后向前遍历数组，每次选择较大的元素放入nums1的末尾(避免避免覆盖未处理的元素)

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]   //升序输出

var merge = function(nums1, m, nums2, n) {
    let i = m - 1, j = n - 1, k = m + n - 1;
    while (i >= 0 || j >= 0) {
        if(nums1[i] <= nums2[j]) nums1[k--] = nums2[j--];
        else if(nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
        else if(i < 0) nums1[k--] = nums2[j--];
        else if(j < 0) nums1[k--] = nums1[i--];
    }
    return nums1;
};

最佳观景台

有一串景点，每个景点都有自己的评分（比如 5 分、8 分、3 分等）。现在要挑两个景点 i 和 j，计算它们的 "组合得分"。

组合得分的计算方式是：i 的评分 + j 的评分 - 两个景点之间的距离

• 写出公式:values[i]+values[j]+i-j
• 拆分公式:values[i]+i+values[j]-j
• 求出最大的values[i]+i
• 保证i<j(不然i-j将会是正数(如i:3,j:1))

// values = [8,1,5,2,6]
// 求Max=values[i]+values[j]+i-j

 var maxScoreSightseeingPair = function(values) {
    let ans = 0
    let max = values[0]; // max 表示 i 左边的 values[i] + i 的最大值
    for (let i = 1; i < values.length; i++) {
        ans = Math.max(ans, max + values[i] - i);
        max = Math.max(max, values[i] + i);
    }
    return ans;
};

两字符字符串的回文对计数(不记得题了,不写了^_^)

控制并发数

• 三个核心函数,start,setPromise,run
• start: 输入URL将并发池填满,并执行最快的一个(Promise.race)
• setPromise:将输入的URL包装成请求,并正式加入并发池
• run:每当并发池中完成一个任务，就再次塞入一个任务,并执行

const URLs = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0];
class PromiseArr {
  constructor(max, fn,urls) {
    this.max = max; // 最大并发数
    this.fn = fn; // 自定义的请求函数
    this.Arr = []; // 并发池
    this.urls = urls; // 剩余的请求地址
  }
  start() {
    //  循环把并发池塞满
    while (this.Arr.length < this.max) {
      let url = this.urls.shift();
      this.setPromise(url);
    }
    // 利用Promise.race 方法来获得并发池中某个任务完成的信号
    this.run(Promise.race(this.Arr));

  }
  setPromise(url) {
    if (!url) return;
    let Promise = this.fn(url);
    this.Arr.push(Promise); // 将任务推入Arr并发池中
    console.log(`${url}开始，当前的并发数:${this.Arr.length}`);
    Promise.finally(() => {
      // 请求结束将该promise任务从并发池中移除
      this.Arr.splice(this.Arr.indexOf(Promise), 1);
      console.log(`${url}结束，当前的并发数:${this.Arr.length}`);
    });
  }
  run(race) {
    race.then(() => {
      // 每当并发池中完成一个任务，就在塞入一个任务
      let url = this.urls.shift();
      this.setPromise(url);
      this.run(Promise.race(this.Arr));
    });
  }
}
// 模拟异步请求函
let fn = (url) => {
  return new Promise((resolve) => {
    setTimeout(() => {
      resolve(`任务${url}完成`);
    }, 2000);
  }).then((res) => {
    console.log(res);
  });
};
// 并发数为3
const Arr = new PromiseArr(3, fn,URLs);
Arr.start(URLs);

子树添加父ID

• 理解递归(大问题分解为子问题)

[
  {
    id: 1,
    children: [{ id: 11 }, { id: 12, children: [{ id: 121 }] }],
  },
]变为
[
  {
    "id": 1,
    "children": [{"id": 11,"parent": 1},{"id": 12,"children": [{"id": 121,"parent": 12}],
     "parent": 1
      }
    ]
  }
]

let arr = [
  {
    id: 1,
    children: [{ id: 11 }, { id: 12, children: [{ id: 121 }] }],
  },
];
function foo(arr) {
  arr.forEach((item) => {
    if (item.children) {
      foo(item.children);
      item.children.forEach((item1) => {
        item1.parent = item.id;
      });
    }
  });
  return arr;
}
console.log(JSON.stringify(foo(arr)));

扑克牌找顺子

• 参考最长连续序列哈希写法
• Set 的查找是 O(1)
• 找连续序列的起点(!set.has(item-1))不存在更小一的数

var longestConsecutive = (nums) => {
    let set=new Set(nums)
    let ans=0
    for(let item of set){
        if(!set.has(item-1)){
            let cur=item
            let count=1
            while(set.has(cur+1)){
                count++
                cur=cur+1
            }
            ans=Math.max(count,ans)
        }
    }
    return ans
}

从52张扑克牌(无大小王)中抽取 5 张牌，判断这 5 张牌是否构成一个顺子，即这 5 张牌是否连续
黑桃（♠）：0-12（13 张）
如:[0,1,2,3,4]true   [13,1,2,3,4]true   [13,14,2,3,4]true
function foo(nums){
  let set=new Set(nums)
  for(let item of set){
    if(!set.has(item-1)||!set.has(item-14)||!set.has(item-27)||!set.has(item-40)||!set.has(item-53)){
      let cur=item
      let count=1
       while(set.has(cur+1)||set.has(cur+14)||set.has(cur+27)||set.has(cur+40)||set.has(cur+53)){
                count++
                cur=cur+1
                if(count==5)return true
            }
    }
  }
  return false
}
console.log(foo([0,1,2,3,4]));//true
//代码貌似有点问题,就这样吧^_^,理解思路

反转链表(超超高频)

• 手写链表数据结构
• 三指针法：使用三个指针pre、cur、next分别记录前一个节点、当前节点和下一个节点。
• 迭代反转：遍历链表，逐个修改当前节点的next指针，使其指向前一个节点。

  function ListNode(val, next) {
      this.val =  val
      this.next = next
  }
var reverseList = function(head) {
    let pre=null
    let cur=head
    while(cur){
        let next=cur.next
        cur.next=pre
        pre=cur
        cur=next
    }
    return pre
};
let list2=new ListNode(2,null)
let list1=new ListNode(1,list2)
let list0=new ListNode(0,list1)
reverseList(list0)
console.log(list0)
console.log(list1)

• 递归到末尾
• 回溯时反转指针：在回溯过程中，将当前节点的next指向前一个节点，实现指针反转。

  function ListNode(val, next) {
      this.val =  val
      this.next = next
  }
var reverseList = function(head) {
    let pre=null
    let cur=head
    let dfs=(pre,cur)=>{
        if(cur==null)return pre
        dfs(cur,cur.next)
        cur.next=pre
    }
    dfs(pre,cur)
};
let list2=new ListNode(2,null)
let list1=new ListNode(1,list2)
let list0=new ListNode(0,list1)
reverseList(list0)
console.log(list0)
console.log(list1)

手写reduce

要求:熟悉this指向,熟悉reduce函数的传参与返回值,用法

• 如果提供了初始值 initialValue，则从数组索引 0 开始，初始累积值为 initialValue。
• 如果未提供初始值，则从数组索引 1 开始，初始累积值为数组的第一个元素 this[0]。

Array.prototype._reduce = function(callback, initialValue) {
    let index =  initialValue ? 0 : 1;
    let res = initialValue ? initialValue : this[0];
    for(let i = index; i < this.length; i++) {
        res = callback.call(null, res, this[i], i, this);
    }
    return res;
}

解析URL query

const url ='www.nio.com?a=1&b=2&c=3'
{a:1,b:2,c:3}

URLSearchParams与Object.fromEntries

const url ='www.nio.com?a=1&b=2&c=3'
let  newUrl=url.split('?')[1]
let ans=Object.fromEntries(new URLSearchParams(newUrl))
console.log(ans);

熟悉常见Api: indexOf,silice,for of ,解构,split

const url ='www.nio.com?a=1&b=2&c=3'
function foo(url){
  let ans={}
  let startIndex=url.indexOf('?')+1
  let arr=url.slice(startIndex).split('&')
  for(let item of arr){
    const [key, value] = item.split('=');
    ans[key]=value
  }
  return ans
}
console.log(foo(url));

ReplaySubjec

• next 方法： 如果缓存数量超过 maxCount，移除最早的缓存值。 将新值添加到缓存数组。 遍历所有订阅函数，执行每个函数并传入新值。
• subscribe 方法： 将新的订阅函数添加到订阅数组。 遍历缓存数组，将每个缓存值传递给新订阅函数。 测试案例

class ReplaySubject {
  constructor(maxCount) {
    this.maxCount = maxCount;
    this.arr = [];
    this.fn = [];
  }

  next(value) {
    if (this.arr.length >= this.maxCount) {
      this.arr.shift();
    }
    this.arr.push(value);
    this.fn.forEach(fn => fn(value));
  }

  subscribe(obj) {
    this.fn.push(obj);
    this.arr.forEach(cur => obj(cur));
  }
}
const sub = new ReplaySubject(3);
sub.next(1);
sub.next(2);
sub.subscribe(console.log); // 输出: 1, 2
sub.next(3); // 输出: 3
sub.next(4); // 输出: 4
sub.subscribe(console.log); // 输出: 2, 3, 4
sub.next(5); // 输出: 5, 5

防抖(高频)

• 闭包保存私有变量
• setTimeout This指向问题

    let btn = document.querySelector("#btn");
      function foo() {
        console.log(this, "已提交");
      }
      let clear;//污染全局变量
      function debounce(fn, time) {
        if (clear) clearTimeout(clear);
        setTimeout(() => {
          fn();
        }, time);
      }
      btn.addEventListener("click", () => debounce(foo, 1000));

可以看到定时器ID将污染全局变量

利用闭包优化

   function foo(arg) {
        console.log(this, "已提交", arg);
      }
      btn.addEventListener("click", debounce(send, 1000, '参数'));
      function debounce(fn, time, ...arg) {
        let timer = null;
        return function () {
          if (timer) clearTimeout(timer);
          timer = setTimeout(() => {
            fn.call(this, ...arg);
          }, time);
        };
      }

数组转树

理解递归

• 通过filter获取子元素
• 将子元素添加至children

const arr = [
  { id: 1, parentId: null },
  { id: 2, parentId: 1 },
  { id: 3, parentId: 1 },
  { id: 4, parentId: 2 },
  { id: 5, parentId: 2 },
  { id: 6, parentId: 3 },
];
function createNode(id, arr) {
  // data中去查找根节点下有哪些子节点
  const childArr = arr.filter(({ parentId }) => parentId === id);
  // 重写节点
  return {
    id,
    children: childArr.map((item) => {
      return createNode(item.id, arr);
    }),
  };
}

科里化

理解闭包,函数参数arguments

function add() {
  let arg = [...arguments];
  let fn = function () {
    return add.apply(null, arg.concat([...arguments]));
  };
  fn.add1 = () => arg.reduce((a, b) => a + b);
  return fn;
}
console.log(add(1)(2,3)(4).add1())

Promise.all

注意:函数参数要求传入迭代器

• 并行执行多个 Promise，返回一个新 Promise：

• 若所有 Promise 都成功，结果为按顺序排列的结果数组。

• 若任何一个 Promise 失败，立即拒绝并返回第一个失败的错误。

Promise._all = function (promises) {
  let ans = [];
  return new Promise((resolve, reject) => {
    promises.forEach((item) => {
      Promise.resolve(item).then(
        (val) => {
          ans.push(val);
          if (ans.length == promises.length) {
            resolve(ans);
          }
        },
        (err) => {
          reject(err);
        }
      );
    });
  });
};

let p1 = Promise.resolve("1");
let p2 = new Promise((resolve, reject) => {
  setTimeout(() => {
    resolve("p2 延时一秒");
  }, 2000);
});
let p3 = new Promise((resolve, reject) => {
  setTimeout(() => {
    reject("p3 延时一秒");
  }, 1000);
});
Promise._all([p1, p2, p3])
  .then((res) => console.log(res))
  .catch((err) => console.error(err));

两个无重复子数组的最大值

理解前缀和,快速求子数组和

• 前缀和数组：预处理数组arr，其中arr[i]表示nums前i个元素的和，用于快速计算任意子数组的和。
• 两次滑动窗口遍历：
• 第一次遍历：固定secondLen子数组在右侧，动态调整左侧firstLen子数组的位置，记录左侧最大和。
• 第二次遍历：固定firstLen子数组在右侧，动态调整左侧secondLen子数组的位置，记录左侧最大和。
• 取最大值：两次遍历结果的最大值即为答案。

var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
    let res = 0, n = nums.length
    let arr = Array(n+1).fill(0)
    for(let i = 0; i<n;i++){
        arr[i+1] = arr[i] + nums[i]
    }
    for(let i = firstLen, t = 0; i + secondLen - 1 < n; i++){
        t = Math.max(t,arr[i] - arr[i-firstLen])
        res = Math.max(res, t + arr[i+secondLen] - arr[i])
    }
    for(let i = secondLen, t = 0; i + firstLen - 1 < n; i++){
        t = Math.max(t,arr[i] - arr[i-secondLen])
        res = Math.max(res, t + arr[i+firstLen] - arr[i])
    }
    return res
};