请教一个ip5s的问题 - 未名空间MITBBS历史存档

w*e2013-11-08 08:11

1 楼

1.when would you use a hash table vs. balance binary tree to represent a
dictionary? Discuss tradeoffs, algorithm performance
2. How would you keep track of the 10 largest elements in an input stream?
3. If the same shared library exists in absolute path /a/path1 and
/b/path2 how would you force a binding to /b/path2 instead of /a/path1 at
runtime?
第一题应该从那些方面考虑呢？只知道 hashtable: ~O(n); BST: ~O(logn)
第二题我想的是可以用数组(~O(n)), 用BST(~(logn), 不过实现起来比较麻烦)
第三题,是在编译的时候用 “gcc -l" 指定链接的路径吗？
希望大家指正，给些意见。多谢！

n*w2013-11-08 08:11

2 楼

哪位帅哥美女可以弹唱这个歌曲，然后放到youtube 上？
歌谱见附件，是个结婚时唱的歌曲。
多谢，
我自己是不行啊，

d*s2013-11-08 08:11

3 楼

【以下文字转载自 PDA 讨论区】
发信人: dodos (步步为营), 信区: PDA
标题: 请教一个ip5s的问题
发信站: BBS 未名空间站 (Fri Nov 8 17:02:18 2013, 美东)
如果现在在美国买ip5s，回国用，假设能破解的话，是不是只能用联通？
如果能用移动的话，买哪个运营商的。
非常感谢

s*n2013-11-08 08:11

4 楼

和10-th大的数比较。如果大于，替换掉最小的那个。
LD_lib_Path I guess, I don't use linux for 4 years.

【在 w*****e 的大作中提到】

: 1.when would you use a hash table vs. balance binary tree to represent a
: dictionary? Discuss tradeoffs, algorithm performance
: 2. How would you keep track of the 10 largest elements in an input stream?
: 3. If the same shared library exists in absolute path /a/path1 and
: /b/path2 how would you force a binding to /b/path2 instead of /a/path1 at
: runtime?
: 第一题应该从那些方面考虑呢？只知道 hashtable: ~O(n); BST: ~O(logn)
: 第二题我想的是可以用数组(~O(n)), 用BST(~(logn), 不过实现起来比较麻烦)
: 第三题,是在编译的时候用 “gcc -l" 指定链接的路径吗？
: 希望大家指正，给些意见。多谢！

n*w2013-11-08 08:11

5 楼

m没有人能做到？
还是大家都太谦虚，不好意思？

【在 n*******w 的大作中提到】

: 哪位帅哥美女可以弹唱这个歌曲，然后放到youtube 上？
: 歌谱见附件，是个结婚时唱的歌曲。
: 多谢，
: 我自己是不行啊，

z*e2013-11-08 08:11

6 楼

移动联通都能用。

g*a2013-11-08 08:11

7 楼

hash table takes more space，but should be faster to search--that is all i
know
keep the largest 10 in a sorted array. for each new element comes in,
compare to the smallest one in the 10-element array, if larger, then insert
new one in the right place, and delete the smallest one. The complexity
should be O(n)

【在 w*****e 的大作中提到】

: 1.when would you use a hash table vs. balance binary tree to represent a
: dictionary? Discuss tradeoffs, algorithm performance
: 2. How would you keep track of the 10 largest elements in an input stream?
: 3. If the same shared library exists in absolute path /a/path1 and
: /b/path2 how would you force a binding to /b/path2 instead of /a/path1 at
: runtime?
: 第一题应该从那些方面考虑呢？只知道 hashtable: ~O(n); BST: ~O(logn)
: 第二题我想的是可以用数组(~O(n)), 用BST(~(logn), 不过实现起来比较麻烦)
: 第三题,是在编译的时候用 “gcc -l" 指定链接的路径吗？
: 希望大家指正，给些意见。多谢！

d*s2013-11-08 08:11

8 楼

买verizon的还是att的？

【在 z****e 的大作中提到】

: 移动联通都能用。

y*e2013-11-08 08:11

9 楼

在实际应用中 hashtable 的效率接近于 O(1)，当然前提是有个好的hash函
数。比如Java的hashtable实现。
hashtable 的速度远比 BST 要高。但是 hashtable 的 memory overhead
会较大。
还有 hashtable 是无序的，BST是有序的。
第二题用大小为10的max heap就可以了。O(Nlog10)的复杂度。

z*e2013-11-08 08:11

10 楼

无所谓，买哪个都可以。一样的。

K*C2013-11-08 08:11

11 楼

第二题，应该用 min heap

【在 w*****e 的大作中提到】

: 1.when would you use a hash table vs. balance binary tree to represent a
: dictionary? Discuss tradeoffs, algorithm performance
: 2. How would you keep track of the 10 largest elements in an input stream?
: 3. If the same shared library exists in absolute path /a/path1 and
: /b/path2 how would you force a binding to /b/path2 instead of /a/path1 at
: runtime?
: 第一题应该从那些方面考虑呢？只知道 hashtable: ~O(n); BST: ~O(logn)
: 第二题我想的是可以用数组(~O(n)), 用BST(~(logn), 不过实现起来比较麻烦)
: 第三题,是在编译的时候用 “gcc -l" 指定链接的路径吗？
: 希望大家指正，给些意见。多谢！

d*s2013-11-08 08:11

12 楼

多谢多谢

【在 z****e 的大作中提到】

: 无所谓，买哪个都可以。一样的。

w*e2013-11-08 08:11

13 楼

Thank you guys.
Question 1: Hashtable memory overhead 是指那些呢？
Question 2: Right. min heap is a good choice.

b*h2013-11-08 08:11

14 楼

我觉得也不一定吧，看你hashtable是怎么实现了。如果是chainning的话，是比bst多
一个数组；但如果用open addressing的话就没有这个overhead了。
Hashtable还有一个问题是如果你不断的往里加东西，接近满了的时候性能就下降了，
需要rehash。

【在 w*****e 的大作中提到】

: Thank you guys.
: Question 1: Hashtable memory overhead 是指那些呢？
: Question 2: Right. min heap is a good choice.

l*a2013-11-08 08:11

15 楼

gcc -l 这是静态链接。不可能修改运行时行为
with win32API,you can use LoadLibrary/GetProcAddress
with Linux ,you can use dlopen/dlsym to get the same behaviors

stream?
at

【在 w*****e 的大作中提到】

: 1.when would you use a hash table vs. balance binary tree to represent a
: dictionary? Discuss tradeoffs, algorithm performance
: 2. How would you keep track of the 10 largest elements in an input stream?
: 3. If the same shared library exists in absolute path /a/path1 and
: /b/path2 how would you force a binding to /b/path2 instead of /a/path1 at
: runtime?
: 第一题应该从那些方面考虑呢？只知道 hashtable: ~O(n); BST: ~O(logn)
: 第二题我想的是可以用数组(~O(n)), 用BST(~(logn), 不过实现起来比较麻烦)
: 第三题,是在编译的时候用 “gcc -l" 指定链接的路径吗？
: 希望大家指正，给些意见。多谢！