发一道面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

发一道面试题

发一道面试题# JobHunting - 待字闺中

o*s2011-08-10 07:08

1 楼

上周三面试的，三个Candidate当中最后一个面试的。面完以后给所有见过的人发了
thank you邮件，有些回了有些没回，感觉也很正常。当时search committee chair没
有回，但是隔了一个多星期，突然他又回了：
Thank you for your email, and thank you for coming to visit us and interview
! We really enjoyed your seminar and teaching session, and the students
provided excellent feedback regarding these.
I, too, enjoyed meeting you and think you did a great job in the interview.
So you are aware, the search committee has finished its work, and the
hiring decision is now in the hands of the administration.
牛人看看这样的回复，有戏吗？

d*n2011-08-10 07:08

2 楼

应该是道老题了，不过后来跟朋友讨论时有些新情况。前几天面试考的，
【都是单向链表】
1.如何判断两个链表相交。
方法不少，遍历两个链表，看最后一个节点是不是相同。或者将其中一个表首尾相连，
看另一个表是不是有环（指针一个一次走一步，一个一次走两步两步，blablabla）
2. 如何找到相交的那个点？
方法也不少。reverse两个链表，从头开始走，走到某一个点不同时，上一个点就是交
点。或者两个链表依次入栈，一个个往外pop，然后比较，跟reverse类似
还有就是便利两个链表，得到长度m和n，然后得到长度差abs(m-n)，较长的链表先走
abs(m-n)这么多个点，然后两边一起走，第一个相同的就是交点。
问题来了，如果两个链表其中一个是有环的，应该怎么解决？特别是针对第一个问题。
见附图

H*N2011-08-10 07:08

3 楼

有

P*c2011-08-10 07:08

4 楼

可以对有环的那个先找到环的交点，然后分两段考虑？

【在 d********n 的大作中提到】

: 应该是道老题了，不过后来跟朋友讨论时有些新情况。前几天面试考的，
: 【都是单向链表】
: 1.如何判断两个链表相交。
: 方法不少，遍历两个链表，看最后一个节点是不是相同。或者将其中一个表首尾相连，
: 看另一个表是不是有环（指针一个一次走一步，一个一次走两步两步，blablabla）
: 2. 如何找到相交的那个点？
: 方法也不少。reverse两个链表，从头开始走，走到某一个点不同时，上一个点就是交
: 点。或者两个链表依次入栈，一个个往外pop，然后比较，跟reverse类似
: 还有就是便利两个链表，得到长度m和n，然后得到长度差abs(m-n)，较长的链表先走
: abs(m-n)这么多个点，然后两边一起走，第一个相同的就是交点。

l*r2011-08-10 07:08

5 楼

感觉是被推荐了

W*r2011-08-10 07:08

6 楼

我的答案：
if(用快慢指针从A的头出发测A是不是有环 == Yes) {
if (用快慢指针分别从A和B的头出发测是否相遇 == Yes) {
确认相交；
追上的一点肯定在环上，以此可以遍历环，再分别从A和B出发依次比较是不是在环上的话，最后可以确定分别的交点。
}
else {
确认不相交；
}
}
else {
if(用快慢指针从B的头出发测B是不是有环 == Yes) {
确认不相交；
}
else {
遍历两个链表，得到长度m和n，然后得到长度差abs(m-n)，较长的链表先走abs(m-n)这么多个点，然后两边一起走，第一个相同的就是交点。始终不同就没交点。
}
}

E*t2011-08-10 07:08

7 楼

感觉是positive
不过也不要过于乐观
“So you are aware, the search committee has finished its work, and the
hiring decision is now in the hands of the administration.”
这句话的意思是说search committee is not involved in the final decision
making process

interview
.

【在 o*****s 的大作中提到】

: 上周三面试的，三个Candidate当中最后一个面试的。面完以后给所有见过的人发了
: thank you邮件，有些回了有些没回，感觉也很正常。当时search committee chair没
: 有回，但是隔了一个多星期，突然他又回了：
: Thank you for your email, and thank you for coming to visit us and interview
: ! We really enjoyed your seminar and teaching session, and the students
: provided excellent feedback regarding these.
: I, too, enjoyed meeting you and think you did a great job in the interview.
: So you are aware, the search committee has finished its work, and the
: hiring decision is now in the hands of the administration.
: 牛人看看这样的回复，有戏吗？

b*82011-08-10 07:08

8 楼

分别对每个链表判断是否有环，有环则记录环的交点，无环则记录终点。
如俩链表一个环一个非环，则断然不交。
如两个都非环，则看终点相同与否。
如都有环，则从一个环的交点出发走一圈看能否到另一个环的交点（同时出发速递1和2
的快慢指针，追上时正好慢指针走完一圈）。

M*P2011-08-10 07:08

9 楼

这个往往是走形式。

【在 E*********t 的大作中提到】

: 感觉是positive
: 不过也不要过于乐观
: “So you are aware, the search committee has finished its work, and the
: hiring decision is now in the hands of the administration.”
: 这句话的意思是说search committee is not involved in the final decision
: making process
:
: interview
: .