r****o
发帖数: 1950 | 1 两个长度分别是l1,l2,假定l1>l2,
那么就让第一个链表先开始，等它visit完 l1-l2个节点的时候第2个链表也开始visit。 |
|
y**i
发帖数: 1112 | 2 vector不事先指定大小在resize的时候效率会有影响吧？假定链表很长的情况下
这也不是大问题，大不了第一次循环可以确定链表大小，再做一次循环就可以了，也可
以在O(n)内完成。
之前的帖子里vector里说是存original list的指针对(pairs)，我还以为是对应node的
指针呢，从你的代码里看应该是对应node的random的指针，那就没有问题
不过感觉这个方法还是不如最前面的那个把copy的node放在原来node的后面然后分离的
那个方法简洁啊，那个方法不需要额外内存 |
|
d**e
发帖数: 6098 | 3
看不懂最后两句
original: A ->B-> C-> D->...
| | | |
copy: A'->B'->C'->D'->...
复制链表的random是怎么指到原始链表那里？ |
|
y**i
发帖数: 1112 | 4 应该是先把原始链表的random转存到复制链表的random里 |
|
y**i
发帖数: 1112 | 5 显然不能用链表，人家考你的就是数组，链表大家都会，正因为是数组才有难度 |
|
y**i
发帖数: 1112 | 6 我怎么感觉这个就跟两个链表有公共结点，找公共结点的题目一样啊
首先确定p和q的层数（对应链表的长度），然后先移动层数多的那个结点向上（父结点
）到和另一个结点同样的层数，然后同时向上移动，找相同的结点指针。
复杂度O(lgn)。
这两个算同一个类型的题目么？
戏么？ |
|
j**l
发帖数: 2911 | 7 假如题目都事先没看过。
估计面试时候也经常会问到一般站友，中级站友和高级站友是主力，长老级作为bar
raiser, 开国大老用来刁难人。
新手上路级：
比如O(n)时间找数组最大元素
一般站友级：
比如链表反转，限制用一层循环找单词个数
中级站友级：
比如二叉树的前序中序非递归遍历
前序中序序列重构二叉树并coding
高级站友级：
O(1)空间反转句子中的每个单词
log(n)时间找两个排序数组的median
O(1)时间GetMin的栈
循环数组的二分查找
二叉树的后序非递归
各种DP题
长老级：
复制含有random指针的链表
开国大老：
发在paper上的算法，比如寻找0-1矩阵最大的的全1子矩阵 |
|
r****o
发帖数: 1950 | 8 刚才看到有人的面经里面有这个题目。
有谁有什么好办法吗？
我想的一个办法是复制这个链表，然后反转，然后两个链表一起从头遍历，这样我们可
以知道环从哪儿开始，也就可以知道环前面一个节点的位置。
这个方法时间复杂度和空间复杂度都是O(n),
有谁有更好的方法吗？ |
|
y*********e
发帖数: 518 | 9 第一题，BST到链表，inorder traverse便是。
从链表到BST，可能产生的BST并不是原先的BST。因为可以有2个不同的BST产生出一样
的inorder traverse，所以反过来，只有inorder traverse并不能确定原先的BST。
若是array的话，这样就好了。每次取array的中点，做成一个node，然后左边的就是
left subtree，右边的就是right subtree，可以做成递归。
public Tree build(int[] array, int low, int high) {
if (low > high)
return null;
if (low == high)
return new Tree(array[low]);
int mid = low + ((high - low) >> 1);
Tree root = new Tree(array[mid]);
root.left = build(array, low, mid - 1);
root.r |
|
Z*****Z
发帖数: 723 | 10 对这个hedge fund公司印象还是非常好的，在这里宣传一下。如果你之前没听过这个公
司，那么即使去网上搜，也找不到什么。这是因为政策规定这种性质的公司必须保持低
调。
这是家hedge fund的特点就是极其依赖计算机，他的trading策略都是电脑算出来的。所
以就和软件公司一样。没有金融背景的CS同学是完全没有问题的。
我把简历放到网上，有recruiter来联系我。我本来没有申过financial的公司，抱着试
试看的心理就让recruiter去投了简历。
然后code test，不难。
然后onsite，由于地理关系，先去了休斯顿。office不大，30几个人的样子。面试也不
难，聊得很愉快。
然后去纽约，见到了一些高级的manager，有几个问题答得不太好。
第一个人，让实现一个游戏，就是你想一个动物，电脑问问题，然后猜。要是猜错了的
话，你需要准备一个yes/no的问题并且提供答案，让电脑学习。这是一个标准的决策树
问题，我当时问需不需要电脑智能的选择问题使得在最短时间内能够得到答案。答曰不
用。我头脑一热就上了链表，没用树。后来被证明链表是行不通的。
第二个人，问了一 |
|
h**k
发帖数: 3368 | 11 把它从链表中删除，再重新插到链表最后就行了。因为是doubly link，操作是O(1)。 |
|
A*********r
发帖数: 564 | 12 永远是从尾插入的，只要O(1)的。
如果要插入的数比当前尾部数大，要删除前面的数直到遇到比当前数大的再插入，链表maintain的是一个递减的序列，并不是整个window的大小，也就是每个数最多插入/删除一次，所以整个的复杂度是O(n)。。
这道题的trick就在这里，链表保留的不是window里面的所有数，否则的话，就达不到O(n). |
|
|
c**s
发帖数: 43 | 14 怎样判断“满足都包含的条件”以及“不破坏条件”？
不用一个counter的话，每次判断都要O(M)。
用counter的话，对应的hasFound超过了needToFind的时候怎么处理？
算下面这个test case时，
当end分别到了C和最后一个B的时候，什么时候begin该停？
S1=ABAAAACAB
S2=AABC
有人解释一下吗？
另外，感觉用另外一个贴paul的链表的算法，在每个node上再加个双向链表，
来指向下一个重复字母，应该就能在O(N)内处理s2有重复字母的情况。
只是变得更复杂了。没这个简洁。 |
|
f****a
发帖数: 54 | 15 找工作一个半月，今天算是阶段性结束了。在这里潜水不少，收获也不小，今天也贡献
一下。
背景很一般，本科在国内念的计算机，这边二流(or三流？)学校硕士，IT管理。
目标是金融行业的tech职位，投了可能有四五十个相关职位，基本都是比较好的银行，
基金，金融软
件公司，外加一些保底的和tech consulting。当中可能不少都不sponsor visa的，另
外开始投
的有些晚，错过了8月底9月的第一波，后悔啊
面试不多，有5，6个，没有特别好的公司，也在意料之中。不过基本都进onsite，最后
有2个
offer。一个是big4的firm，一个是二流的银行。big4不太符合我的个性，应该会去银
行吧。
来了美国之后，整个思想和人生目标发生了巨大转变，因为各种原因，很多时候过的并
不如意。但是
我还是相信“天降大任于斯人，必先苦其心志，劳其筋骨，饿其体肤，空乏其身...”
以此与各位共
勉。
希望大家都能有满意的offer！
Clarifi面经(最后被拒):
这是个capital iq的子公司，team只有20个人，都是developer，一堆俄罗斯人和cs
phd，那
天没见着中国... 阅读全帖 |
|
f*********i
发帖数: 197 | 16 今天在redmond面试，一共见了6个人，5轮technical interview，一轮PM interview.
时间从早上8点到下午4点半。。。累死，没有签什么保密协议，所以一回来就发面经回
报版上，顺便求祝福。
第一轮： 老中，题目很简单，一个数组，有正有负，求最大连续和，这道题直接用经
典的O(n)就做出来了，然后问test cases。 多谢同胞，有了个好的开始。
第二轮：一个美国人，问两个string 是否是 anagram， 附加条件是abc ＝ a c b，
就是允许空格存在。也不难，三种方法，排序，hash table，还有质数相乘。质数相乘
是看版上牛人的答案，这个很快，而且不要extra space， impressive了他一下。
第三轮：老印，据说是这个组里最nice的老印，是90分钟的lunch interview，问了
string 中reverse word， 就是把how are you => you are how，reverse+reverse，
没有什么tricky的，写程序的时候有点麻烦，不过没有出错。
第四轮：老印，这个人是最tough的... 阅读全帖 |
|
s********k
发帖数: 6180 | 17 EE fresh PHD不是大牛名校，面试职位是R&D，不过其实除了研究，主要是考编程，以
及embedded system/RTOS。
早上开始做了一个ppt，大概一个小时，主要是研究相关，interview team的人提问。
接下来是一个老资格台湾工程师面试，考的比较简单，除了简历，问的是比较常规的问
题，比如reverse byte，reverse bit，然后little/big endian判断,SPI的用法，DMA
等等，C++方向问了pure virtual。总的感觉不是太难，但是第一个比较紧张，有点不
适应。还好完了之后就是lunch时间，这个台湾工程师带我开出去吃。
之后下午继续，第一个上来的是一老印，不过挺nice的，因为是在这里做contract的原
因，所以说了一些他自己对公司的看法，以及他跳来跳去的感受。问的问题没有白板
coding，就是简历问题。
接下来一个白人工程师，主要靠RTOS，他我感觉是问的水平最高的，当然也最难。首先
就问说RTOS和普通的OS（windows，linux）主要区别。我说是deterministic。他接着
问，为啥普通OS很难... 阅读全帖 |
|
h****c
发帖数: 10494 | 18 Java方便的地方不在于指针，不使用API提供的方法编码就相当于在C里面不使用指针来
建立链表一样，即使写出来一个非常高效的链表函数，能有多大的意义呢 |
|
w****o
发帖数: 2260 | 19 递归逆序打印链表很好做呀！难的是iteratively逆序打印链表。 |
|
g*********s
发帖数: 1782 | 20
应该是。
一个链表？hash里存链表的指针？ |
|
w*******m
发帖数: 27 | 21 学数据结构时候用的书实现链表的时候是用三个类
节点，迭代器，链表类 |
|
i**********e
发帖数: 1145 | 22 从你那个例子：
"it is a good day today"
可以建个链表，t->s, i->a->g->d->t
然后 merge 成：i->a->g->d->t->s
怎么打印所有 alphabetical order 的可能性如果只有一个链表写个 dfs 就好了.
但如果是这样的情况似乎很复杂啊:
c->a, s->b->a
这题是不是要有对图论有很深的知识才能答出来？
还是有一些 trick 在里面？
这里有介绍 DAG 的算法：
http://allisons.org/ll/AlgDS/Graph/DAG/
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 23 从你那个例子：
"it is a good day today"
可以建个链表，t->s, i->a->g->d->t
然后 merge 成：i->a->g->d->t->s
怎么打印所有 alphabetical order 的可能性如果只有一个链表写个 dfs 就好了.
但如果是这样的情况似乎很复杂啊:
c->a, s->b->a
这题是不是要有对图论有很深的知识才能答出来？
还是有一些 trick 在里面？
这里有介绍 DAG 的算法：
http://allisons.org/ll/AlgDS/Graph/DAG/
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
c****p
发帖数: 6474 | 24 每个hash value里面挂个链表，链表各单元按key值以增序或者减序排序。
我一门课socket编程的时候好像这么处理过selectid。。 |
|
W**********r
发帖数: 8927 | 25 我的答案：
if(用快慢指针从A的头出发测A是不是有环 == Yes) {
if (用快慢指针分别从A和B的头出发测是否相遇 == Yes) {
确认相交；
追上的一点肯定在环上，以此可以遍历环，再分别从A和B出发依次比较是不是在环上的话，最后可以确定分别的交点。
}
else {
确认不相交；
}
}
else {
if(用快慢指针从B的头出发测B是不是有环 == Yes) {
确认不相交；
}
else {
遍历两个链表，得到长度m和n，然后得到长度差abs(m-n)，较长的链表先走abs(m-n)这么多个点，然后两边一起走，第一个相同的就是交点。始终不同就没交点。
}
} |
|
b*******8
发帖数: 37364 | 26 分别对每个链表判断是否有环，有环则记录环的交点，无环则记录终点。
如俩链表一个环一个非环，则断然不交。
如两个都非环，则看终点相同与否。
如都有环，则从一个环的交点出发走一圈看能否到另一个环的交点（同时出发速递1和2
的快慢指针，追上时正好慢指针走完一圈）。 |
|
A*****i
发帖数: 3587 | 27 那个链表是用JAVA写的，完全正确
因为java没有结构体，所以那个类就是链表插入的类，你可以在里面加上delete或者
reverse都可以，建议好好看看java再看这个150题，大部分都是用java写的 |
|
K*****k
发帖数: 430 | 28 可以上网考古，好像是小尾羊Google加试的那轮就被问到。
就是说一个普通链表，每个节点还有一个random link指向别的节点或者自己。
让你In place（除了每个节点new出的copy)的复制这个链表，包括random link的拓扑
结构，也就是一个完全一样的镜像。 |
|
i*******6
发帖数: 107 | 29 #5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
扩展了这道题，写成可以自己设置每几个数reverse一下。
思路大概是这样,一个原始链表为
0->1->2->3->4->5->6
如果每3个数反转一下的话，那么先把5指向0,6指向3,2指向null （换言之则是把第kn
个节点指向(k-2)*n+1个节点，再把第n个节点指向null），可以得到
6->3->4->5->0->1->2
然后把整个链表反转就是我们要的结果：
2->1->0->5->4->3->6
附上java代码和数据结构，以及测试用例，在netbeans5.5测试通过：
class ListElement{
public ListElement next;
public int data;
public ListElement(){
}
public ListElement(int data){
th... 阅读全帖 |
|
s*******f
发帖数: 1114 | 30 面试了很多，有一个offer，不过没赶上H1B。我懒，一直没总结，多数问题板上都有。
慢慢更新帖子列出来，不列公司名。
1. 正则表达式匹配字符串，包含 *， ?
2. give u a function IsBad(item) and an array: good, good, .., bad, bad, ...
always bad, find out first bad
3. design a data structure, support 2 functions: Insert and GetMedian.
4. give a matrix, sorted as follow, M[i][col - 1] < M[i + 1][0]
1 3 4
5 6 8
10 14 16
write function: bool Find(int k)
5. linkedin经典format文本题，我居然没复习到，真得给h1b进度逼死了
6. write function: search(keywords). you have invert table, return top10
b... 阅读全帖 |
|
d****o
发帖数: 1055 | 31 怎么会是胡说呢?如果用一个static variable,确实只有一个head。code我都实现了。
当然，你说的那种多个链表确实就不行了。但是这题里面要求也没有多个链表。。。他
也想我把head写在里面。
他其实就是不懂static和pointer of pointer. |
|
h****n
发帖数: 1093 | 32 双向链表很好做吧
先比较指向的元素和要插入的元素，如果大了，则往左走，如果小了往右走，直到找到
合适的位置然后做插入，要注意保存前后指针以便做插入操作
时间复杂度为o（n），由于是链表，没法binary search达到logn的复杂度 |
|
p*****2
发帖数: 21240 | 33 来自主题: JobHunting版 - 问一道老题
成的链表把。。
你的意思是链表每一个元素指向一个数组？ |
|
p*******m
发帖数: 47 | 34 我5月初要去Twitter onsite，面的是 Trust & Safety team
2轮电面都比较简单，2个engineers都很nice.
但听说onsite 难度会明显加大, 而且我网上能搜到的它家的题目不多，特别是onsite,
所以心里没底，来版上求经验。
希望有面试经验的同学能和我分享, 如果不方便帖出来，你也可以我站内发信或者
email: d********[email protected]
这是recruiter给我的schedule:
11:30am 去公司签到, 然后面7个人, 其中有个 team Product Manager。每轮45min,
第1轮是 lunch interview,
7轮分别有coding, Ph.D. research presentation, large-scale system design (这
个是open question)
下面是我搜集到的Twitter的题目，有些版上有过了，给后来的同学作参考。
如果你们有新的题, 也可以回在下面.
希望版上它家的信息能多些
++++++++++++++++++++++++++++++++++++... 阅读全帖 |
|
|
d****o
发帖数: 1055 | 36 y开头的那个
recruiter电面：
概念题：全部是glassdoor上面的原题。强烈推荐把glassdoor所有面经全部看一遍，过
电面没有问题。
电面：
问了reverse string, 还有一个简单得分布式hash的题，掌握分布式hash就可以了。
公司:
1. spell check算法，比如用户输入一个词前几个数，怎么给出后面的建议。
2. min stack，设计一个堆栈，可以在常数时间内得到最小值
3. 一个链表，每个节点除了next指针外还有一个随机指针指向任意节点或者一个字符
串，复制该链表。
4. mapreduce相关题目，了解一下map reduce的概念应该很好答。 |
|
w****x
发帖数: 2483 | 37
不知道链表长度, 过一遍链表然后随机挑选一个节点返回 |
|
w****x
发帖数: 2483 | 38
不知道链表长度, 过一遍链表然后随机挑选一个节点返回 |
|
h******6
发帖数: 2697 | 39 大概10几个fresh graduate一起去，一屋子，一会儿一个人被叫出去面，最后傍晚所有
人面完，所有人在那等着现场知道结果。lz又杯具了，不知道是不是口语问题，因为最
后拿到offer的三个人都是native speaker。题我尽量用中文，自己翻译成英文吧。另
外有个问题如何知道自己哪里做的不够好？因为recruiter从来不告诉你为什么被刷掉
，而lz已经大小面试被刷很多次了。。。
1.说数组和链表的区别，然后有 a-b-c-d-e，如果是保存在数组里，写代码改成badce
；如果是链表，同样写代码改成那个顺序。
2. 有一个结构体，里面存了三个指针，都是指向字符串的，然后写代码把这个结构体
改成marshal structure
3. 好多个分布的节点，每个存有自己的一个value，最后要达到的结果是所有的节点都
知道其他节点的值。给了两个方程，一个是send给某个特定节点，一个是receive自某
个特定节点，一个节点send的时候是block的，后来我才明白意思是send出去之后要等
待receive到反馈，问如何实现。其实就是把所有节点构造成一个树，recursive... 阅读全帖 |
|
I*********7
发帖数: 125 | 40 感觉这题已经是链表操作指针的题目里面较简单的了
链表题还有更多的奇技淫巧 |
|
s********k
发帖数: 6180 | 41 tree还是有优势，比如所有节点都是不同大小的内存块，那么你知道了需要分配的内存
在这个内存树种就只需要logn找到合适的，链表要n，不过实际上大多数内存块都不是
完全任意大小，而是分别在几个不同大小的级别，Buddy system algorithm就是这样。
所以实际上应该是array加链表最合适，简单高效 |
|
b***m
发帖数: 5987 | 42
就是说，你程序本身的内存使用也需要在buffer的范围呢，不能另开一个链表什么的来
管理内存信息。如果需要单开链表，必须在buffer中。 |
|
h****n
发帖数: 1093 | 43 这道题基本上和programming interview expose里面的题差不多
只不过里面的是要求flatten双向链表
我感觉双向链表更好做，占个位置，稍后上代码 |
|
l****o
发帖数: 315 | 44 尽量中文了.
就俩题,很简单.
1.数组加1, 问变成16进制的时候怎么办.感觉像考小学数学...
2.实现encode,decode函数encode的参数是字符串的链表, 返回字符串. decode参数是
字符串返回字符串链表. 最后list.equals(list.decode(encode(list)) |
|
s********k
发帖数: 6180 | 45 这个 内存分配怎么做？像linux的buddy system一样，把free内存分为2,4,8,16,32.。
。大小，然后每块内存做一个链表，alloc时候如果有多余看能不能segmentation分到
小一块的链表上
free之后检查能不能merge到大一块的内存？
list |
|
f********4
发帖数: 988 | 46
原来是这样子啊。。好巧妙的思路。。我当时想的是两个map，一个map原链表的node到
index，另一个map新链表的index到node。。然后人家跟我说你用一个map就行了。当时
大脑当机就是想不明白了。。就按照两个map做了。。ORZ |
|
h****n
发帖数: 1093 | 47 用map的话，确实一个map就行了key为原链表的节点地址，value为新链表的节点地址 |
|
k*******2
发帖数: 84 | 48 来自主题: JobHunting版 - F M面经 报两个面筋，攒个人品：
F：
第一轮店面：以数数的方式压缩字符串，比如111223333变成312243;
第二轮店面:
题目1： 有个很大的integer数组，找出其中值最小的100个element;
题目2： 给出一串前序表达式，比如312*+ 就是3+1*2, 写个方法parse这个表达式；
然后被加了一轮店面：
题目1：就是那个每个数字对应几个字母，给出一串数字，求所有的对应字母组合；
题目2：一个字符串数组，按照anagram进行排序；
结果：三轮之后挂掉。。说我木有很好的交流我的思维。
M：
on campus: 闲聊；
onsite:
面的哪个组就不说了
第一轮：被放鸽子；
第二轮+lunch: 设计一个数据结构(trie)储存字典里的单词，写一个方法来判断给出一
个单词在不在字典中；写出来后让优化；
第三轮：就是那个带一个random指针可以指向任意一个节点的链表，copy给出的链表；
第四轮：循环方式中序遍历二叉树；
第三天被告知挂了。。不给告诉原因。
基本都不是很困难的题目，但是由于刷提不够，所以要达到一气呵成bug free的境界还
有很大差距。。而且没有实习经历... 阅读全帖 |
|
O******i
发帖数: 269 | 49 面官后来反馈说，the best O(1) solution I know so far is to use a trie
真的能用trie达到O(1)么？如何实现？
*******************************************************************
给定一个大整数N,比如N = 100, 有如下的初始有序序列位于[0, N - 1]之间
[0 1] [4 5 6] [9 10 11] [20] [50] [90] [95 96] [98 99]
请设计一个数据结构保存这个初始序列，然后写一个函数，接受一个input参数x, 满足
0 <= x <= N - 1
1) 假如x在该结构中不存在，出错处理
2) 假如x在该结构中存在，返回x之后第一个不存在的数，并把该数写入结构中
例如
x = 8, 出错，初始序列中没有8
x = 5, 返回7， 序列变为
[0 1] [4 5 6 7] [9 10 11] [20] [50] [90] [95 96] [98 99]
x = 4, 返回8, 序列变为
[0 1] [4... 阅读全帖 |
|
O******i
发帖数: 269 | 50 本来想可以化归到区间合并和二分查找的题
比如最初的数据
[0 1] [4 5 6] [9 10 11] [20] [50] [90] [95 96] [98 99]
用区间表示就是
(0, 1) U (4, 6) U (9, 11) U (20, 20) U (50, 50) U (90, 90) U (95, 96) U
(98, 99)
输入x为12, 二分查找12，找不到在任何一个区间内，算出错
输入x为95, 二分查找在区间(95, 96）, 返回97, 97使得区间(95, 96)扩展到(95, 97)
, 然后要和(98, 99)合并为大区间(95, 99)
问题在：
如果要支持二分查找，区间必须连续存放，不能用链表
假如用链表存放区间，又不能二分查找
比如用std::vector存区间，数据不断插入会导致区间扩展和合并，导致区间增加或者
减少，可在vector中间插入和删除一个区间是O(N)的呀，因为要移动别的元素。 |
|
