Bilibili 搜索工程师电面

Bilibili (the Chinese version of Youtube) tele-interviewed me at yesterday afternoon. This article records the process and content of the interview.

昨天下午参加了B站的一个电话面试，本文记录了面试的内容。

---

作为B站的忠实粉丝，能够参与B站的电面是很高兴的。

给我面试的面试官是来自云技术部的，她的声音很好听 :)

一上来就是自我介绍，讲讲曾经做过的项目，她对我做过的实体链接研究、代码编辑器以及人工智能的项目比较感兴趣，然后我就讲了大概半小时的 Entity Linking in Web Tables……

介绍完背景经历后，就问了一些数据结构方面的问题：

• 讲下你知道的数据结构
• 在这些数据结构中插入元素的时间复杂度

对于第一个问题，我基本把我想到的数据结构都讲了：链表，队列，栈，二叉树，堆，trie树，Hash表

然后在第二个问题中，堆中插入元素的过程我没有答上来，我感觉是自顶向下，用二分查找的方式插入，然而实际上是自底向上，根据堆的性质 (父节点的值大于子节点的值，或者相反) 递归插入。

讲完数据结构，就是限时编程测试，在 CodePad 上做一个题。

题目是环形链表插值，一个环状有序链表，有头指针，里面存储的元素按升序排列(除去环的交接点，即头部元素和尾部元素)。使用C/C++实现一个算法，将新元素插入到当前链表中，不破坏原有链表的各种约束。

[C++ Code]

// Created by sjyan @2017-06-23

#include <iostream>
using namespace std;

class ListNode {
public:
    int val;
    ListNode *next;
    bool isHead;
    ListNode(int val) {
        this->val = val;
        this->next = NULL;
        this->isHead = false;
    }
};

// insert a new element to the linked list
int insert(ListNode *head, ListNode *newone) {    
    // head->head
    if (head->next->isHead == true) {
        head->next = newone;
        newone->next = head;
        return 0;
    }

    ListNode *p = head->next;
    ListNode *q = p->next;
    ListNode *last = p;
    
    // head->newone->p1->...
    if (p->val > newone->val) {
        head->next = newone;
        newone->next = p;
        return 0;
    }
    
    // head->p1->p2->...->pn->head
    while (q->isHead != true) {
        if (p->val <= newone->val && newone->val <= q->val) {
            p->next = newone;
            newone->next = q;
            return 0;
        }
        last = q;
        p = p->next;
        q = q->next;
    }
    
    // head->...->last->newone->haed
    // head->p->head
    if (last->val < newone->val) {
        last->next = newone;
        newone->next = head;
        return 0;
    }
    return 0;
}

// print linked list
void print(ListNode *head) {
    cout<<"head->";
    ListNode *p = head->next;
    
    while(p->isHead != true) {
        cout<<p->val<<"->";
        p = p->next;
    }

    cout<<"head"<<endl;
}

int main() {
    // case 1: head->2->4->6->head, newone = 3
    ListNode *head = new ListNode(0);
    ListNode *p1 = new ListNode(2);
    ListNode *p2 = new ListNode(4);
    ListNode *p3 = new ListNode(6);
    ListNode *newone = new ListNode(5);
    head->isHead = true;
    head->next = p1;
    p1->next = p2;
    p2->next = p3;
    p3->next = head;
    
    // case 2: head->head, newone = 3
    // ListNode *head = new ListNode(0);
    // ListNode *newone = new ListNode(3);
    // head->isHead = true;
    // head->next = head;
    
    // case 3: head->1->head, newone = 3
    // ListNode *head = new ListNode(0);
    // ListNode *p1 = new ListNode(1);
    // ListNode *newone = new ListNode(3);
    // head->isHead = true;
    // head->next = p1;
    // p1->next = head;

    // case 4: head->4->head, newone = 3
    // ListNode *head = new ListNode(0);
    // ListNode *p1 = new ListNode(4);
    // ListNode *newone = new ListNode(3);
    // head->isHead = true;
    // head->next = p1;
    // p1->next = head;

    // insert
    print(head);
    insert(head, newone);
    print(head);
    
    return 0;
}