755. Pour Water

755. Pour Water

Medium

We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After Vunits of water fall at index K, how much water is at each index?

Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:

If the droplet would eventually fall by moving left, then move left.

Otherwise, if the droplet would eventually fall by moving right, then move right.

Otherwise, rise at it's current position.

Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in that direction. Also, "level" means the height of the terrain plus any water in that column.

We can assume there's infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block - each unit of water has to be in exactly one block.

Example 1:

Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3
Output: [2,2,2,3,2,2,2]
Explanation:
#       #
#       #
##  # ###
#########
 0123456    <- index

The first drop of water lands at index K = 3:

#       #
#   w   #
##  # ###
#########
 0123456    

When moving left or right, the water can only move to the same level or a lower level.
(By level, we mean the total height of the terrain plus any water in that column.)
Since moving left will eventually make it fall, it moves left.
(A droplet "made to fall" means go to a lower height than it was at previously.)

#       #
#       #
## w# ###
#########
 0123456    

Since moving left will not make it fall, it stays in place.  The next droplet falls:

#       #
#   w   #
## w# ###
#########
 0123456  

Since the new droplet moving left will eventually make it fall, it moves left.
Notice that the droplet still preferred to move left,
even though it could move right (and moving right makes it fall quicker.)

#       #
#  w    #
## w# ###
#########
 0123456  

#       #
#       #
##ww# ###
#########
 0123456  

After those steps, the third droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would eventually make it fall, it moves right.

#       #
#   w   #
##ww# ###
#########
 0123456  

#       #
#       #
##ww#w###
#########
 0123456  

Finally, the fourth droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would not eventually make it fall, it stays in place:

#       #
#   w   #
##ww#w###
#########
 0123456  

The final answer is [2,2,2,3,2,2,2]:

    #    
 ####### 
 ####### 
 0123456 

Example 2:

Input: heights = [1,2,3,4], V = 2, K = 2
Output: [2,3,3,4]
Explanation:
The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.

Example 3:

Input: heights = [3,1,3], V = 5, K = 1
Output: [4,4,4]

Note:

1. heights will have length in [1, 100] and contain integers in [0, 99].
2. V will be in range [0, 2000].
3. K will be in range [0, heights.length - 1].

---------------------
暴解
O(m * n), heights的长度 ＊ 水滴个个数

class Solution {
    public int[] pourWater(int[] heights, int water, int pos) {
        
        while (water > 0) {
            water--;
            int left = pos;
            
            while (left > 0 && heights[left - 1] <= heights[left]) {
                left--;
            }
            
            if (heights[left] < heights[pos]) {
                heights[left]++;
                continue;
            }
            
            int right = pos;
            while (right < heights.length - 1 && heights[right + 1] <= heights[right]) {
                right++;
            }
            
            if (heights[right] < heights[pos]) {
                heights[right]++;
            }else {
                heights[pos]++;
            }            
        }
        
        return heights;
    }
}

Airbnb

airbnb_2017_fall

-------------------------
倒水

往一个int array 代表海拔的格子里倒水，打印出倒水后的

int[] 海拔， int 水数量， int

倒得位置。

Example:
int[] 海拔 {5,4,2,1,2,3,2,1,0,1,2,4}
水数量8， 倒在位置5

比较开放的题，一些条件要跟面试官探讨，比如左边还是右边优先。

例子：

handle the water drop by drop。 there are infinitely high walls on the left and right 

水先向左走，走到不能走。call it leftMost 

如果leftmost的水比开始点低，leftMost水+1，done 

如果leftmost的水不比开始点低，水向右走，走到不能走，call it rightMost 

如果rightmost的水比开始点低，rightMost水+1，done 

如果rightmost的水不比开始点低，leftMost水+1，done

