印度火车，牛到不行。 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

印度火车，牛到不行。

印度火车，牛到不行。# Joke - 肚皮舞运动

C*u2012-01-09 08:01

1 楼

之前不知道能不能过，所以没上来发，因为感觉面得很忐忑。昨天刚收到二轮电面的通
知，就上来发一下
顺便最近好像很少看到A家面试的帖子了啊。。。
非CS专业（应用数学），也没有做过多少面试题
开头问我简历上的程序，我讲了一下，他们不是很感兴趣的样子。。没有追问
后来问我都熟悉什么数据结构，我就说，用过的不是很多，比较熟的就是数组链表二叉
树什么的。问我会不会hash table，我说不了解(汗)。
然后就开始问我链表，问了一些和数组的比较，主要是时间复杂度的比较
出了一个题目，两条链表，给出两个初始的节点，判断它们会不会merge。我没想出好的
算法，就说我没有好的算法，只能挨个比较，但是肯定不能这样。
然后面试官提示，说可以用hash table，然后说给我一个现成的hash table，里面各种
函数齐备，让我给这道题写code。
面试基本上到这里就结束了。
我自己面试题做得不多，大程写的不多，投简历纯属碰运气的想法，觉得面得很忐忑，
紧张到不行。能过实在是挺奇葩的。不过我感觉仿佛他们并不介意我对hash table不了
解。好在对于他们问到的链表比较熟悉，再就是时间复杂度比较熟悉。
不过下一轮就很凶险的感觉了。最近在恶补。。。但愿能好运

z*c2012-01-09 08:01

2 楼

l*82012-01-09 08:01

3 楼

关于两个链表merge这题，如果链表里面没有环，可不可以分别找到两个链表的最后一
个节点，然后比较是否相同。如果相同就代表merge了？

好的

【在 C****u 的大作中提到】

: 之前不知道能不能过，所以没上来发，因为感觉面得很忐忑。昨天刚收到二轮电面的通
: 知，就上来发一下
: 顺便最近好像很少看到A家面试的帖子了啊。。。
: 非CS专业（应用数学），也没有做过多少面试题
: 开头问我简历上的程序，我讲了一下，他们不是很感兴趣的样子。。没有追问
: 后来问我都熟悉什么数据结构，我就说，用过的不是很多，比较熟的就是数组链表二叉
: 树什么的。问我会不会hash table，我说不了解(汗)。
: 然后就开始问我链表，问了一些和数组的比较，主要是时间复杂度的比较
: 出了一个题目，两条链表，给出两个初始的节点，判断它们会不会merge。我没想出好的
: 算法，就说我没有好的算法，只能挨个比较，但是肯定不能这样。

d*e2012-01-09 08:01

4 楼

第一那几个人真是蛋定

z*82012-01-09 08:01

5 楼

如果有环呢？
基本只有hash，有环也能解决

【在 l*********8 的大作中提到】

: 关于两个链表merge这题，如果链表里面没有环，可不可以分别找到两个链表的最后一
: 个节点，然后比较是否相同。如果相同就代表merge了？
:
: 好的

r*e2012-01-09 08:01

6 楼

再恶劣的情况也要运行,老百姓受益

【在 z**c 的大作中提到】

l*82012-01-09 08:01

7 楼

如果两个链表都是可能有环的，则先要探测是否有环，以及环开始的地方。
如果两个链表都没有环，比较两个链表的最后一个节点。如果相同，说明merge.
如果一个链表有环,一个没有环，说明两链表没有merge.
如果两个链表都有环，那么比较环开始的地方，如果相同，说明merge.

【在 l*********8 的大作中提到】

: 关于两个链表merge这题，如果链表里面没有环，可不可以分别找到两个链表的最后一
: 个节点，然后比较是否相同。如果相同就代表merge了？
:
: 好的

d*z2012-01-09 08:01

8 楼

习惯了。

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

: 第一那几个人真是蛋定

l*82012-01-09 08:01

9 楼

我错了，如果两个链表都有环，那么比较环开始的地方是不够的。
两个链表都有环的话，可以从链表A的环开始的节点绕环一圈，看是否能找到链表B的
环开始的节点。

