YNZH's Blog

IPC通信：

有名管道FIFO ，无名管道PIPE，消息队列，信号量、共享内存，文件，socket等。参考os tag下的IPC通信

页中断：

电梯算法：

是一种磁盘调度算法，大概意思就是想电梯一样，只会往一个方向走哦要么向上，要么向下，比如说电梯本来在1层，有人按了7层，这时候电梯就会开始向上走，走到6层的时候外面有人按了2层，同时也有人按了20层，那么电梯就会继续向上直到，走到向上的层数（被按了的不一定是楼层的最高处），然后向下，在计算机中就有磁盘调度中就可以使用这种算法，磁盘寻址的时候通过盘面的转动来变换扇区的，另一方面是磁头从磁盘圆心向外移动往复的，这里的磁头类似电梯

看个网上的例子吧！：

数据：98 183 37 122 14 124 65 67
读写头起始位置：53
磁头移动方向：0（0磁道减少方向、1磁道增加方向）

计算过程：
①53为基准，向内移动。
②分为两个队列，按由近到远排序：
37 14
65 67 98……183
③先移动到37，再到14，共：53-14 = 39长度
14移动到183，共：183-14 = 169长度；
④则共需移动长度为：39+169 = 208，平均寻址长度为：208/8 = 26

参考链接

线程切换代价：

当时是问到synchronized这个东西，重量级锁的话会引起线程阻塞，产生软中断，发生系统调用（用户态–>内核态），加入阻塞队列，也会进行线程切换，CPU进行线程上下文的保存，加载下一个线程的上下文，然后回到用户态。

TCP的拥塞控制：

回答的时候回答了 滑动窗口（流量控制！！），暴露了对流量控制和拥塞控制概念有点模糊，

流量控制：流量？啥是流量，啥是流？流是有方向的呀，所以一搬值的是端到端的传输才叫流量，啥是量？就是a到b一次传送多少嘛，所以TCP中流量控制指的是端到端的一TCP连接之间传输报文多少的控制呀，因为a和b的发送接收能力谁也不知道是不是匹配的，对吧，所以a，b各自都有一个叫做发送窗口和接收窗口的东西，在通信的 时候附带着传输过去，告诉你我就这接收，传输能力，你看着办，被给我搞多了，弄不过来可别怪我。哈哈所以a和b在建立连接的时候就会沟通，a要给b发送，就会选择 b的接收窗口和自己发送窗口，其中最小值来作为实际的发送窗口。所以就产生了滑动窗口这种策略。总结一下就是流量控制是端到端的的。

拥塞控制：英文单词是Congestion control啥意思 就像是堵车了，交警需要控制不堵车这个意思，他是站在全局的角度开看问题的，说到拥塞控制就不得不提 拥塞窗口（Congestion window，cwind）这个东东，乍一听好像和滑动窗口这个发送窗口有点像，不会是同一个东西吧，当然不是！！为啥？？？？，虽然我们通过三次握手知道了接受方可以接收的滑动窗口大小，那我们发送方是不是可以一次性的把自己发送窗口内的报文全部发完呢？答案是不可以，因为传送过程中其实是要经过很多网络节点的，我们不知道当前路上是不是堵车啊，要是堵车我靠，发送失败那不得重传吗，得不偿失呀，所以TCP协议采用了一种比较保守的策略，除了发送方的发送窗口，还维护了一个拥塞窗口，最开始的时候拥塞窗口大小为1，意思就是尽管你的发送窗口很大，但是你一次只能发送拥塞窗口大小（1）个报文，（其实TCP这里是在小心翼翼的试探当前路上堵不堵车），如果成功接受ACK了，那么就将拥塞窗口+1，然后一次发送两个，结果都成功了，看来路况很好嘛，继续这次发三个，这样依次。。直到当前发送发的发送窗口全部发送完了（称为一轮），发现拥塞窗口 = 发送方发送窗口 大小了，仔细想想确实啊每次收到ACK都会加1，然后下一轮的拥塞窗口就会是上一轮的2倍，这就是慢启动机制，除此之外还提供了拥塞避免、快重传、快启动等机制。

