2.28 笔试

笔试成绩

image-20210228213614246

这是最后的测试结果，算比较满意的一个结果吧，至少中等题（难度应该在中下）拿到分数了。

简单总结一下这次的考题吧。

Task1

由于我没有截图题目，所以就简单复述一下。

题目要求：删除字符串 S 中的一个字符，使得最后的字符串的字典序尽可能小。

例如 acb，删除一个字符可以得到 ac, ab, cb，我们得到的结果应该是 ab，因为它的字典序最小。

属于之前在 Leetcode 上经常遇到的简单题了，实际上就是让字符串在头部尽可能递增，用到的数据结构算是递增数组吧。

具体算法流程见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(S):
    # 尽量保证字符串的开头为递增
    res = []
    n = len(S)
    for i, s in enumerate(S):
        if not res or res[-1] <= s:
            res.append(s)
        else:
            # 若出现递减
            res.pop()
            for j in range(i, n):
                res.append(S[j])
            break
    if len(res) == n:
        res.pop()
    return ''.join(res)

print(solution('acb'))

Task2

题目要求：针对数组 S，找出等和子数组的最大个数，要求子数组的为相邻的两个数且子数组之间不能有重叠部分。

以 [10, 1, 3, 1, 2, 2, 1, 0, 4] 为例，最大的等和子数组数为3，即 [1, 3], [2, 2],[0, 4] 或者 [3, 1], [2, 2], [0, 4]

卡了我蛮久的，我花了大概四十分钟才发现这道题很简单。

用到的数据结构就是哈希表（字典），用字典 dic 来计算出现的和的个数。

假设每个数都只能和它左侧的数组合起来（和右侧数结合等价于右侧数和它左侧数结合），遍历数组。

若当前的数组和同上一个和不同，则说明可能出现该组合。例如，假设数组为 [10, 1, 3]，上一次的和是11，这一次的和是4，则令 dic[4] += 1。

反之，若当前的和同上一次的和相同，则不应该重复计数。例如 [1, 3, 1]，上一次的和是4，这一次的也是4，但是这个4是不可能出现两次的，所以这时不能使 dic[4] += 1。

但是还有一个情况要注意，[1, 3, 1, 3]，此时1 + 3 = 4， 3 + 1 = 4，1 + 3 =4，虽然三次的和都相等，但是这种组合是允许出现两个4的，即分割成两个 [1,3]。为了区分这种情况，我是使用了 flag 变量来确认的，强大的读者应该可以想到更好的办法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import collections

def solution(S):
    n = len(S)
    dic = collections.defaultdict(int)
    last_sum = 0
    flag = 0
    for i in range(1, n):
        cur_sum = S[i] + S[i - 1]
        if last_sum != cur_sum:
            dic[cur_sum] += 1
            flag = 0
        else:
            if flag == 1:
                dic[cur_sum] += 1
                flag = 0
            else:
                flag = 1
        last_sum = cur_sum
    return max(dic.values())


print(solution([10, 1, 3, 1, 2, 2, 1, 0, 4]))

Task3

很尴尬，这道题我提交的时候就知道我拿不了满分了，但是我确实无法想出时间复杂度为O(N)的解法了。👶

题目要求：给定一个字符串 S，字符串的格式为 aa?b?a，要做的是把其中的 ? 替换成 a 或者 b，而且要保证最后结果中不能有连续的三个 a 或者 b。

我的想法比较纯粹，深搜。就搜索各种可能的路径，将 ? 替换成 a 或者 b，直到找到可能的解。

很可惜，题目的 N 限制的是小于 500,000，所以只拿到50分也是意料之中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import copy

