|
z****e
发帖数: 54598 | 2 随便抓一个人
这个人所有的敌人，都是一边的，标识为敌人以及未遍历过
然后这个人所有的朋友，都是一边的，标识为朋友以及未遍历过
这样就形成了两个大团
然后再挨个遍历未遍历过的敌人，把敌人的朋友找出来
如果没被标识过的，则都标识为敌人和未遍历过的，因为敌人的朋友都是敌人
朋友那个团类似，然后继续遍历未遍历过的敌人和朋友……
如此反复，就跟传染病一样，最后会形成两个对立的大团
然后把剩下孤立的人再用这种方式予以操作
最后会形成一些散落的点
以及n个对立的团
这样通过观察人所在团的关系，就可以得出最后的结果了
o(n)就行了 |
|
z****e
发帖数: 54598 | 3 随便抓一个人
这个人所有的敌人，都是一边的，标识为敌人以及未遍历过
然后这个人所有的朋友，都是一边的，标识为朋友以及未遍历过
这样就形成了两个大团
然后再挨个遍历未遍历过的敌人，把敌人的朋友找出来
如果没被标识过的，则都标识为敌人和未遍历过的，因为敌人的朋友都是敌人
朋友那个团类似，然后继续遍历未遍历过的敌人和朋友……
如此反复，就跟传染病一样，最后会形成两个对立的大团
然后把剩下孤立的人再用这种方式予以操作
最后会形成一些散落的点
以及n个对立的团
这样通过观察人所在团的关系，就可以得出最后的结果了
o(n)就行了 |
|
u***n
发帖数: 21026 | 4 你这样说的话搜索的效率就很差啊
比如若Room 206，中国城市里面有多少个Room 206，你要遍历所有的Room，剔除非206
然后是三楼，有多少个三楼，然后再遍历所有城市的所有小区的三楼，排除非三楼
假设不同省份有同样的县区名字（当然这个很少），你要遍历所有省市的县区名，然后
排除，虽然最后可能就剩下一个省份一个国家对应，但是第一步的话，你就遍历了整个
Search tree的leaves了，效率很低啊。
如果从高到小的话，中国，root节点，然后是上海市,你不需要去遍历其他的省份节点
下的数据了，然后是南京路，不需要遍历其他xx路下的信息了，然后是100号，其他的
号和你没有关系，然后是三楼，然后是206，假设这个是二叉树的话，整个搜索就是5次
搜索比较。
如果这个是5层关系，用先小后大的话，那么第一次你就要遍历2的5次方，3125次
如果这个是N叉树的话，你的搜索比较量要多大啊！！
计算机和语言是两码事情
看看计算机的java包文件结构就知道了
java.net.io.*
还有文件夹结构也是从大到小
如果按照楼上的说法的话，计算机文件夹为什么不倒过来实现，整个硬盘全部是先是文... 阅读全帖 |
|
i*********h
发帖数: 49 | 5 感谢以下文章的作者：
二叉树是面试中的常考题目。而且许多别的题是基于二叉树的，所以我们必须对二叉树
无比熟悉。
经过多日的努力，以下所有的题目主页君全部实现了一次，并且加上自己的理解，所有
的算法都基本最优化过，并且递归非递归都实现了一次。敬请大家指正：
以下是目录，以及主页君的代码
http://weibo.com/3948019741/Bq8XobZFD
1. 求二叉树中的节点个数:
getNodeNumRec（递归），getNodeNum（迭代）
2. 求二叉树的深度:
getDepthRec（递归），getDepth
3. 前序遍历，中序遍历，后序遍历:
preorderTraversalRec, preorderTraversal, inorderTraversalRec,
postorderTraversalRec
4. 分层遍历二叉树（按层次从上往下，从左往右）:
levelTraversal, levelTraversalRec（递归解法）
5. 将二叉查找树变为有序的双向链表:
conve... 阅读全帖 |
|
u********e
发帖数: 4950 | 6 ☆─────────────────────────────────────☆
bobcat2010 (bobcat2010) 于 (Tue Jul 12 10:27:18 2011, 美东) 提到:
熵增加是宇宙中的一个普遍原理，很多人觉得很玄。下面的表格可看成熵增加原理在股
市中的
见证。表格中的数据是我用信息论的方法得到的，恕我不能披露所用模型的构造。
Entropy
S&P500 SIRI
1/2/98 97.54 95.44
1/7/99 97.85 96.49
1/2/01 98.37 97.65
1/2/08 98.87 98.43
1/4/10 99.04 98.29
1/7/11 99.12 98.42
表格中包含了S&P500 与 SIRI 在不同日期的熵值。最大值规整为100。
定性地说，熵值越高，TA的效果越差，熵值若真达到100，所有TA方法都将失效。
SIRI的熵值显然低于指数的熵值。而在我的套利交易中SIRI算是盈利较多的。一般来说
个股的熵值低于股指的熵值，这是做个股的优势。SIRI的熵值曾一度下降，... 阅读全帖 |
|
l********k
发帖数: 14844 | 7 两张牌为例，
第一次抽到某张牌（比如A）；
第二次抽到另一张牌（B）的概率为1/2，遍历，共抽两张牌，牌的顺序是AB
第二次抽到同一张牌A的概率也是1/2，没有遍历，接着抽
第三次抽到另一张牌B，遍历，抽到的顺序是AAB，这种情况出现的概率为1/4
第三次弱仍抽到A，接着抽，如此继续
平均抽牌的次数 = Sigma (某种遍历出现的概率 * 这种遍历需要抽的牌数）
所以对于两张牌来说，平均抽牌的次数为
1/2*2(对应于AB） +
1/4*3（对应于AAB) +
1/8*4 (AAAB) +
1/16*5 (AAAAB) +
...
= 3 |
|
A*********r
发帖数: 564 | 8 链表头要min，是为了计算当前子串的长度？
看你的例子：
s1 = "ADOBECODEBANCBBCAA"
s2 = "ABC"
0，3，5，9，10，12，13，14，15，16，17
刚开始依次遍历到0，3，5， hashtable为
a b c
0 3 5
计算此时的字串长度为5， 保存当前最小字串
遍历到9，10，
hashtable 依次被更新为 0 9 5 --> 10, 9, 5, 最小index变为5， 所以计算此时的
字符串长度为5，不比之前的更小，不用更新最小字串
继续遍历到12, hashtable 变为 10， 9， 12， 更新长度为3
继续遍历到13， hashtable变为 10，13，12，长度一样，不更新
继续遍历到14,15,16,17, hashtable依次变为
10, 14, 12 -> 10, 15, 12 -> 16, 15, 12 -> 17, 15 , 12
长度都没有被更新。。
唯一的问题就是在hashtable中，计算当前字串长的问题，貌似直接算的话需要O(m).
如果在链表头保留了当前hashtable中最小ind |
|
S**I
发帖数: 15689 | 9 ☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:03:00 2011, 美东) 提到:
加recruiter一共6人
4个白男，午饭是一个组的经理 像是 土耳其／印度？ 人
除了最后一个都比较nice
另外每个人有时间都问一遍我RA做的项目，说到想吐
1. java keyword
实现浮点数的平方根，经提醒搞出来了。要考虑小于1的特殊情况； 还要想time
complexity，相对于小数点后精确位数算如何时间复杂度
2. paint fill (toggle)。关键是要考虑space complexity，主要是method stack实时
一共有多少
说了组里的相关一个问题，大概说说TRIE，有一个improvement方法不好答，他说的
用一个计算load balance function，我吐
午饭是其中一个经理，详细讲了下组里的东西，基本和我做的有点相关，感觉他们招人还是很看背景的
3. 给一个数据结构数组，（parent, child）， 重建二叉数，... 阅读全帖 |
|
b********t
发帖数: 2 | 10 第一轮：
印度小哥，先讲project。
实现一个二叉树的类，包含parent节点。
给一个二叉树的任意节点，返回inorder遍历的下一个节点。
刚开始写了返回右子树最左边的节点，后来经提醒补充了没有子树要从parent里找的情
况。中间穿插问了一些java和数据结构的小问题，不难。
第二轮：
白人，kindle组搞测试的，先是自我介绍。
然后写题：给一个string，返回出现频率最高的字符。
先给他讨论思路，问他这些char在不在ASCII范围内，他说good question，不一定。
然后用hashmap写了出来，中间让我解释了一下hash得概念，还有一些小问题记不清了
都不难。
中间遍历hashmap的时候卡了一下，忘了那个KV pair怎么写了，经提醒写出来了，后来
又发现不用遍历hashmap，直接遍历string就可以，然后改正。
最后问了一些测试的问题， 比如刚才是我写的如果输入String为空，就返回null，但
是我的方法返回类型是char，不能用null，后来告诉我可以返回‘\0’(这个我之前还
真不知道。。。)
后来又问我改如何测试，给了几个test case... 阅读全帖 |
|
l****g
发帖数: 5080 | 11 证明的办法是有的，如同证明房间里面没有桌子一样。但，没有人做得到。
因为，上帝不非要在某个房间里，即使在也不非得在人的检测手段可以检测的维度里。
证明的办法就是，遍历宇宙的各个角落，遍历宇宙的各个时间（包括现在，以前，和以
后），遍历宇宙的各个维度，空间，如果有其他宇宙，重复做直至遍历所有宇宙，遍历
各种可能的检测手段，都没发现上帝，然后可以说在你所检测的空间，时间，维度，手
段下，上帝不存在。 |
|
发帖数: 1 | 12 一般都会说这个“唵嘛呢叭咪吽”是 观世音菩萨的六字大明咒，乃至当代的法师
，因为是以讹传讹的缘故，他也会说“唵嘛呢叭咪吽”是 观世音菩萨的六字大明咒，
教我们起心动念言语造作都要真诚、清净、平等。这真是一场大误会啊！其实是有多方
面的错误的。一者、在密续中的《佛说大乘庄严宝王经》中说：“那是观自在菩萨的微
妙本心。”又说：“若有知是微妙本心，即知解脱。”那为什么流传之后而转说它是
观世音菩萨所说的呢？后面会依这本密续的内容，来跟各位作个说明。二者、这个咒语
的真正意思，不是一般人所知道，所以就往往被蒙在鼓里，每持一次咒，就被这个咒语
所密灌一次，那就与罗刹、夜叉等鬼神结缘一次，那真的是替学佛人感到担忧啊！
今天仅就引出这六字咒的密续《佛说大乘庄严宝王经》其中事相上的误谬，来跟大
家作说明，知道密续《佛说大乘庄严宝王经》的误谬之处之后，你就可以明白说，到底
要不要持诵这六字咒？乃至要保存跟它有关的条幅、饰物等等。为什么我刚才说，只提
《佛说大乘庄严宝王经》其中事相上的错误，跟大家来说明？因为这部密续中提到法义
的部分是很少的，在正玄教授所著的《俺蒙你把你哄─六字大明咒揭密》这本... 阅读全帖 |
|
g****s
发帖数: 1755 | 13 班门弄斧一下。
我的思路是可以在Linear时间内解决，先假定有N个Array，而且在每个Array中没有重
复的元素；
1. 做一个Hashmap，以Array[i]为Key，以该array[i]数值在全部N个Array中出现的次
数为Value；再做一个OutArray。
2. 从0到N-1遍历每个Array的每个数值，如果Hashmap里有这个数，则把
修正为.如果表里没这个数值，直接存。
3. 全部Array的全部元素都遍历结束后，任取一个Array0，就取第一个吧，遍历此
Array0，如果某个值array0[j],对应在hashmap里的Value是N-1的话，就说明这个数在
每个Array里都出现过，把这个数存到最终输出的数组OutArray里。
4. 输出OutArray；
=========
以下为简化的思路，无论单个数组里有无重复都可以用。
同样假定N个数组，同样初始化HashMap和OutArray；
1. 先把Array0里的数值放到HashMap里，Value全部设为1；
2. 从1到N-2遍... 阅读全帖 |
|
m********5
发帖数: 17667 | 14 真看不懂平均抽多少张是什么意思
以2张牌为例
两次抽到同一张牌的概率是0.5
但你不能说平均抽2次遍历两张牌
三次抽到同一张牌的概率是0.25,三次遍历两张牌的概率是0.75
你可以给出一个抽牌次数让大家算遍历到的几率，但是不能说平均多少次能遍历所有的
牌。这个平均是什么概念？！ |
|
发帖数: 1 | 15 【 以下文字转载自 JobHunting 讨论区 】
发信人: apprentice00 (数学学徒), 信区: JobHunting
标 题: Didi labs糟糕的面试经历
发信站: BBS 未名空间站 (Wed May 16 15:11:49 2018, 美东)
interviewer的名字叫 Xusheng Sun
非常糟糕 不仅粗鲁无礼 喜欢抢话插话 而且技术很差 脑子不够用
按照约定的时间晚了很多 面试时间本来就不长 晚了既不解释也不道歉
问题问不到点子上 说个什么半天反应不过来
宝贵的面试时间竟然当场用来看我的简历 还看了很长时间 我还得保持安静让他把我的
简历看完 作为面试人 你早干什么去了
不停打断我说话 不停用很傻的 自以为有道理的问题challenge我 解释了他为什么是错
的 还是不停的put words into my mouth
（问题是serialize 的serialize 二叉树） 我说用level order traverse 他说指数复
杂度 必须用别的顺序的方式遍历
我解释复杂度是节点数目的线性函数 硬说是指数复杂度 也是树的高度的指数 但是... 阅读全帖 |
|
发帖数: 1 | 16 【 以下文字转载自 JobHunting 讨论区 】
发信人: apprentice00 (数学学徒), 信区: JobHunting
标 题: Didi labs糟糕的面试经历
发信站: BBS 未名空间站 (Wed May 16 15:11:49 2018, 美东)
interviewer的名字叫 Xusheng Sun
非常糟糕 不仅粗鲁无礼 喜欢抢话插话 而且技术很差 脑子不够用
按照约定的时间晚了很多 面试时间本来就不长 晚了既不解释也不道歉
问题问不到点子上 说个什么半天反应不过来
宝贵的面试时间竟然当场用来看我的简历 还看了很长时间 我还得保持安静让他把我的
简历看完 作为面试人 你早干什么去了
不停打断我说话 不停用很傻的 自以为有道理的问题challenge我 解释了他为什么是错
的 还是不停的put words into my mouth
（问题是serialize 的serialize 二叉树） 我说用level order traverse 他说指数复
杂度 必须用别的顺序的方式遍历
我解释复杂度是节点数目的线性函数 硬说是指数复杂度 也是树的高度的指数 但是... 阅读全帖 |
|
g****n
发帖数: 431 | 17 clarify一下题目：不断从网络接收一个stream，要求判断对于当前接受到的数据，是
否为回文，且当
前接受的数据很大，内存装不下。如果题目是这样：
判断回文至少要O(n)时间，遍历已有数据不能避免，那么可以想办法在必须遍历的时候
，才去遍历。可以
有2个条件：
1. 对于接受到的每个字符，用计数器记录出现的次数。回文的必要条件是所有字符的
个数都为偶数（可以有一个奇数）。
2. 开2个m大小的cache在内存中。第一个保存数据最开始的m个字符，第二个保存最后m
个字符（可以用
环形数组实现）。回文的必要条件是2个cache互为回文。
每接收到一个字符，如果上面2个条件满足，那么遍历整个已有数据，判断是否回文。
如果m开得比较大，
那么浪费的时间会非常小。 |
|
p********7
发帖数: 549 | 18 刚才的算法有问题，不能达到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 |
|
x****9
发帖数: 24 | 19 背景：ECE的MS, 过了online assessment智力题，约电面
电面：一共不到40分钟，只有一个面试官，应该是老印，不过没什么口音，听的比较清楚
首先behavior，where do you hear Bloomberg, why Bloomberg, why this position
然后介绍自己project，面试官问project中用了什么data structure，问的比较细
然后让我比较Link List 和 Array的优缺点，怎么优化Link List的random access比较
慢的缺点
然后是两个算法题，第一个问题找数组中第二大的元素，我先说遍历两遍第一遍找最大
第二遍找第二大，然后又说可以先排序再输出，他问排序的效率多少，我说看算法要么
O（N2）要么O（NLogN），他问那种好，我说第一种只用O（N），他问第一种一遍行不
，我想了想说行只要俩变量就行，然后他让给出大概的代码，pseudo code也成，我就
大概看了看然后直接跟他说代码，要考虑输入如果是0个元素或者只有1个元素输出-1，
否则遍历数组然后输出
第二题是经典0-N少一个数找出这... 阅读全帖 |
|
i**********e
发帖数: 1145 | 20 不好意思，可能破坏你这道面试题了。
假设定义为 general tree 的 postorder traversal 是遍历完current node的所有
children再遍历currentnode。
那么主要的trick是要发现 general tree (GT) 的 preorder 跟 binary tree
representation (BTR) 的 preorder 是一样的。另外，GT 的 postorder 和 BTR 的
inorder 遍历也是一样的。
所以重建树就成为了 BTR 的 preorder 和 inorder.
所以这题主要就利用经典的 preorder 和 inorder 遍历重建二叉树，然后再把 BTR 转化成 GT，不知道说对了没有？
http://www.cs.rutgers.edu/~kaplan/503/handouts/btreconNgentrees |
|
r******r
发帖数: 700 | 21 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
r******r
发帖数: 700 | 22 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
l********7
发帖数: 19 | 23
记录结果实在是不容易。我能想到的方法，
得到所有可能的前序遍历，那么生成树就可以根据前序遍历序列(以及中序遍历)
一棵棵建立了。递归是很难得到所有的前序遍历了，那就迭代吧。
节点 k 作为 根节点， 1...k-1为左子树 (可能为空)， k + 1 ... n为右子树(可能为
空)
h(n) = h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)*h(0)
恩，应该就是卡塔兰数了。
构建树：
依次建立和记录
h(0) -- 空树
h(1) -- 一个点的树
h(2) -- 二个点的树
。。。
h(n-1)
序列h(n) 就可以通过 h(0) h(1)...h(n-1) 来建立了
这里要小心的是， 比如 考虑 h(k) * h(n - 1 - k)
连接序列 h(k) 这个集合和 h(n - 1 - k)时, 序列h(n - 1 - k)中的值都要加上一个
笃定的值, i.e., k + 1
这里的序列链接(* 运算)相当于笛卡尔积。
有错请指出！ |
|
h*******e
发帖数: 1377 | 24 对。。是判断T2 是 T1子树。那个如果普通先序遍历 + 普通 中序遍历我觉得，应该
是不行。。Cracking the code Interview说可以。我觉得 如果 是扩展 先序遍历 反
而不用 中序遍历 就足以判断 T2 是 T1 子树 。 |
|
i*********7
发帖数: 348 | 25 第一题，取mid值即可。因为超过了51%，表示不管这个数字的起始点在哪里，必然过
arr[mid]。
第二题，
设立一个count.初始值为1.
设立一个初始值iter为arr[0]。
然后遍历数组，当遇到同样的数字的时候count++,否则count--
当count为0的时候，重置count为1。iter为当前遍历到的值。遍历完署组织后，iter就
是要返回的数。
第三题，其实和第二题做法类似，但是只需要遍历10%的数组长度（假设知道数组长度
）即可（个人猜想）。理由和第二题类似。
第四题，我不是很明白can not measure the volumn是啥意思。我的猜想是取一定量（
譬如10升）的水（和鱼一起）。看看10升水里面有多少鱼。然后把水抽干。看看总水量
，得到鱼的数目。
第五题。看不懂。。掠过。 |
|
c********t
发帖数: 5706 | 26 lol, 太欢乐了。
prefix tree遍历与普通树遍历有啥区别？为啥让你写树遍历，你写个二叉树遍历？ |
|
e****e
发帖数: 418 | 27 来自主题: JobHunting版 - 请教一道题 有点明白了,谢二爷解释.
当遍历到13的时候，map的样子(仅显示相关的pair):
15 -> {15, 15}
12 -> {12, 12}
14 -> {14, 15}
遍历完13之后是什么样子？
遍历完11之后是什么样子？
如果还有一个数是16, 遍历完16之后是什么样子？ |
|
d******l
发帖数: 98 | 28 第一题,我用java作： 只需要遍历一次就够了 O（n）time
首先，定义一个Node head=null, runner=null; int value=carry (进位1 or 0)
接下来用while循环遍历
while(N1!=null && N2!=null){
定义一个新的临时 Node. Node temp=new Node(); //先做个位数节点，第二次遍历
是 就是 十位数节点...
再为遍历作下工作：Node next1=N1.next; Node next2=N2.next;
如果N1 N2 不为null， 把value+=N1.data; value+=N2.data;
if(value>=10) carry=1; else carry=0;
temp.data=value%10; //这是取个位数
接下来按数序插入高位的Node （十 百 千 万位 递增顺序）
if(head==null){ head=temp; runner=head; }
else{ runner.next=temp； runner... 阅读全帖 |
|
g*****g
发帖数: 212 | 29 电面2似乎本版讨论过几次了，我还贴过code。基本就是 high和low boundary一次遍历。
onsite 1： 楼主回家后的思路是对的
onsite 2：
1）前->末遍历 记录到目前位置，使用过的 digit
2）末->前遍历 对每一个数字，查找是否存在，大于自己切未使用的数字，如找到，
break
如果2）到了头，且头是9，需要进位
3) 从break的位置开始-》末遍历，依次选取最小且未使用的数字
string next(string input)
{
int n = input.size();
vector v(10, 0);
// step 1: set used digits
for(int i=0; i
{
v[input[i]-'0'] = 1;
}
// step 2: find bigger unused digit at cur pos
int i= n-1;
for(i=n-1; i>=0; i--)
{
... 阅读全帖 |
|
x********u
发帖数: 1150 | 30 层次遍历, queue里面只有一层的nodes. N很大的时候, N个节点的group还没形成, 有
些点就被poll out了.
觉得就用DFS的遍历, 遍历过的点存起来, 满N了, 就生成一个新树的节点.
直到DFS遍历完老树. |
|
w**********h
发帖数: 31 | 31
Map里面存个list就行吧，把所有重复的index都存进去。不知道你说的遍历所有diff怎
么做，复杂度多少？
这是我的思路， time复杂度为O(L),L 为字符串长。
只考虑有difference的index,否则交换无意义。交换后最多可以使difference减少2，
最少是0.
1.遍历s1，构建一个Map>.key 是s1的字符，value是s1包
含该字符的所有index.
2.遍历s2,如果map.containsKey(s2.charAt(i))， 遍历map.get(s2.charAt(i)), 其中
每个index记为j. 尝试swap(i,j),看difference 减少多少（至少减少1）. 如果发现减
少2的，返回。 |
|
l*3
发帖数: 2279 | 32 我认为应该这么做：
考虑这么一个类似的问题：
m x n 的0 ， 1矩阵，要求：
对于每个 "1", 把以这个 “1” 为左上角，以其位置 + (k,k) 为右下角的正方形内所
有点涂色。 要求复杂度 O(m x n)
再说具体一点，我们考虑一个新的问题，这时候对于每个 “1” , 假设位置在 (i,j),
不是要求涂曼哈顿距离了，而是要求 涂 满 (i,j) 为左上角 和 (i+k, j+k) 为右下
角的正方形。
这个问题有什么好处呢？且看如下图形（对应 k = 3 的情形)：
3 2 1
2 2 1
1 1 1
如果我们把原先矩阵里面的每个 “1” 都换成 k，然后用 “从左上角开始，以矩形圈
的方式往外扩散（具体参见上图中 "1" 的位置 对应的圈）” 的loop顺序对当前点右
方和下方最
邻近的三个点进行值的update就行了。在当前的 (i,j)位置时，需要update (i+1,j) (
i,j+1) 和 (i+1,j+1) 的值， update方法就是，如果新的点的值小于 "(i,j)位置的值
-1" 时，那么就把他update成 "(i,j)位置的值 - 1"。 ... 阅读全帖 |
|
a**********0
发帖数: 422 | 33 interviewer的名字叫 Xusheng Sun
非常糟糕 不仅粗鲁无礼 喜欢抢话插话 而且技术很差 脑子不够用
按照约定的时间晚了很多 面试时间本来就不长 晚了既不解释也不道歉
问题问不到点子上 说个什么半天反应不过来
宝贵的面试时间竟然当场用来看我的简历 还看了很长时间 我还得保持安静让他把我的
简历看完 作为面试人 你早干什么去了
不停打断我说话 不停用很傻的 自以为有道理的问题challenge我 解释了他为什么是错
的 还是不停的put words into my mouth
（问题是serialize 的serialize 二叉树） 我说用level order traverse 他说指数复
杂度 必须用别的顺序的方式遍历
我解释复杂度是节点数目的线性函数 硬说是指数复杂度 也是树的高度的指数 但是如
果用其他方式遍历 同样的复杂度啊 做serialization难道不要把所有节点都遍历一边
任何顺序都要遍历一边 任何方式复杂度相同啊 这点都理解不了 而且我解释了好几遍
还理解不了 didi labs雇的人白痴啊
从来没有这么烂的面试经历 真的很烂 didi lab... 阅读全帖 |
|
h***a
发帖数: 1773 | 34 【 以下文字转载自 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 | 35 //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表示，有的坐标上
有障碍），给定起点和终点，找... 阅读全帖 |
|
m**c
发帖数: 7349 | 36
你先假设机器可以遍历，然后引用了阿发狗的思路。这就有点问题了。
阿发狗思路的前提就是假设机器不能遍历。Nature那篇paper上来就说
"In large games,such as chess and especially Go, eexhaustive search is
infeasible"。然后阿法据此步步优化。
回头来看，假如可以遍历，再假如是两台机器都遍历，我估计每一步都差不多50%,都在
阳光之下了。这跟掷硬币没啥区别了嘛。 |
|
s**********o
发帖数: 14359 | 37 【 以下文字转载自 JobHunting 讨论区 】
发信人: rongxuer (蓉儿), 信区: JobHunting
标 题: 如何秒杀99%的海量数据处理面试题
发信站: BBS 未名空间站 (Thu Apr 5 02:08:57 2012, 美东)
海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的... 阅读全帖 |
|
a********e
发帖数: 16 | 38 哈佛数学系150年 从三流学系到世界中心
丘成桐
哈佛大学 香港中文大学
最近我与我的朋友Steve Nadis写了一本关于哈佛大学数学系历史的书， 由哈佛大学出
版社出版。
这个写作计划开始时，我还是哈佛数学系主任。我对于这个系伟大先驱者的人生颇感好
奇。因为其中有些人藉着他个人的研究甚或透过他们的学生，改变了整个世界数学发展
的路径。
如果其他地方的人，能懂得欣赏这些数学家如何做研究，如何建立起这个优秀的学系，
而且在这段过程裡，还协助建立了哈佛大学的地位，我认为这会是很棒的事。更何况，
这些伟大哈佛数学家的个人轶事，读来也饶有兴味。
我喜欢阅读数学史，认为好数学家需要知道数学的重要概念如何演进。这些概念的演进
充满了生命力，就像从初生婴儿慢慢长大成人的过 程，这段路可能很戏剧化，而且充
满了兴奋与刺激。一旦我们了解数学发展的根源，就更能理解当今数学的发展。我相信
，哈佛数学系从 一个三流学系成长为世界级领导中心的过程， 提供了很值得参考的个
案，或许可以协助许多想建立世界级数学系的大学做为借鑑。我非常感谢我的合着者
Nadis，他做了十分广泛的研究，并採访了许多哈佛的教师与校友。... 阅读全帖 |
|
a*****3
发帖数: 601 | 39 有人在吗？问个傻瓜问题： 如何用双set语句实现 nested loop?
也就是从dataset1 第一条记录开始，遍历dataset2所有记录；
从dataset1 第2条记录开始，遍历dataset2所有记录；
从dataset1 第3条记录开始，遍历dataset2所有记录；
从dataset1 第4条记录开始，遍历dataset2所有记录；
。。。。
给各连接也行。 我找到一片
http://www2.sas.com/proceedings/sugi23/Begtutor/p50.pdf
似乎没看太明白。 |
|
t******g
发帖数: 4044 | 40 老兄，我不是要找十个数加起来是1，那求和然后归一就好了。但这样生成的十个数是
有bias的，很多情况是遍历不到的。
我要的一个算法能大量生成这十个数，例如生成100万组十个数，并且尽可能均匀遍历
整个空间。我也并不是一定要一个0.99，其他所有数加起来0.1，只是举个例子，很多
可能性组合是很难遍历到的。 |
|
s***h
发帖数: 487 | 41 平均和遍历就是个 illusion 而不是 solution 。。。
: 说你不懂还不服，不能遍历当然就不对，分子动力学模拟是希望对通过对轨迹求
和来模
: 拟配分函数，如果达不到遍历，只能是相空间的一个子集，根本得不到真正的的
系综平
: 均。
|
|
c*********t
发帖数: 2921 | 42 1. 如何用iterative 的方法实现postorder遍历binary tree？
recursive的方法太简单了。
好像inorder, preorder的iterative比较容易用stack就行了。可是postorder,我想不
出好的方法。谁能给个pseudo code?
2. 给定postorder 和 inorder遍历的结果，想个算法还原出binary tree.
3. 给定preorder 和 inorder遍历的结果，想个算法还原出binary tree.
我有三个包子，谁给回答对，就发包子给谁，一个包子一题。
给出pseudo code就行了。
谢谢！ |
|
p********7
发帖数: 549 | 43 同时遍历2个树，如果一个树比如是A节点小于另外一个树B的节点，那么就把这个小的
加在另外一个树节点的左边。然后再接着遍历A的下个节点，这个节点比上个节点大。
如果这个节点仍小于B的第一个，那么就把它加入B的左节点；如果比B第一个大，那么
就继续遍历B的第二个节点，看是不是比第二个大，直到在B的2个节点大小之间的时候
，然后插入。 |
|
m******9
发帖数: 968 | 44 我的思路是这样的
1. 把new range [8,28] dump到数组A中，使得A[index] = index, 如果没有出现的
value，则设置为-1，即：
分配一个size=29的数组，[8,28]dump到该数组的结果就是：
A[-1,-1,-1,...-1,8,9,10,11,.....28]
2. 一次遍历list of ranges, 凡是能够在A中能够找到的value全部都设定为A[index]=
-1.
例如：对比[6,10]时， A[6]=-1, A[7]=-1; ... A[10]=-1
这样把整个range都遍历完
3. 再次遍历数组A，将A[index]!=-1的全部打印出来 |
|
d*******8
发帖数: 785 | 45 周三接到了意料之中recruiter的Email据信，为了攒Rp，写下面经
面的是VOD Team的SDE，是版上一个大哥贴的Opening 他帮忙Refer的,多谢这位大哥
HR效率工作超快，第二天就打电话约电话面试，两周两轮
是我开始找工作的第一个电话面试，然后很幸运
拿到了onsite，不过onsite的时候还是失败了，挺可惜的，还挺喜欢西雅图的，
电面一，
自我介绍，一些通常的问题 why amazon等
编程语言问题，对简历上列的语言全部自我评价，说优缺点
C++技术问题， virtual function的实现， OOP的特点。
Python和C++比较的优缺点
技术问题问了一堆，感觉自己答得很罗嗦，教训是一定要答简洁，节省时间给下面的
常见算法题一道，去掉一个数组中重复奇数次的数
hashtable, first sort and scan
写Hashtable的程序，念给他听， 后来他说Hashtable直接用整数当Key空间太大导致
后来的遍历时间比n大得多， 改进， 当时我没想到map到另一个数组里。
电面二
就一道restuarant reservation sy... 阅读全帖 |
|
g**********1
发帖数: 1113 | 46 先把数除3，遍历result1 to 9,然后这个过程中，把（total- count）/2,遍历
result2 to count.也就是说，先确定最大的数的范围，然后确定其次大的数的范围，
然后随便遍历一下，就都出来了，可以把结果存在一个2维数组里面。 |
|
i********s
发帖数: 133 | 47 这个解法是递归的，空间不是常数吧。需要树高(logn）的栈。
而且时间复杂度也不是log(n)的。一种情况是p,q分别在树根的左右两边，而p需要遍历
完左边的所有节点才知道。q需要遍历所有右边节点才知道。
所以复杂度至少是遍历所有节点。 |
|
h**6
发帖数: 4160 | 48 我的解法是这样的，需要五个辅助矩阵: H, L, Lx, R, Rx, 大小都为n*m，与原矩阵X
相等。
H中记录当前点向上连续1的个数，或者称为当前最高一字柱的高度。
L中记录当前点向左连续1的个数。
Lx中记录当前最高一字柱向左最远延伸到的位置。
R中记录当前点向右连续1的个数。
Rx中记录当前最高一字柱向右最远延伸到的位置。
最后再遍历一遍，求出每个点对应当前最高一字柱向左右延拓的面积，最大值就是最大
矩形面积。
S = H(Rx-Lx+1)
优化方法：
第一次遍历可以求出H, L, Lx
第二次遍历可以求出R, Rx, S
每个矩阵只需要保留当前行和上一行，复杂度是O(2m)*5 = O(10m) |
|
g****n
发帖数: 431 | 49 对，确定一颗二叉树（你题目里也没说一定是二叉树）需要包括中序遍历的至少2种遍
历。
我想对于n叉树的一种解法是：
假设判断A树是否为B树的子树，每个节点用正整数编号，并且unique。预处理：A，B每
个节点计算一个sum，sum=子树节点值的和。对于B的每个节点x，如果sum=A树的sum，
则从这个节点开始遍历子树，同时开始遍历A树，比较每个节点的sum值。如果出现不等
的值，则返回。如果全部相等，则A是B树中x节点的子树。
算进预处理时间，这个方法的时间是O(N)，N为A，B树节点数之和。 |
|
p********7
发帖数: 549 | 50 应该还需要加一个判断
2 2 2 1 0 1 表示从这点到右，以及到下都是1 的数量 B2
2 5 1 3 1 1
1 1 0 1 0 1
0 3 1 1 0 1
2 1 0 1 0 1
1 1 1 1 1 1
在遍历C【I，J】的时候，需要算2次，一次是先找min(B1[i,j],B2[i-B1[i,j]+1,j-B1[i,j]+1]);如果这个值是等于B1【i，j】那么就更新C【I，J】。如果是小于的，那么就不变。
然后再算min（B2【I，J】，B1（I+B2[I,J]-1,J+B2[I,J]-1））如果这个数等于B2【I，J】那么就更新C【I+B2【I，J】-1，J+B2【I，J】-1】
其实我在遍历C【1，1】的时候已经得到C【5，5】 = 5；当遍历C【5，5】获得的数是2，其实是小于6的，所以无效，就不更新了。
你这个例子C【3，3】获得是2，是小于B1【3，3】==4的，所以无效。
B2 should be
2 1 0 1
1 0 0 1
0 0 0 1
1 1 1 1 |
|
