小弟现在在当替代役预计2月初退伍, 所以最近开始面试工作, 面试过了几家公司觉得
群晖的面试经验满不错的, 趁还没忘记上来分享给大家.
先讲结论:第四关被打枪
背景
小弟113学+114硕博, 研究领域是Text indexing/Compressive sensing/Scheduling
面试第一关
1. 用白板实做出linked list的reverse
过程: [很普通的reverse]
2. 如果今天是要2个node作反转该怎么做? ex: 3->4->5->6->7 变成 4->3->6->5->7
解法: recursion, 先把node#1跟node#2交换, 再让node#1->next指向下一个
recursion call的回传值
e.g. 3->next = recursion(4->next)
3. 如果今天要推广到k个node作反转该怎么做?
解法: 一开始我说就多加一个counter来计算目前反转了几个node, 然后把这个
counter当作call recursion的条件 e.g. if (counter == k) recur()
不过面试官有说这样会有问题, 因为当linked-list长度不是k的倍数
的时候不应该把不满k的作反转
e.g. (k=3) 1-2-3-4-5 => 3-2-1-4-5 不该是 3-2-1-5-4
我就改成先做traverse, 等确定够的话再转
面试第二关
1. 给一个N*M的Matrix, 特性是每个row从左到右是排序过的, 每个column从
上到下也是排序过的
e.g.
─────→
│┌─┬─┬─┐
││1 │2 │3 │
│├─┼─┼─┤
││4 │5 │6 │
│├─┼─┼─┤
││7 │8 │9 │
↓└─┴─┴─┘
要怎么作search?
解法: 一开始想不到什么好方法就先提出N个binary search的方法, 时间是
O(NlogM), 面试官就请我实作出binary search. 实做完再想了一阵子,
有想出O(N+M)的解法, 方法就是每次都比右上角的那个数字,
根据比的结果可以删掉一个row或是column
e.g. key=5
┌─┬─┬─┐
│1 │2 │3<5
├─┼─┼─┤ ┌─┬─┬─┐
│4 │5 │6 │ => │4 │5 │6 │
├─┼─┼─┤ ├─┼─┼─┤
│7 │8 │9 │ │7 │8 │9 │
└─┴─┴─┘ └─┴─┴─┘
e.g. key=2
┌─┬─┬─┐ ┌─┬─┐
│1 │2 │3>2 │1 │2 │
├─┼─┼─┤ ├─┼─┤
│4 │5 │6 │ => │4 │5 │
├─┼─┼─┤ ├─┼─┤
│7 │8 │9 │ │7 │8 │
└─┴─┴─┘ └─┴─┘
2. process/thread的比较, TCP/UDP的差别, multi-thread programming
过程: 这部分我没讲好, 想到什么就说什么, 不过网络部分我很多都答不出来,
像是为什么youtube可以传资料传那么顺之类的
面试第三关
1. 给一个字串, 将单字顺序反转
解法: 一开始没想到好做法, 就用loop从头开始扫, 然后复制到尾巴那边,
不过这边写白板一直鬼打墙在处理boundary的问题, 后来直接重新弄一个
方法先把整个字串反转再分别把个别的单字转回来
2. 给一串数字, 如何判断有没有某个数字的出现频率超过50%
过程: 一开始我说如果空间不限那就开一个很大很大的vector, 不过面试官说
当然不行XD 后来我就说最简单的方法就是排序后再从头找, 也可以用hash
不过worst case就无法保证linear time. 接下来面试官又问, 那如果
排序好的话呢? 我就说那就直接看中间那个数字.
最后的问题是如果已经确定有一个数字超过50%, 不过未排序, 有没有
办法找出来? 我一开始说用linear time select找中位数, 时间是
O(n), 不过面试官好像不满意, 他给的提示是如果有某个数字a过半,
那如果我们把a跟其他另外的数字一对一的配对, 那最后一定会剩下a,
我的解法就是从这串数字的头开始跑, 碰到两个不一样的就删掉,
碰到一样的就继续往下比
e.g. 1 2 2 1 1 => 1 2 2 1 1 (红色表示已经删掉)
=> 1 2 2 1 1
e.g. 2 2 1 1 1 => 2 2 1 1 1
=> 2 2 1 1 1
大概是这样, 实作时有用到stack
第四关就看到HR进来XD
HR满可爱的, 一脸抱歉的样子XD
这次总面试时间4.5hr, 中间其实等待时间满久的, 不过面试的感觉不错,
很可惜没拿到offer, 不然感觉在这个公司工作coding应该会进步神速