def solution(S):
    res = []

    def dfs(houses, no, cnt_a, cnt_b):
        if res:
            return
        if cnt_a == 3 or cnt_b == 3:
            return
        if no == len(houses):
            res.append(houses)
            return
        if houses[no] == 'a':
            dfs(houses, no + 1, cnt_a+1, 0)
        elif houses[no] == 'b':
            dfs(houses, no + 1, 0, cnt_b+1)
        elif houses[no] == '?':
            tmp = copy.deepcopy(houses)
            tmp[no] = 'a'
            dfs(tmp, no + 1, cnt_a + 1, 0)
            tmp = copy.deepcopy(houses)
            tmp[no] = 'b'
            dfs(tmp, no + 1, 0, cnt_b + 1)

    houses = list(S)
    dfs(houses, 0, 0, 0)
    return ''.join(res[0])


print(solution('a?ab?b?b??b?b?ba??a?bb'))

3.10 一面

3.9 号面试官突然约我明天面试，我吓一跳，原以为会拖得比较后面的。

自我介绍 => 为什么选择前端 => 询问博客相关技术（后来因为面试官的内网无法访问就略过了）

继续询问我的项目相关，然而无论是实验报告模块还是会议预约及门机管理模块，其实和前端相关的技术沾边很少，因此也只是草草略过。

在做页面展示的时候，面试官问我怎么解决缩放导致的字体位置和图标大小问题，我只能说改成以 rem 为单位来描述 font-size 或许对页面有优化。后因面试官也无法调试成功遂跳过。

CSS

问：盒模型？

答：关于盒模型答的马马虎虎，大概讲了由哪几部分组成，在 Chrome 中计算长宽和 IE 中计算长宽有什么区别。

问：flex 布局是否了解过？

答：我暂时还没有去了解过。

JS

问：JS 了解到什么程度？

答：学习了 ES6 的语法。

问：let, const, var 区别？

答：let 定义变量，const 定义常量，var 定义全局变量。……

问：怎么确认语法的浏览器适配性？

答：查询 MDN 网站文档。

问：了解过闭包吗？

答：（刚看过就忘了）……

算法

  1. 确认链表是否有环

    快慢指针，如果两个指针相遇就说明有环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    class Node:
        def __init__(self, value):
            self.val = value
            self.next = None


    def func(head):
        slow, fast = head, head.next
        while fast and fast.next:
            if fast == slow:
                return True
            fast = fast.next.next
            slow = slow.next
        return False


    def main():
        nums = list(range(2, 8))
        head = Node(1)
        nodes = [head]
        for i in nums:
            node = Node(i)
            head.next = node
            nodes.append(node)
            head = node
        nodes[6].next = nodes[2]
        print(func(nodes[0]))


    if __name__ == "__main__":
        main()

  2. 找到有环链表中环的起始节点

    因为只讲出解法，没写出证明，还被面试官问是当场想出来的吗，我只能回答说做过题 😅

    思路和上题类似，快慢指针从链表头部出发，在第一次相遇之后，将快指针退回头部，重新出发，速度设为1，第二次相遇位置就是环的起始位置。

3.17 二面

上次面完第二天就约了我二面，为了巩固一下基础知识，我约在了一面的一周之后。

开局依然是自我介绍 => 介绍项目 => 项目难点？（真的讲不出）

CSS

问：讲一下 flex 布局吧

答：一个更加现代的布局方式，完美适配手机端，唯一问题是不兼容 IE。一般我们用的时候就使用 .container { flex: true }，来使用 flex 布局，然后内部元素如果都设置为 flex: 1，就会依次平均分配容器内区域。

问：flex 的两个参数是什么？

答：应该是三个参数吧，一般默认是 1 1 auto，第一个参数越大占比越大，第二个参数越大占比越小，第三个参数没有做深入了解。

JS

问：可以简单介绍一下 ES6 中的 Promise吗？

答：一个用来进行异步处理的模块，可以有效解决回调地狱的问题。允许我们把异步操作写成链式调用，使代码更加优雅。

问：具体处理成功和失败的参数是什么？什么情况下会返回失败呢？

