面试问题整理

Posted on Edited on In

  1. 如何实现shuffle

    1
    2
    3
    4
    5
    6
    7
    // pseudocode
    list=[1,2,3,4,5]
    for(int i=list.size()-1; i>=0; i--)
    {
        int x=random(0,i);
        swap(list[i], list[x]);
    }

  2. 手写排序算法（quicksort为什么最快）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void Quick_Sort(vector<int>& vec, int start_index, int end_index)
    {
        if(end_index<=start_index)	return;
        int p1 = start_index, p2 = end_index+1, pivot = vec[start_index];
        while(true)
        {
            while(vec[++p1]<pivot && p1<=end_index);
            while(vec[--p2]>pivot && p2>=start_index);
            if(p1>=p2)	break;
            swap(vec[p1], vec[p2]);
        }
        swap(vec[start_index], vec[p2]);
        Quick_Sort(vec, start_index, p2-1);
        Quick_Sort(vec, p2+1, end_index);
    }

    QuickSort为什么最快？

    • 复杂度系数：roughly no difference
    • cache locality：quicksort每次会尝试读取一段连续的内存，而heapsort为了维护heap需要跳跃地读取内存
    • In-place：quicksort实现不需要额外空间，而mergesort需要额外的空间，在数据量足够大时差异会很明显

    QuickSort为什么不够快？

    • worst situation：quicksort对pivot选择要求很高，最坏情况会退化成bubble，所以对pivot选择要求很高，而STL中也对quicksort进行了优化--使用introspective sort

    • stable：quicksort总体上stable，但不能保证stable

    • 在特殊情况下使用bucket sort还会更快

    • 对于处理linked list，cache locality就不复存在，quicksort没有优势，常使用merge sort，此时也不需要额外空间。数据库中sort也常使用disk mergesort

  3. STL sort

  4. unordered_map/map底层实现（hashtable如何处理非数字）

  5. hashtable处理冲突--线性探查/平方探查

  6. virtual function

  7. 哈夫曼编码

  8. max heap如何建立

    参照heapsort的建方式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    void MaxHeapify(vector<int>& vec, int start_index, int end_index)
    {
        int parent = start_index, child = start_index*2+1;
        while(child<=end_index)
        {
            // select the max child node
            if(child+1<=end_index && vec[child]<vec[child+1])	child++;
            if(vec[child]>vec[parent])
            {
                swap(vec[child], vec[parent]);
                parent = child;
                child = parent*2+1;
            }
            else	return;
        }
    }
    void BuildMaxHeap(vector<int>& vec)
    {
        for(int i=vec.length()/2-1; i>=0; i--)
        {
            MaxHeapify(vec, i, vec.length()-1);
        }
    }

  9. \(f\) 等概率生成(0, 1)，要求等概率生成(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)，调用\(f\)次数的期望是多少？--reject sampling

    1
    2
    生成(0, 1, 2)，可以先生成(0, 1, 2, 3)，再对3进行重采样。
    调用次数--做一件事情第0次成功+第1次成功+第2次成功(等差比数列求和)