j***u
发帖数: 16 | 1 如果按inverted index方法
DocID_1 = { word1,word2,word3}
DocID_2 = { word2,word3}
DocID_3 = { word1,word3,word4}
那么,Hash链表
H(word1)-->DocID_1-->DocID_3
H(word2)-->DocID_1-->DocID_2
H(word3)-->DocID_1-->DocID_2-->DocID_3
如查询 word1+word2, 就是求每个word的hash链的交集 {DocID_1}
就变成求所有查询word的hash链的交集.
如果是这样的话，问题可以先简化找2个链表的重复数据，
然后根据得到的重复数据集合，和下一个链表比较 找交集 |
|
i******e
发帖数: 273 | 2
讨论一下用两种数据结构实现的时间、空间复杂度：
1）priority_queue (max heap)
2) 100个元素的链表数组
- 使用1）和2）的getPackage() 的时间复杂度都是O(1)
- 对于receive()， 使用priority_queue， 插入是O(lgN), 使用链表数组如果维护一
个指向每个priority链表结尾的指针，插入是O(1)操作。
- 使用1）和2）空间复杂度都是O(N)
- 使用2）查找当前最高priority 链表也是O(1)操作。
所以2）比1）更有效？ 这样分析对吗？ |
|
b*******3
发帖数: 145 | 3 想了一下这个题目，应该充分利用双向链表的条件，分2步完成，第一步扫描整个双向
链表，如果是奇数就用next链接，如果是偶数就有previous链接，第二部把奇数链表和
偶数链表交换到相应位置。第一步中previous与next一样，只是我们换了叫它previous
而已。
2 3 4 5 2 - 4 3 -5
3 = 5 = 2 = 4
时间复杂度o(n),空间复杂度o(1) |
|
W********e
发帖数: 45 | 4 我的办法就是进行二分，将k个链表分为两个一组，组内进行merge。形成一个新的链表
集合。继续两个一组merge，这样下去一共会进行logk次merge，最后merge成为一个链
表。这里用的辅助函数是mergeSortedList，合并两个有序链表，这个辅助函数复杂度
应该是O(n)。
我觉得这个算法的总时间复杂度是O(nlogK),大家觉得对吗？？
class Solution {
public:
ListNode* mergeSortedList(ListNode*l1,ListNode*l2)
{
ListNode *h1=l1,*h2=l2;
ListNode *newHead=new ListNode(0),*dummy=newHead; //newHead要赋
值，否则没有next。如果是C语言的话可以申请stack的对象
if(l1==NULL&&l2==NULL)
return NULL;
while(h1!=NULL&&h2!=NU... 阅读全帖 |
|
b******7
发帖数: 92 | 5 1.找到中间位置
2.将后半部分链表reverse
3.比较两段链表
4.将后半部分链表reverse，还原原链表 |
|
n*****g
发帖数: 178 | 6 问道balanced binary tree，说如果不balanced会怎样。当时经过一番周折我懒得想了
，就说不balanced的话就是一个不balanced的tree，就是普通的tree。貌似说了等于没
说，不过确实如此啊。他后来跟我说我想要的答案，是不balanced的话这个tree就和链
表一样了，变成了一个链表，搜索时间增大。
好吧。找这样推算，如果我有机会面阿三，我就问他们为什么链表要有指针，我期待的
答案是链表没有指针就变成数组了。是这个道理吧。
矫情。 |
|
a*******n
发帖数: 112 | 7 上周面的，从早9点到晚5点，说好大概一周以内给消息，结果什么消息也没有，是不是
就是婉拒了？也罢，既然没有签什么nondisclosure agreement，我就贡献几道面试题
吧。
- 一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
一个链表。要求把它拍扁，顺序随意。
一开始说了一个类似DFS的算法，他说我的空间复杂度是O(N)，我说递归的方法如果堆
栈空间也算的话确实是O(N)，但他咬定我临时放节点的地方也是O(N)，楞说我存节点需
要分配额外空间，我就很纳闷，这节点都已经是双向链表了，里面有next/prev，为毛
还需要分配O(N)的空间来存这些节点？坚持跟他讨论半天，把节点定义什么都给出来，
一点一点说明白，才证明是他理解有问题，幸好还算坚持，不然就被他带沟里去了。
当然这个算法有更好的解，既然不要求顺序，而且有头尾指针，每次把父子链表接到尾
巴后面就可以了。连递归都省了。
- 算sqrt()
我提出用牛顿法，刚画完坐标系就说不让用。原话是“newton's method is for
mathematics, please use comput... 阅读全帖 |
|
m*h
发帖数: 2750 | 8 OK 百忙之中再说几句
之所以举出链表的例子，是因为链表是CS 基础课之一。你们不是都看career cup考试么？
为什么考？就是它是基础。你当pm,marketing, content manager,都可以不知道链表，但是
你做软件工程师，不知道链表就是你的shame.你说存在就是合理，我没法和你争，因为你已经丧失了质疑的能力，我也怀疑你有没有潜力当上领导。
当然有不少小同学码过几行code 就觉得别人都很弱，那是年轻不知天高地厚。
但是MS这些年积累了一些很会talk，靠关系吃饭的人，级别还都不低，这就是问题了。
比如谁能说说principal sdet 该干什么？
我就知道有这么一位老兄，开会的时候他一说话大家就翻白眼。因为太驴唇不对马嘴了
不是还有的组有partnersde 一checkin 就break build 么?
军心，同学们，军心 |
|
N********n
发帖数: 8363 | 9 小题一道：
一个链表，每个节点里有俩指针Next和Ranext，各个节点的Next连接起来形成
一个单链表，最后一个节点的Next为NULL。每个节点Ranext指向链内某个节点。
没有任意两个Ranext指向同一个节点。输入这样一个链表，要求在O(N)时间内
复制出一个结构相同的链表。 |
|
b***y
发帖数: 2799 | 10 ☆─────────────────────────────────────☆
dArtagnan (达达尼昂) 于 (Thu Mar 13 10:47:37 2008) 提到:
从数据结构上来讲，对于一个链表，应该很容易实现扫描该链表的操作，只要从头开始
扫描链表的第一个元素，然后扫描该元素指向的那个元素，然后。。。。。。
但是在STL的list里面我似乎没有找到什么直接的方式可以扫描这个链表。
想问一下大家如果要扫描一个list一般是怎么做的？
难道用pop_front把第一个元素拿出来，扫描完了再给push_back回去？
或者我就完全用错了class，应该用一个其他的class？
☆─────────────────────────────────────☆
phennia (Phe) 于 (Thu Mar 13 10:50:45 2008) 提到:
iterator
☆─────────────────────────────────────☆
dArtagnan (达达尼昂) 于 (Thu Mar 13 10:53:49 2008) 提到:
T |
|
g*********s
发帖数: 1782 | 11 zaoxie给了个解法，是基于判定单链表是否存在循环链的解法。算法如下：
1. 维护快慢两指针。快的每次走两步，慢的走一步。一直走下去，若在某点相遇，说
明有循环链。这是经典解法。
2. 慢指针回到原表头，快指针留在相遇点，各自保持步长继续前行，再次相遇点即为
循环链起点。
注意这个带循环链的单链表形状像一个羽毛球拍。循环链相当于拍面，之前的单链相当
于拍柄。拍面
和拍柄交接处是循环链的起点。
假设拍柄长为h>=0，拍面周长c>=2。又假设第一次相遇时，慢指针走了h+x步。可证明x
去。如此快指针走了2(h+x)步，也即是(h+x)+k*c步，k>=1。那么下述等式成立：
2(h+x)=(h+x)+k*c => h+x = k*c (1)
如果慢指针回到原表头，快指针留原地，重新各自出发，保持之前步长，再次相遇时慢
指针走了h+y
步，按zaoxia说法，y==0。那么快指针走的步数是2h，也即是(c-x)+t*c。下面等式成
立：
2h=(c-x)+t*c => 2h+x = (t+1)*c (2)
由(1)和(2)得到：h = (t+1-k)*c。这显然可以构造出反例... 阅读全帖 |
|
z**********e
发帖数: 22064 | 12 http://style.sina.com.cn/time/watches/2012-02-23/192792008.shtml
http://www.sina.com.cn 2012年02月23日 19:27 新浪尚品 微博
三问，与陀飞轮、万年历一样，是机械表的一项复杂功能。简单地说，三问表就是
可以报时的表，表壳边有按钮或拨柄，按动它时，便可以听到“叮叮咚咚”的声音报时。
三问报时机构的核心——拾时机构
什么是“三问”表
1、报时方式
报时方式：拨动三问表的拨柄，它会连续发出悦耳的音调。低音调是报时，例如：
“当、当、当”，3响就是3点。接着是报刻，一般是高低音配合，例如：“叮当、叮当
”，即二刻(30分)。接下来，高音调是报分，例如：“叮、叮、叮、叮、叮”，5响是5
分钟，那么现在的时间是3点35分。
三问，与陀飞轮、万年历一样，是机械表的一项复杂功能，是机械制表工艺中一项
最大的挑战：在有限的空间内加入报时用的簧条装置，有时为了音色悠扬，还要装上三
套甚至更多套锤簧，很多零件如头发丝一般细小。各个名表品牌商们精制三问表，似乎
也不是为了赚钱，而是为了证明自己的技术高超，以此提... 阅读全帖 |
|
z******d
发帖数: 302 | 13 如果仅仅只是个算法的话，那么应该可以使用图认论知识来帮忙：
以 邻接表 的形式存储平面上所有N个点：
其中每个节点都存有：1）该点的平面坐标；2）该点的权值为该点与前一点的距离。
计算的时候，直接查找邻接表中P点的链表中所有的节点，只要其权值小于等于R，则存
入到一个新链表中（如果是非完全图的话，还得计算权值总和小于等于R的节点）。最
后输出该新链表。如果该平面上所有N个点之间是两两相通的话（完全图），可以不必
计算权值总和。
空间复杂度是：[符号打不出来：P]（N^2），时间复杂度是：O（N）
如果是想实际编程计算的话，可以使用一些插件。如果是使用C/C++/C#/JSP等的话，可
以使用SharpMap插件，其中就有空间分析函数。 |
|
h**6
发帖数: 4160 | 14 只用遍历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
这一步，删除链表中的3，恐怕无法用O(1)实现吧 |
|
h*****1
发帖数: 435 | 15 master new grad, IC 行业。 周三一个 on site In MA,周五另一个公司on-site in
CA
真希望早点儿结束求职的日子，每天神经都绷得紧紧的
Update:
-------结束了一个，组里四分之三的烙印，面试官分别来自三个组，CAE, IP, R&D。说是几个组都面一面看看那个组的工作适合我。 烙印好实在，一上来自我介绍完就发配我去白板上做题了。只有个美国人比较心好，说自己找工作就最讨厌技术问题，他也不问技术问题，基本上是我一直在吹牛，他最后问你中午去哪吃饭，爱吃辣不，我说喜欢吃辣的，他说他也喜欢，说越来越喜欢我了。。。。汗。。。
请教下 Application Engineer怎样？对于new grad来说是不是一个好的start职位？因为我身边很少有朋友去这个行业，大部分都去R&D了
Update2:
湾区的onsite结束了，比我预期的还要tough一些，面试官是各个部门manager还有一个director，考得范围很广，底层硬件，逻辑电路，时序，memory, 智力题，C，OOP，verilog，systemverilog, 脚本，数据结构... 阅读全帖 |
|
c**s
发帖数: 159 | 16 转载一个大家共勉。
由于之前Amazon已经发了offer，deadline也快到了，所以不管这次Google on-site结
果如何，都不想再继续折腾，Amazon or Google。求职季到此结束，所以，是时候写点
东西回报地里了。本人NYU-POLY，EE专业，作为一个转行的，感觉自己的求职之路还算
挺顺利，希望自己的经历经验能对各位尤其是非CS的各位有所帮助。
一。
感谢一亩三分地，mitbbs, 米群网（QQ群：320065698，可能满了，但是管理员会清理
，大家可以加加试试，另外米群网也是一个非常不错的求职平台，大家可以通过这个链
接去注册下http://www.meetqun.com/member.php?mod=register&x=12）提供的求职信息，内推信息及面经，当然也得感谢LeetCode和CC150。充分利用上述资源十分必要，而且感觉这些已经足够了。
二。
觉得有必要介绍下自己的准备情况，也算给大家涨点自信。
前面说了我是EE的，所学课程，包括本科的课，都没有什么和计算机相关的。去年暑假
决定开始自学CS，为了毕业好找工作，也就是那时候我才写出了自己第... 阅读全帖 |
|
I*****y
发帖数: 854 | 17 停工、跑路、资金链断裂，33万外贸企业的生存大考
发布时间：04-01 13:24
33万企业承压，1.8亿员工收入受影响，这是我干外贸几十年来，遇到的最严峻的考验。
外贸数据，与国际大事件的发展趋势有着微妙的关系。
2016年，远在大洋彼岸的中国义乌小商贩，提前5个月预测出特朗普当选美国总统。
他们发现，此前3个月里，特朗普周边产品的销量，远高于希拉里等竞争对手。
2016年美国总统大选周边销量对比，图/上观新闻
看到这份销售数据，义乌老板姚丹丹还专门囤了大量关于特朗普的周边。
当年竞选结束，仅和特朗普相关的旗帜，他就卖出了25万面。
除了义乌的旗帜，山东的棺材预测得更为直接。
在山东菏泽曹县庄寨镇，这里有木材加工企业2569家，他们制造的棺材90%销往日本。
2018年，小镇里一位老板表示，“来自日本的订单太多，根本做不完，单子甚至已经排
到了明年。”
这预示着，日本当年的死亡人数正在陡增。
不出所料，日本厚生劳动省报告，2018年该国死亡136.9万人，创出二战后最高水平。
日本2018年人口死亡原因占比，图/搜狐新闻
时间来到2020年，全球最大的事件就是肺炎疫情的快速蔓延。
... 阅读全帖 |
|
M**********7
发帖数: 378 | 18 首先感谢推荐以及陪同午饭的大牛哥，以及一直帮忙的美女！
本着同样帮同胞的精神回馈一下版面。
今天接到人力电话，说反馈还不错，但是很遗憾只能明年见了，不知道啥原因。
当时面试感觉挺好的，面之前就知道这个据点不怎么招人，不知道是不是这个原因。
电面两轮。
共五轮，有三轮和面试官谈的双方都很开心，其他的一轮也算中上，有一轮一般，但题
也做出来了。
所有题不是leetcode加面经覆盖过的，就是思路不怎么难的题。
不按照顺序上题
一、一道面经里面提到过讨论过，但是不太一样的。改用中文例子。
就是字符串编码解码。
编码规则是
原字串：
春节快乐喜气羊羊羊年大吉
编码为：
春节快乐喜气3x羊年大吉
两个情况下会有歧义：一个是原字串中的数字加x
之前面经提到的是用两个x转义，但是我遇到的要求是解码程序的逻辑不能改变。
此外还有压缩后前面的数字问题，比如
3羊羊羊开泰
变成33x羊开泰则解码程序会出错。
实际上这两个问题是一个问题，就是编码后源串中代表数字的字符恰好出现在数字加x
前面怎么办。
经过讨论，解决方法是将所有的领头数字编码例如：
3羊羊羊开泰
就编码成
1x33x羊开泰
要求尽量优化，也就... 阅读全帖 |
|
M**********7
发帖数: 378 | 19 首先感谢推荐以及陪同午饭的大牛哥，以及一直帮忙的美女！
本着同样帮同胞的精神回馈一下版面。
今天接到人力电话，说反馈还不错，但是很遗憾只能明年见了，不知道啥原因。
当时面试感觉挺好的，面之前就知道这个据点不怎么招人，不知道是不是这个原因。
电面两轮。
共五轮，有三轮和面试官谈的双方都很开心，其他的一轮也算中上，有一轮一般，但题
也做出来了。
所有题不是leetcode加面经覆盖过的，就是思路不怎么难的题。
不按照顺序上题
一、一道面经里面提到过讨论过，但是不太一样的。改用中文例子。
就是字符串编码解码。
编码规则是
原字串：
春节快乐喜气羊羊羊年大吉
编码为：
春节快乐喜气3x羊年大吉
两个情况下会有歧义：一个是原字串中的数字加x
之前面经提到的是用两个x转义，但是我遇到的要求是解码程序的逻辑不能改变。
此外还有压缩后前面的数字问题，比如
3羊羊羊开泰
变成33x羊开泰则解码程序会出错。
实际上这两个问题是一个问题，就是编码后源串中代表数字的字符恰好出现在数字加x
前面怎么办。
经过讨论，解决方法是将所有的领头数字编码例如：
3羊羊羊开泰
就编码成
1x33x羊开泰
要求尽量优化，也就... 阅读全帖 |
|
发帖数: 1 | 20 不得不承认，目下的中国文化重建工作，正在面临着一种非常复杂微妙的局势。一方面
，国学的复兴热潮正在吸引大量的社会资源与学者的精力，去从事对于中国传统文化的
理解与注释和传播工作；而另一方面，人工智能、大数据等新技术载体的出现，又在全
面地削弱各种传统的文化信息传播模式（特别是对于纸媒）的社会影响力，进而通过对
于“娱乐至上”理念的扩散来抵消严肃文化的传播学效应。耐人寻味的是，国内从事儒
家政治哲学研究的学者，大多倾向于将自己的理论谈话伙伴，定位为同样属于学者意识
形态的自由主义或政治保守主义，却很少顾及信息技术载体下的大众意识形态样态产生
的动力学机制。在笔者看来，这种过于“不食人间烟火”的态度，或许既会削弱儒家在
新技术条件下的说服力与传播学效力，亦会加高在不同专业群之间业已存在的信息壁垒
。而本文的目的之一，也便是本着“消除跨专业对话壁垒”的学术初心，向读者展示激
活传统文化资源应对新技术时代的可能性，由此甚至为一种具有“数码化的儒家”（
digitalized Confucianism）色彩的新技术路线的发育，提供思想层面上的预备性讨论。
然而，使得本文的讨论得以展开的“元语言框... 阅读全帖 |
|
y**i
发帖数: 1112 | 21 等等，你的这个node是原链表的还是copy的新链表的，arr里存的应该是原链表的吧 |
|
C*Y
发帖数: 736 | 22 2个半小时，要写出能run的code。题目大意是这样：
N个方块（N已知），每个方块的4条边用数字表示，只有数字相同的两条边才能相邻摆
放，。每次输入一个方块（不是一次性全给N个），有且仅有一个位置能摆放这个方块
，方块可以旋转（90，180，270度）。要求打印出拼好的图案（即所有方块的摆放位置
和旋转角度）。
我当时的想法是，用一个矩阵储存方块在图案中的位置和角度，一个链表储存图案的边
缘（逆时针地）。每输入一个方块，就拿它的4条边跟链表中的边逐个比较，找到了就
记下它的位置和角度，还要注意如果方块的边跟图案中超过1条的边相邻的话（直角的
位置），所有邻边必须相同。找到摆放位置后需要从链表中删除一些边和插入一些边。
即使是像我这个简单的思路，写出bug free的code来还是很费劲啊。哎。。
还有更快的算法和数据结构吗？ |
|
|
p********7
发帖数: 549 | 24 你说的是哪一步？
我想了下，链表应该是doublelinked的
建立链表肯定是O（N）
顺着链表遍历一次，还是O（N）啊，虽然有删除操作，但是删除不需要遍历，从
hashtable就能直接找到需要删除的节点。删除操作也是O(N)
hashtable记录O（1） |
|
i**********e
发帖数: 1145 | 25 怎样判断“满足都包含的条件”以及“不破坏条件”？
>> 判断“满足都包含的条件”就是利用一个counter。当满足了包含的条件之后，就可
以确保“不破坏条件”了。
不用一个counter的话，每次判断都要O(M)。
>>对的。
用counter的话，对应的hasFound超过了needToFind的时候怎么处理？
>>hasFound 超过了 needToFind counter 就不要加一，否则应该加一。
假设S1=ABAAAACAB，S2=AABC，当你遇到两个 A 的时候就 hasFound['a'] 加两次，值
为二。但是第三次你遇到 A 的时候就不必加了，因为这不帮助于满足条件。当
counter 为四的时候就满足条件了。
算下面这个test case时，
当end分别到了C和最后一个B的时候，什么时候begin该停？
S1=ABAAAACAB
S2=AABC
有人解释一下吗？
>>当end到了 C 的时候，就意味着刚满足条件，因为那时候 counter = 4.这时候就应
该开始移动 begin 指针，往右边挪。这时候 hasFound['a']=5, hasFound['... 阅读全帖 |
|
j***y
发帖数: 2074 | 26 谢谢楼上的回复。对，我面的是experienced的职位。大叔说的acess time是O(1)的意
思应该是access每个元素的意思吧，他当时没提到最大或者最小。
另外，vector的access time是不是O(1)啊？不晓得vector有什么劣势。
昨晚睡了一觉，又想起来一些当时的具体情节。
有个函数，void do_something(int time_out, void (*fprt)(float *), .../*
parameter list to the function pointer */)
有个timer，每隔一秒钟就timeout一次，会call这个do_something()，要求是设计并实
现一个数据结构，以达到当timeout时，找出当前的time_out值对应的function，跑一
遍，再从数据结构里删除这个entry。
比如，time_out的值是3秒的时候，必须把这个数据结构里面3秒所对应的function调出
来跑。
要求对找到这个function entry的search的时间复杂度是O(1)。
用hash table的话，如果key-va... 阅读全帖 |
|
g**e
发帖数: 6127 | 27 来自主题: JobHunting版 - 一到电面题 你的网站做的挺不错的。
链表加法的题目不久前写了一个，主要是要注意进位（包括最后的最高位进一），还有
就是不同长度的两个链表的加法，当一个链表遍历结束，另外一个还没结束的时候，要
循环把没结束的那个全部加到结果去。用递归或循环做都行
single |
|
R********r
发帖数: 48 | 28 bloomberg FSD，面试好大概3天后打电话给的offer，
non-CS 背景是中西部某三流学校生物MS+统计MS，现在很纠结，本来退了生物phd读统
计是为了找统计的工作，结果又转成码工了。板上有没有大牛能说一下去bloomberg好
不好啊？谢谢！
---
phone interview：
开始问会什么，直接说不会C++，数据结构只知道链表栈和树。于是考了链表插入，和
经典的检测环的问题（这个面的时候没见过，开始说了个很笨的方法，然后一边在听面
试官说废话的时候一边google答案，最后他让优化程序的时候直接念给他听）
然后问了些矩阵的问题，都比较简单。
最后让描述一个程序，把一个只有0,1数组把每两个1后面的0变成1。
onsite：
前两个技术面，
（1）链表查找，
（2）ABC。。。顺时针坐圆桌，从A开始顺时针每数K个人去掉一个人直到剩最后一个，
问用什么数据结构，写程序实现。
（3）给定一个数组，怎么快速找到某个number——binary search， 写代码。
（4）怎么索引一个很大的地址本。回答hash table，然后继续问，hash table是什么
，... 阅读全帖 |
|
z****e
发帖数: 54598 | 29 楼主的意思是
我不在乎你用什么
随便你用，只要你能实现目的就行
虽然说背算法不可取，我也反对面试时候让人写链表什么的
但是用算法实现的类实在是太简单的事情
而且这是经常遇到的事
比如上来就问hashmap和hashtable的区别
这个没有什么理由说，我不知道map是什么
而且对于这些类的使用也反映出一个人对于一门语言的使用经验
基本上可以说，对类知道得越多，工作经验越丰富
不需要你去写一个链表，但是要求你会用一个链表
这个是应该要有的
c+ |
|
j********e
发帖数: 1192 | 30 O(n)时间和O(n)内存的算法可以建立一个link list。
class Node {
int V;
int length;
Node *next;
};
每个数V建一个node，然后point到V-1对应的node
（如果V-1不存在就指向NULL）。通过hashmap，这个可以
O(n)时间内建立起多个链表。
然后对每个Node，开始计算以该node为起点的链表长度，
这个长度也保存在node数据里length。
这个也是O(n)，因为每个节点只需要计算一次。例如下面
例子中，从3开始，一直会经过2,1,0对应的node，同时
就把所有这些node的length计算了，以后就不需要再算，
所以每个node花O(1)时间。
后面就是打印最长的链表了。 |
|
w****x
发帖数: 2483 | 31
那就是维护两个指针在同一条next链表上, 设p1, p2.
p2用于连接next链表, p1当前的子节点加入(用p2)next链表中
BST那题咋O(n)啊 |
|
j********e
发帖数: 1192 | 32 一个链表长度10，一个长度12，第2个链表先走2步，
然后两个链表同时开步走，碰到的第一个相同节点就是了 |
|
i*********7
发帖数: 348 | 33 第一题是求一个循环链表的最大和的子链表。
譬如说 1 -> -1 -> 2。然后又回到1，最大和是3，子链表是 2 -> 1。
第二题如下。
There are n gas stations positioned along a circular road. Each has a
limited supply of gas. You can only drive clockwise around the road. You
start with zero gas. Knowing how much gas you need to get from each gas
station to the next and how much gas you can get at each station, design an
algorithm to find the gas station you need to start at to get all the way
around the circle.
跪求各位大神，求思路求解答。 |
|
a****s
发帖数: 559 | 34 1.先复制原链表A得到链表B，链表B中每个node初始置rand＝NULL；
2.建立一map，顺序取A中每个node的地址作为key，和B中相应node的地址作为value，
存入map。
3.顺序取A中每个node中的rand，－－
3.1 如果以rand为key可以在map中找到，获取其value。然后置B中相应node中的rand为
value。
3.2 如果以rand为key不能在map中找到，这是string，建立string copy，然后置B中相
应node中的rand为新建string的地址。 |
|
s***a
发帖数: 1 | 35 月初的时候去西雅图面试M，一上午4轮，吃完饭下午给结果。
第一轮先问了些基本情况，然后代码题是检验一个树是不是BST。写完之后，让我测试
代码，提供test case，然后问了下代码怎么样写能够更简洁。
第二轮两道题，一道是反转链表，另一道是两个stack来模拟queue。
第三轮是反转字符串，就是''Happy Christmas''变成''Christmas Happy''。写完之后
是测试代码，提供test case。写的过程中还顺便问了点其它问题：Java和C++有什么异
同，怎么用C++实现garbage collection，还问了一题，我不会，现在忘了。
第四轮先让我merge两个链表，然后是测试代码，提供test case。又问了一道怎么检验
链表有没有cycle的问题。
整个过程中我自己感觉反转字符串没写好，总是改来改去，其他几题我自己感觉还回答
的挺好的。
下午发offer，SDE级别未知，100k base。因为M是第一家让我去onsite的公司，我也挺
想去的，所以就从了。
另外求版友指点：
M的performance review是怎么一回事？
距离开工还有半... 阅读全帖 |
|
b***m
发帖数: 5987 | 36 稍微讲讲面经吧。今天的题总体比较简单，但是英语口语不好的人会直接跪下。
最开始是recruiter，闲聊半个多小时，基本都是行为问题，不惧。
第一个，烙印，Senior Test Manager，常规题，考的是shifted sorted integer
array，返回minimum element。然后让我在比较高度的位置，讲讲我对测试的理解。最
近面testing的职位比较多，每个面试官让我问问题，我都让他们给我讲一些跟测试有
关的知识，积累了这么久，也能白活了。
第二个，还是烙印，Senior Test Lead，没有做题，纯粹侃山，主要是对测试的理解，
以及对以前项目的阐述。得知我做过跟文件系统相关的工作，开始刨根问底地问问题，
后来才知道这哥们的team主要负责的就是文件系统——俺算是撞枪口上了……
以上是一个team，下面是另外一个team。
第三个，中国人，Senior Test Lead，直接我开车出去吃饭，基本就是拉家常，这个我
最擅长……吃完饭回到办公室，做一道简单题：给定一个binary tree，节点数据是整
数，再传入一个整数值，返回该binary tree... 阅读全帖 |
|
d**e
发帖数: 6098 | 37 ☆─────────────────────────────────────☆
yangcheng (牛魔王) 于 (Tue Apr 24 16:57:24 2012, 美东) 提到:
自称做过无数iPhone
问objective C, 语法都不知道，说忘了。
最近做java 。 cloud啊， hadoop啊，
然后问Java
说equals是比较class, 我问她是不是和instaneof 弄混了 她说java没这个关键字。就
是equals()。
然后我还被告知Object 没有wait() method, 只有Thread有。
☆─────────────────────────────────────☆
danicahu (katelyn) 于 (Tue Apr 24 16:58:13 2012, 美东) 提到:
^_^
☆─────────────────────────────────────☆
colwell2008 (colwell2008) 于 (Tue Apr 24 17:12:57 2012, 美东) 提到:
难道那些... 阅读全帖 |
|
d*k
发帖数: 207 | 38 MTV的onsite，总体很简单，悲剧原因有2：一是最后一面（第五个）的时候已经太累了
，一个老美问了个设计题，其实很简单，但当时又渴又饿又累，大脑已经不转了，估计
老美给了个strong reject。另一个是一个烙印的一道题：
输入是一个双向链表，链表的元素是一个整数，输出这些整数所构成的区间。例如输入是
5 10 1 6 2 4 11 7 3
输出是
1-6
7
10-11
我只想到排序后扫描的办法，不知道怎么利用“双向链表”这个条件。烙印后来试图给
提示，但我没明白他的意思。欢迎大家讨论。
经验教训：累了千万说话，硬撑悲剧后没人可怜你，最后一面的时候哪怕给我一杯水或
者让我出去溜达十分钟呼吸下新鲜空气，结果可能就不一样了。在那个不通风的小屋子
里连着好几个小时真心受不了。其实题目算不上难，我前两面都很好，只好是两个hire
。后面累的和sb一样，结果悲剧了。
祝大家好运。 |
|
Y**Y
发帖数: 66 | 39 这个单向链表就可以吧.这个题误导性太强，很容易往partition上想，昨天晚上想了半
天的partition/sorting. 后来发现其实很简单。面试时要碰到基本上完蛋。
scan一遍,把even number分出去，成另外一个链表；然后把两个链表接起来。
input: 2 -> 3 -> 6 -> 7 -> 4 -> 5 -> 8 -> 10
第一步：3->7->5
2->6->4->8->10
第二步：3->7->5->2->6->4->8->10
list * sort_odd_even(list* head) {
list *odd_head;
list *even_head, *even;
list *current, *previous;
if (!head || !head->next) {
return head;
}
previous = 0;
current = head;
while (current) {
if (current->value%2==0) { /*even number*... 阅读全帖 |
|
w****a
发帖数: 710 | 40 "10分钟前面经"系列的第二弹，这次是F家。上次G家的面经上周已发。
First of all, 求Bless!!
Fresh master非牛人，没准备多久因为H1B的愿意硬着头皮上了。
Skype加我的时间比约的晚十多分钟，是个白人小伙，挺随意的。他说看我的简历我以
前的background是游戏和图形开发，他说他以前也是做这个的，跟我说的还挺亲切的，
这个面试官人挺不错。
首先是behavior问题，先问了我过去project中遇到的最大的挑战，然后是问我为什么
选择F家，都是很经典的问题，事先也准备好了。
技术题1. 翻转链表。说实话我还挺意外的，我给出了一个非递归的实现，然后follow
up，他让我写个递归的，我只得另造一个函数。非递归的我应该写的没问题，递归的出
了点小bug，他给我一个用例让我测一下，我看了下发现确实有问题，迅速改对了，他
表示OK。然后又是follow up，问我当链表很大的时候递归方法有什么问题，我告诉他
会导致堆栈溢出。他继续OK。
技术题2. Leetcode的sort color，没什么好说的，只不过leetcode的原题类型是int，
值只有... 阅读全帖 |
|
n****r
发帖数: 10 | 41 国内fresh master，英语不好，有时交流是个问题。
电面1：寒暄，聊project和reseach。接下来编程题是找数组中最大的k个数：用quick
partition。写没费啥时间，讲思路耗费大部分时间～又聊了些别的结束。
两周后发邮件叫到西雅图onsite，但是几封邮件之后说嫌我远，改成conference call
，让我每次面试前拨通一个OCS的号码建立好连接等他们。好吧，那就相当于两天6个电
面。
第一面：先聊research和project。编程题是给两个链表，找出第一个链表中不在第二
个链表中的元素，不能有重复：用hash做。很快写完，接下来让写test cases。还有接
近15分钟，面试官开始让我问问题，随便聊了聊。
第二面：悲剧的开始。听不懂对方在说什么，一来英语不好，二来对方声音在电话里有
些模糊。很艰难的交流着，不停让对方repeat，我都不好意思了。题是设计题，连蒙带
猜的做，最后也没写出个啥名堂，时间就到了。
第三面：HM，基本就聊天，research，project，然后behavior问题，比如why amazon
等～最后问了个查询的题：就讲了... 阅读全帖 |
|
L*******t
发帖数: 782 | 42 第一题：
如果两个链表分别读完再写和就不止一个循环了，可以一个循环同时读两个链表，边读
边写新链表。 |
|
r**h
发帖数: 1288 | 43 数组存的是链表节点的地址啊，没办法sort
除非你额外做一个hash之类把链表节点的地址映射成该节点在链表中的位置 |
|
z****e
发帖数: 54598 | 44 底层是数组和链表
数组用来定位
然后每一个位置都是链表
当hashcode一致的时候
就用equals从链表开头挨个往后比较
然后hashcode要定位到数组的位置上去
这个稍微有些难，我也木有细看 |
|
p*****2
发帖数: 21240 | 45 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
p*****2
发帖数: 21240 | 46 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
s***e
发帖数: 403 | 47 我不清楚具体的说法。
queue的话应该是FIFO队列，list应该指链表。
那么queue的操作链表支持，链表的操作queue不完全支持。
这样就应该是一个“用list实现queue”的问题。
那么就应该是
class queue : private list
那么这是一个has-a的实现。 |
|
w******g
发帖数: 189 | 48 就是那道双向链表题：
"
一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
一个链表。要求把它拍扁，顺序随意。
"
题目确切是啥意思？有没有大牛讲讲或者举个例子？解题思路呢？
thanks in advance! |
|
w******g
发帖数: 189 | 49 就是那道双向链表题：
"
一个双向链表，带头尾指针，每个节点可能都有父节点和子节点，每个父子节点又是
一个链表。要求把它拍扁，顺序随意。
"
题目确切是啥意思？有没有大牛讲讲或者举个例子？解题思路呢？
thanks in advance! |
|
l*********r
发帖数: 136 | 50 Hi, 下面是我当时的解法，如有不妥的地方请指正
首先，因为是两个integer做除法，所以不涉及无线不循环小数的问题，当然循环位可
能super long导致溢出，此处暂不考虑这种情况。
举个例子，1除以7：
除法 结果集 余数集
1 x 10 / 7 = 1 余 3
3 x 10 / 7 = 4 余 2
2 x 10 / 7 = 2 余 6
6 x 10 / 7 ...
...
循环，每次都用前一步得到的余数乘以10（如果除数大于10的话，这里需要乘以多个10
），然后除以除数，并用一个链表记录下余数，做完上面的三步之后，余数集（链表）
中应该存 3 -> 2 -> 6... 结果集（字符串）中存142...
当遇到相同余数的时候（请注意是余数集中出现duplicates，而不是结果集中），即可
判知有循环出现。循环位数就是链表中两个重复数字的距离，在相应位置插入括号即可。
array |
|
