b******b
发帖数: 300 | 1 为什么是nlgn， 已经sorted了。
我觉得关键他要求的是第一个。。。这个不知道该怎么处理 |
|
d**e
发帖数: 6098 | 2 我觉得前面有同学说的正确
用hash就是O(n)空间，O(n)时间
用bst是O(1)空间，O(nlgn)时间 |
|
i***h
发帖数: 12655 | 3 有最多 NlgN 的算法怎么还会是 NP complete |
|
s********r
发帖数: 277 | 4 上面提到的NlgN的算法都没有办法证明其正确性。
难道是我对题目理解有误？ |
|
i***h
发帖数: 12655 | 5 有最多 NlgN 的算法怎么还会是 NP complete |
|
s********r
发帖数: 277 | 6 上面提到的NlgN的算法都没有办法证明其正确性。
难道是我对题目理解有误？ |
|
|
H***e
发帖数: 476 | 8 n^2的我觉得还是能搞出来的
nlgn的就夸张了 |
|
q******8
发帖数: 848 | 9 int[] smaller_on_right(int[] array){
int length = array.length;
int[] result = new int[length];
ArrayList arraylist = new ArrayList();
for(int i=0; i
arraylist.add(array[i]);
}
Collections.sort(arraylist);//nlgn
for(int j=0; j
result[j] = Collections.binarySearch(arraylist, array[j]);//lgn
arraylist.remove(result[j]);//这步如果是array的话，算法就不是
nlogn了，不过如果是linkedl... 阅读全帖 |
|
q******8
发帖数: 848 | 10 int[] smaller_on_right(int[] array){
int length = array.length;
int[] result = new int[length];
ArrayList arraylist = new ArrayList();
for(int i=0; i
arraylist.add(array[i]);
}
Collections.sort(arraylist);//nlgn
for(int j=0; j
result[j] = Collections.binarySearch(arraylist, array[j]);//lgn
arraylist.remove(result[j]);//这步如果是array的话，算法就不是
nlogn了，不过如果是linkedl... 阅读全帖 |
|
D********g
发帖数: 650 | 11 第二题
１．每台机器sort array, NlgN
2. Maintain一个size为P的min-heap，heap的每个元素是1中每个array当前最小元素
的值和array的id (1 -- p )，以及指向对应array首部的pointer，heap里的元素是按
照array当前最小元素排列的。
3. 对heap的根，increment 对应array的pointer.然后update heap。重复直道找到Ｎ*
P/2个元素为止。
integers
medium |
|
a********m
发帖数: 15480 | 12 如果两个数组通常都相同的话这个期望复杂度是nlgn,只是比排序多了early out吧。 |
|
n******n
发帖数: 49 | 13 第二题和第三题的区别在哪里？如果要求正数之间相对位置不变，负数之间相对位置也
不变，版上讨论过nlgn的in-place解法。不知道有什么n的in-place解法。 |
|
l*****a
发帖数: 14598 | 14 wrong.
你第一次binary search之后，旧已经大大缩小了下一次binary search的范围
so the time complexity should not be nlgn
O( |
|
w****o
发帖数: 2260 | 15 来自主题: JobHunting版 - 一道面试题 按照你的理解，排除排序后，你的两重循环的时间复杂度是O(n^2)吗？
我觉得排除排序后,可以做到O(nlgn).
大概的想法是可以用 a[i]+L 作为key,做binary search,就是类似于STL里的函数upper
_bound，
这样upper_bound-i 就是 interval [a[i] a[i]+L]可以cover的数字的个数。 |
|
|
f**********2
发帖数: 2401 | 17 1. 归并操作
public int[] Merge(int[] a, int[] b) {
int [] c = new int[ a.length()+b.length() ];
int i=0,j=0,k=0;
while (i
if (a[i]
else {c[k]=b[j];k++;j++}
while (i
{c[k]=a[i];k++;i++;}
while (j
{c[k]=b[j];k++;j++;}
return c;
}
时间O（nlgn），空间O（n）？
2 从数组的头和尾开始算和sum，若sum＝SUM，输出；若sum
；若sum> SUM, 偏大了，尾指针－1； 包在一个循环里，结束条件是头指针》＝尾指针。
3 开一个不小于string长度的数组，遍历string，若相同的char，统计到一起；最后遍
历数组，找第一个值为1的index，再在string里面... 阅读全帖 |
|
j*****l
发帖数: 1624 | 18 hashmap o(n)
不然排序就要o(nlgn)了吧。
如果要更小的空间时间俺还没想出来或是忘记了。 |
|
f*********i
发帖数: 197 | 19 The following is an O(nlgn) solution, I hope that helps
// start is initially 0, end = aabb.length-1
public static char[] changeOrderOfString(char[] aabb, int start, int
end)
{
if (end - start <= 1)
return aabb;
if ((end - start + 1) % 4 != 0)
{
for (int i = start + 1, j = end - 1; j > i; j--, i++)
{
char temp = aabb[i];
aabb[i] = aabb[j];
... 阅读全帖 |
|
t********e
发帖数: 143 | 20
Sort is O(nlgn). LZ wants a solution better than that. |
|
t*********7
发帖数: 255 | 21 quickSort nlgn
两个INDEX,一前left, 一后right,求和看等不等于指定数.
比指定数大right--,比指定数小left++,等于输出,left++
直到两个指针相差为1 |
|
t*********7
发帖数: 255 | 22 quickSort nlgn
两个INDEX,一前left, 一后right,求和看等不等于指定数.
比指定数大right--,比指定数小left++,等于输出,left++
直到两个指针相差为1 |
|
t*********7
发帖数: 255 | 23 来自主题: JobHunting版 - 请问两道题 第一题应该没有O(n)的搞法吧...第二题倒是有O(n)的搞法,好像是一篇高端论文...
nlgn的搞法应该是median of medians algo...同求熟悉这个算法的大神指点. |
|
r********g
发帖数: 1351 | 24 第二题如果不用递归，就是iterative的post order遍历？
另外，打印也很麻烦，是不是用一个辅助stack？这样复杂度是O(nlgn)吗？
void printStack(stack S){
stack T;
while(!S.empty()){
T.push(S.top());
S.pop();
}
while(!T.empty()){
cout << T.top()->value << ' ';
T.pop();
}
cout << endl;
}
// post order traverse
void printAllPath(Node* root) {
if(!root) return;
stack S;
Node* prev = NULL;
S.push(root);
while(!S.empty()){
Node* p = S.top();
if(!prev || p == prev->left || p==prev->right... 阅读全帖 |
|
f******h
发帖数: 45 | 25 但是 建suffix tree 还是需要至少 O（nlgn）的复杂度吧。 |
|
G******i
发帖数: 5226 | 26 ☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Sat Oct 29 00:10:37 2011, 美东) 提到:
**********************************
M:
phone interview (1 round):
why MS?
biggest challenge
why like coding and algorithm?
what is good code?
your longest code
biggest accomplishment
if you don't want some functions to be modified in java, what to do?
does java allow multiple inheritance?
what does synchronized keyword mean in java?
CEO wants a book, you find it in the system of a nearby bookshop. You ... 阅读全帖 |
|
l*****a
发帖数: 14598 | 27 数组sort就是nlgn
你字符串sort算是n^2*lgn吧 |
|
a*********e
发帖数: 18 | 28 跑进去看到坐着两个面试官，顿时吓尿了。
说是一个是shadow的，大致就是见习看别人怎么面试的准面试官吧。
但这感觉就犹如我憋了一个灵丸想去打吕弟的，结果迎面走来的是户愚吕兄弟。。。。
于是乎果断挂了。
题目只做了一道，还是在吕弟的指导下做出来的，小bug也很多，最后优化也只是O(N2)
到了O(NlgN)，后来一想可以O(N)的。哎。该是2.0了吧。
onsite面试一共两轮（intern conversion所以少两轮），第一轮就是上面说的2个人面
的，第二轮1个人，还好。 |
|
l****c
发帖数: 782 | 29 曾被问过一个问题 。
什么时候用bubble sort，而舍弃O(nlgn)的sort？ |
|
h**********9
发帖数: 3252 | 30 来自主题: JobHunting版 - 请问G一题
diff
如图可看出对角线之和是delta,找到max diff后swap X/Y, 然后重新计算黄色的cell.
上面的code是偷懒，swap X/Y 后没有重新对 X/Y 排序，否则找 max diff 就是小于 O
(NlgN)。
初始化能保证delta < max(input) - min(input), 每次while() loop使得delta递减直
到收敛，最坏是 max(input) - min(input)次，（实际递减速度应快于每次减一，具体
应该和数据的pattern有关，）现在的问题是能否证明这样每次swap一对元素使得delta递
减，最后能不能收敛到理论最小值。
谁有时间就看看这个行不行吧。 |
|
h**********9
发帖数: 3252 | 31 来自主题: JobHunting版 - 请问G一题
diff
如图可看出对角线之和是delta,找到max diff后swap X/Y, 然后重新计算黄色的cell.
上面的code是偷懒，swap X/Y 后没有重新对 X/Y 排序，否则找 max diff 就是小于 O
(NlgN)。
初始化能保证delta < max(input) - min(input), 每次while() loop使得delta递减直
到收敛，最坏是 max(input) - min(input)次，（实际递减速度应快于每次减一，具体
应该和数据的pattern有关，）现在的问题是能否证明这样每次swap一对元素使得delta递
减，最后能不能收敛到理论最小值。
谁有时间就看看这个行不行吧。 |
|
c******t
发帖数: 391 | 32 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
让再约一次电面。
不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
【UPDATE面经】
就两道题，在sharing doc上实现:
1)实现一个min-heap，并用其找无序数组里的top k;
2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
能自定义node。
【UPDATE三面面经】
让实现函数，返回无序数组里按增序排列后第k个数，比如{3,1,2,4},key=3,就返回3.
先说了naive的排序解法，又说了用max-heap，这哥们貌似第一次听说这个方法，解释
了巨久，指出复杂度O(k)+O((n-k)lgk)后，还让继续找最优算法。经提示后才明白是让
写珠玑里提到的部分快排解法，coding后被指出有个递归的参数传错了，不过时间关系
没有再深入。
这个部分快排的复杂度不还是O(nlgn)么，为啥就比max-he... 阅读全帖 |
|
A****e
发帖数: 310 | 33 谢谢lz分享～
快排是O(nlgn),因为T(n)=2T(n/2) + O(n),但是用它找top k的时候，每次扔掉一半，
只需要考虑一半的数，递推关系是T(n)=T(n/2)+O(n)
复杂度就是O(n)了。 |
|
C*******n
发帖数: 24 | 34 Q: You are given a binary tree in which each node contains a value Design an
algorithm to print all paths which sum up to that value Note that it can be
any path in the tree - it does not have to start at the root.
其实这个题本身就说的不清楚，我看了一下答案解析，发现题意是：给你一个二叉树，
每个节点都有一个数，再给你一个sum，求树中所有和为sum的路径，路径的开始可以
不为root。
答案中给出的解法号称O(nlgn)的时间复杂度（其实就是最直觉化的做法，每个节点都
DFS），但是我感觉答案对时间复杂度的分析有问题，因为他分析的时候有个条件是：
There are 2^r nodes at level r。我感觉他分析的这个不是最坏情况，最坏情况应该
是每一个level只有一个节点，时间复杂度为O(n^2)
求问刷过Cracking Coding Interview的前... 阅读全帖 |
|
|
m********g
发帖数: 272 | 36 public static int longestIncreasingSubConsequence(int[] array) {
int length = array.length;
int[] valueAtLength = new int[length];
int maxNow = 1;
valueAtLength[0] = array[0];
for(int i = 1; i < length; i++) {
int updatePos = findPos(valueAtLength, maxNow, array[i]);
if(updatePos == maxNow) {
valueAtLength[maxNow++] = array[i];
} else {
valueAtLength[updatePos] = array[i];
}
}
return maxNow;
}
private static int findPos(int[... 阅读全帖 |
|
m*****k
发帖数: 731 | 37 谢谢myanything 大虾，
int[] array= new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7,
15
};
如何输出 0 2 6 9 11 15 呢？ |
|
m********g
发帖数: 272 | 38 每次cached的时候把整个序列都cache下来，最后print out那个最长的序列 |
|
m*****k
发帖数: 731 | 39 刚在collabedit上被问到这道题，干脆就直接拷贝了，面试官，一国人兄弟说他看到过
这段ｃｏｄｅ，
既然这样，我也不需隐瞒，直接告诉他就是我发帖要的ｃｏｄｅ，再装没见过就太掩耳
盗铃了，呵呵。
看来国人兄弟也是有意放水，谢过了哈！ |
|
h****n
发帖数: 1093 | 40 lis需要 nlgn的复杂度
lis的特殊情况
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
|
c****m
发帖数: 11 | 41 同球test case
写了一个，思想是这样的：
按照start 排序，取出当前的element（cur），然后往后check每个element（next）,
如果next的end是小于cur.end，说明next这个是被cur完全cover的；直到找到一个next
的end是大于cur.end，这样我们就可以更新cur了，直到遍历完。有点类似于蠕虫爬行
一样。
感觉虽然有两个loop，但是每个Event应该只比较了一次，遍历这块应该还是O(n)的吧
？当然sort的时候是O(nlgN).不知道这样对不对？一直在潜水，求指点，谢谢
int main()
{
Event e1(1, 9);
Event e2(2, 3);
Event e3(4, 5);
vector lVec;
lVec.push_back(e1);
lVec.push_back(e3);
lVec.push_back(e2);
std::sort(lVec.begin(), lVec.end());
int start = 0;
... 阅读全帖 |
|
f*******4
发帖数: 64 | 42 如果基于比较的方法可以做到可以O(m*n), 那么对任意m*n个元素排序，只需要对young
进行(m*n)lgm的堆排序。
固定m的取值，相当于总排序时间为O(N) |
|
f*******4
发帖数: 64 | 43 只是行有序,根据决策树计算是O(m*nlgn)
根据决策树比较可以得出杨氏矩阵更难达到
题外，发现求杨氏矩阵的决策树具体表达式，貌似不那么简单？
。 |
|
n***i
发帖数: 777 | 44 确实不对，还是用递归，思路跟你的比较像。
n=1
a1 b1
n=2
a1 a2 b1 b2 -> a1 b1 a2 b2
n=4
a1 a2 a3 a4 b1 b2 b3 b3
从中间数左边 n/2 个 和 从中间数右边n/2个交换，得到
a1 a2 b1 b2 a3 a4 b3 b4
然后可以recursively在左边n个和右边n个都成为了n=2的子问题
n=8
a1 a2 a3 a4 a5 a6 a7 a8 b1 b2 b3 b4 b5 b6 b7 b8 ->
a1 a2 a3 a4 b1 b2 b3 b4 a5 a6 a7 a8 b5 b6 b7 b8 ->
a1 a2 b1 b2 a3 a4 b3 b4 a5 a6 b5 b6 a7 a8 b7 b8 ->
a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6 b6 a7 b7 a8 b8
T(n) = 2T(n/2)+O(n) 所以是 nlgn 算法
但是问题是n 需要是 2^k.如果 n不是2^k， 需要加入padding把它补到2^k然后在结果
中截取需要的部分,所以严格上说空间复杂度说O(1)比较牵强 |
|
l*****a
发帖数: 559 | 45 第二题leetcode上只给出了nlgn的解法。lgn的解法是如何得到的？
第一题有lgn的解法，不过嫌复杂被放弃掉了。 |
|
a********m
发帖数: 15480 | 46 恩。lgn肯定不行。不过m+n能搞定吗？俺咋脚着至少要nlgn （简化成m=n）？ |
|
s*****t
发帖数: 11 | 47 堆排序算法如下
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i = A.size downto 2
3 exchange A[1] with A[i]
4 A.size = A.size - 1
5 MAX-HEAPIFY(A, 1)
算法书上说
1 BUILD-MAX-HEAP(A) 的时间复杂度为 O(N)
5 MAX-HEAPIFY(A, 1) 的时间复杂度为 O(lg N), N 为当时 A 的长度
那么, 整个算法的时间复杂度是
O(N) + O(lg(N-1)) + O(lg(N-2)) + ... O(1)
= O(N + lg(N-1) + lg(N-2) + ... 1)
= O(N + lg(N-1)!)
= O(lgN!)
比快速排序的 O(NlgN) = O(lg(N^N)) 还要快?
迷惑了,求大牛指点. |
|
c********t
发帖数: 5706 | 48 第二题A有没有重复字符？B有没有？如果都说是set,应该没有重复。你的解正确，而且
比面试官的好。
但既然他不允许（估计他不会），只好排序，用二分查找。
还有一种，就是两个都排序以后，两个指针一起扫A,B,每次输出比较小的值，并改变那
个指针，如果等值则不输出，两个指针一起增加。也是nlgn的复杂度。
总结, 你的面试官是个面瓜。 |
|
f*****e
发帖数: 2992 | 49 parent用count(type int)，不能分辨。parent用你说的那种就变成O(NlgN)了。 |
|
i********m
发帖数: 332 | 50 来自主题: JobHunting版 - BB 电面 昨天电面BB，今天一大早收到onsite通知，真是有效率。
下面是昨天的题，
1。用什么数据结构存(key,value) pair? 如果你只知道这个key的前几个字母，比如
cat，只要是以cat开始的你都想存，用什么数据结构。
2。6位数的彩票，如果前三位和后三位的sum相同，则为中奖彩票，问有多少种中将可
能。
3。 100盏灯，刚开始是灭的，以后第一次全部flip，第二次每隔一个flip，第三次每
隔两个flip，。。。。 问最后亮着的灯是哪几盏。
4。 有很多URL，用什么数据结构存最近访问的100个。 要想访问最近访问的100个 in
order，用什么数据结构。NlgN 他说不太好。有没有其他的？
5。我有什么问题要问他的。
题不难，bless onsite。 |
|
