面试总结

目录

1. 2020-03-04
   1. 链表反转
   2. 面试题32 - III. 从上到下打印二叉树 III
2. 2020-03-10
3. 2020-03-17 - 1
   1. 二叉树上最大连续元素和
   2. 解码方法
   3. 时间复杂度分析，数组中第 k 小元素
4. 2020-03-17 - 2
5. 2020-03-18 - 1
   1. 题目一
   2. 题目二
6. 2020-03-18-2
7. 2020-03-19-1
8. 2020-03-25-1
9. 2020-03-25-2
10. 2020-03-21

常问问题：

1. 线程与进程的区别，进程间通信的方法
2. bert 原理，结构，预训练任务

2020-03-04

这个时间太久记得不是很清楚了，一共三面

一面

链表反转

由于题目要求用 C++，我对牛客系统也不太适应，居然没写出来。

第二个题忘记了，似乎也没写好

二面

面试题32 - III. 从上到下打印二叉树 III

我今天才发现是剑指 offer 的原题。

方法一：排序

我当时想到的做法，O(nlogn) 的时间复杂度，面试官表示很奇葩。当时不太清醒，实际上可以 O(n) 的

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        l = []
        import queue
        q = queue.Queue()
        q.put((root, 1))
        cid = 1
        last_l = 1
        while not q.empty():
            t, level = q.get()
            if level != last_l:
                last_l = level
                cid = 1
            if t:
                flag = 1
                if level % 2 == 0:
                    flag = -1
                l.append((level, cid*flag, t.val))
                q.put((t.left, level+1))
                q.put((t.right, level+1))
                cid += 1
        l.sort()
        ans = [[] for _ in range(level-1)]
        for x in l:
            ans[x[0]-1].append(x[2])
        return ans

方法二：

只需要把每一层分开放入 list，偶数层 reverse 一下就好了，O（n）时间

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        l = []
        import queue
        q = queue.Queue()
        q.put((root, 1))
        last_l = 1
        ans = []
        while not q.empty():
            t, level = q.get()
            if t:
                if level != last_l:
                    last_l = level
                    if level % 2 == 1:
                        l.reverse()
                    ans.append(l)
                    l = []
                l.append(t.val)
                q.put((t.left, level+1))
                q.put((t.right, level+1))
        if l:
            if level % 2 == 1:
                l.reverse()
            ans.append(l)
        return ans

2020-03-10

倒排索引

mysql 索引的原理

b 树，b+ 树的区别

python 实现字典树

2020-03-17 - 1

二叉树上最大连续元素和

节点可能有负数和 0。动态规划

解码方法

也是动归

leetcode 原题：https://leetcode-cn.com/problems/decode-ways/

时间复杂度分析，数组中第 k 小元素

我记不清楚了，只记得 O（n） 复杂度

2020-03-17 - 2

这个面试我面的不好

只有一道题目

实现二叉搜索树，用数组表示。

刚开始我就直接用 1 号为根，i << 1 , i << 1 | 1 为左右孩子。

但是我理解偏了题意，他出这个问题更想考察工程方面。

1. 数组空间要连续使用，即数组下标模拟指针
2. 使用了递归不应该有双层 if else 嵌套，需要优化
3. find 和 insert 的相同流程应该提出了。

2020-03-18 - 1

题目一

/
一个升序数组，寻找给定数值的开始和结束位置。找不到返回[-1, -1]
Given [5, 7, 7, 8, 8, 8, 10] and target value 8, return [3, 5].
请给出足够的测试用例。 /

#include <iostream>
#include <vector>

class Solution {
public:
    std::vector<int> searchRange(std::vector<int>& nums, int target) {
      int l = 0, r = nums.size();
      while (l < r) {
      	int mid = (l + r) / 2;
        if (nums[mid] < target) {
          l = mid + 1;
        }
        else {
          r = mid - 1;
        }
      }
      std::vector<int> ans;
      if (nums[i] != target) {
        ans.push_back(-1);
        ans.push_back(-1);
        return ans;
      }
      ans.push_back(l);
        
      l = 0, r = nums.size();
      while (l < r) {
      	int mid = (l + r) / 2;
        if (nums[mid] <= target) {
          l = mid + 1;
        }
        else {
          r = mid - 1;
      	}
      }
      ans.push_back(r);
      return ans;
    }
};

