虽然已经给CUHK交了留位费但既然HKU给我发了邀请那就参加一下

笔试

时间是1h，zoom监考。

Q1 (30 marks)

题面

In discrete mathematics, Ramsey’s theorem states that for any positive integer k, there is an integer m such that in any party with at least m guests, one of the following statements must be true:
(1) There are at least k guests who know each other.
(2) There are at least k guests who do not know each other.
For example, for k = 3, then in any party of at least 6 guests, either there are three guests who know each other, or there are three guests who do not know each other. This question asks you to write a program (using either Python, C, C++ or Java) to help verify Ramsey’s theorem. The input of the program is organized as follows:

The first line of the input has an integer m, followed by m lines of string, each representing a guest (so there are totally m guests for this input).
Then, there is another line of integer n, followed by n lines of pair of guests (guest a and guest b know each other if and only if there is a line of pair a, b in the input).
Then, there is a line containing an integer k.
For the output, your program should print a set of k guests who knows each other, and if there is no such set, the program should print a set of k guests who do not know each other.
Following is a sample run of the program.

4
a
b
c
d
3
a b
a c
b c
3
0
1
2
0
1
The guests in ['a', 'b', 'c'] know each other

The input specifies that there are four guests a, b, c, d in the party, and a knows b, a knows c, and b knows c. Thus, the set of guests {a, b, c} know each others.
Here is another sample run:

4
a
b
c
d
2
a b
a c
3
The guests in ['b', 'c', 'd'] do not know each other

Note: You will get 15 marks if your program can only solve the case when k = 3.

分析

有m个人，给定他们中指定两个人是否认识，证明一个定理：至少其中k个人互相都认识或互相都不认识。
用邻接矩阵还保存这个无向图，其中两个人认识是无向的，也就是说如果a认识b那么b也认识a。

int graph[maxm][maxm];

其中maxm是m范围的最大值，由于C++不允许设置变量数组长度，而且题中还没给数据范围，所以随便写个500或者1000就行。
由于给出的是客人的名字，所以还要把字符串哈希成数字方便存储。使用STL中的map即可：

string a[maxm];
map<string, int> b;

其中a[i]就是第i个人的名字，b[i]就是叫i的人的编号。
然后深度优先搜索全图：

int ans[maxm];
bool dfs(int pos);

pos记录当前搜到了第几位，ans保存已经搜索过也就是已经互相认识的群体。
每次取一个新值，判断这个人是否与ans中所有人认识，若全认识则将其加入ans中，继续搜pos+1位，有不认识的则舍弃。直到pos共走过k个人，即ans中有k个值时停止搜索，返回答案。
搜索互相不认识的群体只需要把图中认识的改成不认识的，不认识的改成认识的重新搜一下就可以了。

代码

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

const int maxm = 500; // a number >= m
int m, n, k; // same defination in Q1
int graph[maxm][maxm]; // 1 means know each other, 0 means don't
string a[maxm]; // the names of the guests, from number to name
map<string, int> b; // the number of the guests, map from name to number
int ans[maxm]; // answer, the group of people know each other

// depth first search
// pos: current searching position
// return: search succeeded or not
bool dfs(int pos) {
    // finish searching when reaching k people
    if (pos >= k - 1)
        return true;
    // nxt: next person's number
    for (int nxt = ans[pos] + 1; nxt < m; nxt++) {
        bool success = true;
        // lst: the numbers of people who already in answer group
        for (int lst = 0; lst <= pos; lst++) {
            // if the next person don't know one of the person in answer group, stop considering adding he/her into the group
            if (!graph[ans[lst]][nxt]) {
                success = false;
                break;
            }
        }
        // if this person knows all people in the group, add he/her into it and continue searching the next one
        if (success) {
            ans[pos+1] = nxt;
            if (dfs(pos + 1))
                return true;
        }
    }
    return false;
}

