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 的大作中提到】
: 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 的大作中提到】
: 很水啊。。。
|
w*******l
发帖数: 14 | 6 一个美国人，web search quality group的，一个老印。
老印叫Alex。。一开始拿着劲儿说英文还听得懂。。后来说快了就秃噜了。。
【在 r*****k 的大作中提到】
: 老中 还是阿三面的？
|
r*****k
发帖数: 1281 | 7 还行啊 没想出难题搞你
【在 w*******l 的大作中提到】
: 一个美国人，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 的大作中提到】
: 3.(5,10)(15,17)(18,25) 插入 (16,35)
: 合并成（5，10），（15，35）
: 这题没看懂..
|
s******n
发帖数: 3946 | |
|
|
H***e
发帖数: 476 | 11 interval tree?
【在 s******n 的大作中提到】
: 合并区间段，写起来不简单啊
|
p*****2
发帖数: 21240 | 12
这个确实不简单。标准做法应该是什么？
interval tree
or
binary search + linear search
我要是面试没准备过就直接写个linear search再merge的算啦，然后再讨论优化。
【在 s******n 的大作中提到】
: 合并区间段，写起来不简单啊
|
b******t
发帖数: 965 | 13 这里起始的 interval都不overlap
没有必要用interval tree吧
binary search就行吧
简单的用个STL里面的map key存左端 value存右端就很容易写
【在 p*****2 的大作中提到】
:
: 这个确实不简单。标准做法应该是什么？
: 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 的大作中提到】
: (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 的大作中提到】
: 这里起始的 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("----------------------------------");
}
} |