public static void main(String[] ss) {
        int[] a = {5,4,2,1,2,3,2,1,0,1,2,4};
        fillWater(a, 5,8);

        for (int i : a) {
            System.out.println(i);
        }
    }

    public static void fillWater(int[] land, int pos, int water) {

        while (water > 0) {
            int left = pos;
            while (left > 0 && land[left - 1] <= land[left]) {
                left--;
            }

            if (land[left] < land[pos]) {
                land[left]++;
                water--;
                continue;
            }

            int right = pos;
            while (right < land.length - 1 && land[right + 1] <= land[right]) {
                right++;
            }

            if (land[right] < land[pos]) {
                land[right]++;
            }else {
                land[left]++;
            }

            water--;
        }
    }

另一个变种是把最终的图形（墙跟水）都打印出来

-----------------------------
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=273149

题目是给你公式，比如偶数的话除2，奇数的话就变成3*n+1，对于任何一个正数，数学猜想是最终他会变成1。每变一步步数加1，给一个上限，让找出范围内最长步数。
第一题是这样的：比如7，变换到1是如下顺序：7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1, 总共需要17步。

很直接， 没什么好说的。用一个map减少重复计算

public static void main(String[] ss) {
//        int[] a = {5,4,2,1,2,3,2,1,0,1,2,4};

        System.out.println(findLongestSteps(7));
    }

    private static int findLongestSteps(int num) {
        Map<Integer, Integer> map = new HashMap<>();

        int longest = 0;

        for (int i = 1; i <= num; i++) {
            longest = Math.max(findSteps(i, map), longest);
        }

        return longest;
    }

    private static int findSteps(int num, Map<Integer, Integer> map) {
        if (num <= 1) return 0;

        if (map.containsKey(num)) return map.get(num);

        int rt = 0;
        if (num % 2 == 1) rt = findSteps(3 * num + 1, map);
        else rt = findSteps(num / 2, map);

        rt++;
        map.put(num, rt);
        return rt;
    }

----------------------------------------------------
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=279191

Design a Queue with arrayList, 但是有限制条件, arraylist的长度最多为10, queue不限制长度。纠结了很久不知道怎么做，是不是先把max size设置成10，然后发现overflow了在扩大成10个arraylist，以此类推到100, 1000... 但是这样的话，queue的remove操作要从头开始，好像记录起来比较麻烦。求大家讨论！

用linked list来做，每个node包含一个list，长度不能超过定值

class MyQueue {

    private Node head;
    private Node tail;
    private int indexHead;
    private int indexTail;

    public MyQueue() {
        head = new Node();
        tail = head;
        indexHead = 0;
        indexTail = 0;
    }

    public int pop() {
        int rt = head.list.get(indexHead);
        indexHead++;

        if (indexHead == 5) {
            head = head.next;
            indexHead = 0;
        }

        return rt;
    }

    public int peek() {
        return head.list.get(indexHead);
    }

    public void push(int val) {
        tail.list.add(val);
        indexTail++;
        if (indexTail == 5) {
            tail.next = new Node();
            tail = tail.next;
            indexTail = 0;
        }
    }
}

----------------------------------------------------



----------------------------------------------------



----------------------------------------------------

Uber 面经

https://www.1point3acres.com/bbs/thread-490045-1-1.html


第一轮： 面经题， 给起始和终点时间，按月输出中间的时间段，比如给定范围 [2019-01-10, 2019-03-15]， 输出 -> [2019-01-10, 2019-01-31], [2019-02-01, 2019-02-28], [2019-03-01, 2019-03-15]
要考虑不同年月份的，个人觉得有时间还是提前写写吧，各种cases挺多的

先算出头跟尾，中间的就好解决了

第二轮： 韩国大叔，给一个un sorted array，里面数unique，找出所有两两和相等的pairs， 比如[9, 4, 3, 1, 7, 12]
返回：[1, 12] & [4, 9], [3, 7]. & [1, 9], [4, 12] & [7, 9]
卡住了，最后只好暴力解，卒
暴力找出n^2, 然后map存 sum -> pairs

