发表于 | 分类于 | | 阅读次数:
字数统计: 24 | 阅读时长 ≈ 1

1、海量日志数据，提取出某日访问百度次数最多的那个IP。

发表于 | 分类于 | | 阅读次数:
字数统计: 1k | 阅读时长 ≈ 4

https://hit-alibaba.github.io/interview/basic/algo/DP.html

动态规划

适用于动态规划的问题，需要满足最优子结构和无后效性，动态规划的求解过程，在于找到状态转移方程，进行自底向上的求解。

爬楼梯问题 LeetCode 70

经典的动态规划问题之一，容易找到其状态转移方程为 dp[i] = dp[i-1] + dp[i-2]，从基础的 1 和 2 个台阶两个状态开始，自底向上求解：

容易看出其实结果就是 fibonacci 数列的第 n 项。

连续子数组的最大和 LeetCode 53

用 dp[n] 表示元素 n 作为末尾的连续序列的最大和，容易想到状态转移方程为dp[n] = max(dp[n-1] + num[n], num[n])，从第 1 个元素开始，自顶向上求解：

House Robber LeetCode 198

对于一个房子，有抢和不抢两种选择，容易得到状态转移方程 dp[i+1] = max(dp[i-1] + nums[i], dp[i])，示例代码如下：

最长回文子串 LeetCode 5

用 dp[i][j] 表示子串 i 到 j 是否是回文，使用动态规划求解：

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
string longestPalindrome(string s) {
    int m = s.size();
    if (m == 0) {
        return "";
    }
    vector<vector<int>> dp(m, vector<int>(m, 0));
    int start = 0;
    int length = 1;

    for (int i = 0; i < m; i++) {
        // 单个字符属于回文，例如 abcd
        dp[i][i] = 1;

        // 连续两个字符相同属于回文，例如 abb
        if (i < m - 1) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = 1;
                start = i;
                length = 2;
            }
        }
    }

    for (int len = 2; len <= m; len++) {
        for (int i = 0; i < m - len; i++) {
            int j = i + len;
            // 扩展长度
            if (dp[i + 1][j - 1] == 1 && s[i] == s[j]) {
                dp[i][j] = 1;

                if (j - i + 1 > length) {
                    start = i;
                    length = j - i + 1;
                }
            }
        }
    }

    return s.substr(start, length);
}

最小编辑距离 LeetCode 72

2.进程线程（还有有关操作系统的 我忘了

3.数据库查询 然后连接查询

8.链表讲一下 什么单向链表双向链表循环链表 链表适合快排吗为什么

  1. 四次挥手 time_wait

  2. 客户端当被告知服务端接收窗口大小为0后的行为，如果服务端的接收窗口又变大了呢？

  3. 拥塞控制

https://www.cnblogs.com/logsharing/p/8448446.html

  • get参数通过url传递，post参数放在request body中
  • get参数是有长度限制的，而post没有
  • get参数直接暴露在url中，较为不安全，不能传递敏感信息
  • get请求只能进行url编码，而post支持多种编码方式
  • get请求浏览器会主动cache
  • get请求参数会被完整保留在浏览历史记录里，而post中的参数不会被保留
  • get和post本质上就是TCP链接，并无差别。但是由于HTTP的规定和浏览器/服务器的限制，导致他们在应用过程中体现出一些不同
  • get产生一个TCP数据包，post产生两个TCP数据包

总结：

  1. 对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；而对于POST，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok（返回数据）。（据研究，在网络环境好的情况下，发一次包的时间和发两次包的时间差别基本可以无视。而在网络环境差的情况下，两次包的TCP在验证数据包完整性上，有非常大的优点。）
  2. 对于get和post的区别，get传递数据如同是写在脸上，post传递数据如同放在肚子里，脸上不能放太多东西，也不能放隐私东西，肚子里就无所谓啦~（一个面试官给我说的巧记妙招~）

浏览器输入 www.qq.com 发生了什么; 第二次访问与第一次有什么区别吗，长连接和短连接，四次挥手，客户端先发和服务端先发FIN有什么区别，一般是哪端先发，原因，哪端先发好？time_wait持续时间？2MSL? 没有time_wait有什么问题

http 与 https 区别，ssl 的过程

发表于 | 分类于 | | 阅读次数:
字数统计: 161 | 阅读时长 ≈ 1

两种基础的数据结构：链表和数组。

数组占据随机访问的优势，却有需要连续内存的缺点。

链表具有可不连续存储的优势，但访问查找是线性的。

散列表和链表、跳表的混合使用，是为了结合数组和链表的优势，规避它们的不足。

我们可以得出数据结构和算法的重要性排行榜：连续空间 > 时间 > 碎片空间。

  • 数组：连续的内存空间和相同类型的数据。访问时间O(1)，插入删除为了保证连续时间为O(n)。

发表于 | 分类于 | | 阅读次数:
字数统计: 582 | 阅读时长 ≈ 2

快速排序

时间复杂度：O(nlogn)，最差情况为O(n^2)

空间复杂度：O(1)，没有使用额外空间

稳定性：不稳定

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
# -*- coding:utf-8 -*-

# 一、算法导论实现
def quickSort(array, l, r):
    if l >= r:
        return
    mid = partition(array, l, r)
    quickSort(array, l, mid - 1)
    quickSort(array, mid + 1, r)

"""在划分partition的过程中排序，使用小区游标i+循环游标j，将比key小的值j与i在的位置交换，直至分区后交换r与i+1的值，返回i+1的中心位置。"""
def partition(array, l, r):
    # 1.选择主元
    key = array[r]
    # 2.找到小区，使用小区最后一个元素i，游标j
    i = l - 1
    j = l
    for j in range(l, r):
        # 2.1 j循环+1，找到小于key的元素时候，i后移动，并将找到的arr[j]与arr[i]换位置
        if array[j] < key:
            i += 1
            array[i], array[j] = array[j], array[i]
    # 3.游标j循环后，i为小区的最后一个元素，将r与i+1换位置，则分割完成
    array[i + 1], array[r] = array[r], array[i + 1]
    return i + 1

if __name__ == '__main__':
    nums = [6, 1, 2, 7, 9, 9, 3, 4, 5, 10, 8, -1]
    quickSort(nums, 0, len(nums) - 1)
    print nums

归并排序

时间复杂度：O(nlogn)，最好最优平均

空间复杂度：O(n)，每次归并的时候需要开辟临时空间 2倍数组长度的空间

稳定排序

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
# -*- coding:utf-8 -*-

def mergeSort(array):
    # 1.划分小于等于1，则返回自己
    if len(array) <= 1:
        return array
    # 2.大于1，继续划分为左右，mid为中位index。返回为merge排序后的结果。
    else:
        mid = len(array) / 2
        print mid
        left = mergeSort(array[:mid])
        right = mergeSort(array[mid:])
        # 返回排序后的left+right
        return merge(left, right)

"""在merge的过程中排序，输入为left，right数组，使用i、j循环俩数组，返回排序好的合并数组result。"""
def merge(left, right):
    # 1.临时存储空间
    result = []
    # 2.left的下标i，right的下标j
    i = 0
    j = 0
    # 2.循环left和right，将小的存入result，i或j+1，直至i、j有一个分完
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # 3.将未循环完的剩余left或right数组的数字直接与result连接
    result += left[i:]
    result += right[j:]
    # 4.返回merge结果
    return result

if __name__ == '__main__':
    array = [9, 6, 1, 2, 5, 0, 4]
    result = mergeSort(array)
    print result