微软苏州STCA二面凉经

一面是个外国人……上来自我介绍，然后手撕两道题。

二面虽然是个中国人，但是自我介绍也要英文的，之后全程中文，手撕两道题。

一面题目

1.有n个用户，每个用户都会上线一段时间，比如时间a上线，时间b下线，问同一时刻在线的人数最多的有几个？

例，有五个用户

用户 上线时间 下线时间

A 9:30 11:30

B 9:00 12:00

C 10:00 12:30

D 13:30 14:30

E 13:00 14:00

在10:00-11:30期间有3个用户在线，其他时间段都没有超过3个的，所以返回3

2.有一个部分排序数组，若将从下标i到下标j的子数组进行排序，整个数组就会变成一个排好序的，求下标i和j

例 arr[] = {1, 2, 4, 7, 6, 5, 3, 11, 10, 13, 15} 那么应该把从4到10之间的子数组排序，整个数组就是排序的，返回{2, 8}

二面题目

1.判断一颗二叉树是不是平衡二叉树

2.(1)若有一个数组有100w个数，0＜=i＜j＜len，求从下标i到下标j的子数组的和。

(2)若更改了ij之间下标k的数，arr[k]=num，接着求子数组的和，要求时间复杂度空间复杂的O(logn)