第三轮： system design， 友好的美国小哥，设计 oneBusAway 这个app，主要功能为：用户打开app，要显示出周围的bus stops, 点进其中一个bus stop 要展示出该站所经过的公交车，再进一步点某个公交车，显示其路线，
小哥好心的简化了题目，说不考虑时间，只考虑static 状态-baidu 1point3acres
这轮交流很顺，就是一步一步讨论，画图，写schema，跟平常工作一样，很舒服

第四轮： system design 烙印，设计 messanger group chat，比如，关于有收到群聊消息，用户在线或者不在线，怎么更新显示之类的，我提了一些他都不满意，就说latency太高，然后看着你。。。。
本来我就惧怕design，交流真累， 卒

第五轮： hiring manager，各种瞎聊，挺好的老板

----------------------------

https://www.1point3acres.com/bbs/thread-489773-1-1.html

先是phone interview, 后是onsite， phone interview之前发了帖子，一并转过来吧；

其实蛮喜欢uber的，据说后台不少是golang，本身也很喜欢这个语言，
可惜还是挂了，没有拿到他们家senior sde水平， 他们家等待期是6个月，总体面试经验挺好的，每轮都给了feedback，
system design那一轮应该是negative的feedback, 时间有限，准备的还是不够充分，求安慰求大米!!

总体觉得onsite算法不算特别难 题目也是地里出现过的，livecoding的时间蛮紧的，
6个月之后再干！干成功为止！


Phone interview

The main difference between list and set
The main difference between stack and queue
Search of a unsorted list:
Run-time
O(n)
Binary search-run time, why use binary search
log(n)
Application write 60 million operations to a single machine, how to handle it in a single day
Webservice overload to read/get same data
Nosql vs sql pro/con. check 1point3acres for more.
Nosql sharding

Team size
Design architecture
Mentor junior

onsite
第一轮 hire manager 面

主要介绍项目
BQ问题为主， 项目中展示的strength ，difficult to deal with someone
项目的平台架构，dataflow , trade off, design decision

第二轮 算法面
题目：find the number of occurence of duplicate target number in a sorted array
Binary search
类似lc原题
第三轮 system design
design uber-like riding sharing apps
. check 1point3acres for more.

第四轮 live coding. From 1point 3acres bbs
message chunk

----------------------------

https://www.1point3acres.com/bbs/thread-489328-1-1.html

第一轮， hm 白人小姐姐， 感觉没比我大多少，全程bq
第二轮， 系统设计， 国人小姐姐， heatmap
中午吃饭， 小印 + 白墨 聊天。. From 1point 3acres bbs
第三轮， 写code， 白人大哥， 肯定挂在这里了， 那个大哥上来就说我要考你一题NP hard， 我心想好啊， 结果头一天晚上没睡 +中午吃太多， 那一轮巨困，
完全在梦游， 更加坑的是， 他一定要坚持上机写，但是又没有准备C++的输入struct， test case之类的（他只有JAVA和python的， 而且笑着说我是第二个他见过的用C++的）。
而且那一题的输入对c++及其不友好， 花了20分钟parsing input。。。。。。（面试官说这里python就需要一行）。
勉强写完， 没时间了，我最后问他这一轮你expect candidate答出什么， 他说一定要能run过testcase。。 我心里想，那估计挂了。

后面两轮就没啥压力了，因为知道挂了。
-baidu 1point3acres
第四轮， abc小中 +三哥shadow lc medium， 很简单
第五轮， bar raiser， 三哥， 聊得很开心


----------------------------

https://www.1point3acres.com/bbs/thread-487913-1-1.html

