血泪的教训。。谁说Bloomberg面完四轮就一定有offer的！！！

depends on 火车距离A口多远吧

火车>----S----A口-----300-----人----------------700----------------B口

假设火车距离A口距离S, 人速度 V，火车速度 2V
人如果选择A口则 走到A口时间t = 300/V < S/2V 人可以从A口逃脱 所以 S>600时可以选择 A口
如果 人选择 B口，t为火车撞上人的时间 两者走过的路程相同 则 2vt = s+300+vt   => vt = S+300 > 700 人可以从B逃脱 所以 S>400 可以走B口
所以 总体来说选择B口生还的余地大一些。

两个Array 找 two sum的题，把两个Array sort 一下，一个ASC一个DESC
然后O(N)的查找
所以总体是O(N*logN)

个cube表面刷满油漆，然后切成3*3*3，放进一个袋子里，随机取一个出来扔地上，向上那面有油漆的概率是多少。。

8个顶点3面有漆 p = 1/2
12条边2面油漆 p = 1/3
6个面1面有漆 p = 1/6
1个中心 p = 0
总共27块
条件概率加权和 = 8/27 * 1/2 + 12/27 * 1/3 + 6/27 * 1/6 = 9/27 = 1/3

补充内容 (2014-8-29 14:01):
hitogram contain water
很容易，从两头算，time O(N), space O(1)
按小的边计数，比小边小的可以存水，大的则反过来计数
public static int getWaterVolume(int[] array) {

        return getWaterVolumeHelper(array, 0, array.length - 1);

}



private static int getWaterVolumeHelper(int[] array, int begin, int end) {

        while (begin < end) {

                if (array[begin + 1] > array[begin]) ++begin;

                else break;

        }

        while (begin < end) {

                if (array[end - 1] > array[end]) --end;

                else break;

        }

        int sum = 0, beginValue = array[begin], endValue = array[end];

        if (beginValue < endValue) {

                for (int i = begin + 1; i < end; ++i) {

                        if (array[i] > beginValue) {

                                sum += getWaterVolumeHelper(array, i, end);

                                break;

                        } else sum += beginValue - array[i];

                }

        } else {

                for (int i = end - 1; i > begin; --i) {

                        if (array[i] > endValue) {

                                sum += getWaterVolumeHelper(array, begin, i);

                                break;

                        } else sum += endValue - array[i];

                }

        }

        return sum;

}

lidaheng 发表于 2014-6-25 06:22
不管怎样，我觉得不应该在这种问题上挂人吧～本来一个问题就可以很多解法嘛。

定长字符串可以用radix sort，O(n)的时间

去BB onsite面实习，遇到了和楼主一样的问题。
不过同样跪了T_T

火车那个没懂，走A口不是直接撞死？

lidaheng 发表于 2014-6-25 13:22
还没有消息。还在焦急等待中～

同学最后拿到offer了么?周五面试下周一就给通知的节奏么？　

请问lz 那个cube 题答案是1/3 么？

zhenggao1986 发表于 2014-8-29 13:57
个cube表面刷满油漆，然后切成3*3*3，放进一个袋子里，随机取一个出来扔地上，向上那面有油漆的概率是多 ...

概率是不是算错了啊。
我算了是1/2
26/27 * （8/26*3/4 + 12/26*2/4 + 6/26*1/4）=1/2

请问那个设计电话本的题目怎么做？目前只想到用两个hashmap...但那就没有考的意义了。。。