部门是京东平台产品研发中心，主要做OLAP数据库。两轮技术面+一轮HR面，目前已入池，许愿OC。9.18一面：主要是问C++。1. 介绍一下智能指针2. shared_ptr和直接用裸指针有什么区别？3. 虚函数为什么会有开销？4. shared_ptr分配的控制块里放了什么？为什么你说最好用make_shared？5. shared_ptr在并发下是安全的吗？手撕两道算法题，一道是栈的，一道是二叉树的，都很ez，主要看写代码的流畅度。9.20 二面一道算法，两道场景1. 合并两个递增链表为一个递减链表2. 分布式系统下你会如何设计一个单调递增时间戳。3. 假设一个系统有1000台机器，如果保证让他们尽量在，尽可能快地完成打印任务。9.23 HR面然后入池9.30 问了一下面试官说挂了，美团也是把我HR面挂了，HR面挂人的原因一般是啥？有老哥说说吗

岗位：后端9.3 一面拷打项目实习，手撕B+树9.14 二面问项目问实习，部门主要是Java，问我能不能接受转9.29 意向

#include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; string str; map<string, int> tree_map; int main() { cin >> str; for (int i = 0; i < str.size(); ++i) for (int j = i; j < str.size(); ++j) ...

如果说，这题用一个预处理一个二维前缀和，然后枚举子矩阵的左上角与右上角，那么我们可以用O(n4)O(n^4)O(n4)的时间复杂度得到答案。不过对于这题n=100来说，1004=108100^4=10^81004=108会超时。 所以我们要想办法优化，最蛋疼的点其实在于暴力的枚举会涉及非常多无用的状态。我们可以优化枚举，转而变成枚举上界与下界。 类似这样，两条红线是我们枚举的上下界。那么问题来了，如何快速的得到两条红线夹出来的子矩阵里的最大子矩阵？（我称之为子子矩阵） 我们可以考虑这个问题的简化版。如果快速得到一个序列里的最大子序列和？这是一个经典的线性dp问题，可以用O(n)O(n)O(n...

循环左移，但是默认的是无符号左移，那怎么办呢？ 就左移的时候检查一下最高位是不是1，如果是1，咱们末尾给他补上就得了呗。用x << 1 | 1就可以给末尾补1且左移了。 所以，答案就是，两个数a,b，让b循环左移16次，如果16次内任何一次使得a和b相同了那么就输出YES。否则NO。 #include <iostream> using namespace std; int main() { unsigned short a, b; while (cin >> a >> b) { bool flag = ...

这题目就是个裸的LCA（最近公共祖先）问题。 向上标记法，就是让两个结点分别检查自己的父节点是否是两者的公共祖先，如果不是，那么大家一起往上跳一层。不断重复这个过程，直到最终收敛到同一个点。（必然收敛，因为最差大家都跳到根节点） 因为这题数据比较弱，是一个完全二叉树，且数值是int范围的，说明最大深度不过30来层，随便跳。 如果题目范围更大，这一步跳的过程，我们是可以用倍增来加速的，如果想要用倍增法加速，那么就需要预处理出每个结点跳2i2^i2i步之后的祖先结点，不过没必要，所以这里略过。 利用完全二叉树的性质，x/2x / 2x/2就是x的父节点，所以省去构造指针指向父节点的步骤。 然后我们...

#include <iostream> using namespace std; int a, b; int sum1, sum2; int reverse(int x) { int res = 0; while (x) { res = res * 10 + x % 10; x /= 10; } return res; } int main() { while (cin >> a >> b) { sum1 = reverse(a+b); ...

#include <iostream> using namespace std; int main() { string hex; while (cin >> hex) { hex = hex.substr(2); long long res = 0; for (int i = 0; i < hex.size(); ++i) { int n; if (hex[i] >= 'A' && hex[i] <...

是个完***的01背包问题，众所周知01背包的状态转移方程是dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i])。dp[i][j]表示在前i个物品里，j容量的背包能拿的最大价值 总共有n个物品，我们从第一个物品一直枚举到第n个物品，对每个物品只需要考虑拿，还是不拿。 首先是不拿，dp[i][j] = dp[i-1][j]，因为第i个物品不拿，都一样。 然后是拿，dp[i][j] = dp[i-1][j-v[i]]+w[i]，上一个状态是在前i-1个物品中拿，且容量不能超过j-v[i]，不然的话都放不下第i个物品了。 所以把拿和不拿分别看看哪个价值更大...

很丑但是很直观的解法 #include <iostream> #include <vector> using namespace std; vector<int> res; int main() { string n; int a, b; cin >> a >> n >> b; long long x = 0; while (n.size() > 1 && n.front() == '0') //去除前导0 n = n.substr(1); ...

可以用f[i][j]表示在j天内吃完i个巧克力的方案，如果无解就是0个方案 #include <iostream> #include <algorithm> using namespace std; const int N = 25; int f[N][N]; //j天吃完i个巧克力的方案数 int main() { for (int i = 0; i <= 20; ++i) f[i][0] = f[0][i] = f[i][1] = f[1][i] = 1; for (int i = 2; i <= 20; ...

先按空格将句子分成一个一个单词，这样就非常方便替换了。直接检查单词即可了。 #include <iostream> #include <algorithm> #include <vector> using namespace std; vector<string> split(string &s) { int i = 0, j = 0; vector<string> a; while (i < s.size()) { while (s[j] != ' ' &&am...

给大家一个完整的大数除法模板，而且返回了余数。 #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> div(vector<int> &A, int b, int &r) { vector<int> C; r = 0; for (int i = A.size() - 1; i >= 0; --i) { r = r * 10 ...

对于这种会变成环状的，一般可以考虑取模 #include <iostream> #include <algorithm> using namespace std; int main() { string a; getline(cin, a); for (int i = 0; i < a.size(); ++i) { if (a[i] >= 'A' && a[i] <= 'Z') //是大写字母 a[i] = (a[i] - 'A' + 1) % 26 + 'A'...