2020-03-25 一面
自我介绍
面试题：
1、二分查找树里查询一个关键字的最坏时间复杂度是______。A、O(n) B、O(n log n) C、O(n^2) D、O(n^3) E、O(logn) F、不确定2、以下函数的时间复杂度是 （ ）void func(int x,int y, int z){if(x<=0)printf("%d, %d\n", y, z);else {func(x-1,y+1,z);func(x-1,y,z+1);}}A.O(x*y*z)B.O(x^2*y^2)C.O(2^x)D.O(2^x*2^y*2^z)E.O(x!)F.O((x*y*z)!)3. 一个栈的入栈序列为ABCDEF，则不可能的出栈序列是（ ）A、DEFCBA B、DCEFBA C、FEDCBAD、FECDBA E、ABCDEF F、ADCBFE4、用0,1,2,3,4,5组成一个4位数，要求每一位都不一样，请问能组成多少个四位数（ ）A.240B.280C.300D.360E.400F.4505、如果一个博物馆参观者到达的速率是每分钟 20 人，平均每个人在馆内停留20分钟，那么该博物馆至少需要容纳______人才行？A、100 B、200 C、300 D、400 E、500 F、600
算法题：
1. 股票的最大利润（剑指offer上的经典题目）
2. 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
思路：归并排序
public class Main {
public static void main(String[] args) {
}
public ListNode sortList(ListNode head) {
if(head != null || head.next != null) return head;
ListNode fast = head.next;
ListNode slow = head;
// 找到中点进行分割
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 归并排序
ListNode temp = slow.next;
ListNode left = sortList(head);
ListNode right = sortList(temp);
ListNode res = new ListNode(1);
while(left != null && right != null) {
if(left.val > right.val) {
res.next = right;
right = right.next;
}
else {
res.next = left;
left = left.next;
}
res = res.next;
}
if(left != null) res.next = left;
else res.next = right;
return res;
}
}
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
思路：
使用辅助栈的方式，用一个栈来保存当前的最小值，每次弹出栈，辅助栈也同步进行弹出，正常的栈结构不受影响，压入辅助栈时判断当前元素是否比最小值还小，若比最小值还小则更新最小值并压入，否则讲最小值压入辅助栈。
项目相关问题
集合的底层实现，源码
ArrayList：扩容
HashMap
状态码含义：
直接说了2xx 3xx 4xx 5xx 分别对应的情况
2020-03-27 二面
两队列模拟堆栈：
两堆栈模拟队列：
我的想法：假设有两个栈AB，每次压入栈A，每次弹出
全部评论
(2) 回帖