慢启动会通过指数级别的增长，因此会越来越快很容易引起网络阻塞，所以对于慢启动有一个ssh（slow start threshold）阈值，达到这个阈值以后，就会进入拥塞避免阶段，这个阶段不在每轮发送完成拥塞窗口只增加一。这样就可以缓慢的增长较小网络组阻塞的几率，通过这种方式可以试探出当前网络的最大拥塞窗口，当发送方接收到连续三个重复的确认号的时候会触发快重传机制，举个例子加入发送出 4，5，6，7三个报文，那么报文4丢失也就是没有收到确认号5，那么在当接收方收到5的时候，并不会返回确认号6，因为5前面的4并没有接收到，而是会返回确认号5（表面4没收到），6和7也是同样的返回ACK（5），当发送方连续接收到3个重复的ACK（5）的时候，就会乐观的认为5，6，7已经送到了，就会快速重传报文4，同时会有ssh = max（2，cwind/ 2） 阻塞窗口cwnd = ssh + 3 * SMSS，这里我i什么要加三呢，因为收到连续三个重复ACK暗示了后面三个保温已经抵达，所以会提前透支一下窗口大小，不然可能就会导致发送变得很慢，然后当发送方接收到新发送数据的ACK时候表面之前的4，5，6，7已经全部被确认了就会将cwind重新设置为ssh（归还提前透支的窗口大小，因为发生快重传就表明网络有阻塞的风险，cwind应该减小为一半，之所以前面还加了三是因为提前透支嘛，这时候要还回来）。cwind = ssh 也就是变味了原来的一半大小，这就是所谓的快启动（不是从cwind=1开始）。加入发生了更加恶劣的阻塞情况如超时了（比连续三个重复ACK更加阻塞），TCP就会直接进入慢启动状态（cwind=1）重复之前的过程。

注意：上述所涉及到的是Reno拥塞控制算法，此外还有Cubic是 Linux 内核 2.6 之后的默认 TCP 拥塞控制算法，

还有BBR算法是谷歌在 2016 年提出的一种新的拥塞控制算法，目前 BBR 已经集成到 Linux 4.9 以上版本的内核中。不同算法各自都有不同的使用场景。具体问题还需具体分析。

参考：拥塞控制

qucikSort复杂度分析：

最简单的快排的话，加入每次选择数组第一个数作为基准进行 partition分区：

那么：最好情况就是，每次分区都可以将数组分对半分，例如quickSort(arr,0,n),

  1. 第一次快排之后就是quickSort（arr,0,n/2）+ quickSort(arr,n/2+1,n),复杂度为O（N）
  2. 第二次快排之后就是quickSort（arr,0,n/2/2）+quickSort(arr,n/2/2+1,n/2) + quickSort(arr,n/2+1,3n/4)+quickSort(3n/4+1,n);复杂度O(N).
  3. 依次减半知道 l == r，return 。此时递归树共计log（N）高度，一次每次都是对半分。
  4. 整体复杂度为O（N*long（N））

最坏情况下：就是每次都不能对半分，比如说数组是一个递减的顺序，那么递归树高度就是N，整体时间复杂度O（N*N）。

随即快排的话就是每次选择的基准pivot位置随机的分布在[l,r]之间那么其平均的时间复杂度为：

image-20200908094344947

参考算法导论的计算方法，最后得到平均复杂度为O（N*Log（N)）

参考

TOPK

  1. 直接排序，复杂度O( N * log（N))，缺点所有都排序了，然而只需求第K大的数

  2. 既然求topK，我们可以遍历K次每次选择一个最大的值，复杂度O(N*k)，缺点：topK的K个数也被排序了

    实际上只需要求第K大呀！

  3. 堆排，维护一个大小为K的小根堆，遍历一次数组，只要大于小根堆堆顶则加入堆中。topK的K个数也不要排序，时间复杂度O(N * log(K) ).

  4. 随即选择法（利用快排的思想），算法步骤大概如下：

    1. 第一次快排分区之后，找到分区点p，则p左边的数小于p位置的数，p右边的数大于p位置，若p正好是第k大的位置，则直接返回；若p小于第K大的位置，则说明第K大的数在p的右半部分，这是问题转化为求p右半部分数组中第K - （左半部分个数）大的问题；若p的位置大于第K大的位置，则说明第K大在p左半部分数组中，问题转化为求p左半部分数组中第K - （p右半部分数组大小）的topK问题。
    2. 递归上述过程即可。
    3. 整体时间复杂度近似是O( N ), 对于海量数据还有一种BFPRT的优化算法。整体的时间复杂度是线性的。

