面试小记(二)

发表于   |     |   阅读次数

记录在面试过程中遇到的一些编程问题，数组去重、大数据量下的操作等

  • 数组去重(连着两次都被问到~)

    • O(n^2) 的解法，定义一个变量数组 result 保存结果，遍历需要去重的数组，如果该元素已经存在在 result 中了，则说明是重复的元素，如果没有，则放入 result 中

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      /*兼容性写法*/
      function unique(arr){
          var result=[];
          
          for(var i=0,ilen=arr.length;i<ilen;i++){
              var item=arr[i];
              for(var j=0,jlen=arr.length;j<jlen;j++){
                  if(item == arr[j]){
                      break;
                  }
              }
              
              if(jlen==j）{
                      result.push(item;)
                  }
          }
          
          return result;
      }
      //不考虑兼容
      function unique(arr){
          var result={};
          
          for(var i=0,ilen=arr.length;i<ilen;i++){
              var item = arr[i];
              
              (result.indexOf(item)===-1)&&result.push(item);
          }
          
          return result;
      }

      function unique(arr){
          var result=arr.filter(function(item,index,array){
              return array.indexOf(item) === index;
          });
          
          return result;
      }

      /*** 面试官问我indexOf在数组中可以直接用吗，我当时想indexOf不就是array自带
          的方法吗，后来才想到面试官可能想说的是indexOf的兼容性，还有面试官说indexOf最早是string上的方法
      ***/

    • sort()

      1
      2
      3
      4
      function unique(arr) {
          return arr.sort().filter(function(item, index, array) {
              return !index || item != array[index - 1];
      });

    • Object做hash

      1
      2
      3
      4
      5
      6
      7
      function unique(a) {
          var obj = {};

          return a.filter(function(item) {
              return obj.hasOwnProperty(item) ? false : (obj[item] = true);
          });
      }

    • ES6

      1
      2
      3
      function unique(arr) {
          return Array.from(new Set(arr));
      }

  • 海量数据下Top K的问题