答：实际开发中没有正式用过，记不太清了…（正确答案应该是 resolve 和 reject，在 Promise 对象中，调用 resolve() 就是成功，reject() 就是拒绝）

然后又回到了我的项目上，先让我介绍了一下什么叫 MVC 框架，其中模型，视图，控制器各负责什么工作，如何交互。

问：如果一个表格的某一格的文字太长了该如何处理？

答：添加 CSS 属性 {overflow: hidden; text-overflow: ellipse; white-space: no-wrap}

这边一时间没想起来 white-space，面试官允许我搜了一下。

算法

问：能讲解一下搜索二叉树是什么，怎么实现的吗？

答：画出了一个图，然后演示了二叉树是怎么进行搜索（中间卡壳了，面试官引导了一下）。

面试官应该是知道我答不出怎么实现的二叉搜索树，所以把问题换了个方向

问：什么是平衡二叉树？怎么把非平衡二叉树转换成平衡二叉树？

答：平衡二叉树就是叶子的深度差小于等于 1 的树，不太确定该怎么平衡

又在面试官的引导下，学会了怎么平衡二叉树

问：最长递增子序列（一开始是它的困难版，要求返回的是最长子序列本身）

我仍然是在面试官引导下，花了二十几分钟写出了个动归。一开始以为遍历一遍就能得到答案，一直没转过来。

1
2
3
4
5
6
7
8
9
10
11
12
13
def find_longest(nums):
    # 最长非递减子序列
    n = len(nums)
    dp = [1] * (n)
    for i in range(1, n):
        for j in range(i):
            if nums[j] <= nums[i]:
                dp[i] = max(dp[j] + 1, dp[i])
    return max(dp)

nums = [10, 1, 9, 7, 3, 4, 5, 0, 6, 9]

print(find_longest(nums))

感觉有点悬，自己的算法和基础仍然不稳定。

3.18 三面

项目 => Vue 框架和我之前使用的 Laravel 有什么区别 => 两道设计题

设计题

  1. 如果现在我们拥有微信所有公众号的推送的阅读量数据，怎么获取某一天的阅读量的中位数

    一开始我的思路是，根据阅读量的数据的出现频率先把所有的阅读量分成十个部分（各个堆里的数据量需要尽可能接近），比如我把 0-100 的数据放到第一个堆，101-300 的放到第二个堆…，最后大于 10000 的放到第十个堆。通过这个方法我能快速确认每个堆的数据量是多少，然后根据我的总数据量，首先确认中位数在哪一堆，再根据这个堆里的数据，确认中位数。

    后来我又发现这样子计算的话最后还是需要 O(NlogN) 的时间复杂度对堆数据进行排序，不如直接用哈希表。

    最后我就说新建一个哈希表，以 阅读量=>出现次数 的键值对形式来存取所有的阅读量数据。我如果需要确定中位数，就从 dic[0] 开始加，一直加到数据量的一半的时候根据 key 的大小，就能确定中位数。

    由于阅读量的出现频率是随着阅读量的增加而减小的（宏观上），比如阅读量 100 的文章数必然是会比阅读量 100000 的文章多得多，所以我最后应该很快就能找到中位数所在的 key

  2. 怎么样优化网站，才能使用户下滑页面，异步加载更多新闻的时候体验更加流畅。

    由于我没有实际做过这种开发，所以我只能回答出大概的思路：在用户的滚动条滑动到一定位置的时候，让用户提前开始加载他很可能即将访问到的数据，然后确保用户在滑到最底下之前，所需的数据全部传输完毕，最后开始渲染。我们可以收集一些数据并且对用户的网络速度进行一个假设，来确认这个开始传输数据的滚动条的位置。

    我真觉得我就跟讲故事一样，越讲越玄乎。

算法

一道简单题直接把我脑子卡宕机了，在一个小 trick 上浪费了半个小时。

168. Excel表列名称

3.19

内推学长告知等 offer 🤯

4.6 Offer！

GET 💡

image-20210410140356593