上述第4个随机选择法：（快排版本TOPK(第k个大的数)，代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int topK(int[] arr, int l, int r, int k) {
       if (l >= r) return l;
       int p = partition(arr, l, r);// [l,p)区间小于pivot, (p,r]区间大于等于pivot
       if (r - k + 1 == p) return p;
       else if (r - k + 1 < p) return topK(arr, l, p - 1, k - r + p - 1);
       else return topK(arr, p + 1, r, k);
   }
   public static int partition(int[] arr, int l, int r) {
       int pivot = arr[l]; //pivot可以随机选择，这是直接默认
       int i = l;
       while (l < r) {
           while (l < r && arr[r] >= pivot) r--;
           while (l < r && arr[l] <= pivot) l++;
           int tmp = arr[l];
           arr[l] = arr[r];
           arr[r] = tmp;
       }
       arr[i] = arr[l];
       arr[l] = pivot;
       return l;
   }

BFPRT：

  1. BFPRT算法

    该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出,时间复杂度最坏为O（N）

    BFPRT算法步骤如下：

    1. 选取基准元素；

      1. 将n个元素每5个一组，分成n/5(上界)组，最后的一个组的元素个数为n%5，有效的组数为n/5。
      2. 取出每一组的中位数，最后一个组的不用计算中位数，任意排序方法，这里的数据比较少只有5个，可以用简单的冒泡排序或是插入排序。
      3. 对于第1.2中找到的所有中位数，调用BFPRT算法求出它们的中位数，作为基准元素，设为x，偶数个中位数的情况下设定为选取中间小的一个。

    2. 以1.3中选取的基准元素作为分割点，将小于基准元素的放在左边，个数为k个，大于或等于基准元素的放在右边，个数为n-k。

    3. 判断基准元素位置i与k的大小

      1. 如果i==k，返回x;
      2. 如果i<k，在小于x的元素中递归查找第i小的元素；
      3. 如果i>k，在大于等于x的元素中递归查找第i-k小的元素。

    因为每个基准元素都会选择中位数，所以快排每次会对半分区间，所以时间复杂度是最好的。

