w*******l 发帖数: 14 | 1 PHONE1:
1.解释什么是BST,hashtable,时间复杂度是多少。给出情况什么时候用哪个。
2.遍历BST的算法,复杂度。
3.(5,10)(15,17)(18,25) 插入 (16,35)
合并成(5,10),(15,35)
PHONE2:
1.解释C++和JAVA的区别。
2.JAVA的GC机制。什么变量在heap里什么变量在stack里。accessible from root,
root是从哪里。
3.给一个排好序的数组画平衡二叉树。
问题都很水。。OVER。 |
q********c 发帖数: 1774 | |
r*****k 发帖数: 1281 | 3 老中 还是阿三面的?
【在 w*******l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : PHONE1: : 1.解释什么是BST,hashtable,时间复杂度是多少。给出情况什么时候用哪个。 : 2.遍历BST的算法,复杂度。 : 3.(5,10)(15,17)(18,25) 插入 (16,35) : 合并成(5,10),(15,35) : PHONE2: : 1.解释C++和JAVA的区别。 : 2.JAVA的GC机制。什么变量在heap里什么变量在stack里。accessible from root, : root是从哪里。 : 3.给一个排好序的数组画平衡二叉树。
|
s******n 发帖数: 3946 | |
r*****k 发帖数: 1281 | 5 很好 感觉出那些难题有啥意思啊
大部分人见过就会 没见过就不会
要是真想解决那些难题 不如去做research
面试题都是背背答案
【在 s******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 很水啊。。。
|
w*******l 发帖数: 14 | 6 一个美国人,web search quality group的,一个老印。
老印叫Alex。。一开始拿着劲儿说英文还听得懂。。后来说快了就秃噜了。。
【在 r*****k 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 老中 还是阿三面的?
|
r*****k 发帖数: 1281 | 7 还行啊 没想出难题搞你
【在 w*******l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一个美国人,web search quality group的,一个老印。 : 老印叫Alex。。一开始拿着劲儿说英文还听得懂。。后来说快了就秃噜了。。
|
e***s 发帖数: 799 | 8 3.(5,10)(15,17)(18,25) 插入 (16,35)
合并成(5,10),(15,35)
这题没看懂.. |
A**u 发帖数: 2458 | 9 合并区间
【在 e***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 3.(5,10)(15,17)(18,25) 插入 (16,35) : 合并成(5,10),(15,35) : 这题没看懂..
|
s******n 发帖数: 3946 | |
|
|
H***e 发帖数: 476 | 11 interval tree?
【在 s******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 合并区间段,写起来不简单啊
|
p*****2 发帖数: 21240 | 12
这个确实不简单。标准做法应该是什么?
interval tree
or
binary search + linear search
我要是面试没准备过就直接写个linear search再merge的算啦,然后再讨论优化。
【在 s******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 合并区间段,写起来不简单啊
|
b******t 发帖数: 965 | 13 这里起始的 interval都不overlap
没有必要用interval tree吧
binary search就行吧
简单的用个STL里面的map key存左端 value存右端就很容易写
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这个确实不简单。标准做法应该是什么? : interval tree : or : binary search + linear search : 我要是面试没准备过就直接写个linear search再merge的算啦,然后再讨论优化。
|
w****x 发帖数: 2483 | 14 (5,10)(15,17)(18,25) 插入 (16,35)
合并成(5,10),(15,35)
Binary search 找到开始端点刚好小于16的段:(15, 17)
从这个segment开始迭代的merge |
s******n 发帖数: 3946 | 15 情况很复杂的。
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : (5,10)(15,17)(18,25) 插入 (16,35) : 合并成(5,10),(15,35) : Binary search 找到开始端点刚好小于16的段:(15, 17) : 从这个segment开始迭代的merge
|
p*****2 发帖数: 21240 | 16
我用hashset写过一个,跟你思路差不多. 不过用TreeMap binary search应该更容易。
有时间得练练。转了java还没用过TreeMap呢。
【在 b******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这里起始的 interval都不overlap : 没有必要用interval tree吧 : binary search就行吧 : 简单的用个STL里面的map key存左端 value存右端就很容易写
|
p*****2 发帖数: 21240 | 17 我写了一个练练手。
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 Merge(int start, int end)
{
Integer s = tm.floorKey(start);
Integer e = tm.ceilingKey(start);
if (s != null && start <= tm.get(s) + 1 || e != null && end + 1 <= e
) // overlap
{
if (s != null)
{
tm.put(s, Math.max(tm.get(s), end));
}
else
{
tm.put(start, Math.max(end, tm.get(e)));
s = e;
}
while (tm.higherKey(s) != null && tm.get(s) + 1 >= tm.higherKey(
s))
{
tm.put(s, Math.max(tm.get(s), tm.higherEntry(s).getValue()));
tm.remove(tm.higherKey(s));
}
}
else
tm.put(start, end);
}
void Print()
{
for (int i : tm.keySet())
{
System.out.println("(" + i + "," + tm.get(i) + ")");
}
System.out.println("----------------------------------");
}
} |