Algorithm

2018 微软预科生面试

4月2日参加在线笔试,4月13日收到了面试邀请,也是非常开心。 面试时间:4月26日 面试地点:中关村微软大厦 插曲:4月26日因为高铁班次原因,HR小姐姐非常好心地帮我把面试时间调整到了下午并让我注意安全别急着赶路,真是大厂风范,非常感激了。 面试流程 准备 等待面试的同学都被安排在一间大屋子里休息,提供饮料、盒饭,还能享受在微软大厦中俯瞰中关村的风光 :) 认识了几个来自天南地北的小伙伴 下午一点开始面试

Algorithm

倍增 二分

Description 倍增二分,就是先倍增再二分:先逐渐扩大区间来确定一个含有答案的小区间,再在这个小区间里二分确定答案。常用于大数据范围的二分,或者需要二分次数很多的问题,可以用倍增来进行优化。 Problem A source: HDU 6109 tips: 此题需要确定每一个不合法的约束条件的位置,如果每次二分整个区间,时间复杂度可能就很大了。所以我们可以先采用倍增的方法确定一个含有不合法条件的小区间,再二分查找它,这样时间上能优化很多。 Solution