小米校园招聘笔试题和面试题答案(2)

更新时间:2018-11-22 16:01作者:李天扬老师

    二、编程题

      1、数组乘积(15分)

      输入:一个长度为n的整数数组input

      输出:一个长度为n的整数数组result,满足result[i] = input数组中除了input[i]之外所有数的乘积(假设不会溢出)。比如输入:input = {2,3,4,5},输出result = {60,40,30,24}

      程序时间和空间复杂度越小越好。

      C/C++:

      int *cal(int* input , int n);

      Java:

      int[] cal(int[] input);

      [cpp] view plaincopy

      int *cal(int* input , int n)

      {

      int i ;

      int *result = new int[n];

      result[0] = 1;

      for(i = 1 ; i < n ; ++i)

      result[i] = result[i-1]*input[i-1];

      result[0] = input[n-1];

      for(i = n-2 ; i > 0 ; --i)

      {

      result[i] *= result[0];

      result[0] *= input[i];

      }

      return result;

      }

      2、异形数(25分)

      在一个长度为n的整形数组a里,除了三个数字只出现一次外,其他的数字都出现了2次。请写程序输出任意一个只出现一次的数字,程序时间和空间复杂度越小越好。

      例如: a = {1,3,7,9,5,9,4,3,6,1,7},输出4或5或6

      C/C++:

      void find(int* a , int n);

      Java:

      void find(int[] a);

      [cpp] view plaincopy

      // lowbit表示的是某个数从右往左扫描第一次出现1的位置

      int lowbit(int x)

      {

      return x&~(x-1);

      }

      void find(int* a , int n)

      {

      int i , xors;

      xors = 0;

      for(i = 0 ; i < n ; ++i)

      xors ^= a[i];

      // 三个数两两的异或后lowbit有两个相同,一个不同,可以分为两组

      int fips = 0;

      for(i = 0 ; i < n ; ++i)

      fips ^= lowbit(xors ^ a[i]);

      // 表示的是:flips=lowbit(a^b)^lowbit(a^c)^lowbit(b^c)

      int b; // 假设三个只出现一次的其中一个数为b

      b = 0;

      for(i = 0 ; i < n ; ++i)

      {

      if(lowbit(xors ^ a[i]) == fips)

      b ^= a[i];

      }

      // 成功找到三个数中一个数

      cout<

      }

      3、朋友圈(25分)

      假如已知有n个人和m对好友关系(存于数字r)。如果两个人是直接或间接的好友(好友的好友的好友...),则认为他们属于同一个朋友圈,请写程序求出这n个人里一共有多少个朋友圈。

      假如:n = 5 , m = 3 , r = {{1 , 2} , {2 , 3} , {4 , 5}},表示有5个人,1和2是好友,2和3是好友,4和5是好友,则1、2、3属于一个朋友圈,4、5属于另一个朋友圈,结果为2个朋友圈。

      最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。

      C/C++:

      int friends(int n , int m , int* r[]);

      Java:

      int friends(int n , int m , int[][] r);

      [cpp] view plaincopy

      // 简单的并查集应用

      int set[10001];

      inline int find(int x) //带路径优化的并查集查找算法

      {

      int i , j , r;

      r = x;

      while(set[r] != r)

      r = set[r];

      i = x;

      while(i != r)

      {

      j = set[i];

      set[i] = r;

      i = j;

      }

      return r;

      }

      inline void merge(int x , int y) //优化的并查集归并算法

      {

      int t = find(x);

      int h = find(y);

      if(t < h)

      set[h] = t;

      else

      set[t] = h;

      }

      int friends(int n , int m , int* r[])

      {

      int i , count;

      for(i = 1 ; i <= n ; ++i) //初始化并查集,各点为孤立点,分支数为n

      set[i] = i;

      for(i = 0 ; i < m ; ++i)

      merge(r[i][0] , r[i][1]);

      count = 0;

      for(i = 1 ; i <= n ; ++i)

      {

      if(set[i] == i)

      ++count;

      }

      return count;

      }

    为您推荐

    2019年两会《政府工作报告》养老金新政策,要提高养老保障水平

    《关于2018年中央和地方预算执行情况与2019年中央和地方预算草案的报告》要求,提高养老保障水平。从2019年1月1日起,按平均约5%的幅度提高企业和机关事业单位退休人员基本养老金标准。

    2019-06-13 04:57

    如何在另类面试问题中胜出

    在面试中,有些考官会先提一个不甚友好的问题,或者劈头浇你一盆冷水,让你在委屈和激愤中露出本色。在他看来,击溃你的心理防线,才能筛选出有心理承受能力的智者,找到能面对压力的新鲜血液。要想在压力面试中胜出,只能学会绕开陷阱,奋战到底。

    2019-06-08 03:00

    面试紧张时应该怎么办

    面试是进入公职机关的最后一道主要的门槛,因此可以说每一位进入面试的人,心里就像绷住一根弦一样,也就是说每位考生,都会以高度的精神状态去抓住这次进入角色的机会。出现紧张、焦虑的心情也是不可避免的,只有认识了解,才能完全的克服。

    2019-06-08 02:58

    面对变故 学会自我解嘲

    面对降级、减薪、甚至解雇、离婚、丧子等变故,许多人反应过度,很长时间缓不过劲儿来。而有的人却能很快度过,重返正常的生活轨道。其决定因素是一种特殊的心理素质:心理复原力。有了它,人们不怕挫折;而缺少它,会特别害怕受伤害,不敢付出行动。

    2019-06-06 03:12

    办公室里该与不该谈论的话题

    办公室是一个充满原则、纪律,讲求策略的场合,更是一个充满利益冲突的是非之所。既如此,办公室里谈个人私事是否妥当呢?网上调查显示,尽管九成以上的人认为“办公室里隐私不宜说”,但是她/他们又同时承认有在办公室里谈论涉及私人感情、家庭关系、同事喜恶和上下级关系等隐私性内容的行为。

    2019-06-06 03:10

    面试自我介绍的几大原则

    应聘到外企或其他用人单位时,求职者往往最先被问及的问题就是“请先介绍介绍你自己”。这个问题看似简单,但求职者一定要慎重对待,它是你突出优势和特长,展现综合素质的好机会。回答得好,会给人留下良好的第一印象。

    2019-06-01 03:19

    外企面试必须要注意的五“必要”

    到外企面试前,仅仅准备好一份简历是不够的,还要提前做好面试前的“功课”,这样面试通过的几率就会大大增加。

    2019-06-01 03:16

    加载中...