题目二

/*
一个特殊的 urlparse ，规则如下
SCHEME://<?PARAM>/PATH
PARAM = <K1=V1><K2=V2>…

<1> hdfs://cluster?ssd=true&cache=1/dir/file
分解：
scheme = hdfs
netloc = cluster
param = ssd=true&cache=1
path = /dir/file

<2> hdfs://cluster/?ssd=true&cache=1/dir/file
scheme = hdfs
netloc = cluster
param =
path = /?ssd=true&cache=1/dir/file

<3> local:///home/xx/
scheme = local
netloc =
param =
path = /home/xx/
*/

using namespace std;
map<string, string > fun(string url) {
  int i = 0;
  map<string, string> ans;
  while (url[i] != ':') {
    i += 1;
  }
  string scheme = url.substr(0, i);
  int ii = i;
  i += 3;
  while (url[i] != '/') {
    i += 1;
  }
  string netloc = url.substr(ii+1, i);
  ii = i;
  i += 1;
  while (i < url.length() && (url[i] != '?' || url[i-1] == '/')) {
    i += 1;
  }
  string path = url.substr(ii, i);
  string param = "";
  if (i < url.length() && url[i] == '?')
	  param = url.substr(i, url.length());
  map["scheme"] = scheme;
  map["netloc"] = netloc;
  map["path"] = path;
  map["param"] = param;
  return map;
}

2020-03-18-2

#评测题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。
#例如，当从字符流中只读出前两个字符"to"时，第一个只出现一次的字符是"t"。
#当从该字符流中读出前六个字符“tomato"时，第一个只出现一次的字符是"m"。

def fun(s):
    import queue
    import collections
    x = ''
    cnt = collections.Counter()
    q = queue.Queue()
    for ch in s:
        cnt[ch] += 1
        if cnt[ch] == 1:
            q.put(ch)
        if x == '' or ch == x:
            if not q.empty():
                while True:
                    xx = q.get()
                    if cnt[xx] == 1:
                        break
                if cnt[xx] == 1:
                    x = xx
                else:
                    x = ''
            else:
                x = ''
        print(ch, x)

fun('tomato')

问快速排序，如何更好的选择枢轴的值。

2020-03-19-1

二叉树中序遍历，非递归：栈

查找链表是否有环：双指针，一个每次走一步，另一个每次走两步

2020-03-25-1

先问了一堆项目、比赛

堆和栈的区别

问如何设计垃圾回收

问了进程与线程的区别

进、线程间通信的方法。

一道算法题：一棵二叉树，一个节点上有 a，b 两个值，根节点是（1,1），对于任意节点（a,b），左孩子的值是（a+b，b），右孩子是（a，a+b），求元素是（X，Y）的节点是从根节点向左，向右走了多少次。

def fun(x, y):
    left_step = 0
    right_step = 0
    while x != 1 or y != 1:
        if x > y:
            if x%y==0:
                left_step += x // y - 1
                x = 1
            else:
                left_step += x // y
                x = x % y
        else:
            if y%x==0:
                right_step += y // x - 1
                y = 1
            else:
                right_step += y // x
                y = y % x
    return left_step, right_step

2020-03-25-2

先聊了项目

谈到 python 的 with 关键字，问底层原理实现，没答上来

class Palindrome:
    def getLongestPalindrome(self, A, n):
        dp = [[False] * n for _ in range(n)]
        ans = 1
        for i in range(n):
            dp[i][i] = True
            if i < n - 1:
                dp[i][i+1] = A[i] == A[i+1]
                if dp[i][i+1]:
                    ans = 2
        for step in range(2, n):
            for s in range(n-step):
                e = s + step
                if A[s] == A[e] and dp[s+1][e-1]:
                    ans = max(ans, e - s + 1)
                    dp[s][e] = True
        return ans

2020-03-21

https://leetcode-cn.com/problems/rotate-image/ 不同的是要求逆时针

二叉树，带父指针。给出一节点，返回他在中序遍历中的后继。