【在 l*********8 的大作中提到】

: 如果两个链表都是可能有环的，则先要探测是否有环，以及环开始的地方。
: 如果两个链表都没有环，比较两个链表的最后一个节点。如果相同，说明merge.
: 如果一个链表有环,一个没有环，说明两链表没有merge.
: 如果两个链表都有环，那么比较环开始的地方，如果相同，说明merge.

c*e2012-01-09 08:01

10 楼

第二，水陆两用

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

: 第一那几个人真是蛋定

w*o2012-01-09 08:01

11 楼

谁能讲讲如何用hashtable来判断是否两个链表merge?
谢谢！

好的

【在 C****u 的大作中提到】

i*a2012-01-09 08:01

12 楼

第2个是閱兵?

【在 z**c 的大作中提到】

b*t2012-01-09 08:01

13 楼

假设第一个链表长度n
第二个长度m
把第一个链表的指针都放到一个hashtable里
hashtable insert O(1) 总共O(n)
然后遍历第二个链表遍历的时候check 第二个链表的指针在不在hashtable里
check O(1) 总共O(m)
总共O(m+n)

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

: 谁能讲讲如何用hashtable来判断是否两个链表merge?
: 谢谢！
:
: 好的

d*z2012-01-09 08:01

14 楼

过两天，印度航母陆上飞驰的视频可能就要出来了。

C*u2012-01-09 08:01

15 楼

不好意思漏了一些
假设里面是没有环的
关键是我漏了题目要求，要找到merge的节点
所以比较最后一个节点不可行

【在 l*********8 的大作中提到】

m*r2012-01-09 08:01

16 楼

真有气势。。。

p*22012-01-09 08:01

17 楼

这题不就用个hashset就行了吗？不是什么难题。

w*a2012-01-09 08:01

18 楼

第一张那么大的水飞到旁边电线上，会不会大断电？

l*82012-01-09 08:01

19 楼

如果O(1)space 呢？

【在 p*****2 的大作中提到】

: 这题不就用个hashset就行了吗？不是什么难题。

c*w2012-01-09 08:01

20 楼

想起来千寻那个水里跑的火车，
这就是理想与现实的差距。

【在 z**c 的大作中提到】

l*82012-01-09 08:01

21 楼

如果O(1)space 呢？

【在 p*****2 的大作中提到】

: 这题不就用个hashset就行了吗？不是什么难题。

z*c2012-01-09 08:01

22 楼

觉得这大浪比钱塘潮还威猛。其实是想让同学们数一下火车过后人还剩几个：）

p*22012-01-09 08:01

23 楼

关键是没要求O(1)呀。

【在 l*********8 的大作中提到】

: 如果O(1)space 呢？

P*t2012-01-09 08:01

24 楼

第一张不像印度，墙上的涂鸦很欧美。

【在 z**c 的大作中提到】

: 觉得这大浪比钱塘潮还威猛。其实是想让同学们数一下火车过后人还剩几个：）

p*22012-01-09 08:01

25 楼

就是考察一下链表和hashtable的基本知识。楼主赶紧熟悉hashtable，不然onsite
pass的可能性很低。hashtable是面试必备的数据结构。用的最多，必须要熟练掌握。

st2012-01-09 08:01

26 楼

来不及跑了，整个就是激流勇进

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

: 第一那几个人真是蛋定

w*o2012-01-09 08:01

27 楼

北京二爷，
hashset和hashtable是什么关系？
到哪里学习有关hashtable的东西？有什么好的书的章节，或者是什么link?
xiexie!

【在 p*****2 的大作中提到】

: 这题不就用个hashset就行了吗？不是什么难题。

f*e2012-01-09 08:01

28 楼

应该不是印度
1. 桥上的车是靠右走的
2. 桥上的车至少有一辆full size SUV,一辆pickup，一辆fullsize van。
特别是fullsize van，估计只有美国才有。

【在 z**c 的大作中提到】

: 觉得这大浪比钱塘潮还威猛。其实是想让同学们数一下火车过后人还剩几个：）

p*22012-01-09 08:01

29 楼

