g**********y
发帖数: 14569 | 1 对sorted set，logN找左右边界，然后把这个range的数取出来。
TreeSet的实现，你可以去读Java source code. 是通过TreeMap来实现的，API里写的：
“A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to... 阅读全帖 |
|
J***n
发帖数: 391 | 2 【 以下文字转载自 Java 讨论区 】
发信人: JAlan (Alan), 信区: Java
标 题: 几个Java面试题
发信站: BBS 未名空间站 (Tue Sep 27 23:34:20 2011, 美东)
1. 如果数据查找多的话，需要使用哪种数据结构？
// 我复习下来，一直认为插入修改多用LinkedList，查询多的话用ArrayList. 但是好
像都不是正解。ArrayList如果查找value的话，也需要遍历整个列表。后来想了想，查
找最快的话就是binarySearch了，但是要基于sorted list的基础上，那是不是应该使
用SortedLinkedList呢？
2. 1 million的数据 （key-value），多查找，需要使用哪种数据结构？
// TreeMap 吗？
3. 使用线程实现1 billion 整数的求和，最后返回一个数
// 我把数据分成10份，定义10个线程来分别来做求和，最后把每个线程所得数相加，
得到最后的数。不知道思路对不对？
不过我困惑的是，如果是单一任务的话，难道不是单线程要比多线程快吗？可以一口气
运行，为什么还要... 阅读全帖 |
|
y*******g
发帖数: 6599 | 3 我觉得看看Java的源码非常有帮助，treeMap, HashMap, concurrent package
C++ stl的代码没法看， |
|
y*******g
发帖数: 6599 | 4 相当于std::map和java TreeMap的区别
包括 C++ STL可以用buildin type, java collections不行，
STL是value copy, java是reference |
|
b*****s
发帖数: 36 | 5 一面：
很nice的白人，很encouraging，问了以下问题：
1. 自我介绍，最近做了什么project，最喜欢的是什么project
2. 问了Java的基础数据结构的基本概念：Array, LinkedList, ArrayList, HashMap,
TreeMap
3. 算法题：给一个很大的int array，memory不能放下，要求找k个smallest element
。我给了一个O(N logK)的算法。没要求写code
4. 问Java garbage collection原理，我当时只记得reference-counting，HR提示说如
果遇到circle怎么办，我在提示之下想出了mark-and-sweep的方法。
二面：
白人，我跟他交流有点问题，我的口语太烂。
1. 问什么是HashMap，什么是Hash function，HashMap是怎么储存的。
2. 问什么是binary tree，什么是heap data structure。
3. OO设计题：furniture stress test system, 有各种furniture包括Chair... 阅读全帖 |
|
m********l
发帖数: 791 | 6 Thanks for sharing~
**************************************************
一面：
很nice的白人，很encouraging，问了以下问题：
1. 自我介绍，最近做了什么project，最喜欢的是什么project
2. 问了Java的基础数据结构的基本概念：Array, LinkedList, ArrayList, HashMap,
TreeMap
3. 算法题：给一个很大的int array，memory不能放下，要求找k个smallest element
。我给了一个O(N logK)的算法。没要求写code
4. 问Java garbage collection原理，我当时只记得reference-counting，HR提示说如
果遇到circle怎么办，我在提示之下想出了mark-and-sweep的方法。
二面：
白人，我跟他交流有点问题，我的口语太烂。
1. 问什么是HashMap，什么是Hash function，HashMap是怎么储存的。
2. 问什么是binary tree，什么是heap dat... 阅读全帖 |
|
w****o
发帖数: 2260 | 7 1. STL中的std::unordered_map是不是等同于（或者是类似）Java中的Hashmap?
2. STL中的std::map是不是等同于（或者是类似）Java中的Treemap?
3. STL中hashtable是哪个类实现的？Java中类似的哪个类叫什么名字？问的就是在STL
和Java下都是叫什么名字。
4. 为什么在我的linux机器上的目录/usr/include/c++/4.1.2下只有set, map而没有
multiset和multimap?你们的系统里有multiset和multimap吗？
另外我发现STL的unordered_map和unordered_set是定义在/usr/include/c++/4.1.2/
tr1下面的。
谢谢！ |
|
|
p*****2
发帖数: 21240 | 9 我上次用TreeMap写了一个。很简单。一会儿看看能不能找到。 |
|
p*****2
发帖数: 21240 | 10
不是区间树。上次有人提到这个idea，我就做了一下，果然很容易。
TreeMap key store start, value store end.
找了好几次也找不到那个帖子了。没准给删掉了。 |
|
i**********e
发帖数: 1145 | 11 用 map/TreeMap 插入区间的 worst case 是 O(n log n).
这个worst case 就是当 new_int 覆盖了所有的区间，这时候应该把所有里面的区间删
掉。而你代码里面只删掉了一个，所以有问题。 |
|
i**********e
发帖数: 1145 | 12 我仔细读了你代码，你是对的。
其实你算法最坏情况是 O(n) 的。因为删除的时候你传入 iterator，所以删除只需要
constant time.
所以 Map/TreeMap 的确是挺好的数据结构来解决这个问题。
Best case: O(log n), Worst case O(n). |
|
p*****2
发帖数: 21240 | 13 我上次用TreeMap写了一个。很简单。一会儿看看能不能找到。 |
|
p*****2
发帖数: 21240 | 14
不是区间树。上次有人提到这个idea，我就做了一下，果然很容易。
TreeMap key store start, value store end.
找了好几次也找不到那个帖子了。没准给删掉了。 |
|
i**********e
发帖数: 1145 | 15 用 map/TreeMap 插入区间的 worst case 是 O(n log n).
这个worst case 就是当 new_int 覆盖了所有的区间，这时候应该把所有里面的区间删
掉。而你代码里面只删掉了一个，所以有问题。 |
|
i**********e
发帖数: 1145 | 16 我仔细读了你代码，你是对的。
其实你算法最坏情况是 O(n) 的。因为删除的时候你传入 iterator，所以删除只需要
constant time.
所以 Map/TreeMap 的确是挺好的数据结构来解决这个问题。
Best case: O(log n), Worst case O(n). |
|
y*******o
发帖数: 6632 | 17 Read:Java Concurrency In Practice
just google, threadlocal is not
should be these four:
LOCK OBJECTS
Lock objects work very much like the implicit locks (monitors) used by
synchronized code. As with implicit locks, only one thread can own a Lock
object at a time. Lock objects also support a wait/notify mechanism, through
their associated Condition objects. All the lock objects are defined in the
java.util.concurrent.lock package. The biggest advantage of Lock objects
over implicit locks is their... 阅读全帖 |
|
y**********u
发帖数: 6366 | 18 这个类似于java的TreeMap
HashMap和树没有关系,stl扩展里有hash_map,和这个map一点关系都没有 |
|
c****g
发帖数: 85 | 19 华丽丽地用了LinkedList, HashSet, TreeMap
Question 20.10 Given two words of equal length that are in a dictionary,
write a method to transform one word into another word by changing only one
letter at a time. The new word you get in each step must be in the
dictionary.
EXAMPLE:
Input: DAMP, LIKE
Output: DAMP->LAMP->LIMP->LIME->LIKE
既然dictionary可以用hashtable检查，而一个word的长度有限，先把变化的各种可能
组合列出来，直接用hashtable检查这些words是否存在于字典里。这样是不是更快，更
直观。 |
|
s********x
发帖数: 914 | 20 切磋一下. running time 应该是 less than log(K)
public class RandomNextIntExceptK {
private int[] kk;
private int[] kAdd;
private Random rand = new Random();
public RandomNextIntExceptK(int[] k) {
Map kCount = new TreeMap();
for (int i = 0; i < k.length; i++)
{
int key = k[i] - i;
if (kCount.containsKey(key))
{
int count = kCount.get(key);
kCount.put(key, cou... 阅读全帖 |
|
|
p*****2
发帖数: 21240 | 22
不是heap，是treemap。
这题你不知道包裹的数量，所以要动态分配，而且需要调整。 |
|
p*****2
发帖数: 21240 | 23
Treemap，所以最后是nlogn的复杂度 |
|
|
p*****2
发帖数: 21240 | 25
就是balanced binary search tree, 保证search的复杂度是logn
各个语言都有库类支持。Java是TreeMap, C#是SortedMap啥的吧。 |
|
|
l*********8
发帖数: 4642 | 27 java里的TreeMap也就是红黑树吧？ 就像C++的std::map |
|
e***s
发帖数: 799 | 28 第一题怎么做比较好？counting sort之后再放进TreeMap里面吗？ |
|
c********t
发帖数: 5706 | 29 放Treemap有time cost吧，放hashmap, 并得到最大重复值 i，输出时候 while(i>=1)
{list = map.get(i); output; i--}
就可以了吧？
忘了文件输出调用方法是不是也不行？唉。 |
|
p*****2
发帖数: 21240 | 30
感觉你的方法不能scale。用TreeMap应该就可以了。interval tree我也不知道面试好
不好写。 |
|
p*****2
发帖数: 21240 | 31
97)
用TreeMap就可以了。每种语言基本都有响应的数据结构。 |
|
p*****2
发帖数: 21240 | 32
),
我刚才想的是insert interval。LZ的题就一个数字的话TreeMap查找，合并就都是log(
n)了。这题的变化还可以很多呀。 |
|
h**6
发帖数: 4160 | 33 一共有n^2跟短棍子，计算每根短棍子的重量和重心都是O(1)的。然后比较相同长度的
短棍子，用hashmap或者treemap找出相同的重心，只是浮点数的比较可能不太精确。 |
|
|
f*******7
发帖数: 943 | 35 我当时建了个自己的object 继承comparator接口 然后存到heap里
其实可以重写map的compare方法就行
或者用treemap+stack |
|
p*****2
发帖数: 21240 | 36
query
HashMap+TreeMap是不是就行了？ |
|
n****r
发帖数: 10 | 37
TreeMap的key和vaule是什么呢？ |
|
c********t
发帖数: 5706 | 38 二爷，一直没弄懂一件事情。
我知道treeset add,remove,search都是lg(n).但api里就是没提update. 比如当一个
query avg被update的时候，treeset是不是也能自动作排序调整？然后也是O(lgn)?
treemap一样问题。 |
|
p*****2
发帖数: 21240 | 39
多谢讨论。我是用的Long，所以应该不会溢出。想过用TreeMap，但是查找中点也是线
性的应该。如果自己实现BST的话，感觉还需要做balanced，否则估计也过不了。C++有
deque倒是个优势，不知道Java／Scala有没有相对应的数据结构。 |
|
s*******r
发帖数: 2697 | 40 可以用treeMap
也可以维护两个heap: minHeap + maxHeap |
|
l********n
发帖数: 54 | 41 我对楼主TreeMap或者MinHeap & MaxHeap的方案有点疑问。
按我的理解，MaxHeap应该记录Max值的。如果在future的stream price大于heap top的
值，那么更新top.但假设t1的值是20, (t2, 15), (t3, 19),然后t3后的值都小于19。
那么在t1 expire后，max of t3就丢失了。
我能想的用minHeap & maxHeap的情况是用 linked list + heap。linked list 按照时
间顺序insert,当list head expire时候delete。每次insert & delete都fix heap. 不
知道楼主是不是这个意思。
我想到一中方案使用deque.
find max:
(1) 当stream data中一个值v来的时候，不断pop_back queue中所有比v小的。
(2) query max的时候，check queue front的data是否expire, 如果expire pop_front
到12 months内的data,那就是max。有点leetco... 阅读全帖 |
|
|
b******7
发帖数: 92 | 43 TreeMap是用balanced tree实现的map，和hash没关系。
hashset/hashmap在实现上一般是无序的，这也是c++库中hashmap用了unordered_map
这题不知道考点在哪儿，是不是想考桶排序，每个hash对应一个桶，桶内再排序 |
|
b*****n
发帖数: 618 | 44 hashcode貌似跟treemap没啥关系吧 |
|
x*****p
发帖数: 1707 | 45 TreeMap is a Map and it implements red-black tree algorithm inside. |
|
r**d
发帖数: 316 | 46 用应该没问题吧，你可以说这个等价于有序二叉树，
不过插入treeSet的时间复杂度是lg(n) longest sensecutive要求复杂度为O(n)? |
|
f********4
发帖数: 988 | 47
恩，我早上也想到这个了。。果然晚上比较迷糊。。 |
|
o******e
发帖数: 1001 | 48 请问C#有没有类似java 里面的treemap一样的API,能够直接加入Node。网上查了一下，
似乎没有看到，难道在C#里用bineary search tree要自己写类吗？ |
|
w*********m
发帖数: 4740 | 49 hashmap/hashtable/hashset 用hashcode, treemap/treeset用equals
经典面试题是，如果override的equals，还要考虑override哪个function，就是
hashcode |
|
z****e
发帖数: 54598 | 50 不过要真计较起理由来的话
那tree的确用得不多，在现实环境中
大多数时候用map就是hashmap
我反正是没怎么用过treemap
而且扯到tree很有可能要上递归
这两个都是不怎么用的算法
所以说算法在某种意义上就是回字的那多余的三种写法
用来对付面试用的
不要说tree了，就是hashtable
现在也基本上被淘汰了
还有vector，只有在一些老的代码里面才会看到
这主要是实现时候在多线程环境里面做得太死
不够灵活，后期大面积被其他类所取代 |
|
