今天进行了腾讯音乐的数据工程海笔，一个都没写出来真的臊得慌。趁着还记得来进行一下简单的复盘。
首先数据工程和前后端的试题都不同，前后端是3+1，三个算法+一个结构性思维题；数据工程是2+1+2，两个SQL题+一个算法题+两个组件的结构性思维题。两个SQL其实比较简单，但是我SQL并没有想象中的熟练，且听说ac机有点点怪（这不是主要原因），所以没有写出来。题目不太好描述，所以后续搜集到了题目会进行更新。算法是个dfs算法，我算法也不强，想到了递归、想到了指针但是没想到dfs，真该死。。。
两个组件的题也是，简单描述下就是：
- 手写Kafka消费者工程代码，写一个固定格式的5分钟定时消费的代码
- flume
- 维护一个实时排序用什么算法？手写关键代码
- 遇到海量数据时flume背压了，可能的情况和解决方案？
- 结合存储和性能给出的调优、选择方案
很遗憾，我这两个组件的面经都没背，甚至于flume都没有学，所以最后半小时在那一个字都憋不出。下面就对这个算法进行简单复盘。
算法
给定一个字符串和一个字符串数组，输出所有能用字符串数组拼接成字符串的情况。数组中的字符串可重复使用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 例1：
输入：String s = "nowcoder"; String[] arr = {"now", "coder", "no", "wcoder"};
输出：{"now coder", "no wcoder"}
例2：
输入：String s = "nownowcoder"; String[] arr = {"now", "coder", "no", "wcoder"};
输出：{"now now coder", "now no wcoder"}
例3：
输入：String s = "nowcoder"; String[] arr = {"nowcoder"};
输出：{"nowcoder"}
例4：
输入：String s = "nowcoder"; String[] arr = {"now", "wcoder"};
输出：{}
|
为了显著提高我自己的技术，以后的算法笔记采用双版本进行书写。
Java版本：
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
39
| import java.util.*;
public class Main {
public static void main(String[] args) {
Solution s = new Solution();
String s1 = "nowcoder";
String[] s2 = {"now", "coder", "no", "wcoder"};
String[] s3 = s.maxIn(s1, s2);
for (int i = 0; i < s3.length; i++) {
System.out.println(s3[i]);
}
}
}
class Solution {
List<String> res = new ArrayList<>();
String a;
String[] ss;
public String[] maxIn(String s, String[] arr) {
a = s;
ss = arr;
dfs(0, "");
return res.toArray(new String[res.size()]);
}
public void dfs(int parm, String s) {
if (parm >= a.length()) res.add(s);
if (parm < a.length()) {
for(int i = 0; i < ss.length; i++) {
int len = parm + ss[i].length();
if(len <= a.length() && a.substring(parm, len).equals(ss[i])){
if(parm == 0) dfs(len, ss[i]);
else dfs(len, s + " " + ss[i]);
}
}
}
}
}
|
Scala版本：
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
| import scala.collection.mutable.ArrayBuffer
object Main {
def main(args: Array[String]): Unit = {
val s: Solution = new Solution
val s1: String = "nownowcoder"
val s2: Array[String] = Array("now", "coder", "no", "wcoder")
val s3: Array[String] = s.maxIn(s1, s2)
for (i <- s3.indices) {
println(s3(i))
}
}
}
class Solution {
private val res = ArrayBuffer[String]()
private var a: String = null
private var ss: Array[String] = null
def maxIn(s: String, arr: Array[String]): Array[String] = {
a = s
ss = arr
dfs(0, "")
res.toArray
}
private def dfs(param: Int, s: String): Unit = {
if (param >= a.length) res += s
else if (param < a.length) for (i <- ss.indices) {
val len: Int = param + ss(i).length
if (len <= a.length && a.substring(param, len) == ss(i)) {
if (param == 0) dfs(len, ss(i))
else dfs(len, s + " " + ss(i))
}
}
}
}
|
友人提供的C++版本
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <iostream>
#include <vector>
using namespace std;
string s;
int n;
vector <string> v;
vector <vector<string>> ans;
int st[30];
int len;
void getAns() {
vector <string> vi;
for (int i = 0; i < len; i++) {
vi.push_back(v[st[i]]);
}
ans.push_back(vi);
}
void dfs(int p) {
if (p == s.size()) {
getAns();
return;
}
for (int i = 0; i < n; i++) {
int pi = p;
int si = 0;
while (pi < s.size() && si < v[i].size() && s[pi] == v[i][si]) {
pi++;
si++;
}
if (si >= v[i].size()) {
st[len++] = i;
dfs(pi);
len--;
}
}
}
int main() {
cin >> s;
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
dfs(0);
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans[i].size(); j++) {
cout << ans[i][j] << " ";
}
cout << endl;
}
}
|