hashset只有key没有value。
看你用什么语言吧。每个语言都有相应的数据结构，知道怎么用来编程，解决问题就行
了。hashtable深入的东西，我也没学过。一般面试会用就行了吧。

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

: 北京二爷，
: hashset和hashtable是什么关系？
: 到哪里学习有关hashtable的东西？有什么好的书的章节，或者是什么link?
: xiexie!

s*d2012-01-09 08:01

30 楼

视频是阿根廷铁路，Línea San Martín线

s*r2012-01-09 08:01

31 楼

http://www.geeksforgeeks.org/archives/2405
Quoted:
"
Method 1(Simply use two loops): Time Complexity: O(mn)
Use 2 nested for loops. Outer loop will be for each node of the 1st list and
inner loop will be for 2nd list. In the inner loop, check if any of nodes of
2nd list is same as the current node of first linked list. Time complexity of
this method will be O(mn) where m and n are the number of nodes in two lists.
Method 2 (Mark Visited Nodes): Time Complexity: O(m+n)
This solution requires modifications to basic linked list data structure. Have
a visited flag with each node. Traverse the first linked list and keep marking
visited nodes. Now traverse second linked list, If you see a visited node again
then there is an intersection point, return the intersecting node. This
solution works in O(m+n) but requires additional information with each node. A
variation of this solution that doesn’t require modification to basic data
structure can be implemented using hash. Traverse the first linked list and
store the addresses of visited nodes in a hash. Now traverse the second linked
list and if you see an address that already exists in hash then return the
intersecting node.
Method 3(Using difference of node counts): Time Complexity: O(m+n)
1) Get count of the nodes in first list, let count be c1.
2) Get count of the nodes in second list, let count be c2.
3) Get the difference of counts d = abs(c1 – c2)
4) Now traverse the bigger list from the first node till d nodes so that from
here onwards both the lists have equal no of nodes.
5) Then we can traverse both the lists in parallel till we come across a common
node. (Note that getting a common node is done by comparing the address of the
nodes)
Method 4(Make circle in first list): Time Complexity: O(m+n)
Thanks to Saravanan Man for providing below solution.
1. Traverse the first linked list(count the elements) and make a circular
linked list. (Remember last node so that we can break the circle later on).
2. Now view the problem as find the loop in the second linked list. So the
problem is solved.
3. Since we already know the length of the loop(size of first linked list) we
can traverse those many number of nodes in second list, and then start another
pointer from the beginning of second list. we have to traverse until they are
equal, and that is the required intersection point.
4. remove the circle from the linked list.
"
http://www.velocityreviews.com/forums/t587346-where-do-two-link
merge.html

l*u2012-01-09 08:01

32 楼

haha

l*a2012-01-09 08:01

33 楼

好的
bless

【在 C****u 的大作中提到】

D*a2012-01-09 08:01

34 楼

第二个火车走第一个线路才壮观

C*u2012-01-09 08:01

35 楼

嗯，谢谢^^

【在 p*****2 的大作中提到】

: 就是考察一下链表和hashtable的基本知识。楼主赶紧熟悉hashtable，不然onsite
: pass的可能性很低。hashtable是面试必备的数据结构。用的最多，必须要熟练掌握。

R*n2012-01-09 08:01

36 楼

在剑三里恶补么

a*o2012-01-09 08:01

37 楼

链表的merge是啥意思啊

好的

【在 C****u 的大作中提到】

l*a2012-01-09 08:01

38 楼

我的理解是
hashset其实是hash_set 是STL里定义的template
hashtable就是一种数据结构。。。
当然似乎JAVA/C#都有这个类吧？

【在 p*****2 的大作中提到】

:
: hashset只有key没有value。
: 看你用什么语言吧。每个语言都有相应的数据结构，知道怎么用来编程，解决问题就行
: 了。hashtable深入的东西，我也没学过。一般面试会用就行了吧。

p*22012-01-09 08:01

39 楼

STL我不懂a呀

【在 l*****a 的大作中提到】

: 我的理解是
: hashset其实是hash_set 是STL里定义的template
: hashtable就是一种数据结构。。。
: 当然似乎JAVA/C#都有这个类吧？

a*m2012-01-09 08:01

40 楼

