S**C
发帖数: 2964 | 1 The rule of thumb for constant duration bond funds is, if duration is N,
current yield is X, your annualized return in the next 2N-1 years is X. |
|
c********a
发帖数: 16 | 2 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 |
|
m*****n
发帖数: 5245 | 3 ☆─────────────────────────────────────☆
thanksgiving (LEFT) 于 (Tue Dec 12 22:11:10 2006) 提到:
刚刚IBM面回来，问了一对自己做的东西。
技术问题有两个：
1）实现链表反转。
2）一列数n个，找到smallest number显然是只用 n-1 次比较。如果要同时找出
smallest number和 second smallest number，那么要多少次比较。
我说可以找两次，用n-1+n-2=2n-3次比较。
然后她提示可以用n+lgn-2次比较，不用外部空间。我想了想没想出来。
☆─────────────────────────────────────☆
glory (o7) 于 (Tue Dec 12 22:13:08 2006) 提到:
ibm的啥职位？谢谢
☆─────────────────────────────────────☆
glory (o7) 于 (Tue Dec 12 22:14:18 2006) 提到:
2) second sma |
|
g*******y
发帖数: 1930 | 4 成对的比较，找到最大数后，再比较所有跟最大数比较过的数？但空间呢? 可以做到O(
1)吗？如果空间做不到O(1)，2n -> n+lgn的改进也没什么意义吧。
当然，光看最少的比较次数，那这个是不错的。 |
|
s******8
发帖数: 4192 | 5 我的解好像是n*log(k).
移动指针2n.
数组计数log(k)（如果k很大），或者k（如果k很小）
为什么出来n^2? |
|
k***e
发帖数: 556 | 6 嗯 是空间换时间。增加2n个指针，将search time从lgn提高到常数 |
|
x******e
发帖数: 13 | 7 48
It is the number that cannot be represented as:
2n+1 remove 1000 numbers
4n+2 500
8n+4 250
16n+8 125
32n 62
64n 31
128n+64 16
256n+128 8
512n+256 4
1024n+512 2
2048+1024 1
The left number must be represented as 4096n+2048, but the region is [1,2000
]. I got 48 using periodic boundary. |
|
m*****f
发帖数: 1243 | 8 你这个公式只成立于总数为偶的情况
比如
1 2 3 4 5 6 7 8 9 去掉2n+1
2 4 6 8 这里去掉的是4, 8
|
|
g*******y
发帖数: 1930 | 9 一堆扑克n cards，你抽一张出来看再放回来
a). 平均要抽多少次，才能看完所有的n张牌
b). 抽2n次，看过多少张牌(期望，给个大概值即可)
c). 抽k次，看过的牌的数目的期望(最好是准确的式子) |
|
l**a
发帖数: 43 | 10 你的hash算法中没必要对所有元素算一遍hashvalue吧
进来一个元素a，它的hashvalue就是sum-a，如果a已经在hashtable中，就找到返回，复
杂度为n，而你的是2n，没有本质区别，但如果挑毛病的话就是这里了
前移 |
|
H*M
发帖数: 1268 | 11 职业杯上的题是这样的:
Imagine you have a square matrix, where each cell is filled with either blac
k or white. Design an algorithm to find the maximum subsquare such that all
four borders are filled with black pixels.
不过按他的算法,我觉得是O(n^4)而不是O(n^2):
1. iterate each full column ->n
2. iterate each sub column -> n^2
3. check if it can form a sqaure ->n
total O(n^4)
第三步可以用2n个interval tree记录每行每列的连续0的起始index,这样第三步就省到
lgn,总共可以O(n^3.lgn). |
|
r**u
发帖数: 1567 | 12 2个指针，l, r，分别指window的左右边. 开始l = r = 0，
(1) move r，直到这个window has all elems of B. record min window
(2) move l, until A[l] is in B.
(2) move l，直到这个one elem of B is not in the window.
(3) go to 2, if cur win length < min window length, update min window.
需要2n steps.
stop when r == n - 1.
3,1,5,7,3,5,2
l r 3
l r
l r
l r 3
l r
l r
l r 2
co
conta
is |
|
r**u
发帖数: 1567 | 13 l, r都不会往回走，所以复杂度是2n，你再想想。 |
|
|
g*******y
发帖数: 1930 | 15 btw
貌似可以证明，对于任意n个球，最小次数是 ceiling(Log_3(2n)) |
|
r****o
发帖数: 1950 | 16 我想问道经典的题，虽然这个版上可能讨论过了，但是我还是没弄太明白。
有一个array全部由正整数构成，元素个数为2n，如何将其分成2个subarray(元素各n个
)，使得subarray的元素和最接近。
多谢先。 |
|
w**********8
发帖数: 121 | 17 I am thinking this way.
let n = 2m +1;
* Let three median are Am, Bm, Cm
* compare them, let Am < Bm < Cm
* get rid of 0 ... m in A, and m ... n-1 in C
* for the rest of arrays, repeat the 3 steps above.
each time, we get rid of 2/6 of the rest numbers, i.e. T(n) = C+T(2n/3). This
is not O(log(n)) as well.
That's the best I can gave. Any other ideas? |
|
h********0
发帖数: 440 | 18 given an array with data like: a1 a2... an b1 b2 ...bn
Change the array to a1 b1 a2 b2 ... an bn
看到career cup上这个题目可以用divide and conquer，但是那个exchange的部分我
test了几个情况，好像都有问
题。
Rough idea:
find the middle index r = floor((p+q)/2)
It partitions the array to part 1 [p, r] and part2 [r+1, q]
then exchange the second half of part [(p+r)/2...r] and the first half of
part 2 [r+1, (r+q)/2]
recursively call this function.
Initially, call this function func(p,q) use parameters p=1,q=2n
Test case 1: a1 a2 a3 a |
|
r****o
发帖数: 1950 | 19 我也想过这个问题，感觉如果2n是2的几次方的话，用divide and conquer 好做。
否则好像很麻烦。 |
|
c***z
发帖数: 6348 | 20 It seems that it is better to store total # of 1's.
My idea is first fix column i and column j, try to find the max all 0
rectangular between them.
For that purpose, we need one pass on the rows, keeping track of the longest
rectangular ending at row k (LREK). This is a variant of the max sum
subarray problem.
If row k has an 1, then LREK=0; otherwise add 1 to the previous LREK.
To fast calculate if row k has an 1 or not, it is better to store the total
# of 1's and just do a subtraction.
O(M^2N |
|
h**6
发帖数: 4160 | 21 一个无向图，包含2n个点，每两个点一组，共n组，表示为1A, 1B, 2A, 2B, 3A, 3B, .
.., nA, nB
在每一组中选取一点构成子图，问是否存在这样一个n结点的全连通子图，即子图内任意两
结点都相邻。
要求在多项式时间内完成，但不需要求出子图，只需要判断是否存在。 |
|
g*******y
发帖数: 1930 | 22 这样解：
用一个2-CNF来表示这个图:
(x1+!x2)*(!x1+x3)*()....*() ，一共N个括号
怎么给一个图的节点指定一个逻辑变量呢：
任意取第一个节点设为x1，凡是在别的组里面不跟x1相连的图节点统统指定为!x1;
每遇到一个还没设定逻辑变量的节点，直接设为x2，x3(新增加一个逻辑变量)...以此类推;
写出2-CNF后，可能有N~2N个逻辑变量，不过没关系。下一步就是解2CNF，做一个Implication
graph，遍历，搞定。
*****************************
BTW，这是哪家公司的题，貌似不像正常的面试题，不会是楼主的算法课作业题吧?!
*****************************
.
任意两 |
|
l******c
发帖数: 2555 | 23 first, get the length of the two list O(2n)
count = difference;
move the long one with count steps, then both move one by one, if equal, OK
O(n) |
|
j**l
发帖数: 2911 | 24 第六题是著名的杨氏矩阵（Young Tableau, 可不是杨狰狞提出的哦)
一个组合数学的东西, 早在20世纪初就由英国数学家提出。它的运作方式类似于堆和
BST，插入和查找等操作复杂度在O(m+n)
对本题，查找复杂度为O(2n) = O(n) |
|
m****y
发帖数: 28 | 25 你这算法跟逐行binary search毫无区别，把2换成了3而已
你的复杂度是2n*log3(n) |
|
x****r
发帖数: 99 | 26 请问如果用master theorem怎么证明这个算法是2n*log3(N)
虽然intuitively很容易解释。。
谢谢：） |
|
h********e
发帖数: 1972 | 27 我来贴个答案吧。。动态规划不怎么可取，因为多半是伪多项式的。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)就无所谓
了。 |
|
|
b****d
发帖数: 1311 | 29 我不知道啊。
假设开始时 x 黑 y 白，x+y=2n，
一片片翻到最后是 y 黑 x 白。
总有一个时候黑白一样的。 |
|
|
|
|
s*********t
发帖数: 1663 | 33 和最小的n个pair，必定来自A0+Bi,Ai+B0, i=0,1,...,(n-1)这2n个数
这个不对吧？ |
|
b******v
发帖数: 1493 | 34 假设Ai+Bj在和最小的n个pair里面，但是i和j都不等于0
那么我们把它换成A0+Bj或者Ai+B0，都能得到更小的数
所以在考虑完那2n个数之前，不必考虑i,j都不等于0的情形 |
|
z*****o
发帖数: 40 | 35 我觉得 L, U 在不同时候是不同的，否则
否则 s = sum(V) 然后 for i = L to V do x[i] = v * N 就可以了
既然说 L, U, V are parameters of each operation, 我觉得他们就是每次可以不同
，否则为啥叫 parameters.
这个应该有 NlogN 的算法
把 L,U 看作一个线段，对所有的线段端点（2N个）排序，
s=0
从左到有扫描端点
如果遇到一个左端点，s+=线段对应的v
如果遇到一个右端点，s-=线段对应的v
处理完一个端点后，s就是x[这个端点+1]到x[下一个端点]的值 |
|
a*d
发帖数: 47 | 36 来自主题: JobHunting版 - 老题目一问 array of N elements, find M smallest elements. N >> M
我说选pivot 再partition，
expected complexity is: n + n/2 + n/4 ... = 2n.
问我还可以再提高吗？都O(n)了还怎末improve, 除非再constant上做文章。
没想出来。
同胞说可以 "n" 做出来。。。 |
|
m**k
发帖数: 290 | 37 来自主题: JobHunting版 - 再来一道题 My guess
First pass: count frequency
create an array, occur[k][2], occur[i][0] is the i-th unique number, occur
[i][1] is the frequency of this number.
time n, space 2xk
Second pass: sort
sort the array occur[k][2] with occur[i][0] as the key
time O(klogk)
Third pass: restore the sorted array
for i in 0:k-1
for j in 0:occur[i][1]
array[n++] = occur[i][0]
time n
Overall time 2n + O(klogk) = O(n), overall space 2xk = O(1) |
|
y*********e
发帖数: 518 | 38 第一题，什么情况下favor O(n^2) over O(nlogn)
得考虑常数因子阿，比如，一个是O(n^2)但是其实是2n^2，另外一个是O(nlogn)但是是
44nlog(n)。当n比较小的时候，O(n^2)就比O(nlogn)要快了。 |
|
c******n
发帖数: 4965 | 39 the code for the Finnish paper algorithm
// O(n) time O(1) space merge of 2 arrays
//
public class smart_merge {
static int N=50;
//// return the largest i so that data[i]<= data[key_pos]
public static int lower(int data[] , int start, int key_pos ) {// we
know that the largest is 2N;
int end = N * 2;
start --; // if the return value is this one, that means
everything in the sub array is larger than key_pos
while ( start < end -1 ) {
int mid = ( s |
|
j**l
发帖数: 2911 | 40 找第二大那个虽然方法都是O(n),但比较次数还可以改进。
一般方法是先比较n-1次找到最大，然后比较n-2次找到次大，总共比较2n-3次
如果两个一组先比较，可以减少总的比较次数。 |
|
g******e
发帖数: 247 | 41 来自主题: JobHunting版 - 一道面试题 0-99 个数存在array里，如何找到重复的。 回答建一个array记录下出现的次数，
>1的为重复的。再问如果不能有额外的空间，用何方法？回答用heap,但是用heap作
sort时是O(nlogn), 不够快。提示用一个swap，最后结果会是O(2n)。 这个没回答
出, 请各位指教 |
|
c**********e
发帖数: 2007 | 42 来自主题: JobHunting版 - 一道面试题 for(int i=0;i<100;i++) {
while(a[i]!=i) {
if(a[i]==a[a[i]]) { cout << "find dublicate"; return; }
else { int j=a[i]; a[i]=a[j]; a[j]=j; }
}
}
Each i is visited at most twice. For example, if a[0]=5, after a swap
happens at i=0, a[5]=5. Then a[5] will not be visited for i=1,2,3,4. When i=
5, as a[5]==5 is true, the while loop will not run. So a[5] is visited at
most twice (it is likely return happens at i=3). So is each other i. So the
complexity is 2n. |
|
h**k
发帖数: 3368 | 43 但是这个只是一种可能的对角线；一共有2n-1个对角线需要处理。 |
|
i**s
发帖数: 17 | 44 Amazon面试的一道题：
有一个长度为2n 的interger array, 其中所有的数的值在1到n之间，如何找出所有重
复的数 Time Complexity O(n), Space Complexity O(1) ? |
|
a****d
发帖数: 114 | 45 因为每次更新之后满足"a[j] != j"的j的个数减少了一个, 所以所有元素的更新次数总
和不超过 2n. |
|
i**9
发帖数: 351 | 46 我怎么觉得是 “堆的节点数目最多是”max（m，n）,因为每次只能删一个，而要加入
两个，如果 3*n matrix
3*(n+n 2*n n
3*(2n-1) 2*(n-1) n-1
.
.
.
3*(n) 2 1
那么最大的总在第一列我们每次加入heap第一列的下一个和第二（同行）列中的一个，
那么加完第一列 heap中有 n 个 nodes
是（1，1）
，也就是把一个点确定涂黑以后，就把
最大值的操作 |
|
s*********b
发帖数: 815 | 47 最优解是O(Mlog(2N/M)):http://epubs.siam.org/sicomp/resource/1/smjcat/v13/i1/p14_s1?isAuthorized=no
基本主意是每次把一个matrix划分成四个，然后根据第K个元素的
大致范围抛弃一部分子矩阵。注意每个子矩阵都满足左上角元素最
大右下角元素最小的性质。不过如果不知道这篇论文，从头想的话，
要想出判断准则其实挺难。不过要找出O(logM+logN)的解法还是
比较简单的。就是quickSelect的变种：从左下角出发，总可以线性
地把矩阵分成两块。然后根据K的大小，决定是找上半块还是下半块。
如果是上半块，就用经典的quickSelect搞定，如果是下半块，就继
续划分。这个解法的好处是不需要先生成整个矩阵。在划分矩阵时
即时计算边界就行了。需要的空间无非是保存上半块的边界，也就是
O(M+N)。
举个例子，如果
A = [10, 8, 6, 3, 1]
B = [11, 9, 7, 6, 5]
那么对应的矩阵就是
21, 19, *17*, 14, 12, 11
19, 17, *15*, 12, ... 阅读全帖 |
|
h**6
发帖数: 4160 | 48 无论time slot多大，STL map中最多只有2n项，遍历一次就够了。其余没有人进出的时
间点没有检查的价值。 |
|
h**6
发帖数: 4160 | 49 对于每一条对角线，得到两组射线，在其中找出两条相互盖住对方起始点的射线，求最
长重叠区域。这个过程可以有O(nlogn)和O(n^2)的两种算法。
但是2n-1条对角线的数值并不是相互独立的，每一条对角线都只需要寻找比以前的结果更
长的重叠区域，因此可以大大缩短时间。最终我两种寻找重叠区域的算法运行时间都比求
前面几个矩阵的时间还短，因此我认为是O(n^2)的复杂度。 |
|
c**********e
发帖数: 2007 | 50 Step 1. Double/half bah. Start with a guess, say n=10000. If the w[n] is "less" than the given word, double it, check w[2n]. If w[n] is "greater" than, check w[n/2].
Step 2. Binary search. Eventually, you will find a range m...n, the word is between w[m] and w[n]. Then perform binary search to figure it out. |
|
