h****e
发帖数: 928 | 1 请问1log1+2log2+...+NlogN的复杂度是多少？是N*NlogN，还是
N*N。 |
|
t*****e
发帖数: 53 | 2 Can we design an algorithm that can find the triplet in an unsorted array (
including both positive and negative numbers) that sum up to a defined
number? Requirement: the runtime should be o(nlogn).
I can think about alot of O(n^2) way. Do you think this problem has a
solution with O(nlogn).
thanks in advance. |
|
w*********0
发帖数: 48 | 3 有几个蛮常见的
longest increasing subsequence 有O(nlogn)的 我只能写到O(n^2)的 O(nlogn)基本
只能靠背
longest palindrome substring 有O(n)的
还有就是经典的KMP，这个貌似还好
这种题目 需要背下来最优解么。。。。 |
|
w***g
发帖数: 5958 | 4 【 以下文字转载自 Programming 讨论区 】
发信人: wdong (cybra), 信区: Programming
标 题: 算法导论重点
发信站: BBS 未名空间站 (Mon Oct 15 17:15:36 2012, 美东)
上次在CS版答应给划重点的，发到这儿算了。我手上是第二版。我觉得转行的没有基础
的看完下面这些(约300页，全书1/3的样子）在算法上基本上能达到科班出身水平。可
以按书本身的顺序看，也可以按下面给出的顺序看。
A. 基本概念
1-3 pp.1-61
B. 基本程序设计方法
穷举法 看眼八皇后问题的接法和产生全排列的方法
贪心法 16.1-16.3 pp.370-393
23.1-23.2 pp.561-580
动态规划 15.1-15.4 pp.323-356
分治法(divide and conquer) 本书没有专门的章节讲这个，需要自己随便上网搜搜。
结合下面章节看
选中位数 9.1-9.3 183-189
快速排序和二分查找
回溯(recursion) 这个是具体的实现方法，可以和... 阅读全帖 |
|
e***s
发帖数: 799 | 5 我不是很懂你的方法，binary search用在哪里？
我的方法是，
Sort except array O(nlogn)
create new 0 ~ (n-k) array O(n)
Get random number in new array O(1)
整个算法 O(nlogn) |
|
f*********d
发帖数: 140 | 6 NDA滚犊子:)
12:45 HR美女带上楼
////////////////////////
1
////////////////////////
白人年轻哥们比较牛，感觉他反应很快。。但很nice
来了三年多了。。。
单词路径查找问题。。。
刚开始做得不顺利，
提了建立图
再提了bfs
bfs + hash
写了个递归解的code
////////////////////////
2
////////////////////////
刚来的白人本科毕业生
题目出得不难
bst hash比较
相似字符串analog
先用排序方法
再用hash方法
都写了code
////////////////////////
3
////////////////////////
白人大哥30多岁，来7年半了
讲project
排序复杂度
问题等价于 找两个整数，使得和最解接近目标解，但不能超过
会2sum problem，就会这个做问题
平方解
nlogn解
O(n)解 失败， 2sum可以用hash，这个貌似不行，他同意了
写了nlogn的代码
////////////////////////
... 阅读全帖 |
|
c**s
发帖数: 159 | 7 时间复杂度为O(n)的in-place算法 可以搜perfect shuffle problem 很复杂。
还有个O(nlogn)的分治in-place算法 用到循环移位 可以比较简单的解决：
（1） 把b部分循环移 n/2 位 这样 中间的n个元素元素是a的后n/2个和b的后n/2
（2） 对中间n个元素递归完成任务 这样 中间n个满足要求了
(3) 对全体的后3/4×（2n) 的元素 循环移动 n/2位， 这样后面n个元素满足要求
前面n个元素又是一半的子问题
（4）完成前一半的n个的任务
循环移位是O(n)的
复杂度 T(n) = 2 * T(n / 2) + O(n)
总复杂度T(n) = O(nlogn) |
|
f*********d
发帖数: 140 | 8 补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
包子！
===============================================
Oct.19th ，东部时间1:30， 一面，印度a3
1，为什么基于比较的排序问题复杂度下界是O(nlogn)
回答出来了，他表示赞同
2，分析下面递归算法的复杂度
Alg(array, size)
split -> A1, A2, A3.... O(n)
Alg(A1, size/3)
Alg(A2, size/3)
这个题目是硬伤，他push我快快快，我一紧张，递归函数没有写好， 写出来之后
说用主定理，再一紧张把 a 和 b搞反了。。。
F(n) = a * F(1/b n) + O(n)
总的来说这题做错了
3， 大数据的平方 X^2 X很长 不能用int long 之内的表示
一开始就反应时Divide and Conque， 他表示赞同， 但是我始终没有到NlogN, 只
到了N... 阅读全帖 |
|
f*********d
发帖数: 140 | 9 从数学角度，是不对的，
我们说的是从复杂度角度看，
O(logN!) = O(nlogn) 其实不够严谨
应该写 \omega(logN!) = \omega(NlogN), 即同阶:) 不知道你是不是这个意思？！ |
|
j*****y
发帖数: 1071 | 10 一面的第三题一般是可以做到 n^(log3) 吧？
比如 算 A * A where A is n digits number
A = B * 10^(n / 2) + C
A * A = B * B * 10^n + 2 * B*C * 10(n / 2) + C * C
need to compute B * B, B * C and C * C
So we compute three items below:
(B+C) * (B+ C) = B*B + 2*B*C + C*C
B*B
C*C
from which we can get 2*B*C = (B+C) * (B + C) - B*B - C*C
let the time for A^2 is T(n)
so we have T(n) = 3 T(n/2) + O(n)
and T(n) = O(n^(log3)
这里假设两个 n digits number的求和需要 O(n)的时间
补上一份详细的g家店面面经，或许对即将要面的，准备面的都有帮助， 我也顺便搞点
包子！
=======================... 阅读全帖 |
|
l******s
发帖数: 1276 | 11 合并两个排序好的数组 O(n)
合并排序 O(nlogn)
快速排序 O(nlogn)
二元搜索一个排序好的数组 O(logn)
?? |
|
d*******8
发帖数: 30 | 12 发现我说错了，应该是o(n2) 。我是想说从2sum变形过来的，2sum是O(nlogn). 不过排
序是o(nlogn) , 找只要o(n)...
看来接到邮件混乱了 |
|
w****x
发帖数: 2483 | 13
n代表list个数m代表平均节点数吧， 那怎么可能是nlogm, 每个节点都不走一边？
应该是m*nlogn吧， 我那个也是m*nlogn， 一个复杂度 |
|
Y**Y
发帖数: 66 | 14 回错主题了，有另外一贴double link list奇偶排序的。原帖删了。
数组的这个想出了一个nlogn的in place方法
1. 每两个数一组，每组内变成odd/even order，最后一组可以小一些。
2. Repeat: 上次的每两组合并, 前组后面的even numbers和后组前面的odd numbers换
位。直到合成一组。
Complexity: O(2)*n/2+O(4)*n/4+ ...+ O(n) = nlogn
长度不同的组换位：
For example, swap {1...m} with {m+1 ... n} assuming m>n.
swap {1 ... n} with {m+1 ... m+n},
then the problem is reduced to swap {n+1 ...m} and {m+1...m+n}
Complexity: f(m+n) = O(n)+f(m) = O(m+n) |
|
c***s
发帖数: 192 | 15 哦，对，应该是O (nlogn).
用公式算的话，应该是 T(n) = 2T(n/2) + n = O(nlogn).
O( |
|
m****1
发帖数: 41 | 16 这题我正好做过~
好像是O(nlogn)
idea 是这样，依据题意，假如第i天的股价最高，那么前 i-1天都是买， 第i天卖 赚
最多
好，处理完一次以后，前i个可以不看了，从i+1开始，再找从i+1到结尾 最大的最大股
价，重复操作直到 i = size of array -1;
建一个
struct day {
int value; //当天的股价
int id; // 第id天
}
对 value 进行 NlogN 的排序，
然后扫一遍 就Ok |
|
a*******3
发帖数: 27 | 17 对N个数组中的最大元素开始做二分，找到一个最小的m，是的N个数组中恰好有>=k个数
小于等于m，那么m就是所求。
每次求N个数组中多少个元素小于等于m，nlogn，最多二分32或者64次（取决于数据是
32位还是64位），这样看的话是nlogn的，只不过常数有点大
如果不认为这个实常数，那么就是nlog(n)log(max_value-min_value)
klogn的问题是，k可能很大，如果k~n^2/2，那复杂度就高上去了 |
|
d*******3
发帖数: 58 | 18 nlogn的不是这么做的，你想想你的a数组都不是有序的，怎么能binary search呢？
nlogn的是用数组a[i] 保存长度为i的递增序列末尾的最小元素，后面通过二分查找来
维护这个递增数组。
你的例子里不太明显，我换个
src:
2 9 7 3 8 5 10
a id:
0 1 2 3 4
2
2 9
2 7
2 3
2 3 8
2 3 5
2 3 5 10
这样最后递增序列长度为4 |
|
P*******y
发帖数: 168 | 19 一共两轮，通过LinkedIn找人内推拿到的面试。
第一轮：美国人
1. three sum，很快给了n^2的解，然后问nlogn的解，提示说用hash_map，想了一会儿
想不出来，然后就move on下一题。后来到版上问发现被忽悠了，应该不存在nlogn的解
2. 2G 大文件，RAM只有1G，怎么sort。
3. 一个image，每个pixel一个颜色。给你其中一个pixel的位置，以及一个颜色，如果
那个pixel颜色和给的一样，什么都不用做，如果不一样，就把这个pixel变成给定的颜
色，同时把他的neighbor和这个pixel原来颜色一样的也换成新的颜色，然后再
neighbor的neighbor这样下去。给了思路，没让写code，说我肯定写得出，然后就结束
了。
他家recruiter效率很高，结束后一个多小时就通知过了，安排第二轮。
第二轮昨天，一个三姐，迟到了十分钟。recruiter原来邮件里有说如果面试官十分钟
内没来，给她说一下。十分钟刚到，给recruiter发了邮件，三姐就打过来了。就开始
面了。
1. 给个时间，string格式，比如10:35，让你求时... 阅读全帖 |
|
b********g
发帖数: 28 | 20 1. Sort a linked list in O(nlogn) time with o(1) space complexity. Recursion
doesn't work here.
2. Given 3 integer arrays, find an item from each array s.t. a+b+c=0 in O(
nlogn) time |
|
r*********n
发帖数: 4553 | 21 国女问的题应该是increasing subsequence吧，如果是increasing subarray，最优解
法是O(n)，如果是subsequence，最优是O(nlogn)吧
wiki上面有一个O(nlogn)的解法，但是需要两个auxiliary arrays，而且index套index
的，看起来不好理解。其实面官提示用BST是对的。
整个算法的outer loop是DP的思想，inner loop的思想是在array elements seen so
far里面做binary search找到new element的位置，但是要一边BS，一边update 这个
array，所以用binary search tree (balanced)。 |
|
l****i
发帖数: 2772 | 22 报一个迟到的面经，4月底onsite的，早上8点进，下午4点出，第2天早上9点收到offer。
记得的题目,所有题目都白板写了完整coding：
1. 未排序数组返回第K大 （quick select+median of medians）
2. LCA （带parent节点+不带parent节点）
3. 返回链表的倒数第K个数
4. 反转句子，不反转词
5. 中序+后序构建BST
6. 未排序数组，返回需要最少移动几个数，使这个数组变成排序
例如， [1,3,2] 返回1
[1,3,5,2,7,9,4] 返回2
我白板给的是复杂度O（n^2）的DP解法，就是DP里经典的求最长不降序列。面试官
问为什么选择DP。然后让优化，我解释说，最长不降序列有一个O（nlogn）的算法，需
要占用更多的space，具体的算法，我记得不是很清楚。面试官说有一个求2个数组最大
相似度的算法，是O（nlogn）,可以用来解决这个问题。就是比较[1,2,3]和[1,3,2]的
最大相似度。面试官和我说，这个比较相似度的算法，有人发过paper。
其他还有大概3-4道更基... 阅读全帖 |
|
x***y
发帖数: 633 | 23 来自主题: JobHunting版 - 两道F的题 for 2nd problem, flip makes it possible to do insertion sort in O(nlogn)
time.
One nice thing about flip is that if we want to insert an element into an
ordered subarray in the head, it only takes O(logn) time.
For example, if we have an array 1 3 5 7 8 9 6 2 , and we want to insert 6
to 1
3 5 7 8 9.
First we need to know the expected position of 6(O(logn)) (assume that it's
k), then
flip(0) ---> 2 6 9 8 7 5 3 1 (0 is trivial)
flip(1) ---> 2 1 3 5 7 8 9 6 ( 1 = len(array) - ind(6)-1)
flip(4) -... 阅读全帖 |
|
r*********n
发帖数: 4553 | 24 来自主题: JobHunting版 - 周末出道题 因为可以在O(logN)时间内找到median，在O(N)时间内算出每个数到median的绝对差，
所以这到题和下面这题是等价的：
在无序非负数组里面找最小的k个数，时间在O(N)之内。
最坏的情况是k=n/2，所以用基于heap的方法，至少要O(NlogN)。但是这个问题可以继
续用quick sort的思想做，但貌似the expected running time is still O(NlogN)。 |
|
r*********n
发帖数: 4553 | 25 来自主题: JobHunting版 - 周末出道题 a counting argument can show that the theoretical lower bound of any
comparison-based algorithm for this problem is O(NlogN).
suppose you have the sequence sorted, then you know what those k values are.
now we can count how many distinct sequences the algorithm has to resolve:
out of N numbers, we choose k to fill in those k positions centered at the
median:
(N choose k) * k!
however, among those sequences, k! sequences are correct (disregarding the
relative order, since we don't care). hence th... 阅读全帖 |
|
f*******b
发帖数: 520 | 26 总体来说时间复杂度应该是：
Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
memorized了？？就是2爷说的cache
int CalMax(Interval[] inputs,int end, int[] P)
{
if(end<0)
return 0;
return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
CalMax(inputs,--end,P) );
} |
|
f*******b
发帖数: 520 | 27 总体来说时间复杂度应该是：
Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
memorized了？？就是2爷说的cache
int CalMax(Interval[] inputs,int end, int[] P)
{
if(end<0)
return 0;
return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
CalMax(inputs,--end,P) );
} |
|
f****p
发帖数: 18483 | 28 笨死！在那些O(nlogn)的算法中，有两个常数就是说cost = A*(nlogn) + B。
on average，quick sort的这两个常数都是最小的。 |
|
f****p
发帖数: 18483 | 29 在一般情况下，quick sort比heap sort快是因为下面几个原因。
1）quick sort没有事先的准备。heap sort一开始要建堆。
2) quick sort 在一个pass以后，分界的那个element就是最终结果，一个pass的cost
和整个pass的数乘积基本上就是nlogn。heap sort取出一个后得要从上到下做调整，就
是差不多logn，乘积也差不多是nlogn。
3) 如果是多个cpu，多个thread，quick sort 绝对要比heap sort 强。
其实quick sort 主要的强的就是1) |
|
d****n
发帖数: 397 | 30 divide conqur?和mergesort一样nlogn?
有0就输出true,如果数组不含0，
首先讲数组分为两半
判断两半是不是有true,有的话，return true,否则从中间开始，
i=floor[n/2],j=ceiling[n/2],如果i--,j++,直到i=0,j=n-1还没有sum是0的情况，
return false.
这样
T(n)=2T(n/2)+theta(n)=theta(nlogn); |
|
|
d*k
发帖数: 207 | 32 Add my two cents
一個nlogn的方法：求最長遞增子序列，可以nlogn做到。總長度減去最長遞增子序列的
長度即為所求。
應該有更好的方法，因為沒用到1-n這個條件。 |
|
l*n
发帖数: 529 | 33 描述得看不懂啊。写了个感觉比较简明的，就是对所有不可再分的区间进行计数。
排序O(nlogn)+查找O(2*nlogn)+计数O(n*m)，其中m是平均区间分割数。
List mostOverlapped(Interval[] ints) {
Set set = new HashSet();
for (Interval itv : ints) {
set.add(itv.start);
set.add(itv.end);
}
// all candidate intervals;
List ends = new ArrayList(set);
Collections.sort(ends);
int max = 0;
// count overlapped times of each candidates
int[] counts = new int[ends.size()];
for (i... 阅读全帖 |
|
m*******0
发帖数: 38 | 34 又想了一下总时间应该是O(N^{4/3} + NlogN)吧，要对每个n从1～N来验证，每个n验证
的时间是n^{1/3}，加上排序总时间就是N^{4/3} + NlogN ? |
|
m*******0
发帖数: 38 | 35 又想了一下总时间应该是O(N^{4/3} + NlogN)吧，要对每个n从1～N来验证，每个n验证
的时间是n^{1/3}，加上排序总时间就是N^{4/3} + NlogN ? |
|
w*******s
发帖数: 138 | 36 这道题有两种理解方式。当输入是[1, 1]的时候，有两个sequence满足条件，可是他们
都是[1]，所以根据理解的不同，答案可以是1，或者是2。有一种O(nlogn)的方法，不过
是针对答案是2的情形。
首先得将数组中的元素排序，并按数值大小编号，此时我们将原数组变换为新数组，新
数组中的元素值是原数组中数值大小的编号，新数组中的值是从1到n（n为原数组中不同
数值的个数），长度与原数组相同，对于新数组求解等同与对于原数组求解。
举例，原数组是[9,3,6,3]，变换为新数组为[3,1,2,1]
此变换需要排序，故时间复杂度为O(nlogn)
对于此数组（设为A)，我们可以用等同与求LIS的方法来计算个数(DP)，此方法的复杂度
为O(n^2)，DP的状态是对于每一个数组中的元素，我们记录以其为结尾的不同的subseq
uence的个数，设此数组为D。
在求D中每一个元素D[i]的过程中，我们需要对每一个在此元素之前 j < i，并且A[j]
< A[i]的D[j]求和，此操作可以用树状数组（或类似结构）优化为log n，故总时间复杂
度为O(n log n)，空间复杂度为O(n)... 阅读全帖 |
|
l********7
发帖数: 40 | 37 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
一轮电面之后之后让去onsite
onsite是3轮面试，2轮coding加一轮的experience
coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
string大
第二题是有这么一个class Contact，里面有一个String的name，和一个List
装着email address，是这个Contact有的address，用一个list装着是因为一个人有可
能有多个email，现在给你an array of Contact，比如
#1 John [j**[email protected]]
#2 M... 阅读全帖 |
|
l********7
发帖数: 40 | 38 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
一轮电面之后之后让去onsite
onsite是3轮面试，2轮coding加一轮的experience
coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
string大
第二题是有这么一个class Contact，里面有一个String的name，和一个List
装着email address，是这个Contact有的address，用一个list装着是因为一个人有可
能有多个email，现在给你an array of Contact，比如
#1 John [j**[email protected]]
#2 M... 阅读全帖 |
|
d********e
发帖数: 239 | 39 Given 3 integer arrays, find an item from each array s.t. a+b+c=0 in O(
nlogn) time
可能是nlogn的时间么
谢谢 |
|
r******l
发帖数: 10760 | 40 最常见的其实就O(1), O(logn) O(n), O(nlogn), O(n^2)这几种。基本上hash table O
(1)，一重循环O(n)，双重循环O(n^2)，二分查找O(logn)，排序O(nlogn)。
更具体的分析是比较难，但是基本用不到。 |
|
d********i
发帖数: 582 | 41 小弟请大哥们指教，谢谢。
以下两种build heap的方法。
第一种用PriorityQueue建的heap,请问是O(n)还是O(nlogn)?
第二种不用PriorityQueue,请问是是O(n)还是O(nlogn)。
第一种：
PriorityQueue minHeap = new PriorityQueue();
for (int i : a) {
minHeap.add(i);
}
第二种：
public static void buildMaxHeap(int[] a) {
int i = (a.length - 1) >> 1;
while (i >= 0) {
maintainMaxHeap(a, a.length, i);
i--;
}
}
public static void maintainMaxHeap(int[] a, int heapSize, int i) {
int l = (i << 1) + 1;
int r = (i << 1) ... 阅读全帖 |
|
k*******r
发帖数: 355 | 42 以前版里贴过的一题
void minMSwap(int[] num, int m), return the min array after m swaps， each
swap happens only between two adjacent elements([4,2,1,3], 2 return [1,4,2,3
] )
4,2,1,3
4,1,2,3
1,4,2,3
当时贴的解法是找最小的元素，判断swap它需要的最少交换次数n，如果n<=m，swap过
来，m -= n,递归， 如果n>m?那就找次小的，重复上面的步骤
这个应该是O(n^2)时间复杂度，因为n次循环，每次循环里面找到符合交换次数的没有
用过的最小位又是O(n)的时间。
我觉得每次循环里面用heap优化，有希望把总时间降到O(nlogn), 但检查或update
heap中元素是否符合交换次数这一步还是要耗掉O(n), 这样总时间还是O(n^2)
哪位大牛贴个nlogn的完整解法？ |
|
k********6
发帖数: 33 | 43 按身高排序 NlogN， 然后按身高顺序问数，linear time重现元队列，所以只要NlogN。
解释：
最高的人(P0)站哪里都无所谓，因为他记得数是一定是0.
所以直接问身高第二的人(P1)，如果是0站P0前面，如果是1站P0后面。
再问身高第三的人，。。。。
这题不难，我是不是说太细了， 汗。 |
|
D***0
发帖数: 138 | 44 将近三个月里两次面它家，
第一次折在第一个电话onsite了，一个巨长的名字的老印，coding题不难，看一段代码
，指出哪有问题，第二题是删除linkedlist里的一个node，就用一个指针。然后就是写
sql query，老印说要用having，我说ok，然后就写了一个带having的，然后第二天就
收到拒信，说db太弱。。。这个确实没机会练，也没机会接触。
过了一阵子网投另一组，然后店面，计算一个数组的inverted元素的个数，没见过，直
接给了O(n^2)的，然后问如何改进，实在没想到，就说应该用binary search或者merge
sort的，最低也就是O(nlogn)了，店面过了，然后是一轮code challenge，不难，2个
小时做完发过去。然后onsite，
5轮，每轮一个小时，尼玛，其中一轮还是打电话，
1 像是欧洲人， 一道简单题，不记得了，做完了，面试官说good，然后照相，然后就
是design一个system，说他们现在做这个，好像是个什么连续的incoming字符串流，如
何存储，query，如何得到当前某个metric的lifetime的min... 阅读全帖 |
|
m*****n
发帖数: 2152 | 45 完全被虐死了，中间恨不得把电话给扔了。
下面说说过程，首先说明，全程面试官从来没说过我的任何回答是对还是错，我下面的
回答可能很多是错的。
一个西亚或者印度（口音不太像）面试官 A，一开始聊了一下background，然后丫说先
给你一道简单题做做吧，就是一楼的题。
一开始，听到二维平面，最多点，斜率，还以为是那到最多点共线的问题呢？心中一喜
，然后自己重复问题的时候，A 感觉完全不知道我在说什么。丫又重复了一遍问题，这
时才听懂。
当时第一反应是对一个维度排序，然后DP，说给A听了。
A：时间复杂度是多少？
me: O(n^2)
A: 不行，要nlog(n)。
me: （心理一紧，完蛋了，DP都不行）嘴上说好像可以剪枝。
A: How？
me: (心理说我怎么知道)，胡说半天，说什么用tree啦，找parent啦，连我自己都不知
道在说什么。
A: 好吧，假设你有2维的nlogn的算法了，3维怎么办？
me: 先找一个2维最多的点集，再对这个点集的第3维在做一次这个算法。
A: M维怎么办？
me： 依次类推。
A: 时间复杂度多少？
me: 大概是最坏是m*n*logn吧。
A: ... 阅读全帖 |
|
|
p********n
发帖数: 165 | 47 先排序就得nlogn
然后再比较奇偶 n
所以总体还是O(nlogn) |
|
l*********b
发帖数: 65 | 48 赶紧robot13的解法挺好的 排序nlogN 然后搜索只要N 虽然总体是nlogN 但是思路比较
清楚而且好说好实现 |
|
a***n
发帖数: 48 | 49 4b, 要求N方还是NlogN？NlogN那种现场肯定想不出来的。。。 |
|
A*******e
发帖数: 2419 | 50 * Multi task design
用户可以法请求要求某一个task在某一时间开始执行。这样的请求可能很多。设计一个
系统处理这样的请求。问如果处理系统是local的（和发请求的在一起）或者是remote
的有哪些设计上的不同。
这个没怎么实际做过，只能随便侃侃，简单写了几行伪代码。
汗，没看懂要设计啥。什么叫处理这样的请求？同一时间请求太多，资源不够咋办？
* Quad-tree intersection
一个quad－tree表示一个2D的黑白图，每个节点都是平行于坐标轴的矩形，节点的
value 0和1表示黑和白。如果一个节点全黑或全白就是叶子，否则就继续剖分成四份。
要求写一个函数求两个quad－tree的交。
这个比较简单，写了一个递归的程序，不确定是否有bug。
什么是两个树的交？
* Base64 encoding
先解释了一下何谓Base64 encoding（http://en.wikipedia.org/wiki/Base64），然后要求写一个函数将一个字符串按Base64编码。
用位操作实现，写了简单的代码，不确定是否是他想要的答案。
* Swizzle so... 阅读全帖 |
|