双链表找到最后一个然后往前找就可以了，单链表还是hash好。

【在 C****u 的大作中提到】

: 不好意思漏了一些
: 假设里面是没有环的
: 关键是我漏了题目要求，要找到merge的节点
: 所以比较最后一个节点不可行

l*82012-01-09 08:01

41 楼

双链表找到最后一个然后往前找，只能回到其中一个head吧

【在 a********m 的大作中提到】

: 双链表找到最后一个然后往前找就可以了，单链表还是hash好。

f*22012-01-09 08:01

42 楼

多谢lz分享。感觉存一个链表的节点进hash，然后遍历第二个节点找是否有相同的，就
不错

a*m2012-01-09 08:01

43 楼

?
两个链表对照着往前找，第一个不同的节点的后一个就是吧。

【在 l*********8 的大作中提到】

: 双链表找到最后一个然后往前找，只能回到其中一个head吧

l*82012-01-09 08:01

44 楼

你是说双链表？从尾向头倒着走吗？
两个链表merge的那个node的prev指针也只能指向一个节点，没法指向两个。

【在 a********m 的大作中提到】

: ?
: 两个链表对照着往前找，第一个不同的节点的后一个就是吧。

a*m2012-01-09 08:01

45 楼

啊。对。双链表不会有这种情况。看来只有hash一条路了。

【在 l*********8 的大作中提到】

: 你是说双链表？从尾向头倒着走吗？
: 两个链表merge的那个node的prev指针也只能指向一个节点，没法指向两个。

y*n2012-01-09 08:01

46 楼

我的解法如下：
两个链表A，B
1. 先算各自的长度LenA, 与LenB
2. 两个节点指针pA和pB分别指向A和B的头
3. 如果LenA>LenB，则pA向前走（LenA-LenB步）
4. 如果LenB>LenA，则pB向前走（LenB-LenA步）
5. 如果（pA==pB)则找到merge节点，返回
6. 否则，pA和pB各自向前走一步，重复步骤5
算法优点：空间O(1)，时间O(lenA+lenB)，实现简单

y*n2012-01-09 08:01

47 楼

思路实现，没有编译运行：
Node* FindMergeNode(Node* pHeadA, Node* pHeadB)
{
Node* pTempA = pHeadA;
Node* pTempB = pHeadB;
int lenA = GetLength(pHeadA);
int lenB = GetLength(pHeadB);
for(int a=0; a < lenA-lenB; a++)
pTempA = pTempA -> pNext;
for(int b=0; b < lenB-lenA; b++)
pTempB = pTempB -> pNext;
while ((pTempB != null)&&(pTempA != pTempB))
{
if (pTempA == pTempB)
return pTempA;
pTempA = pTempA -> pNext;
pTempB = pTempB -> pNext;
}
return null;
}

p*22012-01-09 08:01

48 楼

没明白
A->B
C->B->D->E->F->H
你先向前走了4步，不就跳过B了吗？

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

: 我的解法如下：
: 两个链表A，B
: 1. 先算各自的长度LenA, 与LenB
: 2. 两个节点指针pA和pB分别指向A和B的头
: 3. 如果LenA>LenB，则pA向前走（LenA-LenB步）
: 4. 如果LenB>LenA，则pB向前走（LenB-LenA步）
: 5. 如果（pA==pB)则找到merge节点，返回
: 6. 否则，pA和pB各自向前走一步，重复步骤5
: 算法优点：空间O(1)，时间O(lenA+lenB)，实现简单

y*n2012-01-09 08:01

49 楼

如果两个链表有merge，那么他们在尾部的N（N>=1）个元素必然相同。
你的例子不对，因为B.Next不一致:
A->B (B.Next == Null)
C->B->D->E->F->H (B.Next == D)
重新举例
A->B->C->D->X->Y->Z (len=7)
K->X->Y->Z (len=4)
p1先走4步，从D开始
p1!=p2，继续p1和p2各走一步。
p1=X；p2=X：此时p1==p2，找到Merge点X。

【在 p*****2 的大作中提到】

:
: 没明白
: A->B
: C->B->D->E->F->H
: 你先向前走了4步，不就跳过B了吗？