l*********r
发帖数: 80 | 1 public TreeMap userAccount;
public TreeMap messagePool;
public hw1_BOM()
{
userAccount=new TreeMap();
messagePool=new TreeMap();
}
public class mPool
{
public int mparentID;
public String mUsername;
public String mSubject;
public String mText;
public mPool(int parentid, String username, String subject, String text)
{
mparentID=parentid;
mUsername=username;
mSubject=subject;
mText=text;
}
}
***************what's wrong with this one below?**********
m |
|
c******n
发帖数: 4965 | 2 in Cassandra, concurrentSkipListMap put() and get() takes the majority of
read access,
actually in this spot we do not need explicit synchronization since the
caller is just one thread. so TreeMap is ok. but TreeMap is not any faster
than concurrentSkipListMap.
so is there a faster sortedMap than TreeMap ?
thanks |
|
f********4
发帖数: 988 | 3 今天做longest consecutive 那个题，觉得用treeset很简单
版上有人面试时候用过这种数据结构嘛？
好像从来没看到有solution用TreeSet或者TreeMap。。到底能不能用呢。。甚纠结。。
是不是用了还要知道这个数据结构咋实现的之类的。。。 |
|
p*****2
发帖数: 21240 | 4 TreeSet, TreeMap面试都可以用。不过那些methods不太容易记得清楚，因为平时用的
几率不是很大。 |
|
r****c
发帖数: 2585 | 5 TreeMap do not allow key duplicate, is there anything like treemultimap in
java? thanks |
|
g**********y
发帖数: 14569 | 6 怎么最简单地sort TreeMap? 我试了Comparator, 陷入chicken-and
-egg loop. 最后只好用个辅助List/Array来sort key. 有更简洁的办法吗？ |
|
l********0
发帖数: 283 | 7
and
Comparator可以搞定
你仔细看看API，使comparator对treemap起作用 |
|
h**j
发帖数: 2033 | 8 TreeMap本来就是sorted 为什么还要sort
and |
|
|
y*********e
发帖数: 518 | 9 treeset和treemap的实现是red black tree，是一个balanced binary search tree.
To locate Nth largest element the cost is O(1) |
|
M******1
发帖数: 90 | 10 import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class UberTest {
List data = new ArrayList<>();
public void fillData(){
//Use integer to denote Time here.. you can change it to DateTime
type.
data.add(new TimedKvPair(new KvPair("name1","Bnn"), 1) );
data.add(new TimedKvPair(new KvPair("name2","Dee"), 2) );
data.add(new Time... 阅读全帖 |
|
z*********e
发帖数: 10149 | 11 不顾虑多用的内存的话
可以把这个Map扔到另一个TreeMap>里面
SortedMap> treeMap = new TreeMap<>();
for(String s: map.keySet())
if(treeMap.get(map.get(s)) == null){
List list = new LinkedList<>();
list.add(s);
treeMap.put(map.get(s), list);
}else{
treeMap.get(map.get(s)).add(s);
}
for(Integer i: treeMap.keySet())
for(String s: treeMap.get(i))
println(s);
their |
|
x***n
发帖数: 70 | 12 请看下面几行简单的代码：
1 TreeMap treeMap = new TreeMap
Integer> ();
2 treeMap.put("Good", 136);
3 Map.Entry e = null;
4 e = treeMap.firstEntry();
5 e.setValue(23);
6 Set> el = treeMap.entrySet();
7 for( Map.Entry e1 : el ) {
8 e1.setValue(23);
9 }
第5行处，报错：java.util.AbstractMap$SimpleImmutableEntry.setValue(Unknown
Source)
但是，第8行处，是类似的操作，却能正常执行。
请问这是为什么？谢谢！ |
|
l*******s
发帖数: 1258 | 13 上周电面Twitter，挂。贡献题目，攒rp。
大约45分钟，那哥们上来就说开始做题，打开一个类似google doc的网站。连互相介绍
寒暄都没有。我怀疑是急着下班去过长周末。
题目不难，我发挥的太烂。
1.描述一下HashMap和TreeMap的区别。
2.实现一个TreeMap里的get(K key)方法，自己定义树的node，最好用java。我写了个
BST的get方法，就是简单的比较根节点然后递归左右子树那个，他说差不多。其实当时
觉得应该用红黑树，只是实现起来太麻烦，就没写。
3.如何防止这个TreeMap里的get，insert，delete等方法多线程调用时出现数据读写出
乱子？答曰用synchronized关键字。然后让直接写到第二题的code中。
4.加synchronnized之后，会有什么不好的影响。答曰会降低concurrence性能。
下午4点面的，晚上9他们给打电话，我当时在外面玩，没听到。三天后接到email，说
是挂了。
总结一下，估计最大的问题还是在coding上。犯了俩语法错误。有个别条件可能写的也
不大严谨。今后要加强练习。老用Eclipse，有... 阅读全帖 |
|
n*****x
发帖数: 686 | 14 最简单的是用1个treemap记录k个高频，一个hash map记录每个股票的频率，每次更新
都看一眼treemap的min，大就查找lowerbound然后更新。update时间复杂度O(k)。
如果update时间要求O1,就再加一个linked list记录k个频率，treemap改成hashmap记
录iterator。
那个楼主说的heap大概不行，得用hash heap |
|
h***s
发帖数: 45 | 15 API是有很多interface，同时API也有很多class已经实现了这些interface，这些i
nterface存在的原因一是可以让用户来实现自己的class，二是可以generic的使用
实现同一interface的classes。
ie. interface Map <- TreeMap, HashMap.
you can code as:
1: Map m;
2: m = new TreeMap();
3: use m as a generic Map.
later on if you want to change TreeMap to HashMap.
use only need to change the line 2 to "m = new HashMap();" |
|
G***l
发帖数: 355 | 16 这还不简单。
用一个hashtable存储，key是单词，values是arraylist，这个arraylist的第一个位置
存放次数，后面依次存放出现的句子数。
顺序读取文件，一个个句子一个个词的扫描。每扫描到一个词，加入到hashtable里或
者改变对于的value里面的值。
要是在java里，可以用treemap代替hashtable来存储，因为treemap的key是排序的。
the |
|
c*****h
发帖数: 166 | 17 大概50分钟的样子 最后5分钟问他问题
我online test选的java, 不过电面上来也就是c/c++的东西
1. 自我介绍
2. static什么意思 怎么用
3. synchronize怎么用
4. Singleton, 什么时候用 什么是double checking(ft这里，我自己说出来了被他追
着打)
5. HashMap和TreeMap,search，insert, delete的复杂度, 有HashMap了为啥还要
TreeMap
6. Sql里面有哪些Join, inner join 和left join的区别 举实际例子
7. 给个dead lock的场景 怎么解决 semaphore和mutex lock区别
完全没有behavioral question, brain tease和project介绍
各位好运~ |
|
R***i
发帖数: 78 | 18 TreeMap> map;
iterate each word in book from front to back
if word found in map, append current page number to ArrayList
if word not found in map, put to map, append current page number
TreeMap automatically sort on key, which is String type word
iterate map to generate "word -> page number" pairs |
|
p*****2
发帖数: 21240 | 19 来自主题: JobHunting版 - G家一面。
我用hashset写过一个，跟你思路差不多. 不过用TreeMap binary search应该更容易。
有时间得练练。转了java还没用过TreeMap呢。 |
|
p*****2
发帖数: 21240 | 20 来自主题: JobHunting版 - G家一面。 我写了一个练练手。
import java.util.*;
public class test3
{
public static void main(String[] args)
{
Interval in = new Interval();
int[][] sam = new int[][]
{
{ 5, 10 },
{ 15, 17 },
{ 18, 25 },
{ 16, 35 } };
for (int i = 0; i < sam.length; i++)
{
in.Merge(sam[i][0], sam[i][1]);
in.Print();
}
}
}
class Interval
{
TreeMap tm = new TreeMap();
void Me... 阅读全帖 |
|
p*****2
发帖数: 21240 | 21 刚才又重写了一遍
class Solution1
{
TreeMap tm = new TreeMap();
void insert(Interval interval)
{
Integer prev = tm.floorKey(interval.start);
Integer next = tm.ceilingKey(interval.start);
if (prev != null && tm.get(prev) >= interval.start || next != null
&& interval.end >= next)
{
int start = -1;
if (prev != null && tm.get(prev) >= interval.start)
{
tm.put(pre... 阅读全帖 |
|
p*****2
发帖数: 21240 | 22
这道题我碰到过三次。有些要求
1.自己设计数据结构。所以不一定用List。按道理来说最好的数据结构是interval
tree, 但是面试的时候太难写了。所以Treemap是不错的数据结构。数据结构要能够存
储，merge这些interval,而不应该每次insert都产生一个新的list。
2. interval list可能会非常巨大。因此性能是个问题。TreeMap search, insert,
delete 都是logn的复杂度。如果用list的话，就应该用binary search了。 |
|
i**********e
发帖数: 1145 | 23 你那边有个 while 循环，不知道是不是我以下所说的这个意思。
Treemap 是很好，但是要考虑到这 insert 最坏复杂度是 O(n log n)。
给个例子：
当新的 interval 与第一个 interval 相交，那总共要从 treemap 里删除 n 个
intervals。每删除一次是 log(n) 时间，那总复杂度就是 O(n log n) 了。
照理说，还是一个 vector 好，maintain sorted intervals，然后 in-place 插入，O(n)复杂度。
实现比较麻烦些，不过应该没想象中那么难。我想五十行代码可以写出来，应该是一个
很好的编程练习。 |
|
p*****2
发帖数: 21240 | 24 刚才又重写了一遍
class Solution1
{
TreeMap tm = new TreeMap();
void insert(Interval interval)
{
Integer prev = tm.floorKey(interval.start);
Integer next = tm.ceilingKey(interval.start);
if (prev != null && tm.get(prev) >= interval.start || next != null
&& interval.end >= next)
{
int start = -1;
if (prev != null && tm.get(prev) >= interval.start)
{
tm.put(pre... 阅读全帖 |
|
p*****2
发帖数: 21240 | 25
这道题我碰到过三次。有些要求
1.自己设计数据结构。所以不一定用List。按道理来说最好的数据结构是interval
tree, 但是面试的时候太难写了。所以Treemap是不错的数据结构。数据结构要能够存
储，merge这些interval,而不应该每次insert都产生一个新的list。
2. interval list可能会非常巨大。因此性能是个问题。TreeMap search, insert,
delete 都是logn的复杂度。如果用list的话，就应该用binary search了。 |
|
i**********e
发帖数: 1145 | 26 你那边有个 while 循环，不知道是不是我以下所说的这个意思。
Treemap 是很好，但是要考虑到这 insert 最坏复杂度是 O(n log n)。
给个例子：
当新的 interval 与第一个 interval 相交，那总共要从 treemap 里删除 n 个
intervals。每删除一次是 log(n) 时间，那总复杂度就是 O(n log n) 了。
照理说，还是一个 vector 好，maintain sorted intervals，然后 in-place 插入，O(n)复杂度。
实现比较麻烦些，不过应该没想象中那么难。我想五十行代码可以写出来，应该是一个
很好的编程练习。 |
|
p*****2
发帖数: 21240 | 27
有人知道TreeMap higherKey的复杂度吗？如果是log(n)的话，那 TreeMap查找log(n),
合并就要n(logn)的复杂度了。那还不如ArrayList了。
ArrayList: search logn, insert n
LinkedList: search n, insert n
貌似ArrayList复杂度最好了。当然写起来更费劲些。今天有时间练练。 |
|
p*****2
发帖数: 21240 | 28
这题用treemap解最合适呀。treemap也是要算hashcode的吧？ |
|
z****e
发帖数: 54598 | 29 楼上打击得有些厉害
楼主写算法都能写出美感来，不容易
有做基础数学或理论物理研究的潜质
我们说点直观的
楼主知道tree, hashtable这些么？刷过题的肯定知道
java如果用过的话，treemap和hashtable你也应该知道
那现在的现状是这样
treemap，这么多年下来，我一次没看到过，在实际代码里面
hashtable倒是偶尔会看到，但是大多数时候，出现在legacy code里面
出现频率最高的，不是hashtable，是hashmap
大多数时候，出现的是hashmap
理由的话，你自己google
所以你问用到多少
那看你说的是什么了
就好比你问初中学的数学证明用到了多少？
如果你问的是，自己会去写，自己去实现的有多少，那基本上是蛋
君子生非异，善假于物
如果你问的是，用过多少次，那还是会用到的
但是不是你学的那么理论化的东西，都是经过改良后的各种版本
所以说对于你来说，这些题只是用来锻炼大脑，也不能说是错的
如果你也喜欢理论结合实际
那你应该多留意一下，别人用什么工具
说到这里你应该能明白为什么二爷很喜欢挑起语言战争了
古德霸可能是买买提上最无私的挨滴了 |
|
c*******7
发帖数: 438 | 30 国人小哥，还算nice。小迟到十分钟，聊一会背景开始做题。他们家用的Web editor可
以直接run，右边有console，可以写一些logging帮助debug。
就问了一题，写的磕磕绊绊后面写完没剩什么时间了。
用Generics 写一个简易版的TreeMap，支持get, put 和size。不用考虑balance，只需
要把entry插入tree就行。
class TreeMap {
get();
put();
size();
}
因为很少写Generics，syntax不是很熟，他出题给出的信息比较少，我一开始写的时候
有点confuse没写key，Google现查的Generics的syntax花了不少时间。之间一直有
compile error，原来是Generics里面关键字必须用extends 而不能用implements，不
明白为什么。之间有几个bug被指出。
应该还有第二问，可能是加balance或者加几个别的method，但这三个写完已经没什么
时间了。
最后问了space和time complexity，简单问了个问题，结束。第二... 阅读全帖 |
|
f********a
发帖数: 367 | 31 电面2：
还是一个国人大哥，LeetCode上的Insert Interval，API稍微有点变化，给的是一个链
表节点。
由于还有时间，还考了一个count tweets的设计题。需要实现如下API：
class CountingSvc {
void tweet(long timestamp, int tweetLength);
double avgLength(long begin, long end, long threshold);
};
另外给了一个hint，TreeMap，让自己customize一下object。
可惜我一看是range query就往线段树上想了，于是给出了如下结构，并解释了原理。
class Node {
long totalLen;
long count;
long begin;
long end;
Node left;
Node right;
}
最后追问了下如何去做模糊处理。我还是在线段树上想，就加了一个threshold。
double avgL... 阅读全帖 |
|
g*****y
发帖数: 94 | 32 我觉得应该也不能用TreeMap吧，treemap本质上也是map，反而还多了复杂度。 |
|
g*****y
发帖数: 94 | 33 我觉得应该也不能用TreeMap吧，treemap本质上也是map，反而还多了复杂度。 |
|
s******7
发帖数: 1758 | 34 O（n）, 差不多也是暴力法，三个篮子2，3，5，每次选最小的，再乘上篮子标号放回
去，搞n就可以了
三个选最小的，都不用什么heap, 直接排序就可以了
篮子实现用个treemap
SortedMap map = new TreeMap<>();
map.put(1,2); // 2^0=1
map.put(1,3); // 3^0=1
map.put(1,5); // 5^0=1
int minK = 0;
for(int i=0;i
minK = map.firstKey();
int minV = map.get(minK);
map.remove(min);
map.put(min*minV,minV);
}
return minK; |
|
y*****e
发帖数: 712 | 35 这题我第一次看到是在板上，在这里
http://www.mitbbs.com/article_t/JobHunting/32876295.html
Tasks: AABABCD
Cooldown Time: 2
A__AB_ABCD
Output: 10
后来发现这题很快变成fb的新欢，各种follow up啊。。。今天看到一个实在心塞的，
越想越复杂，想发上来问问大家有啥好主意
follow up是给你一个task队列， 要求你自己排列要求最后的总时间最小，比如
aaaabbbccd，可以排成abcabcabda。
看到有人建议说每次排gap + 1个任务，取distinct tasks，也就是尽量分开同种任务
，放的时候从frequency高的开始，我觉得这就需要一个treemap了吧，先abc放完，然
后再放一轮abc，放一个减少count,count == 0的时候从treemap里去掉。如果是aaab怎
样的呢？放完ab只能再空等一次才能再放a，这样的话是不是应该有个deque来实现？ |
|
b**********5
发帖数: 7881 | 36 只能说明你吗的东西， 太落后。 我也是从来没吗过， 然后last job， 我吗的是
cutting edge technology， treemap， priority queue经常用。 弄个consistent
hash就用了treemap |
|
s******7
发帖数: 1758 | 37 TreeMap
TreeMap
all update operation should be log(N), and all get operation O(1) |
|
z****e
发帖数: 54598 | 38 r是高阶语言，哪里用来算什么大数据
用来表达一些idea还差不多
真正计算都是压给那些pkg，比如scipy或者hadoop这些
r全部load数据到内存，根本算不出来
mysql底层实现就用了b-tree
c主要用来写一些底层的软件，os, db还有jvm, r这些
其它语言相对c是一种高阶的存在
最后一句是对的
其它语言甚至都不是二叉树是语言的一部分
而是hashtable这种结构是语言的一部分了
全部都是key-value pair，所有语言，到底层都是c
只有一些相对类库比较全的语言，你才能容易找到树结构
比如java里面就有treemap，但是treemap使用次数比起hashmap来说
那不知道是要小多少倍，人类发展这么多年，树有些old了
前面有人说set，set也可以多种实现，treeset比起hashset来说
我估计很多人甚至都不知道有treeset这个类
类似的还有list，arraylist比起linkedlist来说，要常用太多 |
|
p***p
发帖数: 559 | 39
我本意的问题是如果人们不知道HashMap和Treemap怎么办，比如
我现在做的东西都是在写Hashmap等等，不知道将来用户怎么知道
来用我的东西，应该有个什么能自动将TreeMap upcast到Map上 |
|
l*****f
发帖数: 2198 | 40 FLAG 那些算法数据结构题跟这个比就是小儿科
阿里面试题：
一面：电话面试：80分32秒)
1.自我介绍？
2.做过哪些项目？项目中遇到哪些难点，你是怎样解决的？单点登录系统说一下？分布
式缓存的使用场景？(说好的基础呢，上来就是项目，毫无准备，导致好多东西都记不
起来了。面试官还说“那你说一个你记得的项目”，手动无奈。。。)
3.你实习的时候JDK用的是那个版本，这个版本有什么新的特性？
4.G1回收器和其他回收器有什么区别？
5.垃圾回收为什么会停顿？哪些对象可能作为GCRoots?
6.垃圾回收分代收集算法？为什么会有两个Survivor区？new一个对象会保存在哪里？
7.Java内存模型?volatile关键字，使用场景？原子性的理解？先行发生原则？
8.场景题：现在有三个线程，同时start，用什么方法可以保证线程执行的顺序，线程
一执行完线程二执行，线程二执行完线程三执行？
9.你是怎么理解线程安全的？HashMap是线程安全的么？如果多个线程同时修改HashMap
时会发生什么情况？
10.ConcurrentHashMap底层原理？每个版本的实现上有什么区别？
11... 阅读全帖 |
|
l*****f
发帖数: 2198 | 41 FLAG 那些算法数据结构题跟这个比就是小儿科
阿里面试题：
一面：电话面试：80分32秒)
1.自我介绍？
2.做过哪些项目？项目中遇到哪些难点，你是怎样解决的？单点登录系统说一下？分布
式缓存的使用场景？(说好的基础呢，上来就是项目，毫无准备，导致好多东西都记不
起来了。面试官还说“那你说一个你记得的项目”，手动无奈。。。)
3.你实习的时候JDK用的是那个版本，这个版本有什么新的特性？
4.G1回收器和其他回收器有什么区别？
5.垃圾回收为什么会停顿？哪些对象可能作为GCRoots?
6.垃圾回收分代收集算法？为什么会有两个Survivor区？new一个对象会保存在哪里？
7.Java内存模型?volatile关键字，使用场景？原子性的理解？先行发生原则？
8.场景题：现在有三个线程，同时start，用什么方法可以保证线程执行的顺序，线程
一执行完线程二执行，线程二执行完线程三执行？
9.你是怎么理解线程安全的？HashMap是线程安全的么？如果多个线程同时修改HashMap
时会发生什么情况？
10.ConcurrentHashMap底层原理？每个版本的实现上有什么区别？
11... 阅读全帖 |
|
n****t
发帖数: 241 | 42 It is a hard talk time.
inerviewer是个老印，英语是我所听过的人里最难懂的了，而且很不nice,上来就面试，
面完都不让我问问题，连byebye都没有说就挂电话了，唉，相当的rude,也或者是一个
真正搞技术的，所以不专业，：（
面试问题主要集中在JAVA / C++ /design pattern plus a simple algorithm
question.
说题目吧:
1. introduce yourself?
2. 用过什么collection API?
答： HashSet, HashMap, ArrayList, LinkedList, TreeSet and TreeMap.
3. 请解释为什么要用hashmap？
请解释为什么要用arraylist?
4. 比较arraylist和vector有什么区别？
5. 如果删除需要一个元素时，用arraylist好还是linked list好？
6. 什么是mvc model?
可以介绍一下在struts中，那个class控制control layer吗？
几年前的东西，鬼才记 |
|
M***0
发帖数: 1180 | 43 红黑树的插/删不可能让你当场写的，当场也不可能写出来。大部分人红黑树的特征都
说不出来
我遇到过问得最深的不过就是“treemap用什么实现的(红黑树)” |
|
|
|
s***r
发帖数: 12 | 46 来自主题: JobHunting版 - 一道算法题 hashmap,O(n)
如果按字母顺序，treemap,O(nlgn) |
|
y*********e
发帖数: 518 | 47 来自主题: JobHunting版 - 一道算法题 按照顺序也可以用Balanced BST，比如RBTree。Java里面的TreeMap是一个RBTree。 |
|
s*x
发帖数: 3328 | 48 恭喜.
BTW:sliding window 的那个题目,前面不是有人贴链接了,楼上还有没看懂的? 用线性
结构,单纯的链表或者数组肯定不行,必须用到树形结构.堆可以.问题是这里有两个值,
一个是数组的位置,要保存好更新窗口,一个是数组元素的值,这个好取最大最小.所以就
是一个优先队列了,存的元素是数组元素下标,更新的时候将下标和当前窗口边界比较,
超出的就删除;而优先级用数组元素的值来表示.同时取最大和最小,所以一共需要俩优
先队列,伪码大概是这个样子:
for i from 1 to k 窗口的大小
add i with priority v[i] into PQ1, PQ2
max[i],min[i] 分别从 PQ1, PQ2 根的优先级得到
//上面这步是初始化,当然还要考虑窗口比数组还大的特例
// PQ1, PQ2 一个是按顺序, 一个是按逆序来的, 分别得到最大最小值
for i from k+1 to n 数组长度, 1-based index
add i with priority v[i] into PQ1, PQ2
while PQ1 根的值超出窗... 阅读全帖 |
|
s*****n
发帖数: 5488 | 49 Treemap不是red-black tree吗？ 怎么实现max-queue? |
|
g**********y
发帖数: 14569 | 50 对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... 阅读全帖 |
|