10:00～10:15 HR接待
10:15～11:15 algorithm轮 荷兰小哥；
利口 吾幺巴； 我当时没刷到这题，只写了暴力破解DFS，一起讨论了一下怎么做成DFS+memo，这题还有一个标准的DP解法，那个我就没想到了，也没时间了。
LC 518
11:15～12:15 System design轮 英国大哥（浓浓英伦腔） + 从澳洲过来的印度大哥远程；
开始给了一个很开放的问题，就是手机或者浏览器访问网站或者服务器的时候是怎么样一个过程。然后问流量大了之后要如何handle。如何监控服务器的load，然后load很低的时候很不efficient如何调整，load很高的时候又可能handle不了，如何解决。
很多用户突然都访问失败，如何知道是哪里出现问题，如果是某些服务器服务失败，如何处理，又如何提前监测预防这些问题的出现。AB实验如果上了一些新的代码机器，如何上到生产环境中，当上线发现它们里面有bug的时候又如何处理。
12:15～1:00 lunch 和英国大哥 到他们组那边吃的饭，还见到一些将来可以一起工作的组员，还挺不错的

1:00 ～ 2:00 hiring manager
问了几个工作经历和以前的项目，在白板上demostrate了一下技术框架；因为我面的Java组，所以问了为什么选择Java这个语言，why this team, why Uber；多这个组有什么需要了解的
2:00 ～ 3:00 coding
写一个Scheduler，允许上网查Java API，不允许查看其它。这个Scheduler的基本需求就是提供出来一个底层的library，供用户调用；
Input是用户调用这个API，可以提交一个timestamp + 一个Job任务，然后我们可以到了这个timestamp则执行这个任务。如果提交的timestamp小于当前timestamp，则立即执行。
用户可以反复多次call这个API
3:00 ～ 3:45 bahavior面 其他组的两个工程师
和外部其它组合作的项目经验，其它team和我合作人对我的feedback
最proud的项目；和谁合作的最不愉快，为什么；你觉得谁会觉得和你合作的不太愉快；
是否当过mentor，过程如何，自己的收获，哪些地方能做的更好；why uber; 你喜欢什么样的企业文化，对uber的期待；
3:45 ～ 4:00 hr walk out


----------------------------

https://www.1point3acres.com/bbs/thread-487754-1-1.html


已经过去一段时间了，但是还是发一下吧，顺便求点米~

一共6轮9个面试官，是我遇到人数最多的onsite面试了。。。 神了个奇的

1. product manager, 30分钟纯聊天， bq
午饭， 下午的一个面试官带着去吃的，不好吃...
2. hiring manager, 45分钟纯聊天，bq
3. sr engineer， 45分钟zoom纯聊天， bq

4. 中午带着吃饭的小哥，coding
4a. 滑动窗口, 刷题网76
4b. 三组数字， 第一组其中的一个数字和第二组其中的一个数字相加，等于第三组的其中一个数字，找出所有的组合，每一组的数字可能有重复
暴力，枚举1.2的组合，第3组放set里
5. 系统设计， 设计facebook. 1point3acres
6. 先聊了会简历啥的然后coding，有向图，先找出图中一个点最远能travel多远， follow up是找出图中能travel最远的点.
比如， 我有一个图， a->b a->c a->d b->c c->d followup就是要找a-b-c-d这条路径
DFS 或bfs
follow up，把所有点的degree算出来，从in degree > out degree的外面往里面剥离

----------------------------

https://www.1point3acres.com/bbs/thread-487589-1-1.html


uber有个好处是会把面试官的全名附带在schedule里提前发来，去领英上查查就大致能知道会问什么问题。。。

第一轮：所面的组的Hiring manager，看领英是非常senior的大哥，估计是bar raiser+项目
果然，半小时讨论了最主要的项目的细节，剩下时间问了一些behavior，比如和manager的意见不一致，如何应对tight deadline等等。

第二轮：另一个组的hiring manager，工作年限不多但是前一份工作的项目是关于云服务infra的，感觉很厉害。估计也是bar raiser，会问behavior以及工程能力。
上来自我介绍，顺便夸对方之前的工作好屌在这方面我还得多多努力。结果面试官就着这个话头问到底还差哪些能力，以及我对这个职位的理解。之后又是一堆behavior。

