我的博客

面试总结

目录
  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) 的

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
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)时间

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
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].
请给出足够的测试用例。
/

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
33
34
35
36
37
38
#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/
*/

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
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

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
#评测题目:请实现一个函数用来找出字符流中第一个只出现一次的字符。
#例如,当从字符流中只读出前两个字符"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)的节点是从根节点向左,向右走了多少次。

1
2
3
4
5
6
7
8
9
10
11
def fun(x, y):
left_step = 0
right_step = 0
while x != 1 and y != 1:
if x > y:
left_step += x // y
x = x % y
else:
right_step += y // x
y = y % x
return left_step, right_step

2020-03-25-2

先聊了项目

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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/ 不同的是要求逆时针

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

评论无需登录,可以匿名,欢迎评论!