美团点评研发笔试卷-2013年

1、有ABCD四个人要在夜里过一座桥，他们通过这座桥分别需要耗时1、2、5、10分钟，现在只有一支手电，过桥时必须带有手电，并且同时最多只能两个人一起过桥。请问如何安排能够让四个人尽快都过桥。

2、 25匹马赛跑，每次只能跑5匹马，最快能赛几次找出跑得最快的3匹马？赛跑不能计时，并假设每匹马的速度是恒定不变的。请给出答案并描述比赛过程。 

3、在有团购之前，大家都是现场买门票，公园的门票是5元，某天售票处开门时没有准备零钱。假设一天来购票的依次有2N个人，其中有N个人有5元零钱，其他N个人只有10元面值的钱；假设每人只买一张票。请问任何人都不必为找零而等待的概率是多少？ 

4、有一个函数“int f(int n)”，请编写一段程序调试函数f(n)是否总是返回0，并添加必要的注视和说明。

5、 用你熟悉的语言编写程序用两个栈（Stack）模拟队列（Queue）的先进先出操作，仅实现add、remove方法即可。
1）请先描述思路； 2）编写完整代码实现，编程语言不限。

6、编写函数，获取两段字符串的最长公共子串的长度，例如：
        S1= GCCCTAGCCAGDE
        S2= GCGCCAGTGDE
这两个序列的最长公共子串是GCCAG，也就是说返回值。

8、（Android开发选做）关于Activity的生命周期，下拉statusbar时，桌面Activity会触发哪几个生命周期？系统关机时，弹出关机Dialog之后，此时，桌面Activity会触发哪几个生命周期？

9、（系统运维选做）有主机A、B、C通过eth0和同一个交换机相连，A的IP地址为192.168.1.2，子网掩码255.255.255.0，B的IP地址为192.168.2.2，子网掩码255.255.255.0，C的IP地址为192.168.4.2，子网掩码255.255.255.0。现希望A和B能够通信，A和C、B和C不能通信。
1）假设能更改A和B的子网掩码，要如何设置A和B的子网掩码？
2）如果不能更改子网掩码，需要在A和B做什么设置？
3）A和B通信时，C是否能够通过sniffer截获A和B通信的报文，如果只能截获一部分报文，是哪一类报文？
4）C可以仅通过sniffer得知A和B的IP地址和MAC地址吗？如果能，如何获得？

参考答案

int n = INT_MIN; 
do 
{ 
    if(0 != f(n)) 
    { 
        //error 
        break;
     }
} 
while(n++ != INT_MIN); 

if(n != INT_MIN) error;// 

import java.util.Stack;
public class StackToQueue {
    static Stack<Integer> stack1 = new Stack<Integer>();
    static Stack<Integer> stack2 = new Stack<Integer>();
     
    public void add(int node) {
        stack1.push(node);
    }
     
    public int remove() {
        if(stack2.isEmpty()){//pop时如果stack2为空则将stack1内元素倒置入stack2，取栈顶元素；
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

public int LCS_LENGTH(String x,String y){ int m=x.length(),n=y.length();
    nt b[][]=new int[m+1][n+1];
    int c[][]=new int[m+1][n+1];
    Vector<Character> res= new
    Vector<Character>();
    for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++)
        if(x.charAt(i-1)==y.charAt(j-1)){
            c[i][j]=c[i-1][j-1]+1;
            b[i][j]=0; }
        else if(c[i-1][j]>=c[i][j-1]){
            c[i][j]=c[i-1][j];
            b[i][j]=1;
        }
        else {
            c[i][j]=c[i][j-1];
            b[i][j]=-1;
        }
    }
    int i=m,j=n;
    while(i!=0&&j!=0){//根据b来寻找最大子序列的路径
        if(b[i][j]==0){
            res.add(0,x.charAt(i-1));
            i--;
            j--;
        }else if(b[i][j]==-1){
            j--;
        }else
            i--;
        }
    return res;
}