p********7
发帖数: 549 | 1 MAP 是nLogN，但是hash_map需要你提供hash function，很难提供一个没有collision的
这个题应该有个地方需要注意到是，我觉得应该使用分数去算slope，以及于x轴相交的点横坐标。
因为用float很难保证2个float是相同的，他们永远只是近似相同。
需要写个函数去判断2个分数是否相同。 |
|
|
|
j******4
发帖数: 116 | 4 自己回答一下吧。
L[j+1] = w[i]
B[j+1] = i
P[i] = B[j]
很简单哇。写起来比n^2 的还方便。我上面的理解是对的。 |
|
h**6
发帖数: 4160 | 5 hash table是无序的，这里需要用一个有序的map，比如STL map
考虑同一个点可能有多个出入，存储时:如果是入点，就增1；如果是出点，就减1。
最后按照时间顺序遍历STL map，随时更新人数，这是hash map无法完成的。
复杂度O(nlogn) |
|
t*****j
发帖数: 1105 | 6 sell rating的可能值很少，有的是几星几星，数字的话最多是一位小数。
比如 1，2，3，4，5等相当于不同的bucket，先把书放进不同bucket，
然后根据价格排序。最后连起来就行。
design的话，可以考虑bucket总的是个大容器，里面有5个小容器桶，存书的ID和price
.每次新增加书或者书的rating变化的话，就插入到相应的桶里。桶里各个书的结构可
以用BST.
这样排序是O(nlogn),插入，删除，rating调整都是O(logn)
我瞎说的，请高人看看行不行。 |
|
h**6
发帖数: 4160 | 7 对于每一条对角线，得到两组射线，在其中找出两条相互盖住对方起始点的射线，求最
长重叠区域。这个过程可以有O(nlogn)和O(n^2)的两种算法。
但是2n-1条对角线的数值并不是相互独立的，每一条对角线都只需要寻找比以前的结果更
长的重叠区域，因此可以大大缩短时间。最终我两种寻找重叠区域的算法运行时间都比求
前面几个矩阵的时间还短，因此我认为是O(n^2)的复杂度。 |
|
w*****e
发帖数: 158 | 8 Thanks ihasleetcode,
Sieve method to find all prime numbers for n. By using it, my solution is
like following:
1. go through array A and find the maximum number MAX.
2. use sieve method to find all prime number smaller than MAX. and put
them
into a set (hashtable?)
3. go though the Array again and check whether each element is in the set.
~
O(nlogn) ?
If the array size is 100k and the numbers are between 2k to 8k. the
numbers in the set are the prime numbers in the range(2k,8k).
Correct me if I |
|
A*********r
发帖数: 564 | 9 topcoder上有关于LCA的算法，比较能够接受的有两个：
1）用DP作preporcessing, 用 O(nlogn) time, 然后查询再用O(logn) time
2) 转化为 restricted RMQ problem, 可以达到O(n) time, O(n) space.
（详见http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor）
不过看到了careercup上给出的一个非DP算法，recursive的，貌似算法复杂度也只有O(
n), 但是没有用多余的空间。。虽然topcoder上面的可以查询任意两个node之间的LCA,
但在实际面试题中，我们一般都是会给定两个node，这样看来careercup上的不是更好
吗？！
下面给出careercup上的算法，大家讨论一下看看。
/* Returns NULL, p, q or the nearest common ancestor of p and q, assume p
and q are in the tree |
|
y*********e
发帖数: 518 | 10 首先要问，输入是存在主内存中，还是存在外部文件？
若是输入是存在主内存中的array，是否已经排序好了？多半是没排序的。
那么这个问题可以简化成，给定一个未排序的32bit数组，找出出现频率最高的。用
hashtable 是最简单的解法; 不过面官对 hashtable 不满意，你可以分析出
hashtable 的 memory overhead 有多大，这样可以表现出你对 hashtable 内在实
现的了解程度。（hashtable是很占内存的）。
另外一个很简单的方案：对数组排序，用掉O(NlogN)的时间。那么相同的元素都放
在一起了。接下来扫描数组一遍，同时记录相同元素出现的次数，能有用O(1)的空
间找到出现频率最大的相同元素。 |
|
c******t
发帖数: 1500 | 11 来自主题: JobHunting版 - 一道算法题 tree的话为什么是O(n）呢？我怎么觉得是 O(nlogn) 呀？ |
|
p********7
发帖数: 549 | 12 第一次排序需要N*logN，但是以后更新每次只需要logN，因为用binary search查找
去之后N个数排序需要O（NlogN）。 |
|
j********x
发帖数: 2330 | 13 Ah, I got it, the min and max can be found in O(logn) using heap. The
initial heap building is O(n) though. So overall it's O(n) + O(Nlogn) |
|
|
f****g
发帖数: 313 | 15 Agree. For unsorted array, you need to scan the whole array at least.
Sort the array first, then do binary search. It will take nlogn times
怎么办，如果不是
sorted，怎么的你也得O（n）去发现这个事实，这是谁出的面试题？ |
|
c***2
发帖数: 838 | 16 "Given two sorted integer array, how to find the intersection.
what is best comparision number and worst comparison number."
1) No intersect O(1)
AAAAAAAAABBBBBBBBBBBB or BBBBBBBBBAAAAAAAAAAAA
2) Then Binary search for either case: O(logN)
AAAAAAAAAAAA
BBBBBBBBBBBBB
====K==
or
AAAAAAAAAAA
BBBBBBBBBBB
=K==
3) Then binary search overlapping part K*LogK
So
Best O(1)
Worst nlogn |
|
x***y
发帖数: 633 | 17 At worst, you need to find the divide point with time O(logL), where L is
the length of search row or column.
For this Y table, the worset search is that target is not in the table and
each divide take the most time.
So, to divide until only one element is left, we need (assume the matrix is
M*N)
Log(M-1)+Log(M-2)+...log(2) + log(N-1)+log(N-2)+....log(2)
=O(log(M!)+log(N!)) then using stirling's formula
=O(MlogM+NlogN) in the worse case. |
|
x****9
发帖数: 24 | 18 背景：ECE的MS, 过了online assessment智力题，约电面
电面：一共不到40分钟，只有一个面试官，应该是老印，不过没什么口音，听的比较清楚
首先behavior，where do you hear Bloomberg, why Bloomberg, why this position
然后介绍自己project，面试官问project中用了什么data structure，问的比较细
然后让我比较Link List 和 Array的优缺点，怎么优化Link List的random access比较
慢的缺点
然后是两个算法题，第一个问题找数组中第二大的元素，我先说遍历两遍第一遍找最大
第二遍找第二大，然后又说可以先排序再输出，他问排序的效率多少，我说看算法要么
O（N2）要么O（NLogN），他问那种好，我说第一种只用O（N），他问第一种一遍行不
，我想了想说行只要俩变量就行，然后他让给出大概的代码，pseudo code也成，我就
大概看了看然后直接跟他说代码，要考虑输入如果是0个元素或者只有1个元素输出-1，
否则遍历数组然后输出
第二题是经典0-N少一个数找出这... 阅读全帖 |
|
d**e
发帖数: 6098 | 19 ☆─────────────────────────────────────☆
gezwenti (gezwenti) 于 (Sun Feb 28 12:23:17 2010, 美东) 提到:
( 版主能给几个包子吗？ 我从没得过包子， 说的也都是个人真实体验）
真的。 本人在墙街做IT已经六年多了， 拿的也是很普通的薪水， 我现在的Total是135K + 10-25% Bonus （奖金时好时坏， 大致在10% 到 25% 之间）
我只会Java/J2EE。 不会C++, 一点都不会。
现在的Project是做Post-Trading的Changing P&L, Position Calulation.整个
Department是Support Equity Trading的， 公司也是大家都知道的大投行。
我以前的面试经验， 包括我周围IT朋友的面试经验 从来没被问过本版这么难的问题，
1) B-Tree, Graph 这些都太难了， 从没被问过。 最多就问个Binary Tree, 遍历二叉
树。 红黑树都没问道过， 面试官自己都不知道。
2) 数据结构， 最多就问问... 阅读全帖 |
|
g***s
发帖数: 3811 | 20 二分的速度can be polished to O( nlogn + nlog(max of 所有数字) )
DP could be O(nklogn) |
|
d*****e
发帖数: 29 | 21 sum(i)表示到第i个元素的和。O(n)可以做。
nlogn)
────────
可以解释一下什么是满足题意吗？是说sum(p) = maximum吗？如果大数字都在队尾，p
可能不存在。
Number array: 1, 1, 10 k=2
p = ? |
|
g***s
发帖数: 3811 | 22 yes. you can.
So, you can skip all sum(i) < sum(n)/k. in your case, 100,300,600,1000.
but we still need to use binary search to check sum[4] to sum[8]. it
could be still O(nlogn).
But in the following case, it can get much improvement by your changes:
O(n) for this step.
1,1,1,1,1,1......,1, 10000, 10000 k=3 |
|
c******a
发帖数: 789 | 23 There's also an O(nlogn) solution based on some observations. Let A{i,j} be
the smallest possible tail out of all increasing subsequences of length j
using elements {a1, a2, a3, ..., ai}.
Observe that, for any particular i, A{i,1} < A{i,2} < ... < A{i,j}. This suggests that if we want the longest subsequence that ends with a i + 1, we only need to look for a j such that Ai,j < ai + 1 < = Ai,j + 1 and the length will be j + 1.
Notice that in this case, Ai + 1,j + 1 will be equal to ai + 1, and al... 阅读全帖 |
|
b***6
发帖数: 6011 | 24 感觉面的不是很好啊。和我准备的方向有点偏差。。。估计悲剧的面儿大。无所谓了，
实力不济啊
本人 ee ms 对算法 数据结构不是很了解，最近一直恶补，效果不佳 ^_^
印度女 2pm to 2:50pm
介绍一个你最喜欢的project，什么数据结构，什么难点，什么公司的项目。。。。
你熟悉c吗？还是c++？
我说c
她问：解释一下class in c++ （貌似我说的是c。。。。）
橘子 苹果 mix
1-100 找一个数 找两个数
100球，一个分量不同，几次能找出来
两个sorted的数组，怎么找相同的数
我给了一个算法nlogn,他要n+n
我说用merge
他说两个数组大小不同，不用merge
我无语。。
哪位说一下解法
一个非等概率的硬币来决定足球比赛开赛，要公平，怎么办
让我问问题
整个下来磕磕绊绊，估计悲剧了。
回报一下本版，然后继续努力了，bless 各位 |
|
|
x**y
发帖数: 70 | 26 我当场给的解法是: SORT BY第一个COLUMN, 是 1 的行都不用考虑了, 在是 0 的行里
再SORT BY 第二个COLUMN, 是 1 的行也不用再考虑了... 假设平均每次能排除一半行
数, 整个要用 n*logn + n/2*log(n/2) + n/4 * log(n/4) + ... + 1 operations.因
为不用扫描所有的 ENTRY, 所以平均应该比 O(N^2) 好. 但不确定这个类似等比数列求
和最后是 nlogn 吗? |
|
x**y
发帖数: 70 | 27 换句话说,
O() = n*logn + n/2*log(n/2) + n/4 * log(n/4) + ... + 1
最后是 O(nlogn) 吗?
类似思想: 找 kth largest element in int array 是:
n + n/2 + n/4 + ... 1
最后是 O(N) |
|
k*p
发帖数: 1526 | 28 我的point是，你的sort需要nlogn，不是sort完看1或0 |
|
d**********o
发帖数: 279 | 29 我觉得可以 建立一个tree,然后和两个单独的e1,e2.
一个个往tree里插， 如果碰到已经存在的， 删除这个点，并放在e1里，
以后的每个往里插得都先河e1对比，如果==，就是那个triple,如果不等插到tree里，
和前面一样的处理方法。最后肯定会找到,这样空间就是n+2。时间就是 nlogn, 大家觉
得如何。 |
|
g**********y
发帖数: 14569 | 30 这个最坏情况是n^2。
如果没有什么更多的条件限制，好象就是把数组排序O(nlogn), 然后扫描O(n)。
要想有什么更快的，我觉得肯定得加条件，象数值在一定区域，数字连续，等等。 |
|
X*********n
发帖数: 570 | 31 你这两个方法也是我想的 但是
第二题,如果一个stack用的太快,worst case array的利用率只有1/3, 我想的是两个
stack从两头开始,第三个从中间开始,然后左右交替向两边扩展,但是这样worst case也
只有1/2的利用率
第一题,有没有nlogn的方法? 我想是不是能把矩阵切成四份,
|a b|
|c d|
那median只会在矩阵中心或者是b和c自矩阵中,剪掉了一半, 但是接下去似乎就不行了.
希望版上大牛给些意见 |
|
s*******e
发帖数: 93 | 32 Does this still work if there can be negative numbers?
E.g. 1, -2, 3, -4, 5?
Could you please explain the FIFO sub array in more detail?
What I was thinking about is quite similar to hopen's idea
We can calculate the sum from a[0] to a[i] for each a[i]. (Say b[i]=a[0]+a[1
]+...+a[i])
In the meantime, maintain a BST to store the b[i] values
After getting b[i], we search if the node in the BST which is the most close
to t - b[i].
Then add b[i] to the BST (together with i).
It is nlogn, and one sca... 阅读全帖 |
|
i********s
发帖数: 133 | 33 应该不能保证在对角线上。
想到一个nlogn的算法。 |
|
r*****n
发帖数: 20 | 34 恩 make sense
题意理解有误
这个题有比O(n^2)好的算法么？
写了一下O(n^2) 测了一下349901词的一个dichttp://www.math.sjsu.edu/~foster/dictionary.txt 要跑5-6分钟
return:
stekelenburg,hohohohohoho
代码如下
int myfunc(string a, string b){
return a.size()>b.size();
}
void foo(vector arr){
if(!arr.size())
return;
//step 1. sort w.r.t. lentgh of each word O(nlogn)
sort(arr.begin(), arr.end(), myfunc);
//step 2. compute signature for each word
vector sig;
for(long i=0; i阅读全帖 |
|
d**u
发帖数: 1065 | 35 第一轮第一题:BFS
第一轮第二题：DFS
第二轮第一题: 要看max输入有多大，小的话O(N),大的话O(NlogN),是我做的话，不用hash，直接改快排算法
第二轮第二题：DFS |
|
d**u
发帖数: 1065 | 36 第一轮第一题:BFS
第一轮第二题：DFS
第二轮第一题: 要看max输入有多大，小的话O(N),大的话O(NlogN),是我做的话，不用hash，直接改快排算法
第二轮第二题：DFS |
|
w**********y
发帖数: 1691 | 37 @ch222:
用merge sort是不是有问题啊? linked list不支持random access,那样的话还是O(
nlogn)么?
@justicezyx
展开说说该怎么回答呢? 是说要用一些常见的tree么?
俺是编程小白,请不要笑话俺问题的幼稚... |
|
y*******g
发帖数: 6599 | 38 heapsort就是inplace nlogn |
|
b*****n
发帖数: 143 | 39 刚从MIT的网站上看来的：
http://courses.csail.mit.edu/iap/interview/Hacking_a_Google_Interview_Practice_Questions_Person_A.pdf
答案如下：
Question: Axis Aligned Rectangles
Describe an algorithm that takes an unsorted array of axis‐aligned
rectangles and returns any pair of rectangles that overlaps, if there is
such a pair. Axis‐aligned means that all the rectangle sides are either
parallel or perpendicular to the x‐ and y‐axis. You can assume that each rectangle object has two variables in it: the x‐y coordinat... 阅读全帖 |
|
f****g
发帖数: 313 | 40 1. Quick sort.
Since the quick sort is randomization algorithm, the running time varies
each time. But the worst case scenario is O(nlogn)
2. Min-Max Heap.
it takes O(logn) time. |
|
f****g
发帖数: 313 | 41 Sorting algorithms can be categorized as comparison-based and not comparison-
based ones.
For the comparison-based algorithms, the best performance is O(nlogn).
and non-comparison-based ones could be achieved in linear-time. But it
uses space to trade off time. |
|
a**********k
发帖数: 1953 | 42 This can be reduces to LIS, O(nlogn). |
|
i********s
发帖数: 133 | 43 题目：两个文件里面存着行程安排，开始时间以及结束时间，设计算法找所有
conflicts。
还没有看见人讨论这道题。直接的一一比较，复杂度是O(n2).
好像可以降到 O(nlogn + nK)，K是每个interval最多和另外一个文件中interval
conflict的次数。所以最坏情况下，还是O(n2),但average time，可能好很多。 |
|
z****n
发帖数: 1379 | 44 我面google时候的原题。。。
按开始时间排序，然后考察每个interval，用二分法，对于开始时间比当前interval早
的所有interval，考察其中结束时间最晚的interval（这步通过随时更新当前所有考察
过的interval的最晚结束时间可以做到O(1)查找），如果比当前考察的interval开始时
间晚，则找到conflict，否则必然没有conflict；对于开始时间比当前interval晚的所
有interval，只需考察下一个interval的开始时间是否早于当前interval的结束时间即
可，也是O(1)，所以总的复杂度就是排序的复杂度nlogn。 |
|
i********s
发帖数: 133 | 45 在flydog MM的前提下，O(n)算法是存在的。但还有一个前提是要先sort。如果没有
sort，其实还是O(nlogn)的。
如果没有这个假设呢？（There are no conflicts in S1 and S2 itself.） |
|
J*******i
发帖数: 2162 | 46 这样做是nlogn么？我也想了这种做法
问题是虽然binary search到那个interval花的时间是logN
但是这样找到的所有conflict的interval也O(n)数量级的吧
每次把它们一一记录下来也是要花O(n)的时间吧？
比如一个worst case:
[1,m] [2,m] [3,m] ... [m-1,m] |
|
D***h
发帖数: 183 | 47 显然是错的.
横跨两边的最大Rect高度可能比最中间那个小。 |
|
b*****e
发帖数: 474 | 48 考虑到了的。可能我说得简单了点。
看看Code里关于height的那一段你就明白了。 |
|
t*****j
发帖数: 1105 | 49 这道题我onsite碰到了，结果脑袋短路，只给出了O（n2）解法，回家后一想
就想到你这个解法了，一点都不难，不知道为啥当场没想出来，郁闷死了。
可能是给的时间短了点，20分钟左右要理解题目再写出code并且给出复杂度。
我后悔死没带笔记本去onsite了，白板写code又慢又累又难看。面试完右胳膊
都酸的要死，不知道是不是因为我个子不高，老要伸高写字的缘故。
发现当场面试时候要想发挥好也挺不容易的，难免有这个那个疏忽之处。 |
|
g*********s
发帖数: 1782 | 50 The D&C idea is easy to understand.
But to obtain the optimal results, how can you guarantee the partition is
always half to half to make sure T(N) = 2T(N/2) + N holds?
Someone made a valid challenge earlier. |
|