int main(int argc, const char * argv[])
{
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i]; // input their names
        b[a[i]] = i; // save their numbers
    }
    cin >> n;
    for (int i = 0; i < n; i++) {
        string u, v;
        cin >> u >> v; // input relationship with u and v
        graph[b[u]][b[v]] = graph[b[v]][b[u]] = 1; // build the graph
    }
    cin >> k;
    // begin searching with i
    for (int i = 0; i < m; i++) {
        ans[0] = i;
        if (dfs(0)) {
            cout << "The guests in [";
            for (int j = 0; j < k - 1; j++)
                cout << a[ans[j]] << ',';
            cout << a[ans[k-1]] << "] know each other" << endl;
        }
    }
    // reverse the graph, to search the people who don't know each other
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            graph[i][j] = 1 - graph[i][j];
    // same as above
    for (int i = 0; i < m; i++) {
        ans[0] = i;
        if (dfs(0)) {
            cout << "The guests in [";
            for (int j = 0; j < k - 1; j++)
                cout << a[ans[j]] << ',';
            cout << a[ans[k-1]] << "] do not know each other" << endl;
        }
    }
    return 0;
}

Q2 (10 marks)

题面

You has 10 pockets and 44 coins of one dollar. You want to put your dollars into your pockets so distributed that each pocket contains a different number of dollars.
(i) Can you do so? If yes, how? If no, justify your answer.
(ii) Generalize the problem, considering p pockets and n dollars. Or more precisely, specify the relationship between p and n so that you can put n dollars into p pockets such that each pocket contains a different number of dollars.

解决

(i) 第1个口袋放0块，第2个放1块……第10个口袋放9块，最少要45个币，给44块自然做不到
(ii) 高斯公式n>=p(p-1)/2

Q3 (10 marks)

题面

Find the following indefinite integrals.
1.

\int_{}{}\frac{2x+1}{\sqrt{x^2+x+7}}dx

\int_{}{}\frac{7}{(x-3)(2x+1)}dx

Note: Remember that $\int_{}{}\frac{1}{x}dx=\ln{}{x}$

解决

换元
令 $u=x^2+x+7$
所以 $du=(2x+1)dx$
原式 $\int_{}{}\frac{2x+1}{\sqrt{x^2+x+7}}dx$
$=\int_{}{}\frac{1}{\sqrt{u}}du$
$=2\sqrt{u}+C$
$=2\sqrt{x^2+x+7}+C$
因式分解
原式 $\int_{}{}\frac{7}{(x-3)(2x+1)}dx$
$=\int_{}{}(\frac{1}{x-3}-\frac{2}{2x+1})dx$
$=\ln{|x-3|}-\ln{|2x+1|}+C$

Q4 (10 marks)

题面

On a flight of HKA airline, 5% of the passengers take the first-class seats. Among those passengers, 30% of them are Hong Kong citizens. It is known that 60% of the first-class passengers who are Hong Kong citizens have become members of HKA airline, and the airline only accept Hong Kong citizens as their members. If a passenger is randomly chosen from the passenger list of the flight, find the probability that the passenger takes a first-class seat but is not a member of HKA airline.

解决

算概率5%-5%*30%*60%=4.1%

面试

zoom，半小时，6人群面。

提问环节

针对每个人的简历问了下实习/项目相关的事情。问其他人的有的很专业我也听不太懂，问我的问题大概如下
Q：在阿里实习那里写的AI customer service of DingTalk是啥？
A：那是个钉钉聊天机器人（😅果然不能在CV里乱吹水），用来查帐单信息的。
Q：修复的bug是什么？
A：当时系统在升级，旧数据库和新数据库定义不一样，机器人还在查询那个旧的就有可能出问题，我做的是让它适应新的。

聊天环节

covid-19对学习生活的影响？
一个老哥讲了半天，没插上话。

反问环节

有人问
Q：genenal stream和各个stream的区别？
A：大概就是3个固定类别的要求在类别里选够学分，general的随便选。
最后教授（choli@hku.hk）说大概2周后出结果。

感谢HKU CS🚬群友们与评论区的指正。
更新：

有反映说PC端看封面图片太大了，所以换了张横版图。其它文章我有空也找找合适的图片给换上来。
拿到港大的推研啦，但还是打算拒掉去港中文。
相关阅读：罐总的【知乎】因子分解机：🇭🇰 香港计算机硕士留学申请攻略

港大2022Fall CS笔面经

笔试