1. 给一堆二维坐标，这些坐标点能组成一条线，求输出最少的点能还原这条线
2. 利口耳期酒，需要输出所有的完全平方数的数字，而不是多少个3. 第一象限 给一堆点 让你找一个最小正方形能把包含的离原点最近的k个点，followup是找这样的长方形
4. excel类似的功能，需要支持set和get，
- set 就是给你一个col key和它的value, 它的value可以是一个int，也可以是一个reference，指向其他的column
- get 就是给你col key 需要你能resolve它的value
2. 二维空间，给一堆平行于坐标轴的长方形，如果两个长方形相交，就算是属于一个group，求问有几个group。做法就是Union Find，相交的长方形就union为一个group
3. 给一堆各种颜色的球以及个数，比如绿球200个，蓝球300个，红球500个，装在一个不透明的袋子里，让你写一个函数模拟从袋子里拿球再放回去的操作，函数返回拿到球的颜色
4. 酒似遛的变体，stack的模拟操作，这个stack push的rule是必须先放k, 才能放k+1，输入是0到n的permutation，代表pop出stack的顺序，问你给定的输入是否能实现
5. 设计，群聊，侧重点在于清楚的描述你设计的系统每个组建的功能，以及组建之间的通信，以及数据结构
3. 给一堆各种颜色的球以及个数，比如绿球200个，蓝球300个，红球500个，装在一个不透明的袋子里，让你写一个函数模拟从袋子里拿球再放回去的操作，函数返回拿到球的颜色
4. 酒似遛的变体，stack的模拟操作，这个stack push的rule是必须先放k, 才能放k+1，输入是0到n的permutation，代表pop出stack的顺序，问你给定的输入是否能实现
5. 设计，群聊，侧重点在于清楚的描述你设计的系统每个组建的功能，以及组建之间的通信，以及数据结构
刷题网：意思琪琪
2. BQ: team has different opions. handle when one teammate leave during project. handle un-resonable request/task from manager.
3.刷题网：其义务
4. most challenging proj. 刷题网：伊尔无九
5. 2-d 01 矩阵 找最大陆地面积，0=水 1=地，陆地只能上下左右连接，斜着不算连接.
follow
2. BQ: team has different opions. handle when one teammate leave during project. handle un-resonable request/task from manager.
3.刷题网：其义务
4. most challenging proj. 刷题网：伊尔无九
5. 2-d 01 矩阵 找最大陆地面积，0=水 1=地，陆地只能上下左右连接，斜着不算连接.
follow
第一轮：类似吾儿霸，就用了个壳，负载平衡follow up 1, 如果这里面的权重可以改, 怎么搞，要最好的complexity
follow up 2, 怎么测试，现实场景如何验证这个算法
第二轮： 有一数组都是一个个字符串，如果有一个字符串满足一个pattern，假设你有这个检查符合pattern的方法存在， 输出给定前后半径的所有字符串
follow up 1, 把数组换成数据流
应该有follow up2，没太记清楚，主要我也没有时间写了
follow up 2, 怎么测试，现实场景如何验证这个算法
第二轮： 有一数组都是一个个字符串，如果有一个字符串满足一个pattern，假设你有这个检查符合pattern的方法存在， 输出给定前后半径的所有字符串
follow up 1, 把数组换成数据流
应该有follow up2，没太记清楚，主要我也没有时间写了
面的l4, 狗屎运比较偏简单;
走过路过，求好心人施舍点大米😂
（没有设置限制，如果看不到可能是论坛默认。。试试手机版）
----
第1轮：李寇 意思二三； follow-up：还是取数组头和尾k次，新加入multiplier int[k], 每次也从multiplier 按序取出数相乘算结果，求max，例子：k=2, array [3,2,1,4], multiplier [1,2], 第一次取结果：4*1， 第二次取 3*2, 总共10；用的dfs + memorization
第2轮：最近常见的简单雇主树结构；给adjacent list (有向图)
问1： 什么情况下valid：graph 中只有一个disjoint set并且没有cycle， 不在意是否indegree>=2
问2: Valid 下求某个人的分数，即此subtree的count
问3: Validate given graph，用topology sort
走过路过，求好心人施舍点大米😂
（没有设置限制，如果看不到可能是论坛默认。。试试手机版）
----
第1轮：李寇 意思二三； follow-up：还是取数组头和尾k次，新加入multiplier int[k], 每次也从multiplier 按序取出数相乘算结果，求max，例子：k=2, array [3,2,1,4], multiplier [1,2], 第一次取结果：4*1， 第二次取 3*2, 总共10；用的dfs + memorization
第2轮：最近常见的简单雇主树结构；给adjacent list (有向图)
问1： 什么情况下valid：graph 中只有一个disjoint set并且没有cycle， 不在意是否indegree>=2
问2: Valid 下求某个人的分数，即此subtree的count
问3: Validate given graph，用topology sort
1～4
- behavior 就是一般的题目，比如如何handle意见不同的情况。我是结合我实际情况回答的。总之一个原则：communication solves all the conflicts
- 三零一，还有一个ez的题目，具体我不太记得了。
- TicTacToc用android写的变种，我用了一些jetpack的东西，比如viewmodel和livedata
- android写service。算法997？还有一个现出的题目dp，这个我好像当时现场推出来，没见过原题。
5. 三叔，一个ez的题目，然后来了一个我没见过的题目。估计这轮弱。
如果有人知道请告诉下我。
大意是有1～n，可以组合成1,[1,2],[2,1],[1,2,3],[2,1,3],[3,2,1]...
如果把结果放在一个1d的array里，结果是什么？
我用了一个很naive的做法。但是貌似不符合要求。
- behavior 就是一般的题目，比如如何handle意见不同的情况。我是结合我实际情况回答的。总之一个原则：communication solves all the conflicts
- 三零一，还有一个ez的题目，具体我不太记得了。
- TicTacToc用android写的变种，我用了一些jetpack的东西，比如viewmodel和livedata
- android写service。算法997？还有一个现出的题目dp，这个我好像当时现场推出来，没见过原题。
5. 三叔，一个ez的题目，然后来了一个我没见过的题目。估计这轮弱。
如果有人知道请告诉下我。
大意是有1～n，可以组合成1,[1,2],[2,1],[1,2,3],[2,1,3],[3,2,1]...
如果把结果放在一个1d的array里，结果是什么？
我用了一个很naive的做法。但是貌似不符合要求。
第一轮利口846
第二轮利口1182 要求pre compute o（n），follow up二维color矩阵，要求pre compute o（mn），之后query o（k），k为query次数
第三轮bq
第四轮利口16
第二轮利口1182 要求pre compute o（n），follow up二维color矩阵，要求pre compute o（mn），之后query o（k），k为query次数
第三轮bq
第四轮利口16
第一轮1240 given a rectangle x*y, minimum numbers of squares to fit in the rectangle第二轮 design a parking lot
第三轮 flip an array of 1, 0. minimum moves for flipping all. O(n)
第四轮 要斯而散 还有一个follow up，问增加一个array of K len, 每次选的数字要乘以对应的arrayK 里的数，求最大sum
第三轮 flip an array of 1, 0. minimum moves for flipping all. O(n)
第四轮 要斯而散 还有一个follow up，问增加一个array of K len, 每次选的数字要乘以对应的arrayK 里的数，求最大sum
第三轮：
给一个matrix，每个row只能选一个数，如果选第i行第j个元素，第i+1行第j+1的元素，那这两个元素之间有penalty： （j + 1 - j） = 1; 让求最后最大和是多少。思路： dp可以是O（mn^2）的m是行数，n是列数。大哥问能不能优化时间到O（mn），其实不太知道，大哥疯狂带着我做，最后一个for loop是O（n）可以用两个left[] 和 right[]预处理最大数。
给一个matrix，每个row只能选一个数，如果选第i行第j个元素，第i+1行第j+1的元素，那这两个元素之间有penalty： （j + 1 - j） = 1; 让求最后最大和是多少。思路： dp可以是O（mn^2）的m是行数，n是列数。大哥问能不能优化时间到O（mn），其实不太知道，大哥疯狂带着我做，最后一个for loop是O（n）可以用两个left[] 和 right[]预处理最大数。
给一个Oncall表 {张三：1 - 5， 李四： 5 - 7， 王五： 2 - 10} 这个格式是 “谁：什么时候”
要求返回一个格式为“时间段：谁（们）”的表。比如上面的例子的return就是：
1 - 2 张三
2 - 5 张三 王五
5 - 7 李四 王五
7 - 10 王五
return type没有规定，总之这个return能找某时间段有谁在Oncall
第三轮： 国人大哥。人很nice. 一直鼓励我，引导我。给两个string, 叫他们old和new吧，比较他们，已知old是通过改变了一个substring变成new的，分析出old是怎么变成new的。
return三个东西，变化的种类（增加，减少，替换），变化的开始位置（some index in the old string）, 变化的部分是什么（从什么变成什么）
例子1： old: "aaabb" new: "aaaccbb"
old通过在index = 3 的位置增加了一个"cc"变成new
例子2： old: "aaaccbb" new: "aaaddbb"
old通过在index = 3的位置把"cc"替换为"dd"变成new
例子3： old: "aaaccbb" new: "aaac1234"
old通过在index = 4的位置把"cbb"替换为"1234"变成new
需要自己去多问clarification questions。问的越多信息越多，比如讨论return type
要求返回一个格式为“时间段：谁（们）”的表。比如上面的例子的return就是：
1 - 2 张三
2 - 5 张三 王五
5 - 7 李四 王五
7 - 10 王五
return type没有规定，总之这个return能找某时间段有谁在Oncall
第三轮： 国人大哥。人很nice. 一直鼓励我，引导我。给两个string, 叫他们old和new吧，比较他们，已知old是通过改变了一个substring变成new的，分析出old是怎么变成new的。
return三个东西，变化的种类（增加，减少，替换），变化的开始位置（some index in the old string）, 变化的部分是什么（从什么变成什么）
例子1： old: "aaabb" new: "aaaccbb"
old通过在index = 3 的位置增加了一个"cc"变成new
例子2： old: "aaaccbb" new: "aaaddbb"
old通过在index = 3的位置把"cc"替换为"dd"变成new
例子3： old: "aaaccbb" new: "aaac1234"
old通过在index = 4的位置把"cbb"替换为"1234"变成new
需要自己去多问clarification questions。问的越多信息越多，比如讨论return type
题目内容：让我写一段代码来返回一个迷宫，没了。其他基本啥也没给，不是他不给信息，而是本身就不给什么限制，自由发挥。和面试官讨论能获得好的方向，比如，Input是什么, 迷宫要怎么表示，这个迷宫有几个解等等。
input: 迷宫的宽，迷宫的高，起点，终点
output: 一个设计好了的迷宫
input: 迷宫的宽，迷宫的高，起点，终点
output: 一个设计好了的迷宫
酒肆刘 -- follow up, O(1) space
拔散散 -- 变体，如果给的index， source不match就throw，有overlap也throw。 因为都两个case都throw，我认为time complexity是O(S), visiting each char const time, 面试官似乎不太同意-- follow up， 把loop对换，用原string做main loop，two pointers搞定
只有一个根的DAG, 求最长路径长度
-- followup, 多个根
-- followup, 求最长路径
拔散散 -- 变体，如果给的index， source不match就throw，有overlap也throw。 因为都两个case都throw，我认为time complexity是O(S), visiting each char const time, 面试官似乎不太同意-- follow up， 把loop对换，用原string做main loop，two pointers搞定
只有一个根的DAG, 求最长路径长度
-- followup, 多个根
-- followup, 求最长路径
第一轮: 算法 给你一包色子, 每个色子只有两个面, 点数从1-6. 两个色子如果有一端的点数相等就可以连起来. 比如4-1 和6-1 可以连成6-1-1-4 (色子可以左右置换后连) 求给定的这包色子中 能连起来最长的色子数是多少
1. 世界杯淘汰赛阶段，每个球队夺冠的概率。
已知有个表格知道16强两两之间胜负的概率，以及一个16强对阵表。
求输入任意一个球队，返回这个球队最终夺冠概率。
2. 知道两条rule， #1 朋友的朋友是朋友， #2 敌人的敌人是朋友。
给你一串输入: 1 2 F, 2 3 F, 4 5 E, 5 6 E, 等等。。。
前面两个数字表示两个人，第三个f, e 表示关系。
根据两条rule，构建出所有隐藏的关系。
3. 已知
“key1” -> "3489"
"key2" -> " %key1% is awesome!"
.....
给任意一个statement = “ %key1% !!!!! %key2% !!!!!!” 把其中%% 里面的内容替换成value。 注意多层嵌套替换
4. 一个二叉树，把所有子节点的value挪到根节点需要多少move。
move 的定义： 子节点的一个value，移动到上一层算一个move，再移动到上一层，又算一个move。
follow up， 如果要求每个子节点必须保留value=1，其余都move到根节点，需要多少move
已知有个表格知道16强两两之间胜负的概率，以及一个16强对阵表。
求输入任意一个球队，返回这个球队最终夺冠概率。
2. 知道两条rule， #1 朋友的朋友是朋友， #2 敌人的敌人是朋友。
给你一串输入: 1 2 F, 2 3 F, 4 5 E, 5 6 E, 等等。。。
前面两个数字表示两个人，第三个f, e 表示关系。
根据两条rule，构建出所有隐藏的关系。
3. 已知
“key1” -> "3489"
"key2" -> " %key1% is awesome!"
.....
给任意一个statement = “ %key1% !!!!! %key2% !!!!!!” 把其中%% 里面的内容替换成value。 注意多层嵌套替换
4. 一个二叉树，把所有子节点的value挪到根节点需要多少move。
move 的定义： 子节点的一个value，移动到上一层算一个move，再移动到上一层，又算一个move。
follow up， 如果要求每个子节点必须保留value=1，其余都move到根节点，需要多少move
Leetcode 1194 and 979
465. Optimal Account Balancing
Actionable Items
It is so much fun to go over those interview algorithms. I do learn a few good algorithms. I think that I should break into more blogs about those algorithms. I like to learn one by one.
No comments:
Post a Comment