ms别人面经总结
剑指offer一定要过一遍
几种排序算法
冒泡排序
O(N^2),稳定、原地排序。
class Solution {
public int[] bubblingSort( int[] nums) {
int n = nums.length;
for(int i=0;i<n;i++) {
for(int j=0;j<n-i-1;j++) {
if(nums[j]>nums[j+1]) {
swap(nums,j,j+1);
}
}
}
return nums;
}
private void swap(int[] nums,int i,int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
选择排序
O(N^2),非稳定、原地排序。
举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。
找最小,然后放到前排。
class Solution {
public int[] sort( int[] nums) {
int n = nums.length;
for(int i=0;i<n;i++) {
int maxPos = i;
for(int j=i+1;j<n;j++) {
if(nums[j]<nums[maxPos]) {
maxPos = j;
}
}
swap(nums,i,maxPos);
}
return nums;
}
private void swap(int[] nums,int i,int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
插入排序
O(N^2),稳定、原地排序。
class Solution {
public int[] sort( int[] nums) {
int n = nums.length;
if(n<2) return nums;
for(int i=1;i<n;i++) {
for(int j=i;j>0;j--) {
if(nums[j]<nums[j-1]) {
swap(nums,j,j-1);
}
}
}
return nums;
}
private void swap(int[] nums,int i,int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
快速排序
平均O(NlogN),不稳定(前面找小的,后面找大的,不稳定)、原地排序。
class Solution {
Random random = new Random();
public int[] quicklysort( int[] nums) {
quicklysortHelper(nums,0,nums.length-1);
return nums;
}
private void quicklysortHelper(int[] nums,int start,int end) {
if(start>=end) return;
swap(nums,start,random.nextInt(end-start)+start);
int lp = start;
int rp = end;
int pivot = nums[start];
while(lp<rp) {
while(lp<rp&&nums[rp]>=pivot) rp--;
nums[lp] = nums[rp];
while(lp<rp&&nums[lp]<=pivot) lp++;
nums[rp] = nums[lp];
}
nums[rp] = pivot;
quicklysortHelper(nums,start,rp-1);
quicklysortHelper(nums,rp+1,end);
}
private void swap(int[] nums,int i,int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
归并排序
class Solution {
public int[] mergeSort( int[] nums) {
return mergeSortHelper(nums);
}
private int[] mergeSortHelper(int[] nums) {
int n = nums.length;
if(n<2) return nums;
int[] left = mergeSortHelper(Arrays.copyOfRange(nums,0,n/2));
int[] right = mergeSortHelper(Arrays.copyOfRange(nums,n/2,n));
int[] result = new int[n];
int lp = 0;
int rp = 0;
int idx = 0;
while(lp<left.length&&rp<right.length) {
if(left[lp]>right[rp]) result[idx++]=right[rp++];
else result[idx++] = left[lp++];
}
while(lp<left.length) {
result[idx++]=left[lp++];
}
while(rp<right.length) {
result[idx++]=right[rp++];
}
return result;
}
}
堆排序
思想:构造成一个大顶堆,然后对顶和最后一个元素交换,末尾为最大值,然后对剩余的n-1个元素重复。
lintcode 1179朋友圈
public class Solution {
/**
* @param M: a matrix
* @return: the total number of friend circles among all the students
*/
public int findCircleNum(int[][] M) {
int n = M.length;
boolean[] visited = new boolean[n];
int result = 0;
for(int i=0;i<n;i++) {
result += dfs(M,visited,i);
}
return result;
}
private int dfs(int[][] M,boolean[] visited,int student) {
if(visited[student]) return 0;
visited[student] = true;
for(int j=0;j<M.length;j++) {
if(M[student][j]==1) dfs(M, visited, j);
}
return 1;
}
}
并查集
public class Solution {
/**
* @param M: a matrix
* @return: the total number of friend circles among all the students
*/
public int findCircleNum(int[][] M) {
int n = M.length;
int result = 0;
int[] father = new int[n];
for(int i=0;i<n;i++) {
father[i] = i;
}
for(int student=0;student<n;student++) {System.out.println(Arrays.toString(father));
for(int friend=student+1;friend<n;friend++) {
//System.out.println(friend);
if(M[student][friend]==0) continue;
join(father, student, friend);
}
}
Set<Integer> set = new HashSet<>();
for(int student=0;student<n;student++) {
set.add(findFather(father, student));
}
return set.size();
}
private int findFather(int[] father,int n) {
int boss = n;
while(father[boss]!=boss) {
boss=father[boss];
}
int ret = boss;
boss = n;
while(father[boss]!=boss) {
boss=father[boss];
father[boss] = ret;
}
return ret;
}
private int join(int[] father,int a,int b) {
int fa = findFather(father, a);
int fb = findFather(father, b);
if(fa != fb) {
father[fa] = fb;
}
return 0;
}
}
数组中位数
剑指 Offer 41. 数据流中的中位数
class MedianFinder {
// maxHeap可能会比minHeap size大1
PriorityQueue<Integer> maxHeap;
PriorityQueue<Integer> minHeap;
/** initialize your data structure here. */
public MedianFinder() {
maxHeap = new PriorityQueue<>((o1,o2)->o2-o1);
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
if(minHeap.size()==maxHeap.size()-1) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
} else {
minHeap.offer(num);
maxHeap.offer(minHeap.poll());
}
//System.out.println(minHeap);
//System.out.println(maxHeap);
}
public double findMedian() {
if(minHeap.size()==maxHeap.size()) {
return (minHeap.peek()+maxHeap.peek())/2.0;
}
return maxHeap.peek();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
设计游戏排行榜
设计一个数据结构获取一个有上亿用户的游戏中玩家分数排名前一万的用户信息,以及获取排名一万以后任意用户的排名区间,不能借助类似redis的中间件,假设数据结构就在内存中。
排行榜,首先可以想到redis的zset结构,也就是有序集合,可以按照集合中元素的打分来进行排序。
如果数据量小的话,直接一个集合就可以。数据量大的话,可以分桶(按分数分)如0-10一个,10-30一个类似。。
前面的排名直接全部显示,一万以后的用户可以根据分数查桶,大概知道在哪个桶里。
断点续传设计
秒传:
上传文件后,将文件的MD5发给各个服务器,服务器根据传输过来的MD5判断服务器是否存在相同的文件,存在就将文件复制一份(需要复制吗?),而不是本地上传,达到秒传。
断点续传:
总体上是将文件分成一个个小部分,在上传中断情况下,已经上传过的一个个小部分就不用上传了,接着上传其他的。
具体:以http1.1协议为例,它header里面有content-range参数,可以指定第一个字节和最后一个字节位置。例如:
Content-Range:bytes 2048-4096/10240
这里边 2048-4096 表示当前发送的数据范围, 10240 表示文件总大小。
采用断点续传方式时http响应头会变成:HTTP/1.1 206Partial Content
。
为避免服务端文件改动,可以用last modified来标识最后的修改时间。
dijkstra、floyd
leetcode 743网络问题
dj解法:一点A找所有点距离A的最短路径,用最小堆做,确定最短的点B,再往外扩展,找B的出度,期间要判断是否是已经确定过最短路的点。
class Solution {
class Node {
public int outNode;
public int pathValue;
public Node(int o,int p) {
outNode = o;
pathValue = p;
}
}
public int networkDelayTime(int[][] times, int n, int k) {
//dijkstra问题,一点到所有点的最短路径
// 明确有最短路的结点
Map<Integer,Integer> visited = new HashMap<>();
visited.put(k,0);
// 存放当前能够到的路径
PriorityQueue<Node> minHeap = new PriorityQueue<>((n1,n2)->n1.pathValue-n2.pathValue);
// 出度邻居表
List<List<Node>> list = new ArrayList<>();
for(int i=0;i<=n;i++) {
list.add(new ArrayList<>());
}
for(int[] t:times) {
list.get(t[0]).add(new Node(t[1],t[2]));
}
for(Node node:list.get(k)) {
minHeap.offer(node);
}
Node minPathNode;
while(minHeap.size()!=0) {
minPathNode = minHeap.poll();
if(visited.containsKey(minPathNode.outNode)) {
continue;
}
visited.put(minPathNode.outNode,minPathNode.pathValue);
for(Node node:list.get(minPathNode.outNode)) {
if(visited.containsKey(node.outNode)) {
continue;
}
minHeap.offer(new Node(node.outNode,node.pathValue+minPathNode.pathValue));
}
}
//System.out.println(visited);
if(visited.size()!=n) return -1;
int max = 0;
for(int key:visited.keySet()) {
max = Math.max(max,visited.get(key));
}
return max;
}
}
floyd算法:
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
int[][] floyd = new int[n+1][n+1];
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
floyd[i][j] = -1;
if(i==j) floyd[i][j]=0;
}
}
for(int[] time:times) {
floyd[time[0]][time[1]] = time[2];
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int v=1;v<=n;v++) {
if(floyd[j][i]!=-1&&floyd[i][v]!=-1) {
if(floyd[j][v]>floyd[j][i]+floyd[i][v]||
floyd[j][v]==-1) {
floyd[j][v]=floyd[j][i]+floyd[i][v];
}
}
}
}
}
int max = -1;
//System.out.println(Arrays.toString(floyd[k]));
for(int i=1;i<=n;i++) {
if(floyd[k][i]==-1) return -1;
max = Math.max(max,floyd[k][i]);
}
return max;
}
}
floyd带路径
public static void floyd(int[][] graph) {
//初始化距离矩阵 distance
distance = graph;
//初始化路径
//i->j至少上一个路径可以是自己j
path = new int[graph.length][graph.length];
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph[i].length; j++) {
path[i][j] = j;
}
}
//开始 Floyd 算法
//每个点为中转
for (int i = 0; i < graph.length; i++) {
//所有入度
for (int j = 0; j < graph.length; j++) {
//所有出度
for (int k = 0; k < graph[j].length; k++) {
//以每个点为「中转」,刷新所有出度和入度之间的距离
//例如 AB + BC < AC 就刷新距离
if (graph[j][i] != -1 && graph[i][k] != -1) {
int newDistance = graph[j][i] + graph[i][k];
if (newDistance < graph[j][k] || graph[j][k] == -1) {
//刷新距离
graph[j][k] = newDistance;
//刷新路径
path[j][k] = i;
}
}
}
}
}
}
LRU
刚开始没封装成函数,就有错误,封装成函数(move2tail, deleteNode)就没报错了,没找到原因。
class LRUCache {
class Node {
public int value;
public int key;
public Node before;
public Node next;
public Node(int k,int v,Node b,Node n) {
key = k;
value = v;
before = b;
next = n;
}
}
int capacity;
Map<Integer,Node> map;
Node head;
Node tail;
public LRUCache(int capacity) {
map = new HashMap<>();
this.capacity = capacity;
head = new Node(0,0,null,null);
tail = new Node(0,0,null,null);
head.next = tail;
tail.before = head;
}
private void move2Tail(Node cur) {
tail.before.next = cur;
cur.before =tail.before;
cur.next = tail;
tail.before = cur;
}
private void deleteNode(Node cur) {
cur.before.next = cur.next;
cur.next.before = cur.before;
}
public int get(int key) {
if(!map.containsKey(key)) return -1;
Node cur = map.get(key);
// [] - [i] - [] ... []
deleteNode(cur);
move2Tail(cur);
return cur.value;
}
public void put(int key, int value) {
if(map.containsKey(key)) {
Node cur = map.get(key);
cur.value = value;
deleteNode(cur);
move2Tail(cur);
//map.put(key,cur);
return;
}
Node cur = new Node(key,value,null,null);
move2Tail(cur);
map.put(key,cur);
if(map.size()>capacity) {
map.remove(head.next.key);
deleteNode(head.next);
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
设计模式
对云服务了解哪些,是否使用过相关技术
就说用过云服务器,CDN来部署静态博客。
CDN:利用加速结点,将业务内容发布到最接近用户的边缘结点,使得用户请求能够得到快速响应,无需多次网络转发。
传统访问过程:输入url,dns解析出ip地址,浏览器得到ip,对服务器发出访问请求,目标服务器响应,回传数据,浏览器显示。
A记录:域名解析到ip地址
CNAME记录:域名解析到另一个域名。
cdn服务之所以要用cname,最主要的原因是要根据用户所在位置选择并返回最优节点 IP。如果不用cname,A记录只能实现域名解析到ip,因此就无法实现cdn的加速效果。
手写动态代理
interface Man {
public void find();
}
class LHQ implements Man {
@Override
public void find() {
System.out.println("i will find you");
}
}
class ManHandler implements InvocationHandler {
private Man man;
public ManHandler(Man man) {
this.man = man;
}
@Override
public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
System.out.println("before");
method.invoke(man,null);
System.out.println("after");
return man;
}
}
public class Solution {
public static void main(String[] args) {
Man man = new LHQ();
Man proxy = (Man) Proxy.newProxyInstance(man.getClass().getClassLoader(), new Class[]{Man.class},new ManHandler(man));
proxy.find();
}
}
//output
//before
//i will find you
//after
继续。
海量数据处理
设计两个电梯
思维发散程度。
CMD算法题
把一位数转成26位进制,每一位用英文字母表示:例如 1(A)27(AA)
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
StringBuilder sb = new StringBuilder();
while(n!=0) {
int cur = n%26;
n/=26;
sb.append((char)(cur==0?'0':cur-1+'A'));
}
System.out.println(sb.reverse().toString());
}
}
接雨水
有序二维数组找到目标数字的出现次数。时间与空间复杂度。
链表相交节点
判断一个整数是否能表示成几个不同的3的幂之和(LeetCode1780)
删除并获得点数(LeetCode740)
计算两个日期之间的天数,测试用例
删除sorted array里的重复元素,要求空间复杂度是O(1) (LeetCode80,题目描述是英文的)
课程表 II
局部反转链表
判断环形链表
重建二叉树