s********u
发帖数: 1109 | 1 首先lz你用的应该是老版本的书，新版都没这道题。
我看到题目之后的思路是，先sort，然后是用两个index或者两个指针，一个i匀速往后
遍历，另一个j匀速运动且碰到重复就往后跳。
str[i++] = str[j++];最后根据i的位置resize string。
应该没有o(n)的做法吧，除非用bitset。
每次碰到重复都删除的话，哪怕是用hash table存，看起来是一次遍历O(n)，但挪动起
来相当于是O（n^2)了。所以一定用覆盖来做这个事情，最后一起把尾巴去掉就行。 |
|
|
L*********g
发帖数: 8 | 3 自己维护堆栈遍历（non-recursive）时，需要标记已处理过的node, node class应该
加一个标记的属性。否则很容易陷在push, pop node中死循环。
请参考深度遍历的实现。 |
|
J****3
发帖数: 427 | 4 攒人品
From MITBBS:
1. 给一个二叉树 返回镜像 (Binary Tree Mirror)
2. Implement a thread-safe blocking queue.
3. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
4. 给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？我先说
HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。不知道
还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING ALGORITHM
好象不是很合适吧。
5.后缀波兰表达式STRING转换为中缀表达式的STRING。
这题本来很简单，但我可能算错了。纠结的地方是a,b,+,c,/
到底是 (c/(a+b)) 还是 ((a+b)/c)
6. Implement pow(double a, int b)
7. 接着给Amazon的favori... 阅读全帖 |
|
n****e
发帖数: 678 | 5 仔细看了一下code，
有几个问题：
1， Collection只能遍历一边，第二次遍历就出错了。
2， 这里没有iterator的 implementation。 如何用c++实现iterator |
|
n****e
发帖数: 678 | 6 仔细看了一下code，
有几个问题：
1， Collection只能遍历一边，第二次遍历就出错了。
2， 这里没有iterator的 implementation。 如何用c++实现iterator |
|
P**H
发帖数: 1897 | 7 遍历,是prime就hash,不是prime就遍历hash.N^2,如果prime个数的增长和N线性.只能想
到这个. |
|
D******y
发帖数: 316 | 8 半夜收到邮件被拒了，还是写一下，不知道有没有最近面的朋友。
第一轮phone一个国人大哥，白板写了binary search跟design sudoko，感谢一下！
第二轮phone是原题，spiral matrix那个，然后implement一下factory的design
第三轮phone是个态度巨差的三哥，各种打断+不回答我问题。。反转链表跟leetcode上
面那个sort color，此外问了些多线程的概念题，mutex vs semaphore, process vs
thread之类的
第四轮phone两个array找并集，还有implement了singleton的design，问了些基本的
java问题，np hard vs np complete，概念题记不大清了
然后就是onsite了，
第一个人string to integer，基本上只考虑小数点的情况，scientific跟overflow都
不用考虑，还有一个是given tree结构只有一个parent的pointer找first common
ancestor
第二个国人大哥问了我以前做的project... 阅读全帖 |
|
q*******d
发帖数: 49 | 9 搞个hashmap,前n-1个链表挨个遍历一遍，用hashmap统计每个node出现
次数，最后一个链表遍历的时候每个node都在hashmap找value，如果value==n-1,那么
这个点就找到了 |
|
N********g
发帖数: 132 | 10 这个办法不一定能找到啊，比如这个情况：
1-2-3-4-5
6-2-3-4-5
3-7-8-4-5
用前两个做成hashmap，再遍历最后一个链表，结果3是第一个符合value==n-1条件的。
可见条件必要但不充分。
这样行不行：先把所有的链表都reverse一下，然后从头开始一起遍历，找到第一个不
一样的node，那么上一个node就是meet的地方。 |
|
q*******d
发帖数: 49 | 11 搞个hashmap,前n-1个链表挨个遍历一遍，用hashmap统计每个node出现
次数，最后一个链表遍历的时候每个node都在hashmap找value，如果value==n-1,那么
这个点就找到了 |
|
N********g
发帖数: 132 | 12 这个办法不一定能找到啊，比如这个情况：
1-2-3-4-5
6-2-3-4-5
3-7-8-4-5
用前两个做成hashmap，再遍历最后一个链表，结果3是第一个符合value==n-1条件的。
可见条件必要但不充分。
这样行不行：先把所有的链表都reverse一下，然后从头开始一起遍历，找到第一个不
一样的node，那么上一个node就是meet的地方。 |
|
c*******7
发帖数: 438 | 13 这类问题就是N个set求找到两个set使其中的共同token数最多。共同点就是某个token
是否在某个set中的lookup时间为O（1）。假设每个set的size为k
两两比较的方法：对于每个set的每个token，在剩余set中查找是否存在。时间复杂度
为O(k*n^2)
逆向index的方法：对于每个token，建立一个index set，放入到一个map里，这一步需
要遍历所有token，O(n*k)。再建立一个n*n的matrix, 遍历一遍前面建立好的index
map，update matrix里面对应的common token count。worst case 也是O(k*n^2),但是
average 应该会比前面的方法好一些。 |
|
h******6
发帖数: 2697 | 14
就是假设我们现在在a1[i] 然后我遍历a2到a2[j]==a1[i]的话 我swap(a2, i, zero);
zero=j;swap(a2, i, j);其中zero负责记录值为0的位置的index
他让改进 然后我就先扫一遍a2用hashmap记录每个数值的index 这样后面就不用遍历来
找某个数值的index了 |
|
s********f
发帖数: 510 | 15 是不是每个node除了有next之外还有parent和child?
那样的话,保持一个tail指向最后一个节点, 然后从head开始遍历整个list,碰到一个
node有parent(child)就把tail指向parent(child),然后update tail还是指向最后一个
节点.
当遍历结束后,就flatten了. |
|
g****s
发帖数: 1755 | 16 UP楼上， ：）
第一题算是KMP/heap sort; 建一个容纳K个数的Heap，遍历数组，遇到某个值小于Heap
目前最大值的和时候update heap;一次遍历就可以了。
第二题Leetcode原题：两个hashMap 一个toFind() 一个alreadyFound; 再建个Queue存
储string里每个在alphabet里的字符对应的index; alreadyFound找到满足每个
alphabet出现次数的时候，从queue里poll()出此次subString的超始点。时间上一次遍
历就结束了O(n)。 |
|
h****2
发帖数: 46 | 17 我刚开始写的是N^2遍历单词的解法，后来他说可以稍微改进了下
我就说可以先把每个单词处理下，用map记录出现的字母（其实遍历单词的话还是要n^2
的），说了以后他貌似还比较满意，感觉他没想要我写出太高级地方法来｀～
max |
|
l********s
发帖数: 358 | 18 为什么不能遍历，遍历的复杂度又不是O(2^n) |
|
x******0
发帖数: 178 | 19 来自主题: JobHunting版 - 问个G题吧 如果是必须知道精确的indegree，图中每个点都要遍历吧，这样只有遍历的时候维护一
个indegree的hashtable吧。 |
|
r*******2
发帖数: 104 | 20 一周之内面了微软两个组，刚刚收到结果双双悲剧，一个组的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轮：一个小黑Lead II带去一起lunch，午饭之后问了大概半小时设计题，设计当软
件窗口（比如Word窗口）大小变化的时候每个子图标栏的大小如何变化，大概定义了一
下各个class，挑了其中一个function写了code。
第4轮：一个三哥Principle Lead，先问了一个ASCII和Kanji字... 阅读全帖 |
|
r*******2
发帖数: 104 | 21
好的，我把我的解题过程也说一下。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原题就不说了。
第... 阅读全帖 |
|
|
|
m****9
发帖数: 492 | 24 用图的遍历可做，找largest strongly connected component. 反正各个点都只有一个
degree，BFS/DFS都一样。
用python写个:
visited=[0 for i in range(n)]
max_loop_number = 0
k = 0
for i in range(n):
loop_number = 0
while visited[i] == 0:
loop_number += 1
visited[i]=1
i = A[i]
if loop_number > max_loop_number:
max_loop_number = loop_number
k = i
return k
每个点都只遍历一遍，时间theta(n) |
|
z***y
发帖数: 73 | 25 祝福lz！
1.相当于每次产生一个bit，运行k次，保证2^k >= n，如果超过n就重新运算，否则就
返回；
2.可以用一个stack吧，碰到*/操作立马计算，完了以后再处理一下剩下的+ -；
3.用hash table吧。如果对象都只是一个字符，那么char table[256]即可。遍历相等
的串，把相等的元素设置成同样的值。然后遍历不等的串，取值出来比较即可。 |
|
d**k
发帖数: 797 | 26 他不需要遍历整个
只要记住当前的遍历到的位置就可以
DFS |
|
z**a
发帖数: 69 | 27 已跪，回想我的这次onsite经历，那就是一个joke啊，浪费了我的时间，也浪费了面试
官的时间。还浪费了我一天PTO飞过去。
第一轮，关键词，无厘头。开始先各自寒暄了几句，天真的我没有想到后来的尴尬。第
一个问题是：“如果有一个大文件，只有小写的（关键）的a-z（关键），那么怎么压
缩这个文件呢？”我是最近看大数据的东西看得有点太投入了，上来就说把文件分段，
hash每段，有个server专门存内容，bla，bla…，他问，那怎么恢复呢，我说每个文件
最后表现为一串hash key，恢复的时候按hash key找到存放的位置就行了。他没说啥，
我意识到这不是他想要答案，不过我最后才意识到这其实都不是想要问的问题。。。为
了引导我，他举了个例子说比如：abcd…z重复了一百遍。这你怎么存呢？当时我有点
懵了，我说：”这不就是存个abcd…z，然后存个100不就得了？”，他又问还有“怎么
恢复“，我老实点的说：”有多少遍，恢复的时候写多少被“. 他接着说：”abcd…z
100遍不是连续的呢？“我以为他说的是先50遍在这，后50遍在那，虽然我现在感觉有
点地方不对劲了，也只有硬着头皮说，... 阅读全帖 |
|
n**d
发帖数: 26 | 28 第一题貌似要返回个vector之类然后判断是否输出当前节点？
第二题
设树A树B
（可考虑预处理先获得树A树B的size以及高度等info)
遍历树A，构建unordered_map
之后通过树B的节点数量和高度信息访问上述数据结构，试图匹配？
遍历树B... |
|
r*******k
发帖数: 1423 | 29 来自主题: JobHunting版 - 一道面试题 二叉查找树？
那样就遍历树，只输出大于p小于q的叶子就行了吧
二叉树的话
是不是采用任何一种遍历方式，只输出叶子，
且当碰到p之后才开始输出
碰到q，就返回 |
|
g***j
发帖数: 1275 | 30 来自主题: JobHunting版 - 一道面试题 是对的
可惜那有很多不需要的遍历
比如p是root的左子树的最右叶子，q是root的右子树的最左结点。
如何减少不需要的遍历呢？ |
|
r******y
发帖数: 780 | 31 用一个hashMap来辅助，key是column number， value是一个list.
假设root的col是0，从root开始往下遍历，
左节点如果存在，col为root_col-1, 更新hashmap;
右节点如果存在，col为root_col+1, 更新hashmap;
遍历完，对hashMap的keys排序，然后从小到大输出对应key的每个list
用你的例子测了下，输出OK。 |
|
p****6
发帖数: 724 | 32 先遍历, 边遍历边给每个节点一个index, 比如root为0, 做left减1, right加1. 然后
建立一个HashMap, key是index, value是list
贴个java版本的
public List> printVertical1(TreeNode root){
List> res = new ArrayList>();
if(root == null)
return res;
Map> map = new HashMap
TreeNode>>();
getVertical(root, map, 0);
Set keys = new TreeSet(map.keySet());
... 阅读全帖 |
|
r*******k
发帖数: 1423 | 33 第一个，转化完了，正好是排了序的双向链表
标准2sum的解法
转化最简单的方法，中序遍历，存到一个list里
然后遍历这个list，改left和right指针 |
|
a*****y
发帖数: 22 | 34 看了大家的回复，得到启发，思路如下：
遍历两遍：第一遍确定如下情况：
1， 新区间可以被原有的某个区间包含，直接返回
2， 新区间与原有的区间都不相交，push_back，返回
3， 相交，又分为两种情况：（1）新区间完全覆盖原有某区间，将改区间置为无效（
opening > close） （2）部分相交：更新新区间的头或尾，将原有的那个区间置为无效
第二遍遍历，删掉标记为无效的区间
总时间复杂度为O（n）
struct Interval {
int opening;
int close;
};
void MergeInterval(std::vector& org, Interval new_interval) {
int n = org.size();
if (n == 0) {
return;
}
bool is_intersected = false;
for (int i = 0; i < n; ++i) {
if (org[i].opening <= new_interval.opening) {
... 阅读全帖 |
|
r*******k
发帖数: 1423 | 35 heap就是2个数组
如果连这个都装不下，又怎么算中值？
至少得遍历一遍吧？
除非知道数的范围，碰到最大最小值可以删一对
否则没办法减少空间要求吧
要不用bucket统计一下，能猜出中值在哪个bucket里
然后等于是求那个bucket的第k个值
要遍历数组2遍 |
|
k****t
发帖数: 184 | 36 坐标系中， 一个点P(x0,y0), 若干直线y=kx+b；
附加条件，在[0,x1]之间，这些直线不相交。
给出个算法找出离P最近的2条直线.
我给出了算法后烙印加了句，你这还是要遍历所有直线，想个算法不用遍历所有直线。
我没想出来。挂了。
不知道怎么发图片，图在下面链接里。
[IMG]http://i61.tinypic.com/2cne6ug.png[/IMG] |
|
m*****1
发帖数: 147 | 37 如果不想全部遍历，怎么都要先sort吧？ 但是加上sort的时间复杂度还不如直接遍历
呢。 |
|
r*******k
发帖数: 1423 | 38 不加信息是不可能的啊
如果有n个node，求第n个数，
你不遍历前n-1个数，你怎么知道哪个是第n个？
必然是o(n)啊
想到做lgn，必然不会遍历所有的，
剪枝需要额外的信息 |
|
l*********b
发帖数: 65 | 39 应该是假设A unsorted吧 有个不太好的思路 需要大概O（n）时间 和O（n）空间 但是
感觉空间还可以优化 我先说下思路：
把1-N所有N个数放进一个set 然后遍历A数组 假设A = {6,7, 9,2} (是不是A里要是有1
就可以直接返回0了) A[0] = 6， 所有就把6从set里删除（在6 < n的前提下）。。然
后 遍历所有6的倍数 知道这个倍数大于N了 就结束 继续下一个。。
好吧。。时间复杂度好像不止O（n - -|||） |
|
y***e
发帖数: 32 | 40 给定一个2D board B，一个dictionary D和一个初始坐标pair p，返回所有
从这个初始坐标开始的词（要求每一词必须在dictionary里）。例如：
B =
[
["APPL"],
["DMCE"],
["AINE"]
]
D = "APPLE", "ADMIN", "BOY"
p = {0, 0}
返回"APPLE", "ADMIN"
非常类似leetcode上的word search。一个额外的问题是如何优化。这个问题主要针对
在对B搜索的时候，从初始坐标开始，可能要遍历所有其他坐标点，非常不efficient。
问如何避免遍历所有其他坐标点。 |
|
g********t
发帖数: 212 | 41 N^2似乎免不了
我曾经想过自己做一个很smart的pair的iterator，让一对pair可以变成按和的大小顺
序遍历那种，再加上一些加减取负数操作，把这个问题转成一个排序好的pair list和
一个integer list的集合求交的问题。
然后发现那个pair list的遍历，光是数量级上还是会有N^2，所以没有带来量级的优化
，那么就建跟(sum->pair_list)的hash差不多。（可能hash的空间是节省了）。
最后我的答案还是建sum->pair_list的hash.然后中间有一些小细节还可以优化。有的
细节没有想到是面试官提醒出来的。估计也还是比较看push到了你的knowledge
boundary之后，你怎么通过沟通继续优化吧... |
|
g********t
发帖数: 212 | 42 N^2似乎免不了
我曾经想过自己做一个很smart的pair的iterator，让一对pair可以变成按和的大小顺
序遍历那种，再加上一些加减取负数操作，把这个问题转成一个排序好的pair list和
一个integer list的集合求交的问题。
然后发现那个pair list的遍历，光是数量级上还是会有N^2，所以没有带来量级的优化
，那么就建跟(sum->pair_list)的hash差不多。（可能hash的空间是节省了）。
最后我的答案还是建sum->pair_list的hash.然后中间有一些小细节还可以优化。有的
细节没有想到是面试官提醒出来的。估计也还是比较看push到了你的knowledge
boundary之后，你怎么通过沟通继续优化吧... |
|
n******7
发帖数: 99 | 43 我想的是用preorder遍历树，纪录下经过的节点，遇到叶节点O(1)打印出path。这样等
于遍历树的时间复杂度O(N). 不知道哪里想错了...求指点... |
|
i*********7
发帖数: 348 | 44 这一题大部分人应该都知道是用BFS解。
我只是想自己试验一下DFS的解。
DFS解如果要避免TLE，重点在于需要截枝和截枝后的答案更新。
这就是我自己新建一个class和对应的HashMap去记录进行截枝。
我的观念是这个样子的，在遇到重复出现过的节点单词的时候，首先考虑的是这个节点
往下遍历过后是否出现过解，如果没有的话只有两种情况：1，这个节点往下走是没有
解的。（在不变回去的情况下）2.变回去了。 这种情况下都当做无效访问往上一层走。
如果有的话，就比较该节点之前有解的情况下它所居的递归层数是否比当前重复访问的
时候深，如果否，则不更新，如果是，则根据层数差来修正结果。这相当于把之前遍历
过的结果默认放在这一层下面了。
好吧，问题来了。。这个解只能过leetcode 80%的cases。在一个字典很大的case中比
Expected answer多了1. 有没有人能告诉我听我的代码或者逻辑问题出在哪儿了？=。=
class DataSet{
int level, res;
DataSet(){
level = 0;
... 阅读全帖 |
|
h***k
发帖数: 161 | 45 遍历hashmap的entry就是把array从头到尾扫一遍吧，list的contains是全部扫一遍找
到对应的为止吧。
都是O(n), 这里的遍历hashmap不存在查找的问题吧。。请指教 |
|
z*****u
发帖数: 51 | 46 我的想法是，用hashmap保存array 1里面的数字，按照array 2里面的顺序，这样需要
先遍历array 2一遍，然后遍历array 1一遍
|
|
c*********t
发帖数: 171 | 47 我对（2）的解法：
1、首先如（1）计算每个句子的hash，保存入一个文件并排序
2、遍历全部句子并提取所有单词
3、遍历所有句子，尝试每个单词加在头或尾，计算hash，在排了序文件中二分检索是
否有此hash，如有则这两句子符合满足要求，输出
此算法复杂度为O（句子数xlog句子数x单词数），但当句子数很大时，因为单词有限，
所以是O（句子数xlog句子数）
two" |
|
z***y
发帖数: 73 | 48 首先将问题分解一下:
1.一个点是否能通向海洋?
2.一个点是否能通向邻居节点?
那么目标就是找到:
1.一个点可以通向他四个邻居节点,并且四个邻居节点都可以通向海洋.
大致解法就是:
1.首先建立一个矩阵保存状态,一个节点的状态有三种:
a.初始化,还没有处理过;b.可以通向海洋;c.不能通向海洋.
2.然后我们遍历原始矩阵:
2.1.如果当前节点值为0,那么设置此节点状态为b,同时设置此节点右和下邻居状态为b;
2.2.如果当前节点状态不为a,说明处理过,那么不用处理;
2.3.如果当前节点值不为0,且未处理过,循环查找邻居节点状态:
2.3.1如果当前邻居节点不可达,跳到下一个邻居节点;
2.3.2如果邻居节点可达:
2.3.2.1其状态为a,当前节点设置为该邻居节点,递归;
2.3.2.2其状态为b,当前节点状态为b,该节点处理完毕;
2.3.2.2其状态为c,跳到下一个邻居节点.
3.3所有邻居处理完毕,均为发现状态b,该节点状态为c;
3.从节点(1,1)开始遍历到节点(row - 2, column - 2)
1.当前节点大于0,... 阅读全帖 |
|
b*********e
发帖数: 26 | 49 最后一题bfs从一个点开始把图里所有点都遍历一遍就好了吧？如果完全遍历就可以，
不能就不可以
如果是有向图的话就用topological sort之类的，应该也是可以在O（N）解决的。 |
|
y*****e
发帖数: 712 | 50 不好意思我当时没看到你这个solution，我说的是你前面那个python，他是先遍历了一
遍求了一个depth, 然后又遍历的list求sum。你的答案的确是one pass,谢谢分享！ |
|
