CUHK CSE 提前批面经2022.5.20

整个面试从收到信息开始看面经，刷算法题，一共差不多9天半的时间。当然，我在学校也有很多课和大作业，于是每天差不多只能花一个小时准备，算法题还是面试前一天恶补的。

我是早上面试的，10点25下课，老师拖堂到了38分，我45分面试，于是赶紧跑到预先想好的地方，打开电脑，连接耳机，点进去会议链接。
差不多到了48分，面试官放我进入了会议室。
这次面试只有两位教授，一位中国人，另一位看起来是印度人。
首先是自我介绍环节，我提前准备了2分钟的稿子，前一天晚上花了一个多小时反复训练，背熟了，然后我面试的时候灵机一动，打开在电脑屏幕上直接对着念的，但是念了一半就被打断进入下一个环节了。所以这种短时间（15min）的面试，还是准备的简短些比较好。
之后是那名印度教授，他问了我概率论的题目，说X是[0,1]上的均匀分布（怕我没听懂还贴心的在聊天框中打出了X~unif(0,1)），让我给出x的pdf(probability density function)表达式。这题非常非常基础，但是因为好久没看概率论的内容了，我当时确实是懵的，就一边讲“X的pdf在[0,1]上的概率累加是1”这种话术来一边拖延时间一边想。然后教授发现我在打太极，就问我“均匀分布的定义是什么？！”然后我就解释说在区间内每一个值的概率都是一样的，然后教授点点头，开始了下一个问题，说的是再给一个变量Y，服从0-1分布，概率都是50%，让我给出一个函数，将X映射到Y，这题我会，直接答了（随机抽X，若X<0.5，Y取0，否则Y取1），教授点点头。最后，他又问，如果有两个独立变量Y1，Y2，都和Y一样的分布，那么怎么写一个函数，能将X映射到（Y1，Y2）呢？由于一开始没有明白意思，我还询问了一下，后来发现也挺简单的，就是用quarter来分割区间，例如x∈[0,0.25)，映射到（0，0），以此类推，教授又点了点头，然后换另一名华人面孔的教授面试。
这名教授提及到我本科作为一个非CS专业学生，他要考察我一些CS基础知识。他首先问我，如果让我作为助教，我对哪门课比较有把握呢？因为我没有学过其他CS基础课，我就说了《数据结构》，他说好，那我问你，“给你一个list，例如，[3,2,2,5,2]，怎样找到出现概率最高的那个值？”我一开始没有想到什么好的解法，于是就说了最直接的解法，遍历数组，用一个变量记录某个数的出现次数，最终输出输出次数最高的那个。然后教授让我分析时间复杂度和空间复杂度。时间复杂度我比较熟悉，遍历一遍就是O(n)。空间复杂度我不是很清楚，于是猜测也是O(n)。教授又问我O的定义是什么？我说是复杂度的上界，教授点点头。后来，他又说，如果数列里有一个超大的数，例如，100万，那么这时的时空复杂度呢？我猜测和这个数值的大小也有关，于是说O(kn)，然后他又问你还有什么好的方法来解决这个问题吗？我想了一下，脑海中只有一个声音：Hash，但是具体的算法我不太确定，于是试探性的问了一句“Is it hashing?”教授好像微微点头，问我为什么会想到Hashing？我说，因为A到B的Hashing， A中两个相同的数Hashing到B中一定是一样的，（所以比较好统计）。然后又问我Hashing搜索时空复杂度是多少，我说O(1)，之后他又问我最糟情况时间复杂度，我说O(n)，因为A中只有一个值的话，映射到B也是1个值，而B中要遍历链表，于是是O(n)。
教授若有所思的点点头，最后问我“你对我们还有什么问题吗？”我想了想，其实也没有什么，于是问了一个提前准备好的问题“那么如果我通过了面试，那么我们是否需要联系教授（套磁）？”这名华人面孔的教授耐心的和我解释说，大部分情况下是需要的。他还说大概一周内会回复给我面试结果。
面试圆满结束，等待结果！

最后，和同学讨论，以及搜索网上资料后，结果如下：
概率论问题(答案不唯一)：
f(x)=1/(b-a)=1, for x in[0,1]; f(x)=0, else.
(X→Y) F=0 if 0<x<0.5, F=1 if 0.5<=x<1
(X→(Y1, Y2)) G=(0,0) if 0<=x<0.25; G=(0,1) if 0.25<=x<0.5; G=(1,0) if 0.5<=x<0.75; G=(1,1)if 0.75<=x<1
数据结构问题：
总感觉之前见到过，后来一搜果然搜到了
遇到过本题的面经：
https://www.1point3acres.com/bbs/thread-856534-1-1.html?mobile=2
https://zhuanlan.zhihu.com/p/142840101
解答：
https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
https://www.cnblogs.com/eniac12/p/5296139.html
https://blog.csdn.net/fuyufjh/article/details/48037127

我没收到面试邮件。想问一下 lz 是什么背景

Hsing 发表于 2022-8-13 03:21
hi请问您面试通过了吗？另外还想问下这个面试是不是只是走个流程，不是很严格，主要还是看后面套瓷的老师 ...

hello才看到哈哈，我没有过面试，这个面试还是筛掉了不少人的，因为不太想去香港完全没准备加上算法什么的基础知识差不多忘完了所以没过，如果想申请的话要好好准备面试呀

lhwwwwwww 发表于 2022-5-23 12:49
借楼分享下俺滴面经：问我的问题是排序算法的…先问了如何找到第二大的元素，我说了快排，然后问了我快排的 ...

我和你是一样的题目，看起来应该是Siu On Chan老师吧，我也答了快排和堆排，和老师说了每种的时间复杂度，whatever面试官人还是很nice的。

同CUHK提前批，面试前完全没准备以为是问research经历，上去完全是懵的哈哈，啥也没答出来。
不过我是两个教授先后提问，第一个问了算法，第二个简短问了下编程知识。

想问问这是PHD还是mater呀？

黄浩 发表于 2022-5-21 08:21
想问问这是PHD还是mater呀？

PhD和Mphil一起面的

微信用户_1b11089 发表于 2022-5-20 20:42
同CUHK提前批，面试前完全没准备以为是问research经历，上去完全是懵的哈哈，啥也没答出来。
不过我是两个 ...

没关系啦，这个就是走个流程，主要还是得有陶瓷到教授的offer
方便的话可以分享下题目给地里其他小伙伴呀XD

我就先套了导师没套到，就没申😂

小亩_otgcmu8 发表于 2022-05-20 23:39:32
没关系啦，这个就是走个流程，主要还是得有陶瓷到教授的offer
方便的话可以分享下题目给地里其他小伙伴呀XD

跟你的题目差不多哈哈也问到了hashing，然后就简单问了下python迭代器生成器区别之类的问题

楼主收到邮件了吗，要去吗？

借楼分享下俺滴面经：问我的问题是排序算法的…先问了如何找到第二大的元素，我说了快排，然后问了我快排的步骤复杂度，以及还有没有其他方法，如果想找前k大的元素怎么办。我说了堆排，但因为有点忘了，先是分不清大顶堆小顶堆，又n次说错时间复杂度😂最后说完堆排就结束面试了…也没有问project和research什么的…

算法题其实你做得并不好
找出现最多的数字
应该用选举法，这样空间复杂度可以降到O(1)