Google interview questions - Round 2 - #3 - 他人汇总

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

https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/edit?usp=sharing

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


莉蔻三九九及其变种（汇率）
频率：21
就是一个2维数组里的有人和自行车，要每个人匹配到一辆自行车，人和自行车的距离越短越好，没有距离相同的情况。就是算出所有的距离然后放到heap里慢慢pop出来，记录下人和车的状态就可以了。
频率：13
 再跟一下

利口六八四 六八五及其变种（bst删除额外边）
频率：10
-baidu 1point3acres
利口六二
著名变种：DP。给定一个矩形的长宽，用多少种方法可以从左上角走到右上角 （每一步，只能向正右、右上 或 右下走）：整个矩形遍历做DP即可，不需要想复杂. 牛人云集,一亩三分地
Solution

public static void main(String[] ss) {


    System.out.println(ways(7, 6));
}

public static int ways(int m, int n) {
    int[][] dp = new int[m + 2][n];
    dp[1][0] = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m + 1; j++) {
            dp[j][i] = dp[j - 1][i - 1] + dp[j][i - 1] + dp[j + 1][i - 1];
        }
    }

    return dp[1][n - 1];
}

-follow up：如果给矩形里的三个点，要求解决上述问题的同时，遍历这三个点 （切割矩形，一个一个地做DP，然后相加）
Solution, 所有路径必须经过这3个点，求一共有多少种走法（到达右上）
其实这3个点跟起点和终点没有区别。如果存在这3个点，则这5个点中的任意2个点不可能存在在一个column上。按column来划分矩形，分别对两两做dp
可以写一个方法
int ways(int m, int n, int[] start, int[] end, int startCount) 来避免代码重复

-follow up：如何判断这三个点一个是合理的，即存在遍历这三个点的路经
Solution
2个相邻之间的点的连线与水平线的夹脚 <= 45度，就可以说明左边的点能到达右边的点。表示为 |y2 - y1| >= x2 - x1, 假设(x1, y1) (x2, y2) 为左右2点

-follow up：如果给你一个H，要求你的路径必须向下越过H这个界，怎么做 （别问我，我不会）
Solution
找出不越界的路线个数，原来的结果相减就得到越过的个数

楼主这题试一试用镜像做，也就是说重点不在(W, 0), 而在(W, 2H)， W是矩阵的宽度
频率：9
六口把四散（猜词）
843
频率：9


莉蔻八就灵及其变种（word pattern）
890
频率：8

六口死罢就（扫地机器人）-baidu 1point3acres
489
频率：7

莉蔻八五五及其变种（考试找位子）
855
频率：6

带expiration的hashmap
频率：6
Solution:
value存上timestamp
2个方法：1.主动去清空 2. 读写的时候对比timestamp

多个不重复的长方形内重复取点
follow up：多个可能重复的长方形内随机取点
频率：6
497, follow up：先把长方形都分割好

莉蔻八五三（高速路车分cluster）
频率：5
853

莉蔻八五期（雇工人）
频率：5


六口气五菱（matrix里找长方形）
频率：5
利口把衣物及其变种（公交路线）
频率：5
利口六五九及其变种（找顺子）
频率：5
给一个国王家的family tree （n-ary tree），王位继承是先传国王最年长的儿子，假如最年长儿子死了，就传给死儿子最年长的儿子。。。如果这些人都不存在，再考虑国王次年长的儿子，以此类推。要求设计这样一棵树，死掉的人不要求删除，实现birth（）和输出王位继承顺序的method（死掉的人不在继承顺序结果里）。（及其变种）
频率：5
Tree Isomorphism Problem (search in geeksforgeek)
频率：5
给定一个multiple tree，以及需要删除的多个nodes，要求返回一个node的list，以便在nodes被删除之后可以找到这些nodes的child。
例子：. Waral 博客有更多文章,
a. From 1point 3acres bbs
/ / \ \. From 1point 3acres bbs
b d c f. Waral 博客有更多文章,
/ \ \.1point3acres网
h z i
假如删除b和f，返回{a, d, c, h, z, i}
假如删除a和b，返回{d, c, f, h, z, i}
可以用level traverse解。
频率：5
. 1point3acres
可乐饮料机，有一系列按钮，每个按钮按下去会得到一定体积范围的可乐。先给定一个目标体积范围，问不限制按按钮次数，能否确定一定能得到目标范围内的可乐？
举例：有三个按钮，按下去得到的范围是[100, 120], [200, 240], [400, 410],
假设目标是[100, 110], 那答案是不能。因为按下一，可能得到120体积的可乐，不在目标范围里。
假设目标是[90, 120]，那答案是可以。因为按下一，一定可以得到此范围内的可乐。
假设目标是[300, 360], 那答案是可以，因为按下一再按二，一定可以得到此范围内
假设目标是[310, 360], 那答案是不能，因为按下一再按二，有可能得到300，永远没可能确定得到这个范围内的可乐。
假设目标是[1, 9999999999]，那答案是可以。随便按一个都确定满足此范围。
频率：5


