|
s***e
发帖数: 403 | 2 今天看到leetcode的新题，单链表插入排序，本来准备做一下再吃午饭的。结果楞是写
了一个小时，中间bug无数。
感觉对人生失去信心了。 |
|
b***y
发帖数: 2799 | 3 ☆─────────────────────────────────────☆
randperm (昵称是什么？) 于 (Tue Sep 16 06:41:27 2008) 提到:
找单链表中的环，用两个指针，步长分别为1和2就行
问题是，为什么是1和2？其它步长行么？
看见讨论过，当时没仔细看，一下子想不明白了
大虾点拨一二？
谢了
☆─────────────────────────────────────☆
shime (虫) 于 (Tue Sep 16 10:02:45 2008) 提到:
我的想法是，其他步长也可以，只要它们不相等。但是选择1，2确实有好处。
1和2是最小的两个不一样的步长，所以相对其它的大步长可以省步数。
另外如果环的长度如果不能被步长差整除的话，大步长赶上小步长的时候多走的环数应
该就是步长差。所以在事先不知道环的长度的时候，步长差小一点也比较保险。
☆─────────────────────────────────────☆
thrust (WoW 无限期冬眠中) 于 (Tue Sep 16 12:48:53 2008) |
|
c**r
发帖数: 150 | 4
i
slow
matlab
是的，就是因为不是uniform的，以为p很大的话建matrix会很浪费空间和搜索时间。但
是同学，可不可以再帮我看看我有什么问题，虽然我还是没用STL，不好意思哈，我有
点弱
之前的问题原因我找到了，因为我把newvstr free了，就出现了一系列问题。
然后我用对struct里面释放内存的问题就纠结了。这是我写的释放空间的函数
void vstr_destroy(struct node *pvlist)
{
struct node *temp;
temp=pvlist->next;
while(temp!=NULL){
pvlist->next=temp->next;
free(temp);
temp=pvlist->next;
}
free(pvlist);
// pvlist=NULL;
}
在主函数中，比如我先动态分配了空间，
struct node *pvlist=(struct node *)malloc(p*sizeof(struct node));
最后我调用以上函数想释放空... 阅读全帖 |
|
c**r
发帖数: 150 | 5
i
slow
matlab
是的，就是因为不是uniform的，以为p很大的话建matrix会很浪费空间和搜索时间。但
是同学，可不可以再帮我看看我有什么问题，虽然我还是没用STL，不好意思哈，我有
点弱
之前的问题原因我找到了，因为我把newvstr free了，就出现了一系列问题。
然后我用对struct里面释放内存的问题就纠结了。这是我写的释放空间的函数
void vstr_destroy(struct node *pvlist)
{
struct node *temp;
temp=pvlist->next;
while(temp!=NULL){
pvlist->next=temp->next;
free(temp);
temp=pvlist->next;
}
free(pvlist);
// pvlist=NULL;
}
在主函数中，比如我先动态分配了空间，
struct node *pvlist=(struct node *)malloc(p*sizeof(struct node));
最后我调用以上函数想释放空... 阅读全帖 |
|
N*D
发帖数: 3641 | 6 ☆─────────────────────────────────────☆
klabc (恐龙ABC) 于 (Thu Apr 7 19:42:27 2011, 美东) 提到:
一个公司活的时间长了，就会有这种熬了20年熬成Senior的程序员。
实际能力不行，程序写的一塌糊涂；主要靠呼吁，还说不到点上；爱摆谱，装NB, 拿老
资格说事。
对项目的作用就是负值。
公司时不时的re-org也是有道理的...
☆─────────────────────────────────────☆
zjn (严禁灌水) 于 (Thu Apr 7 20:35:19 2011, 美东) 提到:
MS不是早就Senior满地走了么?
☆─────────────────────────────────────☆
qwuq (qigou) 于 (Thu Apr 7 20:37:10 2011, 美东) 提到:
senior Man Di Zou
pricipal Duo Ru Gou
☆─────────────────────────────────────☆
... 阅读全帖 |
|
j**l
发帖数: 2911 | 7 具体细节忘记了，但是梯子的辐条是单向的。
也就是，原始链表的next指针保留，原始链表的random指针改为单向辐条指向对应的复制链表的节点。复制链表的random指针暂时不用，而复制链表的next指针指向的是某个原始链表的节点(因为原始链表的random指针被破坏了，改造成了单向的辐条，所以需要间接通过复制链表的next指针保留原始链表的random指针的指向信息)。接下来，先把复制链表的闲置random指指针改造到正确位置。然后考虑断开：相互辅助，有次序的从表头开始逐个恢复原始链表的random指针和复制链表的next指针。
这是一个老印想到的解法。老中发表在网上的解法，以串成两倍长度的珍珠为多，原始链表和复制链表的对应节点为珍珠串中相邻的一对珠。这道题在国内，也是招聘名题，所有人都会体会到先合后分这种思想的巧妙。 |
|
j**l
发帖数: 2911 | 8 修改后的做法是
原始链表的next指针保留，原始链表的random指针改为单向辐条指向对应的复制链表的
节点。复制链表的random指针暂时不用，而复制链表的next指针指向的是某个原始链表
的节点(因为原始链表的random指针被破坏了，改造成了单向的辐条，所以需要间接通
过复制链表的next指针保留原始链表的random指针的指向信息)。接下来，先把复制链
表的闲置random指指针改造到正确位置。然后考虑断开：相互辅助，有次序的从表头开
始逐个恢复原始链表的random指针和复制链表的next指针。 |
|
m**q
发帖数: 189 | 9 谢谢分享~ 看着有不少最近见过的，尝试说一下思路，请大牛们指正。
公司名字就不说了，呵呵。俺面瓜一个，去之前也没时间看多少网上的题，既然安排了
就姑且一试。可能是运气好，问的题没有想象的难，而且碰到的人都非常nice.尽管这
样，被折磨一天下来到最后已经快神志不清了。把能记的住的题贴出来，造福一下后面
的人，也给大家特别是非牛人们打个气，不要怕，其实没有传说的那么恐怖~
1. Design free and malloc.
=> 不太了解考官的用意, 想到的是buddy system。
开一个指针数组，对应不同大小的空闲数据块。假如内存为1G,数据块大小可以为2^4,
2^5, 2^6，...2^30，指针数组共有27项。每一项引出一个链表，链表的每一项是｛
start,end, next}。
在malloc的时候，根据大小做二分查找，找到最小的能满足需求的指针数组项，
从链表中取一项，如果链表为空，则继续找更大的指针数组项引出的链表，
直到最大数据块对应的链表。如果需要的话，对找到的数据块进行分裂，把
剩余的空闲块插入到对应大小的链表中。
在free的时候，根据数据块大小找到对应的... 阅读全帖 |
|
y**i
发帖数: 1112 | 10 是不是这样：
第一次复制的时候，让复制链表的每个结点的random指针=原始链表的相应结点的
random指针，然后让原始链表的相应结点的random指针=复制链表的那个结点的指针，
第二次遍历的时候就可以通过复制链表的random指针找到原始链表的random，再通过原
始的random找到复制的random应该指向的结点，但这个时候不能修改random的值啊，一
修改后面的结点就不能通过这个方法找了（如果后面的结点random指向前面的结点的话
），看来就需要临时把random的值存在数组里了？第三次遍历的时候再修改random，也
同时break了两个链表的关系。
那个两倍长的方法倒是比较好实现。
个老印想到的解法。老中发表在网上的解法，以串成两倍长度的珍珠为多，原始链表和
复制链表的对应节点为珍珠串中相邻的一对珠。这道题在国内，也是招聘名题，所有人
都会体会到先合后分这种思想的巧妙。 |
|
d********n
发帖数: 191 | 11 应该是道老题了，不过后来跟朋友讨论时有些新情况。前几天面试考的，
【都是单向链表】
1.如何判断两个链表相交。
方法不少，遍历两个链表，看最后一个节点是不是相同。或者将其中一个表首尾相连，
看另一个表是不是有环（指针一个一次走一步，一个一次走两步两步，blablabla）
2. 如何找到相交的那个点？
方法也不少。reverse两个链表，从头开始走，走到某一个点不同时，上一个点就是交
点。或者两个链表依次入栈，一个个往外pop，然后比较，跟reverse类似
还有就是便利两个链表，得到长度m和n，然后得到长度差abs(m-n)，较长的链表先走
abs(m-n)这么多个点，然后两边一起走，第一个相同的就是交点。
问题来了，如果两个链表其中一个是有环的，应该怎么解决？特别是针对第一个问题。
见附图 |
|
P*****f
发帖数: 2272 | 12 我的思路
观察: 追逐Ranext 指针,可将老链表partition为多个disjoint cycles.
算法:
1.建立新链表时,第一次大循环pass只复制Nanext结构.
1.1 对老链表指针追逐,for current disjoint cycle
1.1.1 分配新链表对应节点,复制内容，并设置新链表节点相互之间的Nanext.
1.1.2 注意到此时
a) 老链表已经discovered得cycle节点其Nanext指针信息已复制到新链表中
,属于冗余,可利用为in-pace 空间
b) 其新链表对应的节点next指针不包含有效信息,可利用为in-place空间
for-each 新老节点对 in current cycle（老/新位置的对应有其在cycle
中的相对位置决定）做如下指针操作--为了将来在新链表中复制next结构:
1.1.2.1 老节点的Nanext指向新节点;
1.1.2.2 新节点的next指向老节点。
1.2 forward sca |
|
j**l
发帖数: 2911 | 13 三江口内，风浪不息，铁索连舟，如履平地。
这是小尾羊同学Google最终面的一道经典题目
核心思想就是，先合后分。
先平凡复制整个链表，不考虑random指针。
充分利用random指针和next指针，把原始链表和复制的链表这两个链表关联起来。传说
中有两种连接法：一种是串成长度为2倍的新链表(类似一串珍珠)，另一种是两个平行
但竖直方向对应节点相连的链表（类似横着的梯子)
不管哪种连法，都可以方便的给random指针赋值了。
然后不要忘记把两个链表的关联断开，成为两个一样的独立链表。 |
|
r****o
发帖数: 1950 | 14 能不能详细说说老中的二倍珍珠链解法啊？
老印的解法确实很巧妙。
复制链表的节点。复制链表的random指针暂时不用，而复制链表的next指针指向的是某
个原始链表的节点(因为原始链表的random指针被破坏了，改造成了单向的辐条，所以
需要间接通过复制链表的nex
始链表和复制链表的对应节点为珍珠串中相邻的一对珠。这道题在国内，也是招聘名题
，所有人都会体会到先合后分这种思想的巧妙。 |
|
L***Q
发帖数: 508 | 15 前面有人说建大linked list然后split，不过俺不知道具体啥意思。
俺有另外一个思路，如果是用C++写，可以用map。扫描原链表两遍。
step 1：copy链表，暂不初始化每个node的random指着。copy的同时，把原链表每个
node的地址和cloned链表每个node的地址一一对应，用map建立对应。
step 2：再次扫描原链表，假设当前扫描原链表node A，在clone链表中对应node A+。
可以得到node A random指针指向的node B的地址，然后在map中得到node B对应在
clone链表中的node B+的地址。把node A+的random指针设为node B+。 |
|
l*****0
发帖数: 238 | 16 清华大学《信息学奥林匹克竞赛》系列中有一道卫星覆盖范围的题根这个题是一回事。
这道题处理上稍微麻烦一点，但思路是一样的。
把所有的点都当作一个半径为R的圆来处理，系统维护一个链表，记录所有图形以及图
形的权值。比如取来第一个点A后，链表拥有一个节点N1，权值P1。
当取来第二个点B时，如果A与B不相交则简单，把B加入链表即可
算法的核心在于处理B与A相交的情形。
如果B与A相交，则令b=A&B，沿b的轮廓将A，B分割为 A-b，B-b，b三个图形，链表被重
新整理为
(A-b)(B-b)(b) 三个互不相交的元素，每个元素拥有一个确定的权值。将链表重新表示
为N1，N2，N3
当取来第三个点C时，先分析N1与C的相交关系，如果存在相交，则按照同样的方法进行
切割成N1-c,C-c,c=N1&C三个互不相交的图形，每个图形都有新的权值。注意到 (N1-c)
和 (c) 本来是属于N1的，他们和链表中的其他元素（N2，N3）都不相交，可以直接放
回到列表里，剩下图形标记为C'=(C-c)。接下来用同样的方法分析C'和N2的关系，依次
类推，直到剩下和谁都不相交的c''''放到链表里。
第四... 阅读全帖 |
|
w*****g
发帖数: 3 | 17 我来试一下看对不对。。。
队列+链表
队列就是正常存储的数据， FIFO， 只不过队列中的数据要额外多添加一个指针域， 指向其在链表对应的位置，
入队： 如果新加入的数比链表首要小或者相等（注意相等的细节），添加该数值到队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置为空就好了
出队： 如果要出队列的数值与链表头部的一样大（这种情况下对应的指针域不为空），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列
最小： 就在链表首部
不知道讲清楚了没有。。。 |
|
w****o
发帖数: 2260 | 18 你的这个有点儿问题，
比如队列
头 3 8 5 尾
链表: 3
如果3从队列里出队后，链表就成空了。这就不对了。链表应该是5
指向其在链表对应的位置，
队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置
为空就好了
），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列 |
|
n***y
发帖数: 84 | 19 第十二章 “人类的希望”
自从鲁特格做出了全速前进的决定后，商队这两天气氛开始变的严肃，大伙除了赶路，
几乎没有什么交谈。这天夜里，轮到莱因守夜，虽然已经离开了山区，美国西部昼夜温
差大的特点并没有改变，莱因抱着霰弹枪坐在篝火旁一段枯木上，把手伸向火堆取暖，
盯着忽明忽暗的火焰，不知道在想什么。一阵悉悉簌簌的声音，原来是莉莉娅披着毯子
走了过来。
莉莉娅在莱因身边紧贴他坐下，幽幽的说：”莱因，我想避难所了，不知道爷爷现在怎
么样，没有我照顾他，他现在肯定邋遢的一塌糊涂。你说，我们在地下掩体市能找到水
处理芯片么？”
“鲁特格和邦叔都说地下掩体市是战前科技保存最完好的城市，如果要说的话，肯定是
在那找到芯片的机会最大了。”
“如果找不到的话怎么办？”莉莉娅接着问。
“如果地下掩体市也没有，我们就只能按照已知的线索去别的避难所碰碰运气了。凯恩
先生在地图上还标出了12号避难所，距离地下掩体市很近，我在15避难所里还遇到过一
个拿着11号避难所物品的死人，这么说起来11号避难所也许也在附近，只是我们不知道
具体的位置，也许可以在地下掩体市打听一下。总之就算在地下掩体市找不到芯片，我
们还是有... 阅读全帖 |
|
n***y
发帖数: 84 | 20 第十二章 “人类的希望”
自从鲁特格做出了全速前进的决定后，商队这两天气氛开始变的严肃，大伙除了赶路，
几乎没有什么交谈。这天夜里，轮到莱因守夜，虽然已经离开了山区，美国西部昼夜温
差大的特点并没有改变，莱因抱着霰弹枪坐在篝火旁一段枯木上，把手伸向火堆取暖，
盯着忽明忽暗的火焰，不知道在想什么。一阵悉悉簌簌的声音，原来是莉莉娅披着毯子
走了过来。
莉莉娅在莱因身边紧贴他坐下，幽幽的说：”莱因，我想避难所了，不知道爷爷现在怎
么样，没有我照顾他，他现在肯定邋遢的一塌糊涂。你说，我们在地下掩体市能找到水
处理芯片么？”
“鲁特格和邦叔都说地下掩体市是战前科技保存最完好的城市，如果要说的话，肯定是
在那找到芯片的机会最大了。”
“如果找不到的话怎么办？”莉莉娅接着问。
“如果地下掩体市也没有，我们就只能按照已知的线索去别的避难所碰碰运气了。凯恩
先生在地图上还标出了12号避难所，距离地下掩体市很近，我在15避难所里还遇到过一
个拿着11号避难所物品的死人，这么说起来11号避难所也许也在附近，只是我们不知道
具体的位置，也许可以在地下掩体市打听一下。总之就算在地下掩体市找不到芯片，我
们还是有... 阅读全帖 |
|
h***a
发帖数: 1773 | 21 【 以下文字转载自 JobHunting 讨论区 】
发信人: repeat112 (windfantasy), 信区: JobHunting
标 题: 微软onsite面试悲剧，附面经并求分析，多谢~
发信站: BBS 未名空间站 (Thu May 8 18:31:09 2014, 美东)
一周之内面了微软两个组，刚刚收到结果双双悲剧，一个组的HR说It's a tough call
，另一个组的HR说very close，不知道是不是套话，总之很沮丧……来版上求问一下大
家问题可能出在哪，并且附上大概的面试过程和coding题目。
第一组：
第1轮：是一个SDE II，看名字像是中东人。coding题目是给定2棵树，判定是否其中一
棵是另一棵的subtree，同时用了DFS和BFS，写完code讨论了几个testcases和复杂度就
结束了。
第2轮：一个白哥Senior Lead，问的题目是一个maze（用2D matrix表示，有的坐标上
有障碍），给定起点和终点，找出从起点到终点的path，还是用的常规的DFS解法，搜
索过程排除有障碍的和访问过的坐标。
第3轮：一个小黑... 阅读全帖 |
|
v*****u
发帖数: 1796 | 22 //comfort 应该是真的ｃｌｏｓｅ，要不然老大不会花时间的吧。好好准备，拿个比软
软好的ｏｆｆｅｒ
【 以下文字转载自 JobHunting 讨论区 】
发信人: repeat112 (windfantasy), 信区: JobHunting
标 题: 微软onsite面试悲剧，附面经并求分析，多谢~
发信站: BBS 未名空间站 (Thu May 8 18:31:09 2014, 美东)
一周之内面了微软两个组，刚刚收到结果双双悲剧，一个组的HR说It's a tough call
，另一个组的HR说very close，不知道是不是套话，总之很沮丧……来版上求问一下大
家问题可能出在哪，并且附上大概的面试过程和coding题目。
第一组：
第1轮：是一个SDE II，看名字像是中东人。coding题目是给定2棵树，判定是否其中一
棵是另一棵的subtree，同时用了DFS和BFS，写完code讨论了几个testcases和复杂度就
结束了。
第2轮：一个白哥Senior Lead，问的题目是一个maze（用2D matrix表示，有的坐标上
有障碍），给定起点和终点，找... 阅读全帖 |
|
n********g
发帖数: 6504 | 23 不需要map。人家只限定loop一次字串。
用一个链表一个数组就行了。链表存工作状态，数组存某字符是否已重复了。
扫描到一个字符的时候：
1、如果数组里已经有了，忽略
2、扫描链表，如果已经有了，移除到数组里；否则加在链表末并下标
扫描完字串则链表中第一个元素的下标就是答案。
严格地说只用一链表也可以。如果这么抠门只用26个存储空间没有52个。 |
|
n********g
发帖数: 6504 | 24 嗯，再给一终极程序。
1、一不超过26格双向链表
2、一26格数组。对象为：数字下标及指向链表中对象
扫描字串：
1、检查数组对应对象下标如果为负数，跳过忽略；否则
2、如果为正数，改为-1，将对应链表中对象删除；否则
3、下标改为当前字符串下标+1，并把对应对象加在双向链表末段
全部扫描完后，双向链表中第一个对象的下标-1就是答案。
单循环也不需要遍历数组和链表。不算整数、指针等辅助内存只用了26（52）个对象。 |
|
l*********8
发帖数: 4642 | 25 如果两个链表都是可能有环的，则先要探测是否有环，以及环开始的地方。
如果两个链表都没有环，比较两个链表的最后一个节点。如果相同， 说明merge.
如果一个链表有环,一个没有环， 说明两链表没有merge.
如果两个链表都有环， 那么比较环开始的地方， 如果相同， 说明merge. |
|
t*****s
发帖数: 39 | 26 找工作算告一段落了，这一个多月从版上学到了很多，非常感谢大家，也分享点儿自己
的情况。本人cs fresh phd，投了F和G，准备主要是leetcode，做了50题左右，还有就
是板上的面经。强烈推荐leetcode，特别是对于准备时间有限的同学，基本覆盖了各式
各样的题。虽然最后面试没遇到做过的coding题，但基本都差不多。
0. 给定一个双向链表，以及一个数组。数组里存着一部分链表节点的指针。问数组里
的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
怎么做。算法复杂度分别是什么。
1. coke machines。大中小三个可乐机，每按一次出可乐量分别在[Amin,Amax], [Bmin
, Bmax], [Cmin, Cmax]之间，但不能确定具体容量是多少，现在想通过按这三个可乐
机，达到容量为[D, E]之间的可乐，问能否做到。也就是能否找到非负整数x, y, z使
得x*Amin+y*Bmin+z*Cmin>=D并且x*Amax+y*Bmax+z*Cmax<=E。感觉是个扩展的背包问题
，我给了穷举法和DP的解法，不过面试官最后说有... 阅读全帖 |
|
p**********g
发帖数: 378 | 27 【 以下文字转载自 JobHunting 讨论区 】
发信人: twobits (wahaha), 信区: JobHunting
标 题: 报F和G的offer+面经
发信站: BBS 未名空间站 (Fri Aug 2 20:59:05 2013, 美东)
找工作算告一段落了，这一个多月从版上学到了很多，非常感谢大家，也分享点儿自己
的情况。本人cs fresh phd，投了F和G，准备主要是leetcode，做了50题左右，还有就
是板上的面经。强烈推荐leetcode，特别是对于准备时间有限的同学，基本覆盖了各式
各样的题。虽然最后面试没遇到做过的coding题，但基本都差不多。
0. 给定一个双向链表，以及一个数组。数组里存着一部分链表节点的指针。问数组里
的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
怎么做。算法复杂度分别是什么。
1. coke machines。大中小三个可乐机，每按一次出可乐量分别在[Amin,Amax], [Bmin
, Bmax], [Cmin, Cmax]之间，但不能确定具体容量是多少，现在想通过按这三个可乐... 阅读全帖 |
|
p********7
发帖数: 549 | 28 刚才的算法有问题，不能达到O（N），下面这个应该没问题
先遍历一次，记录S2每个char的位置
s1 = "ADOBECODEBANCBBCAA"
s2 = "ABC"
按顺序记录就行了不用管ABC
record是一个DOUBLE链表 0，3，5，9，10，12，13，14，15，16，17，18
下次遍历的时候用一个hashtable，记录位置，并且记录链表node的指针
只用遍历record的位置，并且record最小值
a b c
0 3 5
下面遍历链表中的9，发现hashtable有b，于是获得位置是3的b的指针，删除链表当中值为3的node，并且更新table
链表现在是 0，5，9，10，12.......
a b c
0 9 5
因为更新的不是最小值，所以不计算
下面是10，发现table已经有a，于是获得以前a的node指针，删除链表当中之前的a，更新table，计算当前节点值和head节点值的差，是5，于是不更新
a b c
10 9 5 |
|
s***e
发帖数: 122 | 29 我觉得这个问题可能得先想清楚数据结构。我的想法是：
用一个二维的链表来存储你最后的结果(行内是单向链接，行头双向链接)：
a->b
|
c->d
节点的结构: (string s, int order, node* prevHead, node* nextHead, node* next)
用一个哈希表来存储所有的单词和对应的行头：
a->pa，b->pa，c->pc，d->pc
用一个哈希表来存储行头和对应的行尾：
pa->pb, pc->pd
这样当你加一个新的单词组的时候，我们先建一个关联列表，用来存储该单词组关联到
的所有行头。
对每个词先查哈希表看这个词是否以前出现过。如果出现过，我们就找到那个词所在
的行头，放到一个关联列表中；如果没有出现我们就把新词加到二维链表中，然后加到
哈希表中，同时把这个新行头也放到关联列表中。
当所有的单词扫描完，把关联列表排一下序，然后把二维链表中对应的行合并起来。
比如如上的时候，我们要加一个单词组e b f d：
1) 加e：哈希表中没找到，我们把它加到二维链表中
a->b
|
c->d
|
e
然后加到哈希表中
a->pa，b->pa，c |
|
j**l
发帖数: 2911 | 30 我修改过了。复制链表的random指针不用，而next指针指向原始链表的某个节点（由原
是链表的最初random指针决定)
original:A -> B -> C -> D->...
| | | |
copy: A' B' C' D ...
假如B的最初random指针(现在指向B'了)指向D, 则B'的next指针指向D
换句话说，复制链表的next，用来保存原始链表中的最初（变为单向辐条前）的random
指针 |
|
h***n
发帖数: 276 | 31 是概念上的新链表，又不分配空间
是从原来的链表挪元素到新的链表，不是拷贝了节点插入到新的链表，再删除再删除旧
链表的节点
还有，你这个广告行为太明显了巴 |
|
l*****a
发帖数: 14598 | 32 oh不算面经
发信人: jetchen (飞机),标 题: 问一个链表方面的算法问题 (转载) (Sun Jan 24
00:09:57 2010, 美东)
小弟EE的，不是cs科班出生，不知道这个问题描述的准不准确：
有一个循环链表 a->d->b->c->e->....->a 每一个节点都是一个整数，且不重复(除了
首尾节点外)。
现在这个链表被拆断开了，每2个相邻节点被存在一个cell里面, 但这些cell不是有序
的。 就是说链表被拆成了 a->d, c->e,...,d->b,...,b->c,.... 我想重新把链表建立
起来，应该用什么样的算法? |
|
|
|
d**********o
发帖数: 11 | 35 第五版
2.5 链表加法，比如输入两个链表3->5->7和6->5->6
(1) 假设低位在前， 输出9->0->4->1
(2) 假设高位在前， 输出1->0->1->3
书上的答案都是要考虑借位，然后一位位对齐加这样的
可是为什么不能把两个链表分别读出来写成整数a和b，然后把a和b直接相加得到的和
再写成链表形式返回？ 这不是不用自己在程序里考虑借位了吗？也不容易出错
2.6 找出带有loop的链表的第一个loop节点
这道题为什么不可以把一个个节点地址都存入hashtable, 然后第一个重复出现的地址
不就是第一个节点吗？
书上的解答好长啊 |
|
r*******2
发帖数: 104 | 36
好的，我把我的解题过程也说一下。Leetcode原题就不用说了。
第一组：
第1轮：判断subtree。假设两棵树T1和T2，先用DFS在T1里找到和T2的root一样的结点
，然后从找到的结点开始和T2进行比较，我用了BFS，就是用queue，一边一个queue，
同时push/pop进行比较，如果碰到不一样的就return false。做完了想起来其实就是
Leetcode上的Same Tree，直接还用DFS递归比queue省事。
第2轮：找出maze中的path。开一个matrix标记maze的每一个点是否访问过，然后DFS搜
索，从起点开始，查找它的上下左右邻居，如果没有访问过也没有obstacle，就作为一
个选择进行下一步搜索，一直递归下去直到找到终点为止。
第3轮：设计题。
第4轮：ASCII和Kanji字符的题以前面过，当时没做出来，答案就是回来网上搜的（参
考这个网址http://discuss.joelonsoftware.com/default.asp?interview.11.334807.4）。Spiral Matrix是Leetcode原题就不说了。
第... 阅读全帖 |
|
p*u
发帖数: 2454 | 37 来自主题: Programming版 - 编程的宗派 总是有人喜欢争论这类问题，到底是“函数式编程”（FP）好，还是“面向对象编程”
（OOP）好。既然现在出了两个帮派，就有人积极地做它们的帮众，互相唾骂和残杀。
然后呢，又出了一个“好好先生帮”，这个帮的人喜欢说，管它什么范式呢，能解决问
题的工具就是好工具！
我个人其实不属于这三帮人中的任何一个。
面向对象编程（Object-Oriented Programming）
如果你看透了表面现象就会发现，其实“面向对象编程”本身没有引入很多新东西。所
谓“面向对象语言”，其实就是经典的“过程式语言”（比如Pascal），加上一点点抽
象能力。所谓“类”和“对象”，基本是过程式语言里面的记录（record，或者叫结构
，structure），它的本质就是一个从名字到数据的“映射表”（map）。你可以用名字
从这个表里面提取相应的数据。比如point.x，就是用名字'x'从记录point里面提取相
应的数据。这比起数组来是一件很方便的事情，因为你不需要记住存放数据的下标。即
使你插入了新的数据成员，仍然可以用原来的名字来访问已有的数据，而不用担心下标
错位的问题。
所谓“对象思想”（区别于“面向... 阅读全帖 |
|
h*h
发帖数: 27852 | 38 http://www.yinwang.org/blog-cn/2015/04/03/paradigms
编程的宗派
总是有人喜欢争论这类问题，到底是“函数式编程”（FP）好，还是“面向对象编程”
（OOP）好。既然出了两个帮派，就有人积极地做它们的帮众，互相唾骂和鄙视。然后
呢又出了一个“好好先生帮”，这个帮的人喜欢说，管它什么范式呢，能解决问题的工
具就是好工具！我个人其实不属于这三帮人中的任何一个。
面向对象编程（Object-Oriented Programming）
如果你看透了表面现象就会发现，其实“面向对象编程”本身没有引入很多新东西。所
谓“面向对象语言”，其实就是经典的“过程式语言”（比如Pascal），加上一点抽象
能力。所谓“类”和“对象”，基本是过程式语言里面的记录（record，或者叫结构，
structure），它本质其实是一个从名字到数据的“映射表”（map）。你可以用名字从
这个表里面提取相应的数据。比如point.x，就是用名字x从记录point里面提取相应的
数据。这比起数组来是一件很方便的事情，因为你不需要记住存放数据的下标。即使你
插入了新的数据成... 阅读全帖 |
|
g**1
发帖数: 10330 | 39 区块链：大公司纷纷布局，高薪挖人，程序员的春天到了？
2018-01-21 · 36氪 0 跟贴
本文由 「AI前线」原创，原文链接：区块链: 暴富的捷径与程序员的舞台
作者｜Vincent Chen
编辑｜Emily
区块链，2008 年由中本聪于《比特币白皮书》中提出，并于次年创立了比特币社
会网络，开发出了第一个区块，名曰“创世区块”。如果用概念解释，区块链是分布式
数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式。
比特币是最早应用区块链技术的产品。区块链使用密码学方法相关联产生数据块，
每一个数据块中包含了一次比特币网络交易的信息，用于验证其信息的有效性（防伪）
和生成下一个区块。
随着比特币的推出，更多人知道了“去中心化”这一概念，区块链技术得到越来越
多的人认可，有更多开发者投身区块链的研究，推出了各种新型的加密代币：狗狗币、
以太币，甚至有些国家已经开始使用区块链技术开发自己国家的加密货币。
随着比特币的价格一路走高，更多的投资者发现了区块链技术能够带来的利益，于
是首次代币发售（英语：Initial Coin Offering，简称 ICO，也称为 ... 阅读全帖 |
|
j**l
发帖数: 2911 | 40 关于random指针是那样的，可以为NULL什么也不指，指向自身节点，指向其它节点。允
许多个random指针指向同一个节点。允许一个节点没有random指针指向它。
如果只复制链表是容易的。难点在于如何把random指针的拓扑关系也一并复制到新链表
。也就是，在原始链表和新链表中，random指针的拓扑关系是同构的。 |
|
j**l
发帖数: 2911 | 41 老中的二倍珍珠解法，用百度搜索中文都可找到的，而且有图。
个人觉得还是老印的解法巧妙，下面具体用例子说说。
假如链表为A->B->C->D->E
A的random指向E, B的random指向D, C的random指向自身C, D和E的random都为NULL。
第一步，平凡复制原始链表，不考虑random指针（全部设为NULL)
这样得到A'->B'->C'->D'->E'，所有random都为NULL
第二步，建立连接
让A的random指向A', B的random指向B', ..., E的random指向E', 成为梯子的单向辐条。
让A'的next指向E, B'的next指向D, C'的next指向C, D'和E'的next都为NULL， 也就是
用复制链表的next保存原始链表的原始random
A->B->C->D->E
| | | | |
A' B' C' D' E'
第三步，给A', B', C', D', E'的空random指针赋值
这样A'的random指向E', B'的random指向D', C'的random指向自身C', D'和E'的random
都 |
|
n******h
发帖数: 50 | 42 你的第二步里的前两句需要extra space，因为原始链表的random赋值需要复制链表的
next，而复制链表的next赋值需要原始原始链表的random。你恐怕要N个临时指针。
条。 |
|
d*******8
发帖数: 785 | 43 估计是免提的，一句话中间音量都不一样，还有背景噪声。
真不是他口音还是我听力的问题，一个问题就是要重复好几遍，太尴尬了。
面得中途我都泄气了。
回来补下电面，是第一轮电面
我估计碰上之前有一个人同样的面试官了，就盯着一个链表不放
简历 bla bla bla
问题：
按逆顺序打印一个single linked list。
用stack, 直接reverse 链表： 分别code
然后他提到不改变原有的链表也不用额外的空间.. n^2的方法。
然后比较诡异的来了，他问用o(n)的space, o(n^2)的复杂度算法。
一开始一直没听明白，后来发现是small o, strictly less than
开始想复杂了，后来一想就用logn个标记均匀分布在链表上，
从n到1, 都从之前最接近的那个标记开始找。
当然我比较土的以为不能用额外的stack什么的， 不然再用个n/logn size stack就很
快了，被他指出来了。
反正题目很简单，但是由于声音效果的问题，浪费很多时间，估计挂了。 |
|
h***n
发帖数: 276 | 44 1）构造一个新链表，初始化为NULL
2) 遍历给定链表的每个元素，遇到一个，就删除一个，然后从头加入新链表
3）重复2)，直到给定链表的元素删完为止 |
|
i**********e
发帖数: 1145 | 45 应该是 inplace swap，只许交换指针，不能利用额外空间和交换链表值。
考点是注意链表为空，链表只有一个值的corner cases。
还有一个很多人都会犯的错就是忘了连接已经交换的 pair 尾巴 和下一个 pair 头部。
要特别注意。
另外，这题还有一个扩展，就是 Reverse Nodes in K-group，
给个例子：
链表： 1->2->3->4->5
k = 2, 返回: 2->1->4->3->5
k = 3, 返回: 3->2->1->4->5
这题稍微复杂些，但思路和上面一样，只是多了个 reverse，然后再连接 group 尾巴
和 下一个 group 头部。 |
|
i**********e
发帖数: 1145 | 46 应该是 inplace swap，只许交换指针，不能利用额外空间和交换链表值。
考点是注意链表为空，链表只有一个值的corner cases。
还有一个很多人都会犯的错就是忘了连接已经交换的 pair 尾巴 和下一个 pair 头部。
要特别注意。
另外，这题还有一个扩展，就是 Reverse Nodes in K-group，
给个例子：
链表： 1->2->3->4->5
k = 2, 返回: 2->1->4->3->5
k = 3, 返回: 3->2->1->4->5
这题稍微复杂些，但思路和上面一样，只是多了个 reverse，然后再连接 group 尾巴
和 下一个 group 头部。 |
|
t********e
发帖数: 344 | 47 clear to me
指向其在链表对应的位置，
队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置
为空就好了
），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列 |
|
C****u
发帖数: 911 | 48 之前不知道能不能过，所以没上来发，因为感觉面得很忐忑。昨天刚收到二轮电面的通
知，就上来发一下
顺便最近好像很少看到A家面试的帖子了啊。。。
非CS专业（应用数学），也没有做过多少面试题
开头问我简历上的程序，我讲了一下，他们不是很感兴趣的样子。。没有追问
后来问我都熟悉什么数据结构，我就说，用过的不是很多，比较熟的就是数组链表二叉
树什么的。问我会不会hash table，我说不了解(汗)。
然后就开始问我链表，问了一些和数组的比较，主要是时间复杂度的比较
出了一个题目，两条链表，给出两个初始的节点，判断它们会不会merge。我没想出好的
算法，就说我没有好的算法，只能挨个比较，但是肯定不能这样。
然后面试官提示，说可以用hash table，然后说给我一个现成的hash table，里面各种
函数齐备，让我给这道题写code。
面试基本上到这里就结束了。
我自己面试题做得不多，大程写的不多，投简历纯属碰运气的想法，觉得面得很忐忑，
紧张到不行。能过实在是挺奇葩的。不过我感觉仿佛他们并不介意我对hash table不了
解。好在对于他们问到的链表比较熟悉，再就是时间复杂度比较熟悉。
... 阅读全帖 |
|
l*********8
发帖数: 4642 | 49 我错了， 如果两个链表都有环， 那么比较环开始的地方是不够的。
两个链表都有环的话， 可以从链表A的环开始的节点绕环一圈，看是否能找到链表B的
环开始的节点。 |
|
b******t
发帖数: 965 | 50 假设第一个链表长度n
第二个长度m
把第一个链表的指针都放到一个hashtable里
hashtable insert O(1) 总共O(n)
然后遍历第二个链表 遍历的时候check 第二个链表的指针在不在hashtable里
check O(1) 总共O(m)
总共O(m+n) |
|
