首页 > 20春腾讯视频一、二、三面(已挂)
头像
offer_plusplus
编辑于 2021-03-27 00:05
+ 关注

20春腾讯视频一、二、三面(已挂)

2020-03-25 一面

自我介绍
面试题:
1、二分查找树里查询一个关键字的最坏时间复杂度是______
AO(n)        BO(n log n)        CO(n^2)        DO(n^3)        EO(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,则不可能的出栈序列是(
ADEFCBA BDCEFBA CFEDCBA
DFECDBA EABCDEF FADCBFE
4、用0,1,2,3,4,5组成一个4位数,要求每一位都不一样,请问能组成多少个四位数(
A.240
B.280
C.300
D.360
E.400
F.450
5、如果一个博物馆参观者到达的速率是每分钟 20 人,平均每个人在馆内停留20分钟,那么该博物馆至少需要容纳______人才行?
A100        B200        C300        D400        E500        F600
算法题:
1. 股票的最大利润(剑指offer上的经典题目)

2. 在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
示例 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;
    }
}

3. leetcode最小栈
设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。

思路:
使用辅助栈的方式,用一个栈来保存当前的最小值,每次弹出栈,辅助栈也同步进行弹出,正常的栈结构不受影响,压入辅助栈时判断当前元素是否比最小值还小,若比最小值还小则更新最小值并压入,否则讲最小值压入辅助栈。

项目相关问题

集合的底层实现,源码
ArrayList:扩容
HashMap

状态码含义:
直接说了2xx 3xx 4xx 5xx 分别对应的情况

2020-03-27 二面

两队列模拟堆栈:


两堆栈模拟队列:
我的想法:假设有两个栈AB,每次压入栈A,每次弹出

更多模拟面试

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