如果有用，请加米，多谢！



补充内容 (2018-10-3 09:35):
multiple tree那道题貌似栗子错了，应该是删除bf的话返回ahzi
. 1point3acres
补充内容 (2018-10-3 09:42):
落了一道题：
判断target字符串是否可以由给定字符串转换得到。转换的规则是：每次转换要变所有的相同字母
比如：abca -> cdec 可以 abca -> abea -> cbec -> cdec
频率：5

补充内容 (2018-10-4 00:53):
这里统计的面经从三四月到九月，lz面试遇到的所有的题里面有三道题出自这个高频题。还有两道是频率为3的没有放到这里。面经见另外一个帖子。

补充内容 (2018-10-4 07:05):
多个不重复的长方形内随机取点，不是重复取点

补充内容 (2018-10-10 11:49):
频率为34的在此
http://www.1point3acres.com/bbs/thread-448608-1-1.html



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


频率4
1. 下围棋，判断棋盘上一个点是不是被包围了。
用了dfs 写的挺顺的。 然后问testcase， 画了各种形状的围棋图
2. 一个map分为n层，每层都m个node， 每个node有值，每一层跟下一层的node是full connected，edge的值不一定相同，求从第一层到最后一层的mini cost
3. ABC 小哥和大黑哥， 问了一个拿纸牌游戏， 纸牌上面有值，比如说 100， 1， -1， 2， 200， 1. 然后两个人轮流拿，直到拿完。 但是每次只能拿从左边数起的前三个，但是如果你要拿第三个，就必须前两个都拿了，你要拿第二个，就必须第一个也拿了，大家都最优策略，问最后第一个人能拿多少分。dfs 加 cache做了。
4. 一个image以2D byte array的方式储存（byte[][] image），每个象素点是1个bit（0或1）。现在要求每行的象素点做对称翻转。我的做法是先把每行的byte对称翻转，然后再把每个byte各自翻转。

如其中一行byte[] row = {11010100，00101010}
第一步{00101010，11010100}
第二步{01010100，00101011}
时间复杂度是O(m*n*8), follow up如何优化时间，应该是在翻转每个byte上把O（8）的复杂度降低，但是不要求使用复杂的位运算
5. 已知screen的高和宽，给你最小和最大的fontSize，要求给定一个string，将string用竟可能大的fontSize显示在screen里。已知两个API getHeight(int fontSize), getWidth(char c, int fontSize)，可以得到每个character在不同fontSize下的高和宽。和面试官交流后，确认string可以拆分成几行显示在screen中，先提出暴力解法，然后用二分法优化.
6. 莉蔻把零散 （打砖块）
7. 莉蔻儿五三及其变种（meeting room）. From 1point 3acres bbs
8. random generate a maze
9. 白人大哥，给一个list intervals of integer ([2,9], [1,3], [10,20] ..), 给一个integer X, 查找X在不在给的interval 里面。答曰一遍遍历，o(n). 他问能不能优化。这个list 是无序的，只有排好序才能优化，但是排序就要o(nlogn)。在我追问下，他说了如果我们有很多的查询x在不在，能不能优化每次的查询？那就是一次性处理这个list intervals. 我先给的解法是遍历一遍intervals, 把所有数字存到hashset里，查询用hashset， O(1)。他貌似对这个解法不满意，说这个方法如果数字很大，很占内存，等等。我就顺着他说先sort, 然后binary search. binary search 前要先remove overlap.然后开始写代码。
10. 实现一个iterator的iterator

