阿里巴巴数据开发实习生三面面经

自我介绍

N个文件, 每个文件有序, 怎么合并成一个整体有序的文件? 时间空间复杂度是多少? (外部排序)

如何设计一个整数压缩算法? 一个整数数组, 用尽可能小的空间存放, 并且可以压缩完之后可以还原. (这个应该有专门的整数压缩算法, 但我不知道, 用之前学的霍夫曼编码构造了一下)

讲讲进程间通讯和线程间通讯的方法?

编程题,

用数组实现队列

class Queue{
private:
  int values[];
  int begin;
  int end;
  int size;
public:
  Queue(int n){
    ++n;
    values = new int[n];
    size = n;
    begin = 0;
    end = 0;
  }
  ~Queue(){
    delete[] values;
  }
  
  void push_back(int a){
    if(end == (begin - 1) % size){
      throw new Exception("FullQueue");
    }
    else{
      end = (end + 1) % size;
      values[end] = a;
    }
  }
  
  int pop_front(){
    if(end == begin){
      throw new Exception("EmptyQueue");
    }
    else{
      int ret = values[begin];
      begin = (begin + 1) % size;
      return ret;
    }
  }
  
}