G家一面。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

G家一面。

G家一面。# JobHunting - 待字闺中

w*l2012-03-07 08:03

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*c2012-03-07 08:03

2 楼

发包子.

r*k2012-03-07 08:03

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*n2012-03-07 08:03

4 楼

很水啊。。。

r*k2012-03-07 08:03

5 楼

很好感觉出那些难题有啥意思啊
大部分人见过就会没见过就不会
要是真想解决那些难题不如去做research
面试题都是背背答案

【在 s******n 的大作中提到】

: 很水啊。。。

w*l2012-03-07 08:03

6 楼

一个美国人，web search quality group的，一个老印。
老印叫Alex。。一开始拿着劲儿说英文还听得懂。。后来说快了就秃噜了。。

【在 r*****k 的大作中提到】

: 老中还是阿三面的？

r*k2012-03-07 08:03

7 楼

还行啊没想出难题搞你

【在 w*******l 的大作中提到】

: 一个美国人，web search quality group的，一个老印。
: 老印叫Alex。。一开始拿着劲儿说英文还听得懂。。后来说快了就秃噜了。。

e*s2012-03-07 08:03

8 楼

3.(5,10)(15,17)(18,25) 插入 (16,35)
合并成（5，10），（15，35）
这题没看懂..

A*u2012-03-07 08:03

9 楼

合并区间

【在 e***s 的大作中提到】

: 3.(5,10)(15,17)(18,25) 插入 (16,35)
: 合并成（5，10），（15，35）
: 这题没看懂..

s*n2012-03-07 08:03

10 楼

合并区间段，写起来不简单啊

H*e2012-03-07 08:03

11 楼

interval tree?

【在 s******n 的大作中提到】

: 合并区间段，写起来不简单啊

p*22012-03-07 08:03

12 楼

这个确实不简单。标准做法应该是什么？
interval tree
or
binary search + linear search
我要是面试没准备过就直接写个linear search再merge的算啦，然后再讨论优化。

【在 s******n 的大作中提到】

: 合并区间段，写起来不简单啊

b*t2012-03-07 08:03

13 楼

这里起始的 interval都不overlap
没有必要用interval tree吧
binary search就行吧
简单的用个STL里面的map key存左端 value存右端就很容易写

【在 p*****2 的大作中提到】

:
: 这个确实不简单。标准做法应该是什么？
: interval tree
: or
: binary search + linear search
: 我要是面试没准备过就直接写个linear search再merge的算啦，然后再讨论优化。

w*x2012-03-07 08:03

14 楼

(5,10)(15,17)(18,25) 插入 (16,35)
合并成（5，10），（15，35）
Binary search 找到开始端点刚好小于16的段:(15, 17)
从这个segment开始迭代的merge

s*n2012-03-07 08:03

15 楼

情况很复杂的。

【在 w****x 的大作中提到】

: (5,10)(15,17)(18,25) 插入 (16,35)
: 合并成（5，10），（15，35）
: Binary search 找到开始端点刚好小于16的段:(15, 17)
: 从这个segment开始迭代的merge

p*22012-03-07 08:03

16 楼

我用hashset写过一个，跟你思路差不多. 不过用TreeMap binary search应该更容易。
有时间得练练。转了java还没用过TreeMap呢。

【在 b******t 的大作中提到】

: 这里起始的 interval都不overlap
: 没有必要用interval tree吧
: binary search就行吧
: 简单的用个STL里面的map key存左端 value存右端就很容易写

p*22012-03-07 08:03

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("----------------------------------");
}
}