d***g
发帖数: 252 | 1 对于第一题，如果有n个array，每个array有m个元素，我能想到的时间复杂度是O(m*n*
lgn)，用堆来存最大和最小元素，取出最小元素，移到下一个，然后比较最大和最小元
素的差 |
|
f*********5
发帖数: 576 | 2 lookup for BST is O(lgn)
but pay attention now u want to compare a word each time,
you need to compare the target word with the word in current node
u need to compare each letter of the word... |
|
n*****0
发帖数: 133 | 3 如果单词可以放在bst的internal node和leaf node的话
可以根据每个单词的字母排列为node创建一个unique的index
lookup的时候比较node的index就可以了，所以整个过程只需要O(lgn) ，假设树是
balance的
而tire的lookup需要O(m)
所以关键还是单词长度m和单词个数n的关系。
不知道理解的对不对 |
|
r****o
发帖数: 1950 | 4 来自主题: JobHunting版 - 狗狗面经~ Cft，挺牛的啊。
请问一下，机器1传string到机器2，怎么判断到了String的end啊？不是看'\0'这么简
单吧。
还有，判断pattern的lgn算法是怎么弄的啊? |
|
r****o
发帖数: 1950 | 5 来自主题: JobHunting版 - 狗狗面经~ 多谢，
那如果字符串是abcabcabc，怎么在O(lgn)的时间内找出pattern呢? |
|
s********l
发帖数: 998 | 6 来自主题: JobHunting版 - 狗狗面经~ 对 我写错了
nlgn
lgn 不可能
反正我当时 能想出来的最好算法
就是先计算string长度
然后从长度1的开始 遇到不是重复就结束 //长度指的是pattern的长度
然后长度x 先用length%x 看length是不是这个长度的倍数
是就check不是就下一个长度 直到长度到length的一半
interviewer好像很高兴 这个就是他要的答案
兴高采烈的让我coding~ |
|
r****o
发帖数: 1950 | 7 试着答一下。
就顺序比较吧，每个比较k次，复杂度O(kn)
可以排序，或binary search，或用min heap，复杂度分别是O(nlgn),O(nlgn),O(klgn)
先找出第k1大的元素，再找出第k2大的元素，介于这两者之间的元素就是所求的元素。
复杂度O(k2 lgn)
binary search的方法可能不行了，用排序和min heap应该还可以。 |
|
r****o
发帖数: 1950 | 8 Could you implement this in O(lgn) without using extra O(n) space? |
|
y**i
发帖数: 1112 | 9 我记得我看到过一个帖子，说是O(lgn)可以，但是需要O(n)额外空间，不需要空间的貌
似要做很多判
断
需要空间的就是把短的扩充成和长的一样 |
|
w********9
发帖数: 8613 | 10
value so that *p3>100-(*p1+*p2). Then any number between p3 and p2
together p1 are such as combination. then ++p1, repeat.
你这个更复杂。我只是给了个框架和大思路，否则不简明。那个方法每一步也是可以用
binaryS的（A1
到Am的和，在准备期就被记下来了），跳过很多数的。
因为中间要列组合，不可能是O(N*lgN)。 |
|
r****o
发帖数: 1950 | 11 这题我也觉得很难，难度可以算个准长老题。还有个变种是2个sorted array，长度不
一定相等，用O(lgn)时间找出第k大的数。 |
|
H****r
发帖数: 2801 | 12 The posts before are O(N lgN). There's a O(N) algorithm.
a |
|
Z*****Z
发帖数: 723 | 13 第二题我是第1次见。这个swap是不是两个部分一定要大小相同，并且不能有overlap。
如果是这样的话就很容易。
查找的复杂度么，如果能再原数组里用binary search，那么处理之后的index可以在常
数时间内算出来。总复杂度还是lgN
PART |
|
c*r
发帖数: 9 | 14 O(n)是肯定的了，但我发现想写出较为elegant的代码同时做到下面两条也不简单。
1. 无重复元素时O(lgn)时间检索
2. 在上述极端情况下O(n)时间正确的检索出3来
看来修炼的还是不够啊。 |
|
i***1
发帖数: 95 | 15 如果只有这一条要求：
无重复元素时O(lgn)时间检索
能做么？假设不能预处理。 |
|
q*******p
发帖数: 39 | 16 面了两个组， 见了8个人
题都不难，很常见，但都是写code，实际的code，而不是pseudo code
题记的不是太清，大致：
1。给一个string，输出所有由这个sting中字符组成的所有可能strings。然后，如果
有重复的字符
怎么办。再然后，如果给你一个string,和输出string长度，找出由这个sting中字符组
成的所有可
能string
2。grep 用法，写出具体的找电话号码的 regular expression
3, 给一个log 文件，找出最长的session。 session 定义：同一个userid，两 log 间
隔时间小
于一小时
4，简单的找单链表环
5，不用乘法实现两数相乘 m*n,原理很简单 O(lgn),tips：用位操作比较快，比如 m+m
=> m<<1
6, 对一个用户只知道他的基本信息（demographic information)，怎么给他他可能感
兴趣的广告
7, 找出两个单词的最短距离 （每相邻两单词必须只有一位不同）
一周以后悲剧
希望后面的xdjm 好运 |
|
K******g
发帖数: 1870 | 17 那用二分法可以检测一个数组是否排序吗？
如果排序的，和O（n)算法一样
如果不是排序的，那么就是O(lgN）了
可以这么说吗 |
|
K******g
发帖数: 1870 | 18 如果数组不是排序的，就是O(lgN）啊，如果是排序的，那就要搜索到底，和O（n）一
样啊 |
|
d**e
发帖数: 6098 | 19 如果不是排序，不可能是O(lgN)，比如
1, 2, 3, 4, 5, 6, 0, 8
还是要比较8次吧 |
|
s*********g
发帖数: 153 | 20 我相信第一题是不可能用lgn做出来的。一个简单的反例就是，如果没有比A大的数，怎么办，如果不是sorted，怎么的你也得O（n）去发现这个事实，这是谁出的面试题？ |
|
a*******8
发帖数: 2299 | 21 我也邪门，可能没写清楚，我估计这个数组是两个递增序列，这个做lgn是完全可能的 |
|
g*****e
发帖数: 282 | 22 lgN是指平均complicity，O(N)是最坏情况。这个与Qsort同理。是个经典算法题，类似
qsort的操作就可以了。
怎么办，如果不是sorted，怎么的你也得O（n）去发现这个事实，这是谁出的面试题？ |
|
x******3
发帖数: 245 | 23 store the subtree size in each node, lgN time complexity |
|
l******n
发帖数: 347 | 24 what? I thought it is already very good that you can answer all the
questions with hints.
Is Amazon that tough?
I did pretty bad the first one as I said "I have no idea for how to improve
a linear search in a sorted integer array to be less O(n).
Quite embarrassing, as I would know a lot about it ( A simple binary search
will make it to O(lgN)
How dumb I was.
Luckily I did not fail as they probably understand that it is quite possible
that I am too old to remember anything like that. |
|
n******n
发帖数: 49 | 25 对的就是挨个网里塞，但是hash_set c++中insert/lookup amortized下来都是o(1),普
通set是红黑树实现，o(lgn),所以普通set慢一点。
set |
|
n*****y
发帖数: 361 | 26 因为赶着年底毕业，九月底才开始投简历。这个offer来的太快，小startup就是动作快
，从十月初联系我，到 offer, 就两周。那几个大公司的 on-campus interview还都没
开始。也算是 hot startup,但这里肯定没人知道的，移民版知道这个公司的更多些。
就不透露公司的名字和考题了，见谅。
HR 联系之后，先是组里的头直接电面，问了一个他们实践中的问题，我没想出答案，
但还是扯了扯。后来就在谈公司做什么，我有准备，问了很多问题。刚放下电话,HR问
我什么时候作 coding test, 可以马上把题发给我, 就是fill Java class, 实现某些
功能，一般给 2-3个小时。我想这么大工作量，不能拖，否则牵扯时间和精力，就说马
上作，决定不准备了，冒一定风险。结果一个小时做完发给他们，小impress了一下。
然后另一个 team lead 马上打电话二面，顺便考察一下是不是真是我自己写的程序。
这就是一天三面，两电一编程，然后就给 onsite了。面了组里的4个lead,HR 和
Founder。前两个基本都在问我的 research和 big ... 阅读全帖 |
|
n*****y
发帖数: 361 | 27 因为赶着年底毕业，九月底才开始投简历。这个offer来的太快，小startup就是动作快
，从十月初联系我，到 offer, 就两周。那几个大公司的 on-campus interview还都没
开始。也算是 hot startup,但这里肯定没人知道的，移民版知道这个公司的更多些。
就不透露公司的名字和考题了，见谅。
HR 联系之后，先是组里的头直接电面，问了一个他们实践中的问题，我没想出答案，
但还是扯了扯。后来就在谈公司做什么，我有准备，问了很多问题。刚放下电话,HR问
我什么时候作 coding test, 可以马上把题发给我, 就是fill Java class, 实现某些
功能，一般给 2-3个小时。我想这么大工作量，不能拖，否则牵扯时间和精力，就说马
上作，决定不准备了，冒一定风险。结果一个小时做完发给他们，小impress了一下。
然后另一个 team lead 马上打电话二面，顺便考察一下是不是真是我自己写的程序。
这就是一天三面，两电一编程，然后就给 onsite了。面了组里的4个lead,HR 和
Founder。前两个基本都在问我的 research和 big ... 阅读全帖 |
|
l*****v
发帖数: 498 | 28 如果range大可以先sort再loop O(lgn*n) |
|
r**l
发帖数: 31 | 29
classic question bit reverse
lgn implementation, there are more efficient and fancy way of bit
operation, but this is most straightforward.
// assume 32 bits integer
unsigned int reverseBits(unsigned int x) {
x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
return((x >> 16) | (x << 16));
} |
|
D***h
发帖数: 183 | 30 第二题怎么可能O(lgn)? 数完节点数目就O(n)了. |
|
j*****u
发帖数: 1133 | 31 if there's a count of subtree nodes on each node, every time you either go t
o left child or right - dropping half nodes, thus O(lgN) assume the bst is b
alanced
achieve |
|
g*********s
发帖数: 1782 | 32 the idea is right but the complexity is O(h). so it requires a balanced
bst to get O(lgN).
n-
度应该是多
少？ |
|
g*********s
发帖数: 1782 | 33 with unbalanced bst, you can't query the median in O(lgN). so the bst you
created doesn't meet the requirement of (2).
for creation of a balanced bst, there's extra work to do. that's why i say
it's not straightforward.
http://en.wikipedia.org/wiki/Binary_search_tree#Insertion, set
numOfDescendents of the newly added node to 1 and increment
numOfDescendents of the nodes along the insertion path by 1. |
|
g*********s
发帖数: 1782 | 34 3. distributed median，（unsorted）数字分布在几台机器上，设计分布式算法找到
它们的median，要考虑网络通讯的overhead。（先local sorting，然后一个数一个数
去看是不是median就行，结果我设计了一个巨复杂的recursive algorithm...还好那个
印度大哥比较nice）
how come local sorting can give u global median?
unless it's the last step that you can get the global median in O(lgN)
with two sorted arrays. |
|
g*********s
发帖数: 1782 | 35 it's been proposed by others to use order statistic tree, i.e., a
balanced bst augmented with size of sub-tree.
this is a classical data structure and most likely the expected answer
by the interviewer. it is easier to understand and stronger in sense of
picking up any n-th element in O(lgN). the complexity is the same as ur
solution though.
ur solution is still interesting to read.
the
(which is
median
of
consecutive
then |
|
i**9
发帖数: 351 | 36 using tournament tree only n+ lgn -2 times of comparison are needed
each
O(n). |
|
g*********s
发帖数: 1782 | 37 if prime is sparse, how do u know # of prime less than N is O(N^0.5)? why
can't it be O(N^0.25) or O(lgN)?
sieve |
|
g*********s
发帖数: 1782 | 38 本来想一起把我的答案发了的，结果被老婆拽去gym。现在发一下。
2. 用递归
因为一个函数调用四次自己，树有log(n)层，所以复杂度是4^(log(n)) = n^2。我复杂
度这块比较弱，在他的提示下写出来的。
how u know tree has lgN level? the worse case could be N.
然后假如左右子树需要交换的情况下，用变量保存总共要交换几次。我用一个引用来保
存，把代码最后一行加几个if语句，在需要交换左右子树的情况下变量自增。但他似乎
不满意，给我写了两个引用，我没懂他什么意思。
why u need a variable to keep the swap? confused here.
it seems this problem has an easy version and a complicated version.
easy version not considering left/right sub-tree swapping. in this case,
you can traverse each tree twice (i... 阅读全帖 |
|
g***s
发帖数: 3811 | 39 "寻找需要时间O（n log n)"
should be 寻找需要时间worst case O（n).
the worst case it also needs scan twice. average time is n+lgn |
|
v*******7
发帖数: 187 | 40 Sure, I know the solutions of cover().
For my solution, you can first perform an covercheck checking whether p and
q exist
in the tree. And actually, this check is not difficult, just DFS is enough
which cost
O(N) in time complexity. if both p and q exist in the, you can call the
recursion
solution that I posted. totally, the time complexity is still O(N), space
complexity
is O(1).
Another solution that I have is time complexity O(lgN) while space
complexity is O(N)
which should consider the hei... 阅读全帖 |
|
g*********s
发帖数: 1782 | 41 sorry, but can u prove this is balanced? i believe this algorithm creates
a bst. but i'm not convinced the created bst is balanced.
u can see the left and right sub-tree can have size difference by 1. if u
do recursion, then is it possible at each level the left and right may
have difference by 1? if so the worst case this difference is accumulated
with an O(lgN) bound... |
|
c***2
发帖数: 838 | 42 doing the tournament with complexity N+lgN in the cost of extra stack spaces
used for recursion
straightforward 2-pass scanning takes N-1+N-2=2N-3 with no extra space
Tournament:
void find_max_2max(int a[], int start, int end, int *max, int *max2)
{
int i, mid;
int max00,max01,max10,max11;
int temp1,temp2;
if(start==end){
*max=a[start];
*max2=a[start];
return;
}
if(end-start==1){
*max=MAX(a[start],a[end]);
*max2=MIN(a[start]... 阅读全帖 |
|
a********e
发帖数: 80 | 43 先通过BST来二分查找到current_node。查找的过程中记录一系列祖先node。这个过程
的复杂度O(lgN)。
然后就可以找中序后继了，具体来讲：
1）如果有right child，就是right child的最左边node。
2）如果是parent的left child，那么就是parent。
3）否则，就沿着祖先nodes往上，直到走到一个node，它是它parent的left child. |
|
l*****a
发帖数: 14598 | 44 you can get the result from PIE
BST give u O(lgn) insertion/lookup but sorted
while
hashtable give u O(1) insertion/lookup but not sorted
if u don't have enough memory and u want an ordered output
u should use BST |
|
g*********s
发帖数: 1782 | 45 yes, for k=2, O(lgN) is surely much better.
doesn't |
|
c********0
发帖数: 112 | 46 My solution:
我们首先第一次循环 一列一列的 找到每一列的所有的连续黑边 每一个黑边用一个坐
标 (x,y)和垂直长度 l 表示
之后一行一行的循环 找到每一行所有连续的黑边 每个黑边用(x,y)加水平长度l表示
之后对每个竖向的黑边 check 存不存在对应的一个竖向的黑边和两个水平的黑边，这
个check应该是很快的 O(1)或者O(lgn) 取决于怎么存连续黑边
这样是不是O(n^2)的复杂度？ |
|
g***s
发帖数: 3811 | 47
~~~this is not easy to get in O(1) or O(lgn).
sample: all (1,y) = B, all (2, even number) = B
now, there are O(n) 水平边.
B
BB
B
BB
B
BB
B
BB
B |
|
g***s
发帖数: 3811 | 48 ＊步骤２需要改成如果已经参加过一次，取最后一天。否则取两天。
否则，反例 （１，２）（２，４）
* 单步步骤３不能在O（１）时间内完成。但需要证明所有第３步的总时间可以在总时
间O（n）时间内
完成(具体算法也稍微麻烦一些)。
不过，既然排序已经用了O（nlgn），这里单步简单的用O（lgn）也就行了。总时间
反正都是O
（nlgn）.
除非，参加的人数n＞＞总天数。那么，可以找到排序的算法是O（n）。那么这题总时
间复杂度才可能是
O（n） |
|
y******5
发帖数: 43 | 49 Thank you for your post.
第二轮
1. is binary tree BST，写两种解法，念code
Solution 1: INT_MIN, INT_MAX go down
Solution 2: in-order traversal
2. efficient recursive way to compute Fibonacci number 念code
Solution: D & C, matrix mulplication. time complexity: O(lgn), space
complexity: O(1)
right? |
|
g*********s
发帖数: 1782 | 50
average O(1)
tree?
O(lgN)
less memory
lg2(100k) = 17.
merge sort for external sort. |
|
