Intern Recruitment

Momenta一面 2019.03.05

C++静态变量 vs 全局变量

全局变量作用域是整个项目，在一个源文件中初始化就可以作用于所有

而static则只在当前作用域有效

C++里const和define有什么区别

define宏是在预处理阶段展开，const常量是编译运行阶段使用

define只是展开，有多少地方使用，就展开多少次，不会分配内存

const可以节省空间，避免不必要的内存分配，C++里面应该只使用const不使用define

C++里虚函数作用是什么

虚函数的作用是允许在派生类中重新定义与基类同名的函数，并且可以通过基类指针或引用来访问基类和派生类中的同名函数

C++里拷贝构造函数在什么时候会被调用

A b;
// 以下均会调用拷贝构造
A a(b);
A a = b;

Python是传值还是传引用

都不是，如下代码

def foo(arg):
    arg = 2
    print(arg)
a = 1
foo(a)  # 输出：2
print(a) # 输出：1

传入的a不会变

但如下

def bar(args):
    args.append(1)
b = []
print(b)#　输出：[]
print(id(b)) # 输出：4324106952
bar(b)
print(b) ＃　输出：[1]
print(id(b))  # 输出：4324106952

传入的b会变

Python中一切皆为对象，数字是对象，列表是对象，函数也是对象，任何东西都是对象。而变量是对象的一个引用。赋值操作 = 就是把一个名字绑定到一个对象上，就像给对象添加一个标签。而Python 函数中，参数的传递本质上是一种赋值操作

在代码段1中，变量a绑定了1，调用函数foo(a)时，相当于给参数arg赋值arg=1，这时两个变量都绑定了1。在函数里面arg重新赋值为 2 之后，相当于把 1 上的arg标签撕掉，贴到 2 身上，而 1 上的另外一个标签a一直存在。因此print(a)还是 1，如下图

对于第二段代码，执行append方法前b和arg都指向（绑定）同一个对象，执行append方法时，并没有重新赋值操作，也就没有新的绑定过程，append方法只是对列表对象插入一个元素，对象还是那个对象，只是对象里面的内容变了。因为b和arg都是绑定在同一个对象上，执行b.append或者arg.append方法本质上都是对同一个对象进行操作，因此b的内容在调用函数后发生了变化（但id没有变，还是原来那个对象）

最后，回到问题本身，究竟是是传值还是传引用呢？说传值或者传引用都不准确。非要安一个确切的叫法的 话，叫传对象（call by object）

参考

Python里list和tuple的区别

list可以修改，tuple不可以修改

---

阿里OceanBase一面 2019.03.15

1. C++DBMS项目介绍

2. 做过的项目里哪个最大

3. 测评系统上算法题

求两个数组int A[n]和int B[m]的交集，例如A={1, 3, 1, 5, 2, 1}, B={2, 1, 1, 4}，交集为{1, 1, 2}

说了哈希表解法，面试官问别的解法，说了一个复杂度更高的排序，再别的没想出来，面试官让把代码写出来

#include <iostream>
#include <vector>
#include <unordered_map>
// 当时忘了using namespace std;

vector<int> solve1(vector<int> A, vector<int> B) {
    vector<int> result;
    unordered_map<int, int> map;
    for (auto num : A) map[num] ++;
    for (auto num : B) {
        if (map.count(num) && map[num] > 0) {
            result.push_back(num);
            map[num] --;
        }
    }
    return result;
}

vector<int> solve2(vector<int> A, vector<int> B) {
    sort(A.begin(), A.end());
    sort(B.begin(), B.emd());
    int ptrA = 0, ptrB = 0;
    vector<int> result;
    while (ptrA < A.size() && ptrB < B.size()) {
        while (A[ptrA] < B[ptrB]) ptrA ++;
        while (B[ptrB] < A[ptrA]) ptrB ++;
        if (A[ptrA] == B[ptrB]) {
            result.push_back(A[ptrA ++]);
            ptrB ++;
        }
    }
    return result;
}

int main() {}

4. 多进程多线程区别

多进程是并发，多线程是并行

5. 进程、线程通信

线程答了共享内存，进程答了信号量/管程/锁/管道等

