腾讯音乐海笔复盘 · Aiznoyer Atlas

2023.3.23

今天进行了腾讯音乐的数据工程海笔，一个都没写出来真的臊得慌。趁着还记得来进行一下简单的复盘。

首先数据工程和前后端的试题都不同，前后端是3+1，三个算法+一个结构性思维题；数据工程是2+1+2，两个SQL题+一个算法题+两个组件的结构性思维题。两个SQL其实比较简单，但是我SQL并没有想象中的熟练，且听说ac机有点点怪（这不是主要原因），所以没有写出来。题目不太好描述，所以后续搜集到了题目会进行更新。算法是个dfs算法，我算法也不强，想到了递归、想到了指针但是没想到dfs，真该死。。。

两个组件的题也是，简单描述下就是：

手写Kafka消费者工程代码，写一个固定格式的5分钟定时消费的代码
flume
- 维护一个实时排序用什么算法？手写关键代码
- 遇到海量数据时flume背压了，可能的情况和解决方案？
- 结合存储和性能给出的调优、选择方案

很遗憾，我这两个组件的面经都没背，甚至于flume都没有学，所以最后半小时在那一个字都憋不出。下面就对这个算法进行简单复盘。

算法

给定一个字符串和一个字符串数组，输出所有能用字符串数组拼接成字符串的情况。数组中的字符串可重复使用。

text

例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版本：

java

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版本：

scala

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++版本

c++

#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;
    }
}