w*****e
发帖数: 158 | 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" 指定链接的路径吗？
希望大家指正，给些意见。多谢！ | s*****n
发帖数: 5488 | 2
和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" 指定链接的路径吗？
: 希望大家指正，给些意见。多谢！
| g*****a
发帖数: 340 | 3
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" 指定链接的路径吗？
: 希望大家指正，给些意见。多谢！
| y*********e
发帖数: 518 | 4 在实际应用中 hashtable 的效率接近于 O(1)，当然前提是有个好的hash函
数。比如Java的hashtable实现。
hashtable 的速度远比 BST 要高。但是 hashtable 的 memory overhead
会较大。
还有 hashtable 是无序的，BST是有序的。
第二题用大小为10的max heap就可以了。O(Nlog10)的复杂度。 | K******C
发帖数: 230 | 5
第二题 ，应该用 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" 指定链接的路径吗？
: 希望大家指正，给些意见。多谢！
| w*****e
发帖数: 158 | 6 Thank you guys.
Question 1: Hashtable memory overhead 是指那些呢？
Question 2: Right. min heap is a good choice. | b********h
发帖数: 119 | 7
我觉得也不一定吧，看你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*****a
发帖数: 14598 | 8 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" 指定链接的路径吗？
: 希望大家指正，给些意见。多谢！
|
|