第三轮：组里的engineer。我看他做的东西和我正在做的几乎完全一致，而且他之前是非CS出身，以为会主要面项目或者ML算法，结果，
简单自我介绍以后直接做题：不用sqrt方法来求平方根。因为一直觉得他会面ML算法而不是一般的算法题，所以没说二分，直接说用牛顿法。白板上公式推了一下，伪代码大致过了下流程，就继续在白板上正式写代码了。牛顿法基本上做好终止阈值设置就没太大问题，需要注意的是中间运算不要越界，以及如果函数收敛的话可能需要用反函数来确定阈值。之后问了复杂度及其原因，以及test case。

午饭：两个engineer（似乎是测试工程师？）带着吃饭，后来又有第三个工程师加入，聊城市和工作体验之类的。人多不尴尬，撩（大误）得他们很开心。

第四轮：system design
面试官非常和蔼。题目是如何做一个uber车辆状态的监测系统（比如如果车辆正常会定时发一个信号，如果发警报或者好久没响应就会提示后台介入）。之后又问如何做一个全球uber数量可视化系统，给CEO看的那种。这部分我不是很擅长，尽量按照套路来走了，先问用例再问规模。估算了一下两个题都是单机规模可解的，可能是面试官看我太菜了没出难题？然后单机规模下分别提一个实现。第一题我提用一个以时间戳为Key的priority queue + 以车辆id为key 节点指针为value的map来做，有点类似LRU cache。第二题我提的是搞一个不同zoom in大小下的grid构成的tree（octree），然后算出grid里所有车的平均位置作为显示时的代表节点。都不知道对不对。

第五轮：coding
聊了一点点项目里的实现细节，直接做题。假设有一个linkedlist，但只提供三个接口：getNode(value), getRightNode(Node) 以及 getLeftNode(Node)。另给了一个vector<int>，问这些数字在linkedlist里构成了几段连续的片段。
其实就是把vector转成set (unordered_map)，然后遍历一遍set，如果在linkedlist里找到当前值，就往左右继续查找直到不在set里为止。同时注意找到的值要从set里删掉。
之后问set冲突怎么办，以及如果set遍历时要保证按大小顺序/插入顺序输出，但依然要保证set的θ(1)性质，分别应该用什么结构，分别是什么复杂度。其实就是unordered_map和map的底层实现方法，BST和红黑树之类的。

其实每轮答得都有些虚，也都有些小遗憾。不过和每个面试官都聊得很开心，早上还很困面试完反而精神了。

几天后收到offer。



----------------------------

https://www.1point3acres.com/bbs/thread-487212-1-1.html



昨天刚面的uber marketing组，来一波新鲜面经，签了协议不方便说的太细，就大致说一下，
1. manager轮，behavior questions，没什么好说的，主要就是介绍组介绍人员配置然后问问我的优点缺点什么的。
2. 烙印senior，standford毕业的，来uber工作3年多，问的题是一个alian name的问题，就是给你一堆string，说是已经按照某种逻辑排好序的，但是排序的规则未知，然后让你找出规则输出，其实很简单，就是topological sort，我写了个dfs+剪枝的代码，虽然也可以work但是复杂度有点高，代码最后刚写完还没改完typos，时间就到了，主要和manager之前那轮多聊了五分钟，加上之前一直requirement没搞清楚浪费了好多时间，只有15分钟写代码，而且这代码量也挺大，最后烙印说先这样吧，你可以一会把代码补全了然后明天早上他再来看。感觉这轮gg，回家补全了代码，顺便topological sort的方法也写了，也不知道烙印会不会真的看。
3，lunch，一个中国的小妹妹带我去吃的，没啥好吃的没吃几口就回去了。今天schedule特别紧。
4. 白人小哥，tech lead还是senior忘了，system design，原来以为我是new grad想问我算法，后来发现我面的不是new grad就给我换了个system design题，设计uber heat map，要求可以zoom in，还可以查看特定时间的heat map，挺简单，geo hash+ ring pop+ casendra/dynamoDB，服务器数据库sharding什么的乱扯一通，然后算了一下qps，storage什么的，小哥看起来挺满意，看着我画的图想了半天觉得没什么可以问的了，然后就谈笑风生聊天起来。
5。中国大哥，谷歌senior之前，人非常nice，问的题目也不难，就是给你一个有typo的string和一个字典，让你correct这个string，typo可能是大小写，也可以能是元音字母弄错，很快写完加优化完，然后重构了一下代码，改成单例模式，因为给你的字典是固定的不需要每次都初始化。之后愉快的聊天。
6， bar rasie，新加坡大哥，感觉表现最好的一轮，刚开始出了一个智力题，就是砸金蛋的游戏，主持人砸的就剩一个蛋的时候问你换不换。然后把之前公司自己设计的服务架构什么的以超快的语速加上画图说了一通，说的口干舌燥，大哥感觉也挺有兴趣，一问一答有来有回，最后问问题，愉快的结束聊天送我下楼。