代码:来源网络

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
>public class BFPRT {
   public static void main(String[] args) {
       int[] arr = {6, 9, 1, 3, 1, 2, 2, 5, 6, 1, 3, 5, 9, 7, 2, 5, 6, 1, 9};
       // sorted : { 1, 1, 1, 1, 2, 2, 2, 3, 3, 5, 5, 5, 6, 6, 6, 7, 9, 9, 9 }
       printArray(getMinKNumsByHeap(arr, 10));//通过堆排方式得到Top-K元素
       printArray(getMinKNumsByQuick(arr, 10));//通过快排方式得到Top-K元素
       printArray(getMinKNumsByBFPRT(arr, 10));//通过BFPRT算法得到Top-K元素
   }

   /**
    * 堆排解法，时间复杂度为O(N*logK)
    *
    * @param arr
    * @param i
    * @return
    */
   private static int[] getMinKNumsByHeap(int[] arr, int k) {
       if (k < 1 || k > arr.length) {
           return arr;
       }
       int[] kHeap = new int[k];
       for (int i = 0; i != k; i++) {
           heapInsert(kHeap, arr[i], i);
       }
       for (int i = k; i != arr.length; i++) {
           if (arr[i] < kHeap[0]) {
               kHeap[0] = arr[i];
               heapify(kHeap, 0, k);
           }
       }
       return kHeap;
   }

   private static void heapInsert(int[] arr, int value, int index) {
       arr[index] = value;
       while (index != 0) {
           int parent = (index - 1) / 2;
           if (arr[parent] < arr[index]) {
               swap(arr, parent, index);
               index = parent;
           } else {
               break;
           }
       }
   }

   private static void heapify(int[] arr, int index, int heapSize) {
       int left = index * 2 + 1;
       int right = index * 2 + 2;
       int largest = index;
       while (left < heapSize) {
           if (arr[left] > arr[index]) {
               largest = left;
           }
           if (right < heapSize && arr[right] > arr[largest]) {
               largest = right;
           }
           if (largest != index) {
               swap(arr, largest, index);
           } else {
               break;
           }
           index = largest;
           left = index * 2 + 1;
           right = index * 2 + 2;
       }
   }

   /**
    * 通过快排的方式，时间复杂度为O(N)
    *
    * @param arr
    * @param k
    * @return
    */
   private static int[] getMinKNumsByQuick(int[] arr, int k) {
       if (arr != null && arr.length > 0) {
           int low = 0;
           int high = arr.length - 1;
           int index = partition(arr, low, high);
           //不断调整分治思想，直到position=k-1
           while (index != k - 1) {
               //大了，往前调整
               if (index > k - 1) {
                   high = index - 1;
                   index = partition(arr, low, high);
               }
               //小了，往后调整
               if (index < k - 1) {
                   low = index + 1;
                   index = partition(arr, low, high);
               }
           }
       }
       int[] res = new int[k];
       for (int i = 0; i < res.length; i++) {
           res[i] = arr[i];
       }
       return res;
   }

   private static int partition(int[] arr, int low, int high) {
       if (arr != null && low < high) {
           int flag = arr[low];
           while (low < high) {
               while (low < high && arr[high] >= flag) {
                   high--;
               }
               arr[low] = arr[high];
               while (low < high && arr[low] <= flag) {
                   low++;
               }
               arr[high] = arr[low];
           }
           arr[low] = flag;
           return low;
       }
       return 0;
   }

   /**
    * 通过BRPRT算法获得Top-K问题的解，时间复杂度为O(N)
    *
    * @param arr
    * @param k
    */
   private static int[] getMinKNumsByBFPRT(int[] arr, int k) {
       if (k < 1 || k > arr.length) {
           return arr;
       }
       int minKth = getMinKthByBFPRT(arr, k);
       int[] res = new int[k];
       int index = 0;
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] < minKth) {
               res[index++] = arr[i];
           }
       }
       for (; index < res.length; index++) {
           res[index] = minKth;
       }
       return res;
   }

   private static int getMinKthByBFPRT(int[] arr, int k) {
       int[] copyArr = copyArray(arr);
       return select(copyArr, 0, copyArr.length - 1, k - 1);
   }

   private static int[] copyArray(int[] arr) {
       int[] res = new int[arr.length];
       for (int i = 0; i < res.length; i++) {
           res[i] = arr[i];
       }
       return res;
   }

   private static int select(int[] arr, int begin, int end, int i) {
       if (begin == end) {
           return arr[begin];
       }
       int pivot = medianOfMedians(arr, begin, end);
       int[] pivotRange = partition(arr, begin, end, pivot);
       if (i >= pivotRange[0] && i <= pivotRange[1]) {
           return arr[i];
       } else if (i < pivotRange[0]) {
           return select(arr, begin, pivotRange[0] - 1, i);
       } else {
           return select(arr, pivotRange[1] + 1, end, i);
       }
   }

   private static int medianOfMedians(int[] arr, int begin, int end) {
       int num = end - begin + 1;
       int offset = num % 5 == 0 ? 0 : 1;
       int[] mArr = new int[num / 5 + offset];
       for (int i = 0; i < mArr.length; i++) {
           int beginI = begin + i * 5;
           int endI = beginI + 4;
           mArr[i] = getMedian(arr, beginI, Math.min(end, endI));
       }
       return select(mArr, 0, mArr.length - 1, mArr.length / 2);
   }

   private static int[] partition(int[] arr, int begin, int end, int pivotValue) {
       int small = begin - 1;
       int cur = begin;
       int big = end + 1;
       while (cur != big) {
           if (arr[cur] < pivotValue) {
               swap(arr, ++small, cur++);
           } else if (arr[cur] > pivotValue) {
               swap(arr, cur, --big);
           } else {
               cur++;
           }
       }
       int[] range = new int[2];
       range[0] = small + 1;
       range[1] = big - 1;
       return range;
   }

   private static int getMedian(int[] arr, int begin, int end) {
       insertionSort(arr, begin, end);
       int sum = end + begin;
       int mid = (sum / 2) + (sum % 2);
       return arr[mid];
   }

   private static void insertionSort(int[] arr, int begin, int end) {
       for (int i = begin + 1; i != end + 1; i++) {
           for (int j = i; j != begin; j--) {
               if (arr[j - 1] > arr[j]) {
                   swap(arr, j - 1, j);
               } else {
                   break;
               }
           }
       }
   }

   /**
    * 公共方法，交换数据和打印数据
    * @param arr
    * @param i
    * @param j
    */
   private static void swap(int[] arr, int i, int j) {
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
   }

   private static void printArray(int[] arr) {
       for (int i = 0; i < arr.length; i++) {
           System.out.print(arr[i] + " ");
       }
       System.out.println();
   }
>}

两个一亿个数的集合，求交集：

bitmap（提前是整数都是int类型） ，如果换成long呢我那一瞬间没想出来，后面结束了才想到可以用hash分桶的方法，也就是分治。。紧张了:laughing:,

社交网络中两个用户之间的最短距离（无向图、路径权重为1）

双向BFS。。写代码 面试官说代码可以简化。


 上一页

 评论


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 ， 总访问量为 次 。
载入天数...载入时分秒...