字节跳动教育部，许愿

一面(趁热，4点45刚刚面完)

没有自我介绍，简单问了一下

开始面试，十个问题

1. 单链表判断是否有环，要最优解

没想，快慢指针，快指针一次走两步，慢指针一次走一步，有环必定相遇

2. 两字符串，在长串中匹配短串

知道有一个KMP算法，但是没有深入研究过

只能说我自己的想法了，暴力解，遍历，问了时间复杂度

3. 知道一个二叉树的中序遍历和前序遍历。

前序遍历：根左右

中序遍历：左根右

根据这两个特征，第一步可以确定根节点，让后将中序遍历分成了两部分

跟着这个思路继续向下找

4. 连通图最小生成树

不会，直说了

5. 最长上升子序列，动态规划经典题。

两个循环，时间复杂度O(n**2)

def lengthOfLIS(self,nums):
        n = len(nums)
        if n == 0:
            return 0
       	dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i],dp[j]+ 1)
        return max(dp)

6. 有一个栈，三个操作，push，pop，getMax，要求时间复杂度为(O(1)).

pop和push都是正常操作。

getMax才是问题的关键所在。要求时间复杂度为O(1)。采用空间换时间

新建一个私有Stack，每次push和pop操作和原栈相同，区别在于每次push

的时候和栈顶元素比较大小，大了才push进去，保证栈顶元素一直是最大的。

7. 进程间通信方式

8.线程池

9.面向对象三特征，重要介绍多态

10.MVC介绍一下

11.MySQL中drop,delete,truncate区别，啥时候用

12.代码题：大数求和 (20分钟) leetcode415

写了这么点，讲了下思想

循环里面还把alist写成了mxlen

n1 = len(lis1)
n2 = len(lis2)
mxlen = n1 if n1 > n2 else n2
tmp = 0
alist = [0] * mxlen 
for i in range(mxlen-1, -1, -1):
    if (lis1[i] + lis2[i] + tmp) > 10:
        mxlen[i] = (lis1[i] + lis2[i] + tmp) % 10
        tmp = (lis1[i] + lis2[i] + tmp) // 10
    else:
        mxlen[i] = lis1[i] + lis2[i] + tmp

总结下

基本算法的一两个不会，其他的都能说出一二来，78910记的东西，想到啥说啥，也不是特别熟悉。。。

面的问题我都小本本记下来了。

这感觉。。。有点迷，不知道什么结果

最后问我有没有啥问题，扯了一点后台啊，数据库啊，语言啊之类的东西问了下加班，

加班的问题是单双周好像，不过周末加班双倍工资。

我最后问了个问题：这才一面，问这个问题是不是有点早了(主要是我也没抱什么希望，三月初面了一次字节，问的都是靠脑子记的东西，答得也不好)

约的时间一个小时，最后差不多45分钟结束。

#字节跳动教育一面##字节跳动##校招##Java工程师##面经#