总结一下，uber换了ceo后企业文化还是很好的，大家很友好，很geek的感觉，marketing组做的东西我也很喜欢，就是as we all know，食堂的饭菜不敢恭维
每次面完都会发面经，感觉第二轮要挂，还是求人品求offer求大米











----------------------------

https://www.1point3acres.com/bbs/thread-487187-1-1.html



一年半工作经验。



印度老哥 中国人shadow 全是behavior，偏技术方面，虽然我没事先准备这个，但是我在亚麻呆过两个组，见得多了，答起来得心应手
国人姐姐 中国小哥shadow 设计推特，写schema。 自认为做得特别差，但是面完后他俩说“别紧张，你这样没事”。
印度小哥 LRU 秒了 然后问了各种follow up
黑人大哥 bar raiser 全是behavior
白人小哥 两个Interval list 合并和排序，输出一个list作为结果。因为两个list是事先排序好的，所以有O（n+m）解法。



面完后感觉很棒，design的那轮面得不好，但是两个国人面试官都不错，终于今天拿到offer了。
感觉Uber这次面试有点放水，题都不难，behavior也都不棘手，面试官特别是国人面试官都特别友好。
但是Ube毕竟还没上市，面试的那栋楼硬件条件一般，没有高大上的感觉，吃午饭也是上个楼排队随便找地方吃就完事了，比不上湾区亚麻和Google。。。
















----------------------------

https://www.1point3acres.com/bbs/thread-477650-1-1.html
















----------------------------

https://www.1point3acres.com/bbs/thread-477650-1-1.html

460. LFU Cache

460. LFU Cache

Hard

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

--------------------
1个hashmap存key - value
1个存key - frequency
1个存 frequency - keys

用min来存最小的frequency
LinkedHashSet里面是hashset + doubly linked list的实现方式，所以是有序的

class LFUCache {

    private Map<Integer, Integer> map;
    private Map<Integer, Integer> keyToFrq;
    private Map<Integer, LinkedHashSet<Integer>> frqToKeys;
    private int cap;
    private int min;
    
    public LFUCache(int capacity) {
        min = -1;
        cap = capacity;
        map = new HashMap<>();
        keyToFrq = new HashMap<>();
        frqToKeys = new HashMap<>();
    }
    
    public int get(int key) {

        if (!map.containsKey(key)) return-1;
        int frq = keyToFrq.get(key);
        frqToKeys.get(frq).remove(key);
        if (min == frq && frqToKeys.get(frq).isEmpty()) min++;
        
        frq++;
        if (!frqToKeys.containsKey(frq)) frqToKeys.put(frq, new LinkedHashSet<Integer>());
        frqToKeys.get(frq).add(key);
        keyToFrq.put(key, keyToFrq.get(key) + 1);
        
        return map.get(key);
    }
    