进程通信方式

• 管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
• 有名管道 (namedpipe) ： 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
• 信号量(semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
• 消息队列( messagequeue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
• 信号 (sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
• 共享内存(shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。
• 套接字(socket ) ： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信

---

腾讯WXG一面 2019.03.16

WXG组面试，意向城市填的是北京，但选了服从调剂，是广州的组来面的，感觉北京微信真是高冷..

一开始就开了一个牛客网页面，有三道题来做

1、倒转单链表（在原链表上倒转）

struct LinkNode {
  int value;
  LinkNode *next;
};
LinkNode *reverseList(LinkNode *head);

普通翻转链表题，之后问只用一个LinkNode指针临时变量，可以完成翻转吗，答不能，因为过程中分前后两半，一个指针无论指前还是指后，都连不起来

LinkNode* reverseList(LinkNode *head) {
    if (head == nullptr || head->next == nullptr) return head;
    LinkNode *prev = head, *now = head->next;
    while (now != nullptr) {
        LinkNode *temp = now->next;
        now->next = prev;
        prev = now;
        now = temp;
    }
    return prev;
}

2、在二叉排序树上面找出第3大的节点。

注意：不能把二叉树全量存储到另外的存储空间，比如存储到数组中，然后取出数组的第三个元素。

struct TreeNode {
    int value;
    struct TreeNode * left, * right;
};
struct TreeNode * find( struct TreeNode * root );

和leetcode这道题一样230. Kth Smallest Element in a BST (Medium)

现场很紧张，第一遍想不对，跳到后面暴力写完第三题，回过头才写了下面这版，其实found可以不要，num每次加1，超出2直接return就好

TreeNode* recursion(int& found, int& num, TreeNode* root) {
    if (root == nullptr) return root;
    TreeNode* result = recursion(found, num, root->right);
    if (found) return result;
    if (num == 2) {
        found = true;
        return root;
    }
    num += 1;
    return recursion(found, num, root->left);
}

TreeNode* find(TreeNode* root) {
    int found = 0, num = 0;
    return recursion(found, num, root);
}

3、给定一个数字串，使用","将数字串拆分为不大于1000的多个的数字，输出所有可能性

例如数字串 1111 可拆分为：

1,1,1,1
1,1,11
1,11,1
1,111
11,1,1
11,11
111,1

当时跳过第二题来写这道题，只暴力地写了递归版本，效率会很低

void recursion(vector<vector<string> >& result, vector<string>& v, string s) {
    if (s.size() == 0) {
        result.push_back(v);
        return;
    }
    v.push_back(s.substr(0, 1));
    recursion(result, v, s.substr(1));
    v.pop_back();
    if (s.size() < 2) return;
    v.push_back(s.substr(0, 2));
    recursion(result, v, s.substr(2));
    v.pop_back();
    if (s.size() < 3) return;
    v.push_back(s.substr(0, 3));
    recursion(result, v, s.substr(3));
    v.pop_back();
    if (s.size() < 4) return;
    if (s.substr(0, 4) == "1000") {
        v.push_back(s.substr(0, 4));
        recursion(result, v, s.substr(4));
        v.pop_back();
    }
}

vector<vector<string> > solve(string s) {
    vector<vector<string> > result;
    vector<string> v;
    recursion(result, v, s);
    return result;
}

改进的话，可以在分割完成后，将后size()-i位字符串的结果记录一下

4. 之后的问题

一些员工按年龄排序

桶排序即可

100个球里有一个比其它球重，称几次可以称出来

5次，33-33-34

100->33->11->3->1
100->33->11->4->2->1
100->34->12->4->2->1

求二叉树深度，可以用O(1)空间复杂度做出来吗

迭代或BFS都可以求深度

O(1)方法没有想到

下来后查资料，可以用Morris来O(1)遍历，同时维持一下高度即可

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    TreeNode *cur = root, *prev = nullptr;
    int mx = 1, depth = 1;
    while (cur != nullptr) {
        if (cur->left == nullptr) {
            cur = cur->right;
            depth ++;
        } else {
            prev = cur->left;
            int temp = 1;
            while (prev->right != nullptr && prev->right != cur) {
                prev = prev->right;
                temp ++;
            }
            if (prev->right == nullptr) {
                prev->right = cur;
                cur = cur->left;
                mx = max(mx, temp + depth ++);
            } else {
                prev->right = NULL;
                depth = depth - 1 - temp;
                mx = max(mx, depth ++);
                cur = cur->right;
            }
        }
    }
    int rightPath = 0;
    for (TreeNode *ptr = root; ptr != nullptr; ptr = ptr->right) rightPath ++;
    return max(mx, rightPath);
}

面完后问面试官多久会有反馈，面试官说他应该会给通过，后面会有同事来面，但后面就没了第二面，然后简历被释放，尴尬...

---

蚂蚁金服一面 2019.03.21

目前为止答得最糟糕的一面

1. 代码从cpp到编译到执行，经过哪些步骤

2. linux动态链接库如何加载

3. 锁的类型

---

腾讯云一面 2019.03.22

WXG莫名没了第二面，腾讯云约了面试

1. 问DBMS项目，数据库事务特性，MergeJoin算法

数据库事务 事务(Transaction)，一般是指要做的或所做的事情。在计算机术语中是指访问并可能更新数据库中各种数据项的一个程序执行单元(unit)

• 原子性 (Atomicity) 事务作为一个整体被执行，包含在其中的对数据库的操作要么全部被执行，要么都不执行
• 一致性 (Consistency) 事务应确保数据库的状态从一个一致状态转变为另一个一致状态。一致状态的含义是数据库中的数据应满足完整性约束
• 隔离性 (Isolation) 多个事务并发执行时，一个事务的执行不应影响其他事务的执行。
• 持久性 (Durability) 一个事务一旦提交，他对数据库的修改应该永久保存在数据库中。

2. 进程线程区别，进程通信方式，虚拟内存介绍

3. Linux中一个程序只启一个进程的方法

回答了用脚本启动和信号量控制访问竞争资源

面试官说可以用文件锁来实现

4. Hadoop原理

5. TCP三次握手，和UDP区别

6. SIGKILL可以捕获吗

不可以，SIGKILL即kill -9的信号。有时候使用kill命令不能杀死进进程，但是使用kill -9 可以。因为默认的时候kill发送的是SIGTERM信号，而kill -9是发送的SIGKILL信号

CTRL+C是SIGINT信号

SIGSTOP(19) 也不能被捕获

7. 100GB字符串，有限内存比如4MB，如何用哈希表去重

hash取余，分割成小文件，然后再逐个去重

8. 写quickSort代码

这里还写错了，惭愧...不过自己手写了一个样例是对的，面试官看了一下也没发现错误，下来后想了想才发现自己写的不对...

9. C++里struct，一个int一个char，sizeof结果是多少

8，因为要4字节对齐

---

腾讯云二面 2019.03.26

1. DOS攻击预防方案

购买带宽，清理数据包

2. C++11智能指针里，share和weak的区别

share会维持对对象的引用计数，析构中会将计数减一，如果计数为0，则销毁对象

weak是指向share的指针，但不增加share的引用计数

3. TCP挥手后，TIME-WAIT状态

TIME_WAIT即TCP四次挥手时，主动关闭的一方，在接收到别动关闭的FIN后，会进入TIME_WAIT状态，等待2*MSL时间，RFC推荐设为2分钟

TIME_WAIT的出现，就是为了解决网络的丢包和网络不稳定所带来的其他问题：

1. 防止前一个连接上延迟的数据包或者丢失重传的数据包，被后面复用的连接错误的接收
2. 确保连接方能在时间范围内，关闭自己的连接。其实，也是因为丢包造成的，主动关闭方关闭了连接，发送了FIN；被动关闭方回复ACK同时也执行关闭动作，发送FIN包；此时，被动关闭的一方进入LAST_ACK状态。主动关闭的一方回去了ACK，主动关闭一方进入TIME_WAIT状态；但是最后的ACK丢失，被动关闭的一方还继续停留在LAST_ACK状态。此时，如果没有TIME_WAIT的存在，或者说，停留在TIME_WAIT上的时间很短，则主动关闭的一方很快就进入了CLOSED状态。 也即是说，如果此时新建一个连接，源随机端口如果被复用，在connect发送SYN包后，由于被动方仍认为这条连接【五元组】还在等待ACK，但是却收到了SYN，则被动方会回复RST。造成主动创建连接的一方，由于收到了RST，则连接无法成功

TIME_WAIT深入介绍

4. read()函数返回值

---

腾讯音视频实验室一面 2019.03.29

这个部门搞视频编码一类的工作，主要就科研问了些问题，看背景是否match，发现不match后很快被拒

---

PayPal笔试 2019.03.30

连续答了三卷

• 第一场是设计卷，逻辑部分答得还可以，但SQL部分完全不会
• 第二场是编程卷，4道题AC两道，一道并查集不知道为什么只过了40%，一道如下，过了60%
• 第三次科学卷，全是machine learning的问题，随便答了些就交卷了

1. K架飞机，测最低俯冲高度H

这个问题即楼层扔鸡蛋的改版，一个是从下往上，一个是从上往下

这个问题常见问法是100层楼，2个鸡蛋，确定鸡蛋会摔碎的最低楼层的最少次数

思路是设最少次数为K，那么第一次在第i层扔，如果碎了，就要遍历1到i-1层楼，故i=k，由此

• 第一次 K层扔
• 第二次 $K+K-2+1=K+K-1$层扔，如果碎了，遍历扔$K-2$层即可
• 第三次 $K+K-1+K-2$层扔

由此，扔K次最多可以测出$1+2+...+K=\frac{(K+1)K}{2}$层

因为$\frac{14\times13}{2}=91$ $\frac{14\times15}{2}=105$

最少需要扔14次鸡蛋

一般性问题

而要问M层楼，N个鸡蛋扔法，则要用动态规划，$dp[i][j]$表示i层楼用j个鸡蛋测，最少需要次数

dp[i][1]=i

dp[0][j]=0

而到dp[i][j]转移方程，则想第一次在哪个楼层扔鸡蛋，设在k层，那么

• 鸡蛋碎了，变成k-1层扔j-1个蛋的最少次数+1
• 鸡蛋没碎，变成i-k层扔j个蛋的最少次数+1

因此dp[i][j]=min(max(dp[i-k][j], dp[k-1][j-1])+1 for k in [1,i-1])

代码如下，注意mn不能大于i

int minNumber(int floors, int eggs) {
    vector<vector<int>> dp(floors+1, vector<int>(eggs+1, 0));
    for (int i = 1; i <= floors; i ++) dp[i][1] = i;
    for (int i = 1; i <= floors; i ++) {
        for (int j = 2; j <= eggs; j ++) {
            int mn = floors;
            for (int k = 1; k < i; k ++) {
                int temp = max(dp[k-1][j-1], dp[i-k][j]) + 1;
                mn = min(mn, temp);
            }
            dp[i][j] = min(mn, i);
        }
    }
    return dp[floors][eggs];
}

2. Python函数没有return语句的返回值

是函数指针

3. SQL里面的Inner Join

是合并两个表里共同项

---

网易互娱笔试 2019.03.31

十道单选题，涉及逻辑、操统、cpp等

三道编程题，第一道是并查集，第二道感觉就是单纯写业务代码，第三题是SQL

前两题过了90%，第三题完全没做...

---

微软笔试 2019.04.03

两小时四道题，AC前两道，第三道90%，第四道直接返回input1拿了30%的分

1. N个人，满足N整除M的N和M之间有线相连，从P开始沿线传递球，求K次内能传回到P手上的方案数

BFS，每次将球传递一次，累加回到P手上的方案数

2. 一个字符串，每次可以消除一个回文串，最少几次消除完

DP，dp[i][j]表示i开始到i+j的最少消除次数

转移方程大概如下，从length-1到length，只有当s[i+length]和s[j]相等时，有可能缩小dp[i][length]

for length in [1, s.size() - 1]:
    for rank in [i, i + length - 1]:
        dp[i][length] = 1 + dp[i][length-1]
        if s[rank] == s[i + length]:
            temp = 0
            if rank > i : temp += dp[i][rank-1-i]
            else if i + length - rank - 2 > 0:
                temp += (dp[rank][i+length-rank-2] - 1)
            temp += 1
            dp[i][length] = min(dp[i][length], temp)

3. 有编号为1-N的N个人排队，中途会有人离开，多次求编号为K人在第几个，返回总和

维护一个链表，每次访问沿链表数一遍，有人离开时更新前后节点的prev和next

只有一个点过不了

4. 二维坐标系内许多个蜂巢坐标，许多个花坐标，蜜蜂从一点出发采蜜，有限步数内(欧几里得距离)回到该点，求能采的最多蜂蜜数(每朵花有1单位的蜂蜜)

没有思路，写了一行返回蜂巢数，居然还过了三个点

---

腾讯笔试 2019.04.05

题型是20道多选和3道编程，多选题里好多拿不准的，编程题做的时候感觉都很简单，不到一小时就全部AC交卷了，下来后想想发现自己一道题想错了，但应该是测例比较亲和，当时也全过了

多选题里有一道，如下代码哪一行会引发错误

#include <iostream>

template<typename T>
class vector {
public:
    void push_back(const T&);
    void clear();
private:
    T* elements;
};

void vector::clear() {}

int main() {
    vector v;
}

当时没答上来，应该是

void vector::clear() {}和vector v;

前者是因为模板类的函数声明和定义必须放在一起，解释如下

C++中每一个对象所占用的空间大小，是在编译的时候就确定的，在模板类没有真正的被使用之前，编译器是无法知道，模板类中使用模板类型的对象的所占用的空间的大小的。只有模板被真正使用的时候，编译器才知道，模板套用的是什么类型，应该分配多少空间。这也就是模板类为什么只是称之为模板，而不是泛型的缘故。

既然是在编译的时候，根据套用的不同类型进行编译，那么，套用不同类型的模板类实际上就是两个不同的类型，也就是说，stack和stack是两个不同的数据类型，他们共同的成员函数也不是同一个函数

后者是因为模板类声明时要声明类型，如改为一下就可以编译通过

#include <iostream>

template<typename T>
class vector {
public:
    void push_back(const T&);
    void clear() {}
private:
    T* elements;
};

int main() {
    vector<int> v;
}

这里要注意的是如果加上using namespace std;，那么vector的声明也会出错，因为会重复

还有一道，如下代码结果

#include <stack>
#include <iostream>
using namespace std;

class A {
public:
    virtual void x() {
        cout << "A\n";
    }
};

class B {
public:
    virtual void x() {
        cout << "B\n";
    }
};

int main() {
    A* T = new B;
    T->x();
}

应该是编译不通过，但当时选了输出B，如果加一个类型转换，可以输出B

A* T = (A*) new B;

编程题三道

1. 有n种硬币，给一个金额m，求能表达出1-m所有数额的最少硬币数

贪心就可以解，思路是这样的，必须要有1，如果没有1，那么输出-1，因为1无法表达，只要有1，那么所有金额都可以表达

然后在有了1这个可表达窗口后，之后要做的就是加上一个金额来移动这个窗口覆盖更大范围，比如现在窗口是[1, limit]，接下来就从limit+1开始递减，看哪个金额有硬币就加上这个金额 i，窗口变成[1, limit+i]

这里可以记录一下硬币的最大值，如果limit超过最大值，可以直接除法来计算还需要的最大值硬币个数

#include <iostream>
#include <unordered_map>
using namespace std;

int m, n;
unordered_map<int, int> dict;

int limit = 1;
int num = 1;

int main() {
    cin >> m >> n;
    int mx = 0;
    for (int i = 0; i < n; i ++) {
        int temp;
        cin >> temp;
        if (temp > m) continue;
        dict[temp] = 1;
        mx = max(temp, mx);
    }
    if (!dict.count(1)) {
        cout << -1 << '\n';
        return 0;
    }
    while (limit < m) {
        if (limit + 1 > mx) {
            num += ((m - limit) / mx + 1);
            break;
        }
        for (int i = limit + 1; i >= 1; i --) {
            if (dict.count(i)) {
                limit += i;
                num ++;
                break;
            }
        }
    }
    cout << num << '\n';
}

2. 一个01串，每次可以消除01或10，求最后串的长度

数一下0和1的个数，最后相减即可

#include <iostream>
#include <string>
using namespace std;

int n;
string s;

int main() {
    cin >> n >> s;
    int n0 = 0, n1 = 0;
    for (auto& c : s) {
        if (c == '0') n0 ++;
        else n1 ++;
    }
    if (n0 >= n1) cout << n0 - n1 << '\n';
    else cout << n1 - n0 << '\n';
    return 0;
}

3. 闯关游戏，有n个怪兽，每个怪兽对应一个金币数和一个武力值，可以买怪兽作为打手，如果自己的打手武力值之和大于遇到的怪兽，可以直接过关，求过关所需的最少硬币数

当时想，遇到一个怪兽判断能不能打过，打不过就买，就可以了，写了后确实AC了

但这个思路是错的，因为可能需要在能打过时依然买怪兽来最小化硬币数

正确思路应该是动归，印象中每个怪兽的coins数都不高，怪兽数量最多50头，可以dp[i]表示i个硬币所能达到最大武力值，同时记录一个经过前i-1个怪兽所需要的最少金币数

然后到第i个怪兽时，先判断一下当前dp数组里存放的武力值有没有大于该怪兽的

1. 没有的话就必须买，然后更新最少需要金币数
2. 从最少金币数开始，尝试更新之后硬币所能达到的最大武力值

最后全局维持的最少金币数即为答案

下面是自己当时写的错误代码

#include <iostream>
using namespace std;

long long fight[60];
double myfight;
int coins, n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> fight[i];
    for (int i = 0; i < n; i ++) {
        int temp;
        cin >> temp;
        if (myfight < fight[i]) {
            coins += temp;
            myfight += fight[i];
        }
    }
    cout << coins << '\n';
}

---

2019.04.11 Paypal面试

二分查找

返回不大于其的最大值

这里被提醒如果写成int m = (l + r) / 2，有可能会溢出，应该写成int m = l + (r - l)/2

int binarySearch(vector<int>& v, int target) {
    int l = 0, r = v.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (v[m] <= target) l = m + 1;
        else r = m - 1;
    }
    return r;
}

Nosql数据结构

平衡二叉树如何平衡

红黑树

hadoop具体过程，包括shuffle等

迭代器好处

---

2019.04.11 腾讯北京onsite面试

378题

233题

---

2019.04.23 微软面试

一面

早上9点的面试，8点多起来，打开Team等面试官，姗姗来迟的面试官到九点十几分才进入视频会议室

1. 自我介绍，就简历问了一些问题

2. python一句话从数组里筛出秩为偶数且值为偶数的数

刚上来有些迷糊，想用filter写但没写出来，想用if写又没写对，面试官提示下写了下面第一行版本；其实本来想写的是下面的filter

[num for num in arr[::2] if num % 2 == 0]
filter(lambda x : x % 2 == 0, [num for num in arr[::2]])

3. 设计模式

答了策略模式、单件模式、工厂模式、适配器模式

4. 不用临时变量，交换两个int。一开始想用位交换来做，但没想出来，面试官说加加减减也可以，想到是用delta来算，如下

void swapValue(int& num1, int num2) {
    num1 = num2 - num1;
    num2 -= num1;
    num1 += num2;
}

写完说这样可能存在溢出的问题，然后面试官问除了溢出还有什么问题，没答上来

5. 一个很多位数的整数，判断调整顺序可否被8整除

二面

1. 介绍一个项目及自己在其中承担的任务，有没有为开源项目贡献过代码

2. 给多个股票数据，以及一个窗口长度，实现两个接口push和get，求这个窗口内的最大值

三面

1. B树和B+树区别

2. 一棵二叉树，用先序和后序能否还原出中序遍历

一开始上来说应该可以，然后画了一棵树看了一下，发现如果一棵树只有左节点或只有右节点，只有先序和后序无法确定是哪个分支，需要是完全二叉树才行

之后面试官问如果有重复元素怎么办，发现有重复元素也是不行的，事实上加上中序遍历，有重复元素也不行

接着问: 那需要什么条件，先序 中序 后序中哪两个可以组合出另一个

答：先序+中序、后序+中序都可以

接着写了先序+中序还原树，然后后序遍历的代码；面试官说可以直接得到后序遍历吗，改为传入vector即可

---

2019.04.25 腾讯复试

C++类的多态如何实现，虚函数机制

答: 多态可以由虚函数实现，即父类定义一个虚函数，子类重载后就可以通过父类指针来调用子类方法

虚函数机制: 每个类维护一个虚函数表，将函数名称映射到函数地址上，子类重载后会覆盖父类的地址

CPU调度的DP解法

没答上来

无序数组找中位数

没回答上来$O(n)$解法，这里很不应该，其实就是找第k大数的问题

一个字符串，统计其中只出现过一次的字符

256*2 bits

---

2019.04.28 Hulu初试

n个数，求k窗口内最大值

vector<int> getKMaxNumbers(const vector<int>& v, const int k) {
    if (v.size() < k) return {};
    deque<int> q;
    vector<int> result;
    int ptr = 0;
    while (ptr < k) {
        while (q.size() > 0 && q.back() < v[ptr]) q.pop_back();
        q.push_back(v[ptr]);
        ptr ++;
    }
    result.push_back(q.front());
    while (ptr < v.size()) {
        if (v[ptr - k] == q.front()) q.pop_front();
        while (q.size() > 0 && q.back() < v[ptr]) q.pop_back();
        q.push_back(v[ptr]);
        result.push_back(q.front());
        ptr ++;
    }
    return result;
}

一个非负整数数组，给两个整数$a\ge b>0$，每次数组中一位减去a，其余减去b，求将整个数组全部减为小于等于0的最少次数

面试官提示下写了二分的代码

bool ifKWorks(const vector<int>& v, int a, int b, long long k) {
    long long n = 0;
    for (auto number : v) n += (number - k * b + a - b - 1) / (a - b);
    return (n <= k);
}
int subABMinimun(const vector<int>& v, int a, int b) {
    if (a == b) {
        int result = 0;
        for (auto n : v) result = max(result, (n + b - 1) / b);
        return result;
    }
    long long l = 1, r = 0;
    for (auto n : v) r += (n + a - 1) / a;
    while (l <= r) {
        long long m = (r - l) / 2 + l;
        bool f = ifKWorks(v, a, b, m);
        if (f) r = m - 1;
        else l = m + 1;
    }
    return l;
}

还剩十分钟，口头问了一道题，BST中交换两个节点，恢复出来

答的是中序遍历，然后看两个节点不满足有序排列，交换即可

#include <iostream>
#include <vector>
using namespace std;

class TreeNode {
public:
    int value;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
    TreeNode(int val) : value(val) {}
};

TreeNode* recursion(const vector<int>& preOrder, int preHead, int preTail, const vector<int>& inOrder, int inHead, int inTail) {
    if (preHead > preTail || inHead > inTail) return nullptr;
    TreeNode* root = new TreeNode(preOrder[preHead]);
    if (preHead == preTail) return root;
    int ptr = 0;
    while (inOrder[inHead + ptr] != preOrder[preHead]) {
        ptr ++;
    }
    root->left = recursion(preOrder, preHead + 1, preHead + ptr, inOrder, inHead, inHead + ptr - 1);
    root->right = recursion(preOrder, preHead + ptr + 1, preTail, inOrder, inHead + ptr, inTail - 1);
    return root;
}
TreeNode* buildTree(const vector<int>& preOrder, const vector<int>& inOrder) {
    int preHead = 0, preTail = preOrder.size() - 1, inHead = 0, inTail = inOrder.size() - 1;
    TreeNode* root = recursion(preOrder, preHead, preTail, inOrder, inHead, inTail);
    return root;
}

void postTraverse(TreeNode* root) {
    if (root == nullptr) return;
    postTraverse(root->left);
    postTraverse(root->right);
    cout << root->value << ' ';
}

int main() {
    vector<int> pre = {1, 2, 3, 4, 5};
    vector<int> in = {2, 1, 4, 3, 5};
    TreeNode* root = buildTree(pre, in);
    postTraverse(root);
}