2021字节跳动算法面试题为什么这么难？上周刚面过算法题已整理成pdf（分享）

比眉伴天荒 2023-01-15 03:58 202阅读 0赞

>   前几天博主刚去面试字节跳动，面试官问了一些算法题。已经记录下来整理成文档了。去面试之前就听说字节跳动面试非常喜欢考算法题，基本每轮技术面都会有算法题，而且很难。  
>   即将要去大厂面试的小伙伴可以采纳一波。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81NjEzNDM4MQ_size_16_color_FFFFFF_t_70_pic_center]

拒绝白嫖，各位看客记得点赞评论"妙…啊~~~"在此占坑

>   趁着年轻生猛，我要再和生活死磕几年。要么我就毁灭，要么我就铸就辉煌。如果有一天，你发现我在平庸面前低了头，那么请向我开炮。 – 《在路上》

--------------------

### 字节跳动算法题 ###

#### 链表 ####

面试题：反转单向链表

题目需要将一个单向链表反转。思路很简单，使用三个变量分别表示当前节点和当前节点的前后节点，虽然这题很简单，但是却是一道常考题

以下是实现该算法的代码

var reverseList = function(head) { 
      // 判断下变量边界问题
      if (!head || !head.next) return head
      // 初始设置为空，因为第一个节点反转后就是尾部，尾部节点指向 null
      let pre = null
      let current = head
      let next
      // 判断当前节点是否为空
      // 不为空就先获取当前节点的下一节点
      // 然后把当前节点的 next 设为上一个节点
      // 然后把 current 设为下一个节点，pre 设为当前节点
      while(current) { 
        next = current.next
        current.next = pre
        pre = current
        current = next
     }
      return pre
    };

#### 二叉树遍历 ####

*  原理: 递归

function traversal(node,tempOrderTraversal) { 
    if (node != null) { 
      // tempOrderTraversal.push(node.value) 前序遍历
      if (node.left != null) { 
        preOrderTraversal(node.left,tempOrderTraversal)
      }
      // tempOrderTraversal.push(node.value) 中序遍历
      if (node.right != null) { 
        preOrderTraversal(node.right,tempOrderTraversal)
        }
        // tempOrderTraversal.push(node.value) 后序遍历
         }
      }

不能使用递归时，则使用栈就是JS的数组push、pop

// 非递归遍历
    var kthSmallest = function(root, k) { 
    const tempArr = [];
    let result;
    tempArr.push(root);
    while (tempArr.length > 0) { 
     result = tempArr.pop();
     if (result.value == k) break;
     if (result.left != null) tempArr.push(result.left);
     if (result.right != null) tempArr.push(result.right);
    }
    return result;
    };

#### 按位操作 ####

**1）按位与**  
每一位都为 1，结果才为 1

8 & 7 // -> 0
    // 1000 & 0111 -> 0000 -> 0

**2）按位或**  
其中一位为 1，结果就是 1

8 | 7 // -> 15
    // 1000 | 0111 -> 1111 -> 15

**3）按位异或**  
每一位都不同，结果才为 1

8 ^ 7 // -> 15
    8 ^ 8 // -> 0
    // 1000 ^ 0111 -> 1111 -> 15
    // 1000 ^ 1000 -> 0000 -> 0

从以上代码中可以发现按位异或就是不进位加法

面试题：两个数不使用四则运算得出和

这道题中可以按位异或，因为按位异或就是不进位加法， 8 ^ 8 = 0 如果进位了，就是 16 了，所以我们只需要将两个数进行异或操作，然后进位。那么也就是说两个二进制都是 1 的位置，左边应该有一个进位 1，所以可以得出以下公式 a + b = (a ^ b) + ((a & b) << 1) ，然后通过迭代的方式模拟加法

function sum(a, b) { 
      if (a == 0) return b
      if (b == 0) return a
      let newA = a ^ b
      let newB = (a & b) << 1
      return sum(newA, newB)
    }

#### 堆排序 ####

堆排序利用了二叉堆的特性来做，二叉堆通常用数组表示，并且二叉堆是一颗完全二叉树（所有叶节点（最底层的节点）都是从左往右顺序排序，并且其他层的节点都是满的）。二叉堆又分为大根堆与小根堆。

*  大根堆是某个节点的所有子节点的值都比他小
 *  小根堆是某个节点的所有子节点的值都比他大

堆排序的原理就是组成一个大根堆或者小根堆。以小根堆为例，某个节点的左边子节点索引是 i \* 2 +1 ，右边是 i \* 2 + 2 ，父节点是 (i - 1) /2 。

1.  首先遍历数组，判断该节点的父节点是否比他小，如果小就交换位置并继续判断，直到他的父节点  
    比他大
2.  重新以上操作 1，直到数组首位是最大值
3.  然后将首位和末尾交换位置并将数组长度减一，表示数组末尾已是最大值，不需要再比较大小
4.  对比左右节点哪个大，然后记住大的节点的索引并且和父节点对比大小，如果子节点大就交换位置
5.  重复以上操作 3 - 4 直到整个数组都是大根堆。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81NjEzNDM4MQ_size_16_color_FFFFFF_t_70]

以下是实现该算法的代码

以上代码实现了小根堆，如果需要实现大根堆，只需要把节点对比反一下就好。

#### 树的深度 ####

面试题：树的最大深度

题目需要求出一颗二叉树的最大深度

以下是实现该算法的代码

var maxDepth = function(root) { 
      if (!root) return 0
      return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
    };

对于该递归函数可以这样理解：一旦没有找到节点就会返回 0，每弹出一次递归函数就会加一，树有三层就会得到3。

#### 快速排序 ####

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

*  从数列中挑出一个元素，称为 “基准”（pivot）；
 *  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 *  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

以下是实现该算法的代码

✨[面试题文档分享][Link 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81NjEzNDM4MQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81NjEzNDM4MQ_size_16_color_FFFFFF_t_70_pic_center 2]

### 写在最后 ###

[【点击我】][Link 2]即可免费获取web前端面试宝典、知识点、字节跳动真题文档（含解析）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81NjEzNDM4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/ce3800e7dfa941dbb21014e38895b0c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81NjEzNDM4MQ_size_16_color_FFFFFF_t_70]: /images/20221022/9e79a22cdf22499ca7e0483b79e596c6.png
[Link 1]: https://jq.qq.com/?_wv=1027&k=4Mt0h4KG
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81NjEzNDM4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/f8e60d8cc2624785870e0200143b74ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81NjEzNDM4MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/48618f6362a34cf9a4cd90b0f845b63f.png
[Link 2]: https://jq.qq.com/?_wv=1027&k=lCxfW2VI