b******v
发帖数: 1493 | 1 T(N) = O(\sqrt(N)) + T(3N/4) =O( nlog n). N=n^2
那么T(N)=O(N^(log_4 3()=O(n^(log_2 3)) 比nlog(n)大。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器 |
|
h********e
发帖数: 1972 | 2 一般面试不会见到这种东西的。权当娱乐吧。
P1:两个sorted数组，每个数组选一个数，相加。求第k大的和。
P2:一个n*n的矩阵，行和列都是sorted的，求第k大数。假设是从左到右递增，从上到
下递增。
P1是P2的特例。
这个题目O(n^2)是最直接的解法。然后有个O(k logn)的用堆来做，稍微tricky一些。
下面说下n logn的怎么搞出来。
首先想到的是套median的算法。比如一开始拿矩阵中心的那个数,say q 出来。从右上
开始往左下 能用O(n)的时间找出一条分界线, 这条分界线是单调的。使得这条线以上
的数比q小，下的数比q大。然后扔掉不对的那一半递归。第一次这么扔能扔掉至少1/4
的矩阵。问题来了，第二次继续在剩下的里面怎么做。
剩下的是神马。。是n 个row。每个row大小都不一样。目标是在这堆row里面扔掉至少1
/4. 这时候，每个row 可以找出一个median来。然后一般的做法找medians的median。
但是在这里行不通，因为有的row size比较小，这么做不能保证每次扔掉1/4. 必须修
正算法。要找weighted median。这... 阅读全帖 |
|
h********e
发帖数: 1972 | 3 我还是写出来吧。。。T(N) = sqrt(N) + T(3N/4) = sqrt(N) + sqrt(3N/4) + T(9N/
16) = ... = sqrt(N)+sqrt(3N/4)+sqrt(9N/16)+sqrt(3^3 N/4^3) ... = 一共重复log
_{4/3} N次。。所以最后是O(nlog n)... |
|
s******n
发帖数: 7 | 4 Just a guess: suppose O(n^2) = C_1*n^2 and O(nlog(n)) = C_2*nlog(n) then for
n such that C_1*n^2 < C_2*nlog(n) ,i.e. when n/log(n) < C_2/C_1 we prefer
the former ? |
|
p*********9
发帖数: 30 | 5 sorry,看错了。
但是最外面两层loop已经是Nlog(N)了，里面还有跟j相关的loop，所以这个复杂度比
Nlog(N)高了。
还有一点没有看明白，最后交换的时候，您老是怎么保证order的？特别是正数的长度
和负数的长度不一致的时候 |
|
R********n
发帖数: 3601 | 6 【 以下文字转载自 SanFrancisco 讨论区 】
发信人: soldiercrab (老军医专治装B文学小青年), 信区: SanFrancisco
标 题: 一朋友被Google的电面干掉了
发信站: BBS 未名空间站 (Sat Dec 5 15:03:55 2009, 美东)
栽在一道编程题上：Find a longest increasing subsequence in an integer array。
问问题的人要求朋友拿出O(nlog(n))的算法，但朋友只给出了O(n^2)的dynamic
programming的方法。其实我觉得给出dynamic programming算法足够进入下一轮了。那
个O(nlog(n))的算法好歹也值当年一篇paper，而且貌似不是那么直观。电面就想出来
不容易。不过多半是我段位不够，还不够Google的要求。或者朋友的dynamic
programming其实错了（这道题要倒过来找，稍微绕一点点）。 |
|
h*******e
发帖数: 1377 | 7 第三题似乎一般一个整数的勾股数个数是确定的。大概只有几组解 可以先 (nlog n)
sort之后再查找那几组数是否存在。 3 可以知道勾股数大概是 (3*3+1)/2 (3*3-1)/2
4 可以知道勾股数 也有公式 4/2=2 2^2-1 2^2+1 这样只用 binary search 就可以了
总复杂性nlog n |
|
b*******g
发帖数: 355 | 8 如果是32bit int，则512M，不算很过分的空间要求。
如果用map，则avarage time complexity是nlog（n）（如果不对请指正）
在nlog（n）的情况下就不用map了，直接sort后再遍历一边就可以了。 |
|
b*k
发帖数: 27 | 9 O(nlog(n)) solution:
Using DP in general:
sort (i, ai) by ai take O(nlog(n))
got (i_1, ai_1), (i_2, ai_2), .... (i_n, ai_n)
where ai_1 >= ai_2 >= ... ai_n
then keep a minHeap and maxHeap for i_k
maxInfo.cap = -INF;
for (each i_k from (i_1 to i_n))
i_min = minHeap.getMin();
i_max = maxHeap.getMax();
tmpCap = ai_k*(max(abs(i_k - i_min), abs(i_k - i_max)))
if (tmpCap > maxInfo.cap)
maxInfo.cap = tmpCap
//book keeping the i_k, and i_min or i_max
minHeap.insert(i_k)... 阅读全帖 |
|
k****n
发帖数: 369 | 10 来自主题: JobHunting版 - 一道G老题 Master theorem wont lie...
Really think about the bottom-up heapify example.
the root element needs lgn siftdown, the two child need lgn-1 siftdown, ...
how can the whole operation takes O(n)?
of coz if m and n differ a lot, that's another story,
suppose array size m is much bigger.
At the leaves level, in total n binary searches are done on average m/n
segments, that is log(m/n) each, so its n log(m/n)
at its upper level, n/2 binary searches on segments sized 2m/n,
it's nlog(m/n)* (log2/2) = n ... 阅读全帖 |
|
y*****n
发帖数: 243 | 11 I made it wrong again, it should be nlog(n)
log(n-1)+log(n-2)+....log(1) = log((n-1)*log(n-2)*...log(1))
=O(nlog(n))
Hope it is right this time |
|
d******y
发帖数: 244 | 12 log(n-1)+log(n-2)+....log(1) = log((n-1)*log(n-2)*...log(1))
=O(nlog(n))
this one should be
log(n-1)+log(n-2)+....log(1) = log((n-1)(n-2)...(1))
log(n-1) O(nlog(n))
Is this right? |
|
l*********8
发帖数: 4642 | 13 如果在每行使用binary search，那么每轮更新是nlog(m).
但如果采用顺序查找，因为矩阵A在每列也是有序的，所以查找的下标在一轮中是不用
回头的。
例如：
假如pos[4]值为13,因为A[5][13] >= A[4][13]，所以pos[5]就从13开始递减搜索，
假如pos[5]值为8，因为A[6][8] >= A[5][8], 所以pos[6]就从8开始递减搜索。
....
查找下标最多移动m次，重复使用的下标值最多n次，所以是O(n+m).
当然，如果m相对n很大，可以用binary search, 这样nlog(m)的效率还是比 O(n+m)好
些。 |
|
e****e
发帖数: 418 | 14 这题用partition + merge搞是nlog(n)吧。
T(n) = 2T(n/2) + n, 用主定理算出来是nlog(n). |
|
l**h
发帖数: 893 | 15 通过多次两路归并？这个复杂度比min heap要高吧，
假如合并之后的总数据长度为n,
多次两路归并 O(nlog(n))
多路归并(用min heap): O(nlog(k)), k是原始linkedlist个数 |
|
f******k
发帖数: 43 | 16 多线程来做无非就是复杂度除以线程数，不会改变复杂度级别吧，还是nlog(n)吧，除非
生成的线程数是和n相关的
是啊，但是paralellized不就可以超过nlog(n)吗。一般的merge sort是sequential的。 |
|
x****g
发帖数: 1512 | 17 我的理解是给出任意时间点，最繁忙的进程。
假设数每个数据为A{start,end,load}
举个简单例子:
A{0, 3, 1} A{1,4} 2.
那么结果就是:
{0,1}最大1
{1,4}最大2
其它时间没有.
貌似Nlog(N)的算法?
按开始时间排序. Nlog(N)
A1.....An
如果:
A1.end <= A2.start 输出A1就行.
否者
A1.end > A2.start.
输出A1.start A2.start A1 weight
同时更新 A2 weight = max (A1,A2) weight.
继续下一个,直到结束. |
|
g*******7
发帖数: 32 | 18 排序是nlog(n), Heap是nlog(k) |
|
m*****n
发帖数: 2152 | 19 C++用map插入就是nLog(n)，好处是不用排序。
用unordered_map插入式O(n)，但是之后要导入sequence container排序，还是nLog(n)。
这题最好的解法应该还是hash table。
不过为了避免rehash，可以traverse tree 一次找出最小和最大的column ID。
然后平移[min, max] -> [0, max-min] (min是负的)， root column ID就是-min了。
同vector >(max-min)，可以用level traverse tree，插入每个节点，
这样可以保持vertical的顺序。最后O(n) 遍历一下vector，以及下面的list就搞定了。
最后是time complexity 3*n，勉强也算O(n)吧。
treeset |
|
h***s
发帖数: 45 | 20 来自主题: JobHunting版 - F家题请教 我理解题意是："n条线段，所有线段的端点都在圆上，找出包含最多不相交线段的集合
。"
计算出所有线段的slope，有n个。
因为2n个点都是distinct的,所以n个线段不会有重叠的，找出不相交的线段最多的集合
，也就是找出同样斜率最多(平行线最多)的集合。如果将n个斜率排序，问题就转化成"
find the most duplicates in a sorted list"
Time: O(nlog(n) + n) --> TO(nlog(n))
Space: O(n) 需要一个array来存slopes，排序也会需要额外的空间，不会超过O(n)
不知道我理解的对不对，大家指正一下。 |
|
b**********n
发帖数: 21 | 21 我来回答下第一题：
先放等式：
需要的房间数 = meeting overlap 涉及meeting数量最大的meeting数
可能以上公式比较抽象，举两个例子
Example #1
Meeting #A， start 1:00, end 3:00
Meeting #B， start 2:00，end 4:00
Meeting #C， start 3:00，end 5:00
在Example #1 中，需要的meeting room 数是2， 因为这三个meeting的overlap部分最
多只涉及到2个meeting
Example #2
Meeting #A， start 1:00, end 3:00
Meeting #B， start 2:00，end 4:00
Meeting #C， start 2:00，end 5:00
在Example #2 中，需要的meeting room 数是3， 因为第三个meeting时间提前了，
overlap部分最多涉及到3个meeting
所以算法如下：
1.按照starting time给meeting排序（nlog（n））
2.iter... 阅读全帖 |
|
b**********n
发帖数: 21 | 22 大家真的看懂我的答案了吗？感觉大家都没看懂，好桑心！
可能是我语言表达能力太差，我的意思是这题有nlog（n）的解法啊！
帖code
import headq
def scheduleMeeting(self, meetings):
meetings.sort(key = lambda x: x[0])
heap = []
cnt = 0
max_cnt = 0
for i in range(len(meetings)):
while heap and heap[0]<=meetings[i][0]:
heapq.heappop(heap)
cnt -= 1
cnt += 1
max_cnt = max(max_cnt, cnt)
heapq.heappush(heap, meetings[i][1])
return max_cnt
... 阅读全帖 |
|
s*****n
发帖数: 2174 | 23 good point. 我那个code复杂度是nlog(n)级的, 你那个的本质是n级的. 其中n是平均每个symbol对应的数据长度.
不过这两个的速度优劣要看数据的情况. 如果一个symbol对应的数据较多, 第一种solution里面的排序的确比较慢. 如果对应的数据较少第二种solution里面独立算sign(), max(), 相乘, 取== 的成本比较高.
实际复杂度, 第一个solution 大概是 nlog(n), 第二个solution是4n.
当log(n) > 4 也就是 n > 56 的时候, 第二个快, 反之第一个快.
看实测:
### 26个symbol, 总共1000个数据, n大约等于40, 第一种稍快
> data <- data.frame(
+ symbol = sample(LETTERS[1:26], size = 1000, replace = T),
+ fold = sample(-15:15, size = 1000, replace = T)
+ )
>
> system.time(for (i in 1:1000)
+ te |
|
发帖数: 1 | 24 对于大部分人来讲CS的难度是O(n)，因为新东西出来总归要花时间去学去看文档，而物
理的难度因人而异，聪明人可能是nlog(n)，笨人就是n!，cs里面再难的东西找个有经
验的人教教总是能明白，物理就不行。
当然有些theoretical computer scientist试图弄出很fancy很难的理论，在物理学家
看来就像小孩模仿大人穿衣服一样搞笑。 |
|
M*P
发帖数: 6456 | 25 现在还整什么比什么难，这就是脑子里进水了。难的东西未必有用。
：对于大部分人来讲CS的难度是O(n)，因为新东西出来总归要花时间去学去看文档，而
物理的难度因人而异，聪明人可能是nlog(n)，笨人就是n!，cs里面再难的东西找个有经
：验的人教教总是能明白，物理就不行。 |
|
发帖数: 1 | 26 对于大部分人来讲CS的难度是O(n)，因为新东西出来总归要花时间去学去看文档，而物
理的难度因人而异，聪明人可能是nlog(n)，笨人就是n!，cs里面再难的东西找个有经
验的人教教总是能明白，物理就不行。
当然有些theoretical computer scientist试图弄出很fancy很难的理论，在物理学家
看来就像小孩模仿大人穿衣服一样搞笑。 |
|
M*P
发帖数: 6456 | 27 现在还整什么比什么难，这就是脑子里进水了。难的东西未必有用。
：对于大部分人来讲CS的难度是O(n)，因为新东西出来总归要花时间去学去看文档，而
物理的难度因人而异，聪明人可能是nlog(n)，笨人就是n!，cs里面再难的东西找个有经
：验的人教教总是能明白，物理就不行。 |
|
|
c********a
发帖数: 16 | 29 1. Research topic
2. Algorithms questions
(1) Given an arry of integers, how to find the maximum and mininum?
My first answer is 2N comparisons. Then the interviewer asked how to
improve the number of comparisions.
(2) Given two sorted arrays of size m and n respectively. How to merge them
together? Write the code.
My answer is m + n. Then he asked what happen if m >> n.
My answer is interting the n numbers to the larger array by binary search
.
The complexity is O(nlog m).
(3) How to d |
|
k***e
发帖数: 556 | 30 555 I made mistake again
it should be nlog{total sum} or n(lgn + lg(max))
when negative numbers are allowed, it is very messy. i am not quite sure the
binary search works. But DP definitely works, which require nk space and n^
2k time.
max}? |
|
t**g
发帖数: 1164 | 31 给一个sorted array
想知道是否有2个元素的和等于s
问O(n)的算法 (不是O(nlog(n))
thanks |
|
c*m
发帖数: 1114 | 32 其实插入法虽然是n^2,很可能大多数情况下比nlog(n)的堆排序都要更有效率。
1. 大多数情况下它不需要排序完就知道结果了。
2. 排序过程中可以配合相同元素(分别在不同数组里时才执行)消去的操作,导致n比较
小。
3. Implement比较简单。 |
|
j****a
发帖数: 55 | 33 我对第一题的想法是：
LZ的方法是2*n log(n) + n,最后那个n是因为两个list要比较一下。
我的想法是: 只要sort一个list，n log(n)，然后拿另外一个list的每一个数字去
sorted list里面找。这样是：n * log(n)。所以最后是2*n log(n)。
虽说两个方法都是O(nlog(n)),可是少一个n在practical programming的时候还是有可
能挺重要的... |
|
f**r
发帖数: 865 | 34 The divide & conquer algorithm is nlog(n) ah, N elements swapped in each
round, logn rounds in total. |
|
b******v
发帖数: 1493 | 35 有序的话，对每个元素a[i]，用binary search找K-a[i]，代价是log n
那么一共是 O(nlog(n))吧？ |
|
h*******x
发帖数: 12808 | 36 第一题先排序，然后二分搜索。
这样O（nlog n），还有更快的吗？ |
|
z****g
发帖数: 1978 | 37 其实还有更简单的
假设数据存在list a里
bool IsNegaitve(int left, int right){ return left<0 && right>0; };
a.sort();
这个应该就可以了，原理上是nlog(n)的全排序，但是因为只有left<0, right>0才是正
序，所以应该是n要快 |
|
g******i
发帖数: 354 | 38 多谢。简洁明了。
不过这样找的话， 要用nlog(n) (loop the array is n, and binary search is log(
n)).
In additon to that, the first step: sorting is nlong(n) as well.
plus this two steps together = 2nlog(n), and it's still nlong(n) in
complexity. |
|
h********e
发帖数: 1972 | 39 我来贴个答案吧。。动态规划不怎么可取，因为多半是伪多项式的。hashtable 也不好
，怎么说呢，hash都是投机取巧。很多面试摆明了不要你hash的答案。sort吧，挺好。
。重点是然后可以这么做。。
8, 10, 2, 9, 5, 7, 1
排好序是
1 2 5 7 8 9 10
然后用19 减一下是
18 17 14 12 11 10 9
然后干啥。。
用一次merge排序的merge方法。。就能用n的时间找到是否两个序列有相同的东西了。
当然还有些细节。。
这样好歹能拿出个nlog+2n的算法。。还凑合，当然如果考官只要求O(nlogn)就无所谓
了。 |
|
f*******r
发帖数: 1086 | 40 也可以说是nLog(n) 吧，我是看到有文章提到k表示子序列的长度 |
|
l******l
发帖数: 497 | 41 其实题目很简单，可能我非cs专业的吧
早上见了recruiter , 然后去了 city center 面 bing
（1） 印度人，人很nice, 口音不重。 coding: 一排球，有红有绿。 给出算法，使得
最后红球在左边，绿球在右边。 （不能数数）。 我给出了O(n) 和 O(nlog(n)) 的算
法。 然后如果有三种颜色，怎么办
(2) 俄国人。给一个linked list, 一个getnext() 函数。到list 末端的时候，
getnext()=0 。不能 go back. 给出算法，使得getnext=0 的时候，输出一个随机数，
这个数在list 里面， 而且每个数出现的概率相等
（3） 俄国人，lunch interview. 饭后coding. 下楼梯问题
就面了这些，当时就觉得希望不大。果然今天收到拒信一封。
不知道这些能不能帮上大家。为下周的面试攒rp |
|
|
|
t****a
发帖数: 1212 | 44 What about:
1. get a sorted x vector and y vector individually
2. visit the element in x and y by the time liking merge sorting
3. when visit an element in x, count++; when visit an element in y, count-
-;
4. record the max count in visiting.
it is O(nlog(n)) |
|
g***s
发帖数: 3811 | 45 二分的速度can be polished to O( nlogn + nlog(max of 所有数字) )
DP could be O(nklogn) |
|
r******d
发帖数: 308 | 46 用堆思路可能更加清楚把, 不插入一个节点过复杂度都是 lg(n)
http://en.wikipedia.org/wiki/Selection_algorithm
上面的连接还有o(n)的算法, 不过......看了半天没有琢磨明白, 所以面试的时候就说
了说我能够理解的方法
Data structure based solutions
Another simple method is to add each element of the list into an ordered set
data structure, such as a heap or self-balancing binary search tree, with
at most k elements. Whenever the data structure has more than k elements, we
remove the largest element, which can be done in O(log k) time. Each
insertion operation also takes O(... 阅读全帖 |
|
b*****n
发帖数: 143 | 47 Thank you for your replies, guys. So after the cumulation array is sorted,
we will ignore the original cum[0] and cum[1] during the binary search of
cum[2]+t. Is this the idea?
By the way, if my memory is correct, "Programming Pearls" claims that the
optimal solution to this kind of problem is nlog(n). So a linear-time
solution doesn't exist. (Note that we are looking for a subarray whose sum
is closest to t. So the sum could be either smaller or larger than t.)
Thanks again. |
|
b*m
发帖数: 6 | 48 for each cum[i], should search for cum[i]+/-t. so 2nlog(n) + original sort(n
(logn)) 3nLog(n) ==> nLog(n). |
|
c******n
发帖数: 4965 | 49 thanks
but no, if u do k-way merge, you get a strictly monotonic sequence,
instead of the more relaxed condition.
unless you can show details of the k-way merge you are talking about.
the point of the relaxed condition is that it should give you
opportunity to come up with a faster than nlog(n) time
belong to |
|
c******n
发帖数: 4965 | 50 thanks
but no, if u do k-way merge, you get a strictly monotonic sequence,
instead of the more relaxed condition.
unless you can show details of the k-way merge you are talking about.
the point of the relaxed condition is that it should give you
opportunity to come up with a faster than nlog(n) time
belong to |
|
