9.19小米笔试

算法卷 两个代码题第一题带c个1的背包问题 100第二题 两个数组可以交换对应位置问能不能得到递增或递减数组 100

9.9一面hr9.11二面闲聊1.你现在是在实验室吗？2.平时都几点回去？3.现在学业繁忙吗？4.我们业务比较核心，对Java基础，安卓基础，数据结构，算法基础比较重视。手撕归并排序 控制在半小时以内1.你看你写了那么多的循环，有没有优化的空间？2.输入的数组能不能尽可能乱一点？搞些负数、0、重复的数字还有大一点的数字。3.输入能不能不要用n来限制，输几个数就排几个数，实际开发不都是这样的吗？4. 你感觉你的算法写的怎么样？八股1. 实习中最常用的集合框架是什么？2. 为什么不用LinkedList而要用ArrayList？3. 把HashMap的value 值转化为List，你能想到几种方法...

第一题dp，第一次卡在中间dp过程要取最大值，第二次卡在数组大小宽度要设置成1000```c++#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;int main(){    int t;    cin>>t;    const int N = 505;    const int B = 1005;    while (t--)    {        int arr[N];         int box,num,single;        cin>>box>>num>>single;        for(int i =1;i<=num;i++)        {            cin>>arr[i];        }        if(single>=box)        {            cout<<"YES"<<endl;            continue;        }        //cal        bool dp[N][B];        for(int i = 0;i<B;i++)        dp[0][i]=0;        //只有num个物品        //dp[a][b]表示选择装了前a个东西能塞满b个空间        //2 3 5 7        //dp[0][...]=0        //dp[1][01]=0,dp[1][2]=1,dp[1][3]...=0        //dp[2][01]=dp[01],dp[2][2]=1,dp[2][3]=1,dp[2][4]=0(从dp[1][1]转移过来,为0)dp[2][5]=1()        for(int i = 1;i<=num;i++)        {            for(int j = 0;j<B;j++)            {                //如果放不下，就复制                //放得下,dp[i][j]=dp[i-1][j-arr[i]]                if(arr[i]>j)dp[i][j]=dp[i-1][j];                else if(arr[i]==j) dp[i][j]=1;                else if(arr[i]<j)                //要么放进去，要么不放进去                dp[i][j]=max(dp[i-1][j-arr[i]],dp[i-1][j]);            }        }        bool res=false;        //只要满足[box-single,box]的区间就能装满        for(int i = box;i>=box-single;i--)        {            if(dp[num][i]==true)res=true;        }        if(res)cout<<"YES"<<endl;        else cout<<"NO"<<endl;    }        return 0;}```第二题贪心，每一次往前看的时候如果是升序序列就选符合条件下尽量小的，反之亦然```c++#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;const int N = 1e5+10;int arr[N];int brr[N];int main(){    int n;    cin>>n;    while(n--)    {        int size;        cin>>size;        for(int i=0;i<size;i++)        {            scanf("%d",&arr[i]);        }        for(int i=0;i<size;i++)        {            scanf("%d",&brr[i]);        }        int res1=true;        //升序和降序都试一次，每一次选择符合条件的且        //升序的时候更小的，降序的时候更大的        int cur =0;        cur = min(arr[0],brr[0]);        for(int i = 1;i<size;i++)        {            int a = arr[i];            int b = brr[i];            if(a>=cur && b>=cur)            {                cur = min(a,b);            }            else if(a<cur && b<cur)            {                res1 = false;                break;            }            else            {                cur = max(a,b);            }        }        bool res2=true;        int cur2 =0;        cur2 = max(arr[0],brr[0]);        for(int i = 1;i<size;i++)        {            int a = arr[i];            int b = brr[i];            if(a<=cur2 && b<=cur2)            {                cur2 = max(a,b);            }            else if(a>cur2 && b>cur2)            {                res2 = false;                break;            }            else            {                cur2 = min(a,b);            }        }        if(res1||res2)cout<<"YES"<<endl;        else cout<<"NO"<<endl;    }    return 0;}```

一面hr面：（非常知性有礼貌的hr姐姐，因为约了晚上面试，一直在和我抱歉）1、问了家里人情况，期待在哪里工作？2、实习期间最难忘的一件事？3、实习i期间遇到了什么问题吗？4、为什么不在腾讯转正（hc太少，竞争过于激烈。。。。）5、以后希望去哪里工作，想做什么方向的工作？6、手上还有其他offer吗？二面：时间不长，约半小时就是半小时，总体体验很棒，项目和八股参半，主要考察java基础，可能是看我实习是go的原因，想检测一下我的Java水准。1、介绍一下实习的项目，然后拷打项目？2、项目里kafka是怎么使用的，谁是生产者，谁是消费者，丢消息怎么办？（回答我的项目丢了也没事。。。，给面试官...