k***e
发帖数: 556 | 1 if it is rb balanced or AVL balanced, we can make sure to find the i-th
largest
in lgn time.
i guess he wants you to mention this. |
|
h*********e
发帖数: 56 | 2 和重复没关系。Tree size N, find M-th biggest, 你的算法O(N)，有O(lgN)算法。 |
|
|
d******a
发帖数: 238 | 4 I don't think you could find a solution of O(lgn) for this problem in the
worst case. when a BST is similar to a linked list, you need O(n) time |
|
m*****k
发帖数: 64 | 5 你是说，如果知道at each node that records the number of nodes in the subtree
rooted at it. 那么，可以根据number of nodes in left and right subtrees,来找?
比如说left subtree has 3 nodes, right subtree has 3nodes, and we want to
find the 6th biggest node, then it should be on left subtree,then
recursively find it? so it is o( lgn). Is it what you are talking about?
information
it? |
|
h*********e
发帖数: 56 | 6 我来试试。
struct Node {
....int nSmaller;....//total number of node in its left subtree
....Node *left, *right;
};
//select m-th in the sorted order, starting with zero
Node* select(Node* root, int m) {
....if(root==NULL)
........return NULL;
....if(root->nSmaller == m)
........return root;
....if(root->nSmaller < m)
........return select(root->right, m-nSmaller);
....else
........return select(root->left, m);
}
最好嵌入到balanced BST中，以保证O(lgN),比如AVL， red-black tree. |
|
h*********e
发帖数: 56 | 7 来自主题: JobHunting版 - 问一道旧题 一般情况下是不行，但用这种态度回答面试问题可不对。有Balanced BST不用不是和自
己过不去么？
有时面试问题本身的数据结构设计就有问题，你要善于纠正。
具体 lgN 解法 google "dynamic order statistics". |
|
|
|
c****s
发帖数: 241 | 10 the worst case is O(n). the average is O(lgn). |
|
r****o
发帖数: 1950 | 11 preprocessing这一步的的复杂度是不是O(n)？
考官是不是要O(lgn)的复杂度？
一个左移的方法太差了，他面试官才问他怎么优化的。 |
|
g*********s
发帖数: 1782 | 12
why linear scan is weak? how does the binary search work? O(lgN) is just
for a single element. To de-duplicate the whole sorted array, i think O(N)
is the best. |
|
m*****k
发帖数: 64 | 13 log n的算法怎么做？如果是一个array可以用selection algorithm，两个呢？
然后问了如何在2个排序好的数组里面找第K大的数。 我知道肯定要lgN的算法，但是一
时半会儿没
想好怎么做。所以先写了个O(k)的简单版本。然后果然要求改进，我就开始写logN的版
本，最后写
的八九不离十，面试官提醒我边界条件写错了。不过时间到了。 后来想想，如果别忙
着写，想清楚，
用递归就几行代码而已。 我用循环写，就非常墨迹。
签什么不许泄
露题目的协议。而且大部分题目都是见过的。
换，
index -> 数字，coding完，问测试。
word反
转，另一个忘了。 套路都是先扯淡，再coding，再测试。
是话很多的
人，所以面试超级没话讲。 对怎么测试俄罗斯方块这种题目测试毫无概念，我怎么答
面试官都不满
意。。。 西雅图几天都是阴雨天气，预感肯定被拒。 果然一周收到据信。
天没等
到电话。 然后过了几天，没有任何通知，就打过来了。。面试官问我想不想面，我想
了一下，我的
recruiter那么不靠谱，可能不会帮我重新安排，就硬头皮开始面。
后问了如何
在2个排序好的数组 |
|
s****e
发帖数: 43 | 14 zan~ niu mm~
签什么不许泄露题目的协议。而且大部分题目都是见过的。
换，index -> 数字，coding完，问测试。
word反转，另一个忘了。 套路都是先扯淡，再coding，再测试。
是话很多的人，所以面试超级没话讲。 对怎么测试俄罗斯方块这种题目测试毫无概念
，我怎么答面试官都不满意。。。 西雅图几天都是阴雨天气，预感肯定被拒。 果然
一周收到据信。
天没等到电话。 然后过了几天，没有任何通知，就打过来了。。面试官问我想不想面
，我想了一下，我的recruiter那么不靠谱，可能不会帮我重新安排，就硬头皮开始面。
后问了如何在2个排序好的数组里面找第K大的数。 我知道肯定要lgN的算法，但是一时
半会儿没想好怎么做。所以先写了个O(k)的简单版本。然后果然要求改进，我就开始写
logN的版本，最后写的八
solve问题的能力
是似乎他也没看出来。。 后来开始设计系统，非常发散的题目，讨论到了cache，
network, index， 因为和我做的东西有些相关，所以聊得很high |
|
m******9
发帖数: 968 | 15 这个可以log2k找到
你从array 1中取前k个数, 从array2中也取前k个数. 然后对取出来的这2个子数组, 找
median, 就是整个array1和array2的kth min了 |
|
|
g********n
发帖数: 127 | 17 Then go to the second array to find k+r elements (in which r = k - length_
1st_array). |
|
|
y**i
发帖数: 1112 | 19 不能merge同时计数么，到第k个的时候停止，就是要找的数了 |
|
|
m******9
发帖数: 968 | 21 他说的是对的.
用log(m+n)找median可以看看这个帖子:
http://geeksforgeeks.org/?p=2105
意思就是, 你要取2组sub array, 使得它们的元素总个数是2k, 此时当你找到median时
,自然就是
kth min了. 对2个sorted array找median in log(m+n), 可以参考一下上面那个连接 |
|
r****o
发帖数: 1950 | 22 明白了，多谢。
不过，如果第2个数组不够长(也就是说，第2个数组长度>k，第一个数组长度
两个数组总长度还是<2k）的话，这个方法还是不行把。 |
|
h**6
发帖数: 4160 | 23 碰上两个数组总长度不够2k的情况，那么就找第m大的，这时必然有m |
|
|
|
|
r****o
发帖数: 1950 | 27 如果你想每次查找的时间比较稳定就用map，复杂度 O(lgn)，
hashtable则有快有慢，有可能是O(1)，也有可能是O(n)。 |
|
x******3
发帖数: 245 | 28 first find the search cache line, update its LRU value
then just walk up the tree to update each LRU value along its way towards to
root
since updating LRU value only needs to check itself and the new LRU value,
its complexity is just lgn
change |
|
x******3
发帖数: 245 | 29 保存子树中的节点个数， 查找中值的就可以判断中值应该在那边的子树里
比如你的根节点里子树大小是9，中值就是rank是5的值，
如果左边子树大小是3，右边是5，你应该在右边子树中找rank是1（5-3-1）的值
这样的话查找的时间就是树高， RBT的话就是lgn |
|
w******0
发帖数: 43 | 30 这样行吗,
第一次选n/2,然后让老鼠喝 左边n/2的,如果死了,就是左边有毒
在此递归验证
最后是lgn |
|
b******v
发帖数: 1493 | 31 2. 给定一个方形矩阵, 有正整数组成, 每一行按升序排列, 每一列也按升序排列, 已
经给定整数n, 怎样确定是否在矩阵中, 先说思路, 然后白板coding, 要求linear time
的solution.
这道题可以这么来做：
用binary search分别找到n在最上面一行中的位置top, 在最下面一行中的位置bottom,
在最左边一列中的位置left, 在最右边一列中的位置right
容易验证top>=bottom, left >=right
那么，top右边的列，left下边的行，right上边的行，bottom左边的列都不用考虑
所以我们只要在right行到left行，bottom列到top列围成的中心的小矩阵中找n就行了
所以问题转化为一个递归问题
不过这个时间复杂性我暂时还没想清楚，我想大概是O[(lgN)^2]，
其中N为矩阵的size. |
|
f******6
发帖数: 723 | 32 给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
如何找他们的lowest common ancestor。
如果是BST（但这里不是），这是个经典的问题。
你的solution要O(lgn)time和constant space。
如果大家已经讨论过，能不能给我一个link看看？
经过提示完成，中间紧张无比（原谅我比较菜），communication不是很好，这样有戏么？
谢谢大家。 |
|
q*********u
发帖数: 280 | 33 我自己胡乱写了一个伪代码，指正一下
findCommonParent(p, q){
if(parent(p) == parent(q))
return parent(p);
else if(parent(p) == Root || parent(q) == Root || p == Root || q ==
Root)
return Root;
else
return findCommonParent(parent(p), parent(q));
}
给你一个tree（任何tree，但是你可以assume binary tree)，给你两个nodes，p和q，
如何找他们的lowest common ancestor。
如果是BST（但这里不是），这是个经典的问题。
你的solution要O(lgn)time和constant space。
如果大家已经讨论过，能不能给我一个link看看？
经过提示完成，中间紧张无比（原谅我比较菜），comm |
|
f******6
发帖数: 723 | 34
我就是想到这个。呵呵，不过题目里n是tree nodes个数，所以，算lgn？ |
|
f******6
发帖数: 723 | 35
对，我也认为是这样。不过interviewer没有质疑O(lgn)。。。应该没有tree is
balanced 这个假设
我现在想想，又想不通了。。。 |
|
y**i
发帖数: 1112 | 36 我怎么感觉这个就跟两个链表有公共结点，找公共结点的题目一样啊
首先确定p和q的层数（对应链表的长度），然后先移动层数多的那个结点向上（父结点
）到和另一个结点同样的层数，然后同时向上移动，找相同的结点指针。
复杂度O(lgn)。
这两个算同一个类型的题目么？
戏么？ |
|
f******6
发帖数: 723 | 37
能不能说的清楚点，为什么有了parent pointer，确定level就是
O(lgn）。谢谢
楼上的，思路就是这个，就是要有parent pointer。 |
|
a***9
发帖数: 364 | 38 直观上我是这么理解的:别的题目中，比如给n个ID，让找一个target的，
那么就是扫一遍就行，我们一看就是linear的，那是因为跟每个ID大小
没关系，只跟有多少个ID有关系。
但这题，复杂度是跟给的N的大小有关系。
所以，定义复杂度，是根据输入串长度的bits数来的，前一个的输入串
长是n*(log ID)，最后做到步骤跟n线性，但这里输入串只需要lgN，也
得做N步，就nb了 |
|
|
i********s
发帖数: 133 | 40 应该不用先找分解点，直接用binary search, 只不过需要分情况讨论每次应该往左边
还是右边跳。所以复杂度O(lgn)
>我首先说是找到分界点， 然后对两边用binary search， 这个效率应该是O(n)>吧， 毕
竟最坏情
况下找到分界点要遍历一遍。 |
|
x******3
发帖数: 245 | 41 好像预处理找sorted array的起点和结束可以是lgN, 用binary search找起点和结束 |
|
l*********y
发帖数: 142 | 42 given an array of n elements, find if there is a subset of 3 elements sum up
to value T with time complexity O(nlgn).
感觉这道题定义很清晰，但是只能想出O(n^2*lgn) 的brute force解法.
careercup上的讨论不清楚。谢谢。 |
|
r****o
发帖数: 1950 | 43 想了一下，好像可以达到O(nlgn). 假定数组为 a[1]...a[n]。
先排序 O(nlgn)
然后用binary search 找a[i]，过程如下：
对于a[mid],如果a[n]+a[n-1]也比T-a[mid]小，说明a[mid]选值过小，故在右半边继续找a[mid]；如果a[1]+a[2]也比T-a[mid]大，说明a[mid]选值过大，则应在左半边继续找a[mid]，
继续该binary search，一直找到a[mid]，使得a[1]+a[2]<=T-a[mid]<=a[n-1]+a[n]，
然后可以线性查找出i,j，使得a[i]+a[j]=T-a[mid]。
binary search共需O(lgn)步。线性查找O(n)。
总复杂度还是O(nlgn)。
希望大家对我的想法多提意见。 |
|
m*********r
发帖数: 1797 | 44 来自主题: JobHunting版 - 估计是挂了 在第四个人面完的时候，他说你下个面的是hiring manager把，好像有收到他的邮件
说他病了，我去确认一下。然后让我等一会儿，我就去了一下卫生间，回来以后，他说
hiring manager病了，你回去等recuiter的消息把。
感觉，有一个人面的一般，O(1)的解法答出了O(lgn),没时间了；其他人感觉面的不错。
anyway了，也算一次经历；面前看到好多中国面孔等面试，呵呵。 |
|
x****r
发帖数: 99 | 45 一般这种题可以用hash的话就是O(n)呗，不然的话sort了对每一个a做binary search找
N - a，O(n*lgn)？还有别的方法么？ |
|
m*****g
发帖数: 226 | 46 这个是图省事
在heap找最小当然O(1)。但是等下update要O(lgn)。 |
|
b******v
发帖数: 1493 | 47 假设两个整数y>x，并且y=n*x+r
那么用每次让x增大两倍的办法，能迅速找到k, 使得2^k*x
然后让y = y-2^k*x，继续上面过程，每次过程相当于从n中去掉一个2^k。
这样，计算的复杂度最坏情形是n的二进制表示里全是1
假设n的二进制有m位，这样的复杂性是(1+2+...+m) = O(m^2) = O((lgn)^2) |
|
r****o
发帖数: 1950 | 48 大家看看我的想法对不?
可以模仿merge sort,先考虑N为偶数的情况
设这N列为c1,c2,...,cN
将c1和c2, c3和c4, ..., c_{N-1}和cN 两两 merge成一个长2N的列，设为d1,d2,...d_{N/2}
然后再将d1和d2,d3和d4,...,d{N/2-1}和d{N/2}两两merge成一个长4N的列，
如此反复merge,直到最后剩下两个长N*N/2的列，用binary search可找到median。
时间复杂度，O(N)+O(2N)+...+O(N*N/2)+O(2lgN)=O(N^2 lgN).
空间复杂度O(N^2).
当N为奇数时，可将最中间那列先空着，当左右两边都merge成了长(N-1)N/2的列后，再merge成一个长(N-1)N的大列，然后问题可归结为一个长(N-1)N的列和一个长N的列，都排好序，找median的问题。
时间复杂度和空间复杂度应该和偶数时一样。 |
|
j***n
发帖数: 301 | 49 最少需要比较n+ceiling(lgn)-2次，这个时候有常数空间复杂度的实现么？ |
|
m*****g
发帖数: 226 | 50 没有吧
如果用那种tournament的方法，每一轮都要保存胜利者的信息。
即使每次把失败者的信息丢弃，从最底层到最顶层，需要的空间至少
O(n) ---> O(lgn) |
|
