想请教一下面试如果遇到一些偏高级的数据结构的题，面试官究竟想听到怎样的回答

想请教一下各位，如果面试的时候被问到的题目只有用到某些高级点（或者说不是很常用）的数据结构才能是最优解的题目，面试官究竟想听到怎样的回答呢？

比如729 My calendar 这题，如果insert最优的话应该是维护一个sorted container，这时候作为面试者可以自由使用语言自带的sorted container (python的SortedList, Java的TreeSet，C++的multiset之类的）吗？还是说面试官想让我们自己实现一下呢？对于普通的BST还不是很复杂，但是会退化到O(N)的复杂度，不是完美。AVL Tree 红黑树之类的我等凡人肯定是现场写不出来的，但是如果提一下的话是加分项还是给自己挖坑呢？

还有比如307 range sum之类的用segment tree虽然代码量大一点，但是还是比较好理解。如果用BI Tree的话那个模板基本很难靠理解写出来。同样的如果被问到BIT，要用什么策略来回答呢？感谢大家！

我觉得multiset okay.一般面试不会考线段树。除非是pony这种。一般会考线段树，那肯定都会考最大流和数学几何问题。所以某种意义上不会出。因为基础线段树太简单，复杂的话要再线段树做dp或延迟。没有模板不太可能30分钟写完。

lifesuckad 发表于 2021-4-15 09:15
我觉得multiset okay.一般面试不会考线段树。除非是pony这种。一般会考线段树，那肯定都会考最大流和数学几 ...

c++我其实不太熟，不知道multiset是不是在stl里面的😂  Python的话都没有native的sorted container，需要自己手动装，但是我看蠡口上可以直接用，所以比较纠结

2Hurric 发表于 2021-4-16 08:57
c++我其实不太熟，不知道multiset是不是在stl里面的😂  Python的话都没有native的sorted containe ...

我个人建议 。你得会两门语言。 python 在处理一些题得时候不太方便。 没有现成得STL. 另外BIT 也可以准备。 不过一般 BIT 得题也可以用merge sort 去算逆序数。 我觉得你可以掌握merge sort 得那套。

lifesuckad 发表于 2021-4-16 10:49
我个人建议 。你得会两门语言。 python 在处理一些题得时候不太方便。 没有现成得STL. 另外BIT 也可以准 ...

嗯嗯 感谢分享哈