    public void put(int key, int value) {
        if (cap <= 0) return;
        if (map.containsKey(key)) {
            map.put(key, value);
            get(key);
            return;
        }
        
        if (map.size() >= cap) {
            
            int evit = frqToKeys.get(min).iterator().next();
            frqToKeys.get(min).remove(evit);
            map.remove(evit);
            keyToFrq.remove(evit);
        }
        
        map.put(key, value);
        min = 1;
        keyToFrq.put(key, min);
        if (!frqToKeys.containsKey(min)) frqToKeys.put(min, new LinkedHashSet<Integer>());
        frqToKeys.get(min).add(key);
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

759. Employee Free Time

759. Employee Free Time

Hard

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation:
There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Note:

1. schedule and schedule[i] are lists with lengths in range [1, 50].
2. 0 <= schedule[i].start < schedule[i].end <= 10^8.

----------------------
不用想太复杂
把所有的interval都插入到priorityQueue，然后找gap。题目中给的多少个人其实没有什么意义
O(n), n为总的interval数量

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        PriorityQueue<Interval> que = new PriorityQueue<>((a, b) -> a.start - b.start);
        
        for (List<Interval> list : schedule) {
            for (Interval i : list) {
                que.add(i);
            }
        }
        
        List<Interval> rt = new ArrayList<>();
        int max = -1;
        while (!que.isEmpty()) {
            Interval top = que.poll();
            if (max != -1 && top.start > max) {
                rt.add(new Interval(max, top.start));
            }
            max = Math.max(max, top.end);
        }
        
        return rt;
    }
}

829. Consecutive Numbers Sum

829. Consecutive Numbers Sum

Hard

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

Example 1:

Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3

Example 2:

Input: 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4

Example 3:

Input: 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

Note: 1 <= N <= 10 ^ 9.

---------------------
求等差数列为1，和为N的数列的个数，假设数列的首项为x，项数是m，则如果存在这一数列，N = (x + (x + m - 1)) * m / 2. 那么我们就遍历m的可能性

O(lgN)
ref: https://zhanghuimeng.github.io/post/leetcode-829-consecutive-numbers-sum/

class Solution {
    public int consecutiveNumbersSum(int N) {
        int rt = 0;
        
        for (int m = 1; ; m++) {
            int mx = N - (m - 1) * m / 2;
            if (mx <= 0) break;
            if (mx % m == 0) rt++;
        }
        
        return rt;
    }
}

542. 01 Matrix

542. 01 Matrix

Medium

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1: 
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2: 
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

---------------------
Solution #1
BFS, 把所有的0放入queue中，用额外数组记录visited情况
O(m*n) time and space

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] rt = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> que = new LinkedList<>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) que.add(new int[]{i,j});
            }
        }
        
        int dis = 0;
        while (!que.isEmpty()) {
            for (int size = que.size(); size > 0; size--) {
                int[] top = que.poll();
                int r = top[0], c = top[1];
                
                if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c]) continue;
                visited[r][c] = true;
                rt[r][c] = dis;
                que.add(new int[]{r - 1, c});
                que.add(new int[]{r + 1, c});
                que.add(new int[]{r, c + 1});
                que.add(new int[]{r, c - 1});
            }
            
            dis++;
        }
        
        return rt;
    }
}

Solution #2， DP，每个点有上下左右4个方向可以选择，如果符合条件，选每个方向路径都增加1。那我们先从matrix左上走到右下，再右下到左上。这样4个方向全部检查过
跟#1一样的复杂度
ref: https://leetcode.com/problems/01-matrix/discuss/101039/Java-33ms-solution-with-two-sweeps-in-O(n)

255. Verify Preorder Sequence in Binary Search Tree

255. Verify Preorder Sequence in Binary Search Tree

Medium

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Consider the following binary search tree: 

     5
    / \
   2   6
  / \
 1   3

Example 1:

Input: [5,2,6,1,3]
Output: false

Example 2:

Input: [5,2,1,3,6]
Output: true

Follow up:
Could you do it using only constant space complexity?

Accepted

32,826

Submissions

76,719

Seen this question in a real interview before?

