q****x
发帖数: 7404 | 1 即使想清楚算法，指针也很容易搞乱。
是个很好的练习。 |
K*****k
发帖数: 430 | 2 有两种串法，经典的是双倍长单珠串型，还看到过一种梯子型（平行双珠串，上下珠珠相连）。
面试的时候经典的那个好写。 |
q****x
发帖数: 7404 | 3 就是写单串那个。看上去没问题了，一测试就发现有错。
珠相连）。
【在 K*****k 的大作中提到】
: 有两种串法，经典的是双倍长单珠串型，还看到过一种梯子型（平行双珠串，上下珠珠相连）。
: 面试的时候经典的那个好写。
|
A**u
发帖数: 2458 | 4 什么是 copy random link.
完全看不懂啊
珠相连）。
【在 K*****k 的大作中提到】
: 有两种串法，经典的是双倍长单珠串型，还看到过一种梯子型（平行双珠串，上下珠珠相连）。
: 面试的时候经典的那个好写。
|
t*********7
发帖数: 255 | |
K*****k
发帖数: 430 | 6 可以上网考古，好像是小尾羊Google加试的那轮就被问到。
就是说一个普通链表，每个节点还有一个random link指向别的节点或者自己。
让你In place（除了每个节点new出的copy)的复制这个链表，包括random link的拓扑
结构，也就是一个完全一样的镜像。
【在 A**u 的大作中提到】
: 什么是 copy random link.
: 完全看不懂啊
:
: 珠相连）。
|
q****x
发帖数: 7404 | 7 如果之前没见过，当场能写对，还是很牛的。
【在 K*****k 的大作中提到】
: 可以上网考古，好像是小尾羊Google加试的那轮就被问到。
: 就是说一个普通链表，每个节点还有一个random link指向别的节点或者自己。
: 让你In place（除了每个节点new出的copy)的复制这个链表，包括random link的拓扑
: 结构，也就是一个完全一样的镜像。
|
K*****k
发帖数: 430 | 8 确实如此，所以我等小辈除了练习，以不变应万变对付一些简单题，保证简单题少bug,
少丢分外，就只能多背一些BT题以防问到。
【在 q****x 的大作中提到】
: 如果之前没见过，当场能写对，还是很牛的。
|
q****x
发帖数: 7404 | 9 这个单串做法必须扫描两遍？第一遍复制随机，第二遍劈链？
我试图边复制边劈开，似乎不行。
其实扫两遍和扫一遍复杂度一样，因为扫一遍时循环步长加倍了。
bug,
【在 K*****k 的大作中提到】
: 确实如此，所以我等小辈除了练习，以不变应万变对付一些简单题，保证简单题少bug,
: 少丢分外，就只能多背一些BT题以防问到。
|
A**u
发帖数: 2458 | 10 你是cs科班的吧
bug,
【在 K*****k 的大作中提到】
: 确实如此，所以我等小辈除了练习，以不变应万变对付一些简单题，保证简单题少bug,
: 少丢分外，就只能多背一些BT题以防问到。
|
|
|
A**u
发帖数: 2458 | 11 你是先 扫一遍，用next创建链表，
再扫第二遍，创建link?
【在 q****x 的大作中提到】
: 这个单串做法必须扫描两遍？第一遍复制随机，第二遍劈链？
: 我试图边复制边劈开，似乎不行。
: 其实扫两遍和扫一遍复杂度一样，因为扫一遍时循环步长加倍了。
:
: bug,
|
f*******t
发帖数: 7549 | 12 应该是扫描3遍吧
1.在每个节点后面插入一个复制的结点
2.修改所有复制结点的random指针
3.拆分出新的链表 |
K*****k
发帖数: 430 | 13 从本科开始就是的。但是白板编程还是不熟练
【在 A**u 的大作中提到】
: 你是cs科班的吧
:
: bug,
|
q****x
发帖数: 7404 | 14 我说扫大链表两遍。
【在 f*******t 的大作中提到】
: 应该是扫描3遍吧
: 1.在每个节点后面插入一个复制的结点
: 2.修改所有复制结点的random指针
: 3.拆分出新的链表
|
A**u
发帖数: 2458 | 15 我都晕了
next一遍
random一遍
还不够吗?
【在 q****x 的大作中提到】
: 我说扫大链表两遍。
|
q****x
发帖数: 7404 | 16 科班和写代码熟没必然联系。就像中文系的未必个个都是快写手。
【在 K*****k 的大作中提到】
: 从本科开始就是的。但是白板编程还是不熟练
|
d*******d
发帖数: 2050 | 17 好吧，我写个copy random graph的通解，对一切graph，tree，list什么的都有效。
区别是O(n)space 复杂度。可以拿来救场。
标准list copy应该是O(n) time, O(1) space.
假设hash class, equal class已经定义好了。
Node * copy(Node * root, unordered_map & rec){
if(root == 0)
return 0;
unordered_map::iterator it = rec.find(root);
if( it != rec.end()){
return it->second;
}else{
Node * newnode = new Node(root);// a new node, copy data
rec.insert(make_pair( root, newnode));
// then copy each child
newnode->child1 = copy(root->child1, rec);
newnode->child2 = copy(root->child2, rec);
......
// after all copied
return newnode;
}
}
【在 q****x 的大作中提到】
: 即使想清楚算法，指针也很容易搞乱。
: 是个很好的练习。
|
K*****k
发帖数: 430 | 18 面试时间总共就45分钟，如果细节纠结不好，就会超时
当时小尾羊的策略就是：坦诚告诉面试官这题他见过，知道串珠的解法，然后写了个你
这样的容易实现的hash方法
最后他拿到了G的offer.
【在 d*******d 的大作中提到】
: 好吧，我写个copy random graph的通解，对一切graph，tree，list什么的都有效。
: 区别是O(n)space 复杂度。可以拿来救场。
: 标准list copy应该是O(n) time, O(1) space.
: 假设hash class, equal class已经定义好了。
: Node * copy(Node * root, unordered_map & rec){
: if(root == 0)
: return 0;
: unordered_map::iterator it = rec.find(root);
: if( it != rec.end()){
: return it->second;
|
A**u
发帖数: 2458 | 19 hash了，还算in place吗
【在 K*****k 的大作中提到】
: 面试时间总共就45分钟，如果细节纠结不好，就会超时
: 当时小尾羊的策略就是：坦诚告诉面试官这题他见过，知道串珠的解法，然后写了个你
: 这样的容易实现的hash方法
: 最后他拿到了G的offer.
|
K*****k
发帖数: 430 | 20 不算了...
但是这个策略还有一个mitbbs59的案例：
中午1个小时的lunch interview, 虽然和对方在一个环境十分优雅的餐厅吃饭. 可是真
正让我吃饭的时间恐怕连10分钟都不到. 她先问了我一个不太难也不太简单的问题,
其实我知道答案, 可是这个问题如果coding, 会比较繁琐, 很容易出错. 我也就老实的
告诉她, 我已经看过这个问题了, 然后把方案说了一遍, 令我意外的是, 她主动换了另
外一个问题. 题目简单许多, coding也简单许多, 我顺利的coding完. 然后就和她聊
了聊旅游, 生活, 我也潦草的塞了几片菜叶到肚子里, 结束了愉快的午餐.
最后他拿到了M的offer
【在 A**u 的大作中提到】
: hash了，还算in place吗
|
|
|
q****x
发帖数: 7404 | 21 嗯，见多识广也是水平的一部分。
【在 K*****k 的大作中提到】
: 不算了...
: 但是这个策略还有一个mitbbs59的案例：
: 中午1个小时的lunch interview, 虽然和对方在一个环境十分优雅的餐厅吃饭. 可是真
: 正让我吃饭的时间恐怕连10分钟都不到. 她先问了我一个不太难也不太简单的问题,
: 其实我知道答案, 可是这个问题如果coding, 会比较繁琐, 很容易出错. 我也就老实的
: 告诉她, 我已经看过这个问题了, 然后把方案说了一遍, 令我意外的是, 她主动换了另
: 外一个问题. 题目简单许多, coding也简单许多, 我顺利的coding完. 然后就和她聊
: 了聊旅游, 生活, 我也潦草的塞了几片菜叶到肚子里, 结束了愉快的午餐.
: 最后他拿到了M的offer
|
A**u
发帖数: 2458 | 22 你太厉害了
你关注这个版很久了吧
【在 K*****k 的大作中提到】
: 不算了...
: 但是这个策略还有一个mitbbs59的案例：
: 中午1个小时的lunch interview, 虽然和对方在一个环境十分优雅的餐厅吃饭. 可是真
: 正让我吃饭的时间恐怕连10分钟都不到. 她先问了我一个不太难也不太简单的问题,
: 其实我知道答案, 可是这个问题如果coding, 会比较繁琐, 很容易出错. 我也就老实的
: 告诉她, 我已经看过这个问题了, 然后把方案说了一遍, 令我意外的是, 她主动换了另
: 外一个问题. 题目简单许多, coding也简单许多, 我顺利的coding完. 然后就和她聊
: 了聊旅游, 生活, 我也潦草的塞了几片菜叶到肚子里, 结束了愉快的午餐.
: 最后他拿到了M的offer
|
A**u
发帖数: 2458 | |
O******i
发帖数: 269 | 24 我怎么觉得那两个方法完全一样的呢？都是两串拼成一串，画法不一样而已。
【在 A**u 的大作中提到】
: http://blog.csdn.net/zyang008/article/details/6388284
: 这里面有两个方法
: 怎么写的很容易啊
|
B*******1
发帖数: 2454 | 25 是啊，看来他是长老级别的。
【在 A**u 的大作中提到】
: 你太厉害了
: 你关注这个版很久了吧
|
r*******g
发帖数: 1335 | 26 我看下面的都要先构建整个表 还是I place?
【在 K*****k 的大作中提到】
: 可以上网考古，好像是小尾羊Google加试的那轮就被问到。
: 就是说一个普通链表，每个节点还有一个random link指向别的节点或者自己。
: 让你In place（除了每个节点new出的copy)的复制这个链表，包括random link的拓扑
: 结构，也就是一个完全一样的镜像。
|
