美团点评湖南研发工程师笔试卷-2013年

1、一堆硬币，一个机器人，如果是反的就翻正，如果是正的就抛掷一次，无穷多次后，求正反的比例。

2、一个汽车公司的产品，甲厂占40%，乙厂占60%，甲的次品率是1%，乙的次品率是2%，现在抽出一件汽车时次品，问是甲生产的可能性？

3、一个栈的入栈序列是A,B,C,D,E,则栈的不可能的输出序列是（）

 A. EDCBA

 B. DECBA

 C. DCEAB

 D. ABCDE

4、用两个栈模拟队列先进先出，模拟其add和romve功能，给出思路和代码。

5、一景区需要门票5元，售票员没有零钱，假设这一天会来2N个人，其中N个人会给5元钱，N个人给10元，问所有人都不需要等待的概率是多少？

6、给两个字符串，输出其最长共同字符串的长度：如
        S1: asdfghjqweryuiase
        S2: astyfrtfghjqwsa
其最长共同字符串为fghjqw 长度为6，给出代码。

参考答案

1、3：1

解析：如果是正就再抛一次，因此此时正的概率为 1/2 * 1/2 = 1/4，反的概率为 1/2 * 1/2 = 1/4；如果反就翻正，因此此时正的概率为 1/2 * 1 = 1/2；所以正的概率为 1/4 + 1/2 = 3 /4，反的概率为 1/4；从而正反比例为 3：1。

2、典型的贝叶斯公式，p(甲|废品) = p(甲 && 废品) / p(废品) = （0.4 × 0.01） /（0.4 × 0.01 + 0.6 × 0.02） = 0.25

3、C

4、思路：两个栈stackIn 和 stackOut，
        add：push stackIn
        remove：若stackOut不为空，pop stackOut；若stackOut为空则把stackIn倒入stackOut，再pop stackOut。

代码如下：

public void add(String in){
    stackIn.push(in);
}
 
public String remove(){
    if(stackOut.isEmpty()){
        while(stackIn.isNotEmpty()){
            stackOut.push(stackIn.pop());  }
    }
    stackOut.pop();
}

5、任何人不必等的情况数 Cn=2N!/(N!*N!*(N+1)) 总的情况数 T=2N!/N!*N! 不必等的概率为：Cn/T = 1/(N+1)

6、