频率3 （很神奇，大多都是莉蔻原题变种）
1. 离扣留气流各种变种
2. 莉蔻把四九
3. 莉蔻丝一把
4. 离扣留吧
5. 莉蔻把丝丝. From 1point 3acres bbs
6. 莉蔻三九思
7. 莉蔻三三四
8. 莉蔻琪琪死
9. 利口三三期
10. 粒扣三丝翎
11.设计个log start，finish finish后 输出log id跟内容 但finish的时候 如果start前面还有start 就不能输出
直到没有pending了 就全输出
比如
start(1, time1)
start(2, time2)
start(3, time3). 牛人云集,一亩三分地
finish(2, time2)
finish(3, time3)
finish(1, time1) . check 1point3acres for more.
输出 1， 2 ，3
为啥 因为finish2得时候 前面还有个1 被start过
finish3的时候 2虽然没了 前面还有个1 被start过
12. 莉蔻斯八六
13. 莉蔻儿药物
14. 粒扣三一而
15. 莉蔻气流就
16. 莉蔻舞领舞
17. 利口酒流
18. 莉蔻把三丝


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


第一题：矩阵从左上角到右下角有多少种走法
给定一个矩形的长宽，用多少种方法可以从左上角走到右上角 （每一步，只能向正右、右上 或 右下走）
Follow up 1：如果给矩形里的三个点，要求解决上述问题的同时，经过这三个点
Follow up 2：如何判断这三个点一定是合理的，即存在路径
Follow up 3：如果给你一个H，要求你的路径必须向下越过H这个界，怎么做
Follow up 4：要经过某些特定row怎么走？要先经过一个row再经过另一个row怎么走？
. From 1point 3acres bbs
感觉可以第一问用two pass DP解决。Follow up 1和2可以纵向切割矩阵，一个矩阵一个矩阵做DP。
但是Followup 3&4我就不太会了，该咋做呢~




第二题：01矩阵走路问题
0和1的grid，1是墙，0是路，从左上角走到右下角，最少多少步。
Follow-up: 现在说能把grid中的一个1变成0，问新的最小步数是多少步。

第一问应该就是常规的DP。第二问不知道该怎么做~




第三题：User CPU Peak问题
给了一堆log，log里有用户id，resource id以resource在某个起始时间和终止时间的使用量，比如用户abc在1到5秒钟使用了CPU的数量是2，用户abc在2到3秒使用的CPU数量是4，也就是一个用户对某个resource的使用在某个时间是可以叠加的，给定一个resource id，根据用户对这个resource的peak使用量，找到top k的用户。上面的例子中abc的CPU的peak使用量是2+4=6
Follow up：如果数据量很大怎么办。

感觉可以把占用resource id的user id对应log聚合在一起，但是怎么计算这个peak就想不通了，感觉跟Meeting room有点像？但不知道该怎么实现。



第四题：拿卡片游戏
每张卡片都有一个值，给定一堆卡片从一头拿，每次可以拿一到三张，两人轮流拿，求最高得分。考虑卡片值为负的情况。

这个用DP？DFS？



第五题：是男人就跳问题
给一个二维坐标平面和一个起始点，从这点开始垂直下跳，下面有若干水平挡板，位置长度会在input里给，板的形式是（x, y, distance)，当跳到挡板上时，可以选择走到挡板的左端或者右端，然后继续垂直下跳，直到落地位置，求从开始到落地需要走过的路程最短是多少。

懵逼中，有大神能讲讲做法吗~



第六题：找到一条线将坐标系中的点分成两等份
题目是在一个坐标系里给很多离散的点，找到一条线将所有点分成两个数量相等的集合，不用考虑基偶性或者多个点在一条线上的特殊情况。

这是啥。。楼主数**渣。。



第七题：随机生成一个Candy Crush
黑人问号脸？有大神能详细描述下题目吗？




补充内容 (2018-6-11 11:33):
第二题解法有问题，由于可以随便走，所以应该用BFS，而非DP