K*k
2 楼
有两种串法，经典的是双倍长单珠串型，还看到过一种梯子型（平行双珠串，上下珠珠相连）。
面试的时候经典的那个好写。
面试的时候经典的那个好写。
q*x
3 楼
就是写单串那个。看上去没问题了，一测试就发现有错。
珠相连）。
【在 K*****k 的大作中提到】
: 有两种串法，经典的是双倍长单珠串型，还看到过一种梯子型（平行双珠串，上下珠珠相连）。
: 面试的时候经典的那个好写。
珠相连）。
【在 K*****k 的大作中提到】
: 有两种串法，经典的是双倍长单珠串型，还看到过一种梯子型（平行双珠串，上下珠珠相连）。
: 面试的时候经典的那个好写。
A*u
4 楼
什么是 copy random link.
完全看不懂啊
珠相连）。
【在 K*****k 的大作中提到】
: 有两种串法，经典的是双倍长单珠串型，还看到过一种梯子型（平行双珠串，上下珠珠相连）。
: 面试的时候经典的那个好写。
完全看不懂啊
珠相连）。
【在 K*****k 的大作中提到】
: 有两种串法，经典的是双倍长单珠串型，还看到过一种梯子型（平行双珠串，上下珠珠相连）。
: 面试的时候经典的那个好写。
t*7
5 楼
梯形串啊,很SMART的解法
K*k
6 楼
可以上网考古，好像是小尾羊Google加试的那轮就被问到。
就是说一个普通链表，每个节点还有一个random link指向别的节点或者自己。
让你In place（除了每个节点new出的copy)的复制这个链表，包括random link的拓扑
结构，也就是一个完全一样的镜像。
【在 A**u 的大作中提到】
: 什么是 copy random link.
: 完全看不懂啊
:
: 珠相连）。
就是说一个普通链表，每个节点还有一个random link指向别的节点或者自己。
让你In place（除了每个节点new出的copy)的复制这个链表，包括random link的拓扑
结构，也就是一个完全一样的镜像。
【在 A**u 的大作中提到】
: 什么是 copy random link.
: 完全看不懂啊
:
: 珠相连）。
q*x
7 楼
如果之前没见过，当场能写对，还是很牛的。
【在 K*****k 的大作中提到】
: 可以上网考古，好像是小尾羊Google加试的那轮就被问到。
: 就是说一个普通链表，每个节点还有一个random link指向别的节点或者自己。
: 让你In place（除了每个节点new出的copy)的复制这个链表，包括random link的拓扑
: 结构，也就是一个完全一样的镜像。
【在 K*****k 的大作中提到】
: 可以上网考古，好像是小尾羊Google加试的那轮就被问到。
: 就是说一个普通链表，每个节点还有一个random link指向别的节点或者自己。
: 让你In place（除了每个节点new出的copy)的复制这个链表，包括random link的拓扑
: 结构，也就是一个完全一样的镜像。
K*k
8 楼
确实如此，所以我等小辈除了练习，以不变应万变对付一些简单题，保证简单题少bug,
少丢分外，就只能多背一些BT题以防问到。
【在 q****x 的大作中提到】
: 如果之前没见过，当场能写对，还是很牛的。
少丢分外，就只能多背一些BT题以防问到。
【在 q****x 的大作中提到】
: 如果之前没见过，当场能写对，还是很牛的。
q*x
9 楼
这个单串做法必须扫描两遍？第一遍复制随机，第二遍劈链？
我试图边复制边劈开，似乎不行。
其实扫两遍和扫一遍复杂度一样，因为扫一遍时循环步长加倍了。
bug,
【在 K*****k 的大作中提到】
: 确实如此，所以我等小辈除了练习，以不变应万变对付一些简单题，保证简单题少bug,
: 少丢分外，就只能多背一些BT题以防问到。
我试图边复制边劈开，似乎不行。
其实扫两遍和扫一遍复杂度一样，因为扫一遍时循环步长加倍了。
bug,
【在 K*****k 的大作中提到】
: 确实如此，所以我等小辈除了练习，以不变应万变对付一些简单题，保证简单题少bug,
: 少丢分外，就只能多背一些BT题以防问到。
A*u
10 楼
你是cs科班的吧
bug,
【在 K*****k 的大作中提到】
: 确实如此，所以我等小辈除了练习，以不变应万变对付一些简单题，保证简单题少bug,
: 少丢分外，就只能多背一些BT题以防问到。
bug,
【在 K*****k 的大作中提到】
: 确实如此，所以我等小辈除了练习，以不变应万变对付一些简单题，保证简单题少bug,
: 少丢分外，就只能多背一些BT题以防问到。
A*u
11 楼
你是先 扫一遍，用next创建链表，
再扫第二遍，创建link?
【在 q****x 的大作中提到】
: 这个单串做法必须扫描两遍？第一遍复制随机，第二遍劈链？
: 我试图边复制边劈开，似乎不行。
: 其实扫两遍和扫一遍复杂度一样，因为扫一遍时循环步长加倍了。
:
: bug,
再扫第二遍，创建link?
【在 q****x 的大作中提到】
: 这个单串做法必须扫描两遍？第一遍复制随机，第二遍劈链？
: 我试图边复制边劈开，似乎不行。
: 其实扫两遍和扫一遍复杂度一样，因为扫一遍时循环步长加倍了。
:
: bug,
f*t
12 楼
应该是扫描3遍吧
1.在每个节点后面插入一个复制的结点
2.修改所有复制结点的random指针
3.拆分出新的链表
1.在每个节点后面插入一个复制的结点
2.修改所有复制结点的random指针
3.拆分出新的链表
K*k
13 楼
从本科开始就是的。但是白板编程还是不熟练
【在 A**u 的大作中提到】
: 你是cs科班的吧
:
: bug,
【在 A**u 的大作中提到】
: 你是cs科班的吧
:
: bug,
q*x
14 楼
我说扫大链表两遍。
【在 f*******t 的大作中提到】
: 应该是扫描3遍吧
: 1.在每个节点后面插入一个复制的结点
: 2.修改所有复制结点的random指针
: 3.拆分出新的链表
【在 f*******t 的大作中提到】
: 应该是扫描3遍吧
: 1.在每个节点后面插入一个复制的结点
: 2.修改所有复制结点的random指针
: 3.拆分出新的链表
A*u
15 楼
我都晕了
next一遍
random一遍
还不够吗?
【在 q****x 的大作中提到】
: 我说扫大链表两遍。
next一遍
random一遍
还不够吗?
【在 q****x 的大作中提到】
: 我说扫大链表两遍。
q*x
16 楼
科班和写代码熟没必然联系。就像中文系的未必个个都是快写手。
【在 K*****k 的大作中提到】
: 从本科开始就是的。但是白板编程还是不熟练
【在 K*****k 的大作中提到】
: 从本科开始就是的。但是白板编程还是不熟练
d*d
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 的大作中提到】
: 即使想清楚算法，指针也很容易搞乱。
: 是个很好的练习。
区别是O(n)space 复杂度。可以拿来救场。
标准list copy应该是O(n) time, O(1) space.
假设hash class, equal class已经定义好了。
Node * copy(Node * root, unordered_map
if(root == 0)
return 0;
unordered_map
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
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;
当时小尾羊的策略就是：坦诚告诉面试官这题他见过，知道串珠的解法，然后写了个你
这样的容易实现的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
: if(root == 0)
: return 0;
: unordered_map
: if( it != rec.end()){
: return it->second;
A*u
19 楼
hash了，还算in place吗
【在 K*****k 的大作中提到】
: 面试时间总共就45分钟，如果细节纠结不好，就会超时
: 当时小尾羊的策略就是：坦诚告诉面试官这题他见过，知道串珠的解法，然后写了个你
: 这样的容易实现的hash方法
: 最后他拿到了G的offer.
【在 K*****k 的大作中提到】
: 面试时间总共就45分钟，如果细节纠结不好，就会超时
: 当时小尾羊的策略就是：坦诚告诉面试官这题他见过，知道串珠的解法，然后写了个你
: 这样的容易实现的hash方法
: 最后他拿到了G的offer.
K*k
20 楼
不算了...
但是这个策略还有一个mitbbs59的案例：
中午1个小时的lunch interview, 虽然和对方在一个环境十分优雅的餐厅吃饭. 可是真
正让我吃饭的时间恐怕连10分钟都不到. 她先问了我一个不太难也不太简单的问题,
其实我知道答案, 可是这个问题如果coding, 会比较繁琐, 很容易出错. 我也就老实的
告诉她, 我已经看过这个问题了, 然后把方案说了一遍, 令我意外的是, 她主动换了另
外一个问题. 题目简单许多, coding也简单许多, 我顺利的coding完. 然后就和她聊
了聊旅游, 生活, 我也潦草的塞了几片菜叶到肚子里, 结束了愉快的午餐.
最后他拿到了M的offer
【在 A**u 的大作中提到】
: hash了，还算in place吗
但是这个策略还有一个mitbbs59的案例：
中午1个小时的lunch interview, 虽然和对方在一个环境十分优雅的餐厅吃饭. 可是真
正让我吃饭的时间恐怕连10分钟都不到. 她先问了我一个不太难也不太简单的问题,
其实我知道答案, 可是这个问题如果coding, 会比较繁琐, 很容易出错. 我也就老实的
告诉她, 我已经看过这个问题了, 然后把方案说了一遍, 令我意外的是, 她主动换了另
外一个问题. 题目简单许多, coding也简单许多, 我顺利的coding完. 然后就和她聊
了聊旅游, 生活, 我也潦草的塞了几片菜叶到肚子里, 结束了愉快的午餐.
最后他拿到了M的offer
【在 A**u 的大作中提到】
: hash了，还算in place吗
q*x
21 楼
嗯，见多识广也是水平的一部分。
【在 K*****k 的大作中提到】
: 不算了...
: 但是这个策略还有一个mitbbs59的案例：
: 中午1个小时的lunch interview, 虽然和对方在一个环境十分优雅的餐厅吃饭. 可是真
: 正让我吃饭的时间恐怕连10分钟都不到. 她先问了我一个不太难也不太简单的问题,
: 其实我知道答案, 可是这个问题如果coding, 会比较繁琐, 很容易出错. 我也就老实的
: 告诉她, 我已经看过这个问题了, 然后把方案说了一遍, 令我意外的是, 她主动换了另
: 外一个问题. 题目简单许多, coding也简单许多, 我顺利的coding完. 然后就和她聊
: 了聊旅游, 生活, 我也潦草的塞了几片菜叶到肚子里, 结束了愉快的午餐.
: 最后他拿到了M的offer
【在 K*****k 的大作中提到】
: 不算了...
: 但是这个策略还有一个mitbbs59的案例：
: 中午1个小时的lunch interview, 虽然和对方在一个环境十分优雅的餐厅吃饭. 可是真
: 正让我吃饭的时间恐怕连10分钟都不到. 她先问了我一个不太难也不太简单的问题,
: 其实我知道答案, 可是这个问题如果coding, 会比较繁琐, 很容易出错. 我也就老实的
: 告诉她, 我已经看过这个问题了, 然后把方案说了一遍, 令我意外的是, 她主动换了另
: 外一个问题. 题目简单许多, coding也简单许多, 我顺利的coding完. 然后就和她聊
: 了聊旅游, 生活, 我也潦草的塞了几片菜叶到肚子里, 结束了愉快的午餐.
: 最后他拿到了M的offer
A*u
22 楼
你太厉害了
你关注这个版很久了吧
【在 K*****k 的大作中提到】
: 不算了...
: 但是这个策略还有一个mitbbs59的案例：
: 中午1个小时的lunch interview, 虽然和对方在一个环境十分优雅的餐厅吃饭. 可是真
: 正让我吃饭的时间恐怕连10分钟都不到. 她先问了我一个不太难也不太简单的问题,
: 其实我知道答案, 可是这个问题如果coding, 会比较繁琐, 很容易出错. 我也就老实的
: 告诉她, 我已经看过这个问题了, 然后把方案说了一遍, 令我意外的是, 她主动换了另
: 外一个问题. 题目简单许多, coding也简单许多, 我顺利的coding完. 然后就和她聊
: 了聊旅游, 生活, 我也潦草的塞了几片菜叶到肚子里, 结束了愉快的午餐.
: 最后他拿到了M的offer
你关注这个版很久了吧
【在 K*****k 的大作中提到】
: 不算了...
: 但是这个策略还有一个mitbbs59的案例：
: 中午1个小时的lunch interview, 虽然和对方在一个环境十分优雅的餐厅吃饭. 可是真
: 正让我吃饭的时间恐怕连10分钟都不到. 她先问了我一个不太难也不太简单的问题,
: 其实我知道答案, 可是这个问题如果coding, 会比较繁琐, 很容易出错. 我也就老实的
: 告诉她, 我已经看过这个问题了, 然后把方案说了一遍, 令我意外的是, 她主动换了另
: 外一个问题. 题目简单许多, coding也简单许多, 我顺利的coding完. 然后就和她聊
: 了聊旅游, 生活, 我也潦草的塞了几片菜叶到肚子里, 结束了愉快的午餐.
: 最后他拿到了M的offer
A*u
23 楼
http://blog.csdn.net/zyang008/article/details/6388284
这里面有两个方法
怎么写的很容易啊
【在 q****x 的大作中提到】
: 我说扫大链表两遍。
这里面有两个方法
怎么写的很容易啊
【在 q****x 的大作中提到】
: 我说扫大链表两遍。
O*i
24 楼
我怎么觉得那两个方法完全一样的呢？都是两串拼成一串，画法不一样而已。
【在 A**u 的大作中提到】
: http://blog.csdn.net/zyang008/article/details/6388284
: 这里面有两个方法
: 怎么写的很容易啊
【在 A**u 的大作中提到】
: http://blog.csdn.net/zyang008/article/details/6388284
: 这里面有两个方法
: 怎么写的很容易啊
B*1
25 楼
是啊，看来他是长老级别的。
【在 A**u 的大作中提到】
: 你太厉害了
: 你关注这个版很久了吧
【在 A**u 的大作中提到】
: 你太厉害了
: 你关注这个版很久了吧
r*g
26 楼
我看下面的都要先构建整个表 还是I place?
【在 K*****k 的大作中提到】
: 可以上网考古，好像是小尾羊Google加试的那轮就被问到。
: 就是说一个普通链表，每个节点还有一个random link指向别的节点或者自己。
: 让你In place（除了每个节点new出的copy)的复制这个链表，包括random link的拓扑
: 结构，也就是一个完全一样的镜像。
【在 K*****k 的大作中提到】
: 可以上网考古，好像是小尾羊Google加试的那轮就被问到。
: 就是说一个普通链表，每个节点还有一个random link指向别的节点或者自己。
: 让你In place（除了每个节点new出的copy)的复制这个链表，包括random link的拓扑
: 结构，也就是一个完全一样的镜像。
相关阅读
求西部挂cpt学校名单背景调查材料工程是不是要火了请问, 有绿卡(甚至公民)和H1B/OPT找码工有大区别吗?H1B Consulting【工作机会】flow cytometry position找2016 summer cs 的实习什么时候开始狗不就是美国的创新工场么 李开复赢了上海化学工作机会OPT延期这个事情扳回来的希望很小了 (转载)一直很好奇，除了中国人，其他国家的人刷题吗有没有苹果家的？现在公司还有什么创新么一个人做到什么程度能被称为无耻？New Grad可以找到工作后立刻入职吗？non cap H1b transfer问题 和 h1b同时延期opt的问题技术都是砍边的，大气都是动态的中国人这下彻底被阿三玩死了I797A附带的I94出境需要交回吗？换工作中间的几天保险是怎么cover的?感觉以后进f会越来越难