小米暑期实习笔试题-2015年

编程题

1、世界上有10种人，一种懂二进制，一种不懂。那么你知道两个int32整数m和n的二进制表达，有多少个位(bit)不同么？

2、风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。 给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，数组中第i个元素（prices[i]）代表该股票第i天的股价。 假设你一开始没有股票，但有至多两次买入1股而后卖出1股的机会，并且买入前一定要先保证手上没有股票。若两次交易机会都放弃，收益为0。 设计算法，计算你能获得的最大收益。 输入数值范围：2<=n<=100,0<=prices[i]<=100

3、git是一种分布式代码管理工具，git通过树的形式记录文件的更改历史，比如： base'<--base<--A<--A' ^ | --- B<--B' 小米工程师常常需要寻找两个分支最近的分割点，即base.假设git 树是多叉树，请实现一个算法，计算git树上任意两点的最近分割点。 （假设git树节点数为n,用邻接矩阵的形式表示git树：字符串数组matrix包含n个字符串，每个字符串由字符'0'或'1'组成，长度为n。matrix[i][j]=='1'当且仅当git树种第i个和第j个节点有连接。节点0为git树的根节点。）

参考答案

1、参考代码

//JAVA 
public int countBitDiff(int m, int n) {
 
        int dif=m^n;//先将二者做异或运算，得到结果；
        int cnt=0;
        while(dif!=0){
            dif=dif&(dif-1);
            cnt++;
        }             //统计一个整数dif含有多少个1；
        return cnt;
    }

2、利用动态规划的思想。

public int calculateMax(int[] prices) {
    if(prices==null||prices.length<2)
        return 0;
    int len=prices.length;
    int[] left=new int[len];
    left[0]=0;
    int min=prices[0];
    int max=0;
    for(int i=1;i<len;i++){
        if(prices[i]<min)
            min=prices[i];
        if(prices[i]-min>max)
            max=prices[i]-min;
        left[i]=max;
    }
    int[] right=new int[len];
    right[0]=0;
    int high=prices[len-1];
    max=0;
    for(int i=len-2;i>=0;i--){
        if(prices[i]>high)
            high=prices[i];
        if(high-prices[i]>max)
            max=high-prices[i];
        right[i]=max;
    }
    int result=0;
    for(int i=0;i<len;i++){
        if(left[i]+right[i]>result)
            result=left[i]+right[i];
    }
    return result;
}

3、参考代码：

class Solution {
public:
    /**
     * 返回git树上两点的最近分割点
     *
     * @param matrix 接邻矩阵，表示git树，matrix[i][j] == '1' 当且仅当git树中第i个和第j个节点有连接，节点0为git树的跟节点
     * @param indexA 节点A的index
     * @param indexB 节点B的index
     * @return 整型
     */
    int getSplitNode(vector<string> matrix, int indexA, int indexB) {
        if(matrix.empty()||indexA>=matrix.size()||indexB>=matrix.size())  return 0;
        vector<int> pathA,pathB;
        int sz=matrix.size();
        dfs(matrix,pathA,sz,-1,0,indexA);
        dfs(matrix,pathB,sz,-1,0,indexB);
        int size=min(pathA.size(),pathB.size());
        for(int i=0;i<size;++i){
            if(pathA[i]!=pathB[i]){
                return pathA[i-1];
            }
        }
        return pathA[size-1];
    }
private:
    bool dfs(vector<string> &matrix,vector<int> &pathR,int &sz,int pre, int x,int &index){
        pathR.push_back(x);
        if(x==index){//注意0，0
            return true;
        }
        if(matrix[x][index]=='1'){
            pathR.push_back(index);
            return true;
        }
        for(int i=0;i<sz;++i){
            if(i==pre) continue;
            if(matrix[x][i]=='1'){
                vector<int> path{pathR};
                path.push_back(i);
                if(dfs(matrix,path,sz,x,i,index)){
                    swap(path,pathR);
                    return true;
                }
            }
        }
        return false;
    }
};