-----------------------
Solution #1, O(n) time and space
stack里保证的是递增（从top到底下），遇到比top大说明是走到了右子树，然后把之前左子树跟root全部pop掉，取root为lower bound（之后再也不会遇到比这更小，如果有，说明顺序有错误）
这方法是模拟preorder traversal的iterative的版本

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> st = new Stack<>();
        int low = Integer.MIN_VALUE;
        for (int i : preorder) {
            if (i < low) return false;
            
            while (!st.isEmpty() && st.peek() < i) {
                low = st.pop();
            }
            st.push(i);
        }
        
        return true;
    }
    
}

Solution #2 O(n) time, O(1) space, 把给定的preorder数组利用起来，当作stack来存

934. Shortest Bridge

934. Shortest Bridge

In a given 2D binary array A, there are two islands.  (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped.  (It is guaranteed that the answer is at least 1.)

Example 1:

Input: [[0,1],[1,0]]
Output: 1

Example 2:

Input: [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

Input: [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Note:

1. 1 <= A.length = A[0].length <= 100
2. A[i][j] == 0 or A[i][j] == 1

-------------------
BFS
先标记出一个岛，然后做BFS直到碰到另一个岛
注意dis的初始值是 -1

class Solution {
    public int shortestBridge(int[][] arr) {

        Queue<int[]> que = new LinkedList<>();

        for (int i = 0; i < arr.length; i++) {
            boolean f = false;
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] == 1) {
                    dfs(arr, i, j, que);
                    f = true;
                    break;
                }
            }
            if (f) break;
        }

        int dis = -1;
        while (!que.isEmpty()) {
            
            for (int size = que.size(); size > 0; size--) {
                int[] top = que.poll();
                int i = top[0], j = top[1];
                if (i < 0 || j < 0 || i >= arr.length || j >= arr[0].length || arr[i][j] == 3) continue;
                if (arr[i][j] == 1) return dis;
                arr[i][j] = 3;
                que.add(new int[]{i + 1, j});
                que.add(new int[]{i, j + 1});
                que.add(new int[]{i - 1, j});
                que.add(new int[]{i, j - 1});
            }
            dis++;
        }


        return 0;
    }

    private void dfs(int[][] arr, int i, int j, Queue<int[]> que) {
        if (i < 0 || j < 0 || i >= arr.length || j >= arr[0].length || arr[i][j] == 0 || arr[i][j] == 2) return;

        arr[i][j] = 2;
        que.add(new int[]{i, j});
        dfs(arr, i + 1, j, que);
        dfs(arr, i - 1, j, que);
        dfs(arr, i, j + 1, que);
        dfs(arr, i, j - 1, que);
    }
}

640. Solve the Equation

640. Solve the Equation

Solve a given equation and return the value of x in the form of string "x=#value". The equation contains only '+', '-' operation, the variable x and its coefficient.

If there is no solution for the equation, return "No solution".

If there are infinite solutions for the equation, return "Infinite solutions".

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"

--------------------
解一元一次方程。难点在处理string parsing上。计算左右2边常数项和变量各自的差，sign表示等号左右

class Solution {
    public String solveEquation(String equation) {
        int i = 0, start = 0, cof = 0, cos = 0, sign = 1;
        
        for (; i < equation.length(); i++) {
            if (equation.charAt(i) == '+' || equation.charAt(i) == '-') {
                if (i > start) cos += sign * Integer.parseInt(equation.substring(start,i));
                start = i;
            }else if (equation.charAt(i) == 'x') {
                if (i == start || equation.charAt(i - 1) == '+') {
                    cof += sign;
                }else if (equation.charAt(i - 1) == '-') {
                    cof -= sign;
                }else {
                    cof += sign * Integer.parseInt(equation.substring(start,i));
                }
                
                start = i + 1;
            }else if (equation.charAt(i) == '=') {
                if (i > start) cos += sign * Integer.parseInt(equation.substring(start,i));
                sign = -1;
                start = i + 1;
            }
        }
        
        if (start < equation.length()) cos += sign * Integer.parseInt(equation.substring(start));
        if (cof == 0 && cos == 0) return "Infinite solutions";
        if (cof == 0) return "No solution";
        return "x=" + Integer.toString(- cos / cof);
    }
}