面经0225

本次面试更多是开放性，不怎么针对较为难的问题

笔试题目

leetcode677

笔试思路

不会做不要怕，思路很重要，记住题目的关键点，对问题原始的思路，扩展思路

第一种是两个hashmap（面试过程中，如果写不出其他更好的办法）

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

class MapSum {
public:
	/** Initialize your data structure here. */
	MapSum() {
	}
 
	void insert(string key, int val) {
		int delta = val - m[key];
		m[key] = val;
		string prefix = "";
		for (auto &ch : key) {
			prefix += ch;
			score[prefix] = ((score.find(prefix)==score.end())?0:score[prefix] + delta);
		}
	}
 
	int sum(string prefix) {
		return score[prefix];
	}
private:
	unordered_map<string, int> m;
	unordered_map<string, int> score;
};

第二种是前缀树（字典树）

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
44
45
46
47
48
49
class MapSum {
    typedef struct Node
    {
        int count;
        vector<Node*> children;
        Node(int c):
            count(c)
        {
            children.resize(26, NULL);
        }
    } Node;
    Node* root;
    map<string, int> mym;
    void add(const string& str, int delta)
    {
        Node* cur = root;
        for (const char& c : str)
        {
            if (cur -> children[c - 'a'] == NULL)
                cur -> children[c - 'a'] = new Node(0);
            cur -> children[c - 'a'] -> count += delta;
            cur = cur -> children[c - 'a'];
        }
    }
public:
    /** Initialize your data structure here. */
    MapSum() {
        root = new Node(0);
    }
    
    void insert(string key, int val) {
        int delta = val;
        if (mym.count(key))
            delta -= mym[key];
        mym[key] = val;
        add(key, delta);
    }
    
    int sum(string prefix) {
        auto cur = root;
        for (const char& c : prefix)
        {
            cur = cur -> children[c - 'a'];
            if (cur == NULL)
                return 0;
        }
        return cur -> count;
    }
};

git和svn的区别

  • Git是分布式的，SVN不是；最核心的区别
  • Git把内容按元数据方式存储，而SVN是按照文件
  • Git和SVN的分支不同：分支在SVN中一点都不特别，版本库的一个目录
  • Git没有一个全局的版本号 ，而SVN有
  • Git的内容完整性要优于SVN：Git的内容存储使用的是SHA-1哈希算法，能够确保内容的完整性

TCP/IP协议栈 分层 是什么来的

物理链路层 MAC 确认主机的物理地址，传输数据
网络层 ip icmp ARP（获取目标主机的地址） 定义IP地址，通过IP进行MAC寻址，转发数据包
传输层 tcp udp 数据包端对端传输
应用层 DNS https smtp ftp;

什么是虚函数(回答不够简洁)

关键字：被virtual关键词修饰的成员函数为虚函数
析构函数为什么要虚函数（内存管理）

堆排序 算法复杂度（手撕待定）

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
44
45
46
47
48
49
50

// 从大到小排序
// void Down(int array[], int i, int n) {
//     int child = 2 * i + 1;
//     int key   = array[i];
//     while (child < n) {
//         if (child + 1 < n && array[child] > array[child + 1]) {
//             child++;
//         }
//         if (key > array[child]) {
//             swap(array, i, child);
//             i = child;
//         } else {
//             break;
//         }
//         child = child * 2 + 1;
//     }
// }

// 从小到大排序
void Down(int array[], int i, int n) { // 最后结果就是大顶堆
    int parent = i;                    // 父节点下标
    int child  = 2 * i + 1;            // 子节点下标
    while (child < n) {
        if (child + 1 < n && array[child] < array[child + 1]) { // 判断子节点那个大，大的与父节点比较
            child++;
        }
        if (array[parent] < array[child]) { // 判断父节点是否小于子节点
            swap(array, parent, child);     // 交换父节点和子节点
            parent = child;                 // 子节点下标 赋给 父节点下标
        }
        child = child * 2 + 1; // 换行，比较下面的父节点和子节点
    }
}

void BuildHeap(int array[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆，必须从下往上比较
        Down(array, i, size);                 // 否则有的不符合大顶堆定义
    }
}

void HeapSort(int array[], int size) {
    BuildHeap(array, size); // 初始化堆
    display(array, size);   // 查看初始化结果
    for (int i = size - 1; i > 0; i--) {
        swap(array, 0, i); // 交换顶点和第 i 个数据
                           // 因为只有array[0]改变，其它都符合大顶堆的定义，所以可以从上往下重新建立
        Down(array, 0, i); // 重新建立大顶堆
    }
}

linux和自我学习能力

对于未接触的，怎么调整自己的心态，如果规划好自己的学习计划。