https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/
这道题是求最短subarray包含所有set的数吧，sliding window
第四轮是一个黑小哥，一个设计题，设计如何design一个可以返回随机数的函数， 出了bug怎么办之类的
第四轮：国人小哥，n-ary tree里面的最长路径。
面试官是个印度姐姐，感觉她有点笨拙（或者是认真仔细），我们bb了很多没用的，所以最后只有题目，没有follow up question
题目很简单，输出string “5*3+10” 的运算结果，我是用stack做的
我觉得我解法还是挺常规的，但是不知道为什么她好像有些细节处理的地方不是很明白，稍微浪费了一点时间
Set<String> res = new HashSet<>();
findUtil(n, 0, (char)('A'-1), new StringBuilder(), res);
return res;
}
void findUtil(int n, int curr, char max, StringBuilder sb, Set<String> res) {
if (curr >= n) {
res.add(sb.toString());
return;
}
for(int i = 0 ; (char)('A' + i) <= max ; i++) {
sb.append((char)('A' + i));
findUtil(n, curr + 1, max, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
max = (char)(max + 1);
if (max > 'Z') return;
sb.append(max);
findUtil(n, curr + 1, max, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
第一面很简单，利口200，1和0换成圈圈叉叉，经典面筋。第二面先问了两个BQ，然后问了道OOD。设计一个limiter，input是event的个数和cooldown时间，每次调用来查询还有没有event在继续。
有些同学问limiter的问题，是这样的：
补充内容 (2018-11-30 05:45):
limiter = new MyLimiter(2, 60)
limiter.MayContinue() // true
limiter.MayContinue() // true
limiter.MayContinue() // false
sleep(60)
limiter.MayContinue() // true
sleep(30)
limiter.MayContinue()//true
补充内容 (2018-11-30 05:47):
这是面试官给的例子，用系统时间，不用实现sleep()。
希望能帮到大家～～
水滴浸树
第一题，是一个台湾小姐姐，给了一颗树状图，每一个节点代表一个水塔，每一条边代表一根水管，每根水管上有一个数字，代表水流过这个水管需要多久。问题是从root开始灌水，需要多久可以灌满整个图。follow up是如果图里有环该怎么做。
思路：
把树当成带权图，然后bfs或者dfs即可
应该是最小生成树把，遍历图里面的所有节点但是要求权值最小。
完全树求节点
第二题，是一个北欧小哥，题目是给一颗complete tree，每课树节点只有left，right这两个变量，求特定标号的节点在不在树上。follow up是给定一颗complete tree，求这棵树有多少节点。
思路：
见前文
特定标号的节点 是什么意思，是说我们需要preprocess tree每个node带一个标号，然后判断input 标号在不在里面嘛？还是traverse whole tree find node.val == input val
如果是n 个node的话，node ID 是从1 到n。根是1，然后2,3，再下一层4,5,6,7。。。这么排下来。traverse whole tree 算法复杂度太高了 O(n)的。可以根据给定的index的二进制表示来判断从根开始往左还是往右搜索，这样算法复杂度是O(lgn）
LRU和LFU
第三题，一个中东小哥，比较简单，竟然是LRU和LFU……，都是老题了，比较幸运。
思路：
见lc
Subarray包含所有set里的数
第一轮是 给一个list，一个set，问这个list里面有没有一个Subarray能够包含所有set里面的数
这道题是求最短subarray包含所有set的数吧，sliding window
找photo id
第三轮是很迷茫的印度大哥。。input output都没说太清楚，就是给一个list of like ，每一个Like包含 photo id和timestamp，然后要我output出所有的photo id，这些photo id需满足，在当时是最大的，同时在24小时里也是最大的。。。贼迷茫
resource picker
第四轮是设计一个resource picker，有两个api getResource() 和Return resource() ,assume有1billion个resource，然后只有一台机器，1GB memory，问如何实现 getResource()和returnResource()
思路：
bitmap,
机器人左上到右上(频率 10)
第一轮是中国小哥，查了linkedin是staff engineer。。出了一个很简单的dynamic programming的题，就是给一个matrix，从一个grid 到另一个grid，只能往右上，右，右下三个方向走， 求有多少种走法。利口 六四变种
思路：
前文总结
n层楼m个房间关灯
第二轮是一个南亚人，出了一个很有意思的题：一栋楼有n层，每层有m个房间加一个过道，每条过道两侧有楼梯，只能通过两侧的楼梯上下楼。现在这栋楼里有一部分房间开着灯，每走过一个房间的cost是1，现在要把所有的房间的灯关掉，求问minimum cost是多少。 这题可以用动态规划解，也可以用dfs解，思路就是只有两种情况，爬左边的楼梯或者爬右边的楼梯，也就是一个binary tree，所以dfs可以暴力解
思路：
- 如果不上楼，只下楼，用dp逐行扫描
dp[i][0]代表第i层从左边下楼的最小cost dp[i][1]第i层从右边下楼的最小cost，dp[i][0] = dp[i - 1][1] + # of rooms in level i - 1 / dp[i - 1][0] + 2 * farest room with light on
dp[i][1]同理
dp[i][1]同理
2. 如果可以上下楼 （按照楼主描述，应该是不考虑上下楼）
天际线
第三轮是一个烙印， 利口原题 skyline
lc原题
code：
Provider: Leetcode discussion
class Solution {
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> sides = new ArrayList<>();
for(int[] b: buildings) {
// open side
sides.add(new int[]{b[0], b[2]});
// close side
sides.add(new int[]{b[1], -b[2]});
}
Collections.sort(sides, (a, b) -> {
if(a[0] != b[0]) return a[0] - b[0];
else return b[1] - a[1];
});
List<int[]> res = new ArrayList<>();
// sweeping line, the height of points on the line
Queue<Integer> line = new PriorityQueue<>(Collections.reverseOrder());
line.offer(0);
int prev = 0;
for(int[] side: sides) {
prev = line.peek();
if(side[1] > 0) line.offer(side[1]);
else line.remove(-side[1]);
if(prev != line.peek()) {
res.add(new int[]{side[0], line.peek()});
}
}
return res;
}
}
Random Number Generator
第四轮是一个黑小哥，一个设计题，设计如何design一个可以返回随机数的函数， 出了bug怎么办之类的
计算矩阵的dot product
(Provider: Stella Qiu)
电面：给定一个n*n矩阵和整数r, c，计算矩阵第r行和第c列的dot product.
solution: naive for loop，时间复杂度O(n)，空间复杂度O(1)
follow up: 如果矩阵是sparse matrix。设计数据结构来表示这个矩阵，并计算第r行和第c列的dot product.
solution: 矩阵可以用一个rowMap(HashMap<Integer, HashMap<Integer, Integer>>)和一个colMap(HashMap<Integer, HashMap<Integer, Integer>>)表示。从rowMap中找出key为r的HashMap<Integer, Integer>，这个map中的key表示column index，value表示矩阵中element的值。同理，从colMap中找出key为c的HashMap，key表示row index，value是element value。再找出两个map中相同的key，将它们的value相乘并求和。时间复杂度O(n)，空间复杂度O(n)。
矩阵中找最长线
电面：和LC 562 Longest Line of Consecutive One in Matrix 类似
lc solution：用三维数组压缩代码
public int longestLine(int[][] M) {
int rows = M.length;
if (rows == 0) return 0;
int cols = M[0].length;
int res = 0;
// 0 horizaental, 1 vertical, 2 diagonal, 3 anti-diagonal
int[][][] dp = new int[rows][cols][4];
for (int i = 0 ; i < rows ; i++) {
for (int j = 0 ; j < cols ; j++) {
if (M[i][j] == 1) {
dp[i][j][0] = j > 0 ? dp[i][j-1][0] + 1 : 1;
dp[i][j][1] = i > 0 ? dp[i-1][j][1] + 1 : 1;
dp[i][j][2] = (i > 0 && j > 0) ? dp[i-1][j-1][2] + 1 : 1;
dp[i][j][3] = (i > 0 && j < cols - 1) ? dp[i-1][j+1][3] + 1 : 1;
res = Math.max(dp[i][j][0], res);
res = Math.max(dp[i][j][1], res);
res = Math.max(dp[i][j][2], res);
res = Math.max(dp[i][j][3], res);
}
}
}
return res;
}
LC 399 Evaluate Division (汇率题， 频率10+)
电面：给一堆钱和他们直接转换的汇率
A B 3 A = 3 * B
B C 7 B = C * 7
C D 1 C = D * 1
D C 1 D = C * 1
实现 double convert(String currency1, String currency2)这个函数， 输入两个货币，返回他们之间的汇率。
确认眼神后确定输入都是valid， 汇率都是正数，有小数
需要自己建立图，需要考虑自己换自己的情况
思路：
- 建立图，首选dfs方法
- 如果有多次查询，让优化查询时间可以用map cache或者用union find做
Jan 9
Valid word abbreviation(lc408) + unique word abbreviation(lc288) + word abbreviation(lc527)
一开始是就是easy那个，找abbreviation， 接着是给你一个sting[] 和一个string abbr判断是否是unique abbreviation. 最后是给你一个string[] 和一个String abbr, 找出这个string[]里abbreviation是abbr的所有string
思路：lc原题
拿棋子 （频率 5）
给定一个棋盘，里面有一些棋子。你能移走这个棋子，当且仅当这个棋子的同行同列有其它棋子。要求最多能移走多少棋子
思路：LC 947
follow up ：返回拿的路径，其实就是让用dfs不要用union find。每次移除棋子的时候加入路径就好
人车匹配 （见首页，频率 20+）
- 人车匹配，说了bfs和pq，写的pq。follow up有tie怎么办，小哥说第一次出这个题让我自己想怎么处理，就随便说了
买卖股票1和4
- 蠡口姚八巴（lc188） 先写1个transaction 然后实现k transaction 最大profit
如果k小于天数的一半，状态机
状态1: 第一次买入股票后的最大profit
状态2: 第一次卖了股票后的最大profit
状态3: 第二次买入股票后的最大profit
状态4: 第二次卖了股票后的最大profit
状态2: 第一次卖了股票后的最大profit
状态3: 第二次买入股票后的最大profit
状态4: 第二次卖了股票后的最大profit
…...一共2*k个状态
在新的一天，对于每个状态，我们可以选择停留在昨天的状态，或者通过买卖股票转移，如果状态转移后的profit比停留小，我们选择停留在昨天的状态
在新的一天，对于每个状态，我们可以选择停留在昨天的状态，或者通过买卖股票转移，如果状态转移后的profit比停留小，我们选择停留在昨天的状态
如果k大于天数的一半，贪心做法
Log Class，猜数字，矩阵最长连续路径
刚刚面完的狗家onsite，来地里汇报一下面经。题都不难。
第一轮国人大哥。给Log class, 然后给一个list里存的都是log，一个max number, 叫你找出最佳的切割点满足切割出来的log总数小于等于max(思路binary search 参考lc410)
第三轮是非常激情的白人大哥，聊了五分钟简历。题是输入matrix，找到最长的连续的递增路径
第四轮是我觉得最不爽的，面试官全程基本没有提示，根本不互动，低头狂敲键盘。也是一个log class。然后写一个函数，每次调用该函数的时候判断，如果在10s内的某个log数超过5，raiseAlert。raise后在某个10s内该log数小于等于3后，clearAlert。这轮我真的已经累了累了， 然后写的也很乱。代码最后面试官最后说他觉得work，但我觉得其实并不一定， 哈哈哈哈哈哈哈。
|
多支树剪支
第一题 一个多支树，有的node有颜色 剪掉所有没有蓝色subnode的branch
写一个recursive的preorder就行
后面非常间接的想问iterative怎么写 我反应慢 半天才知道他是想问这个 然后提了一下stack的写法 就没时间了
思路
wildcard match变种b
第二个人 类似leetcode wild card match
给个regex pattern，树的形式，给个string 问有没有march
regex pattern用tree表示
分情况讨论 recursive写
函数签名
Boolean isMarch(node regex, string s)
思路
参考代码
I
匹配search index和input phrase
第三个人 给你google的search index， 再给你一个input phrase，问有没有match
input自己定义 但是存的是每个词在每个document里面出现的位置。
这题不难 不用准备哈哈 o of nk的题 k是phrase长度 因为你可以define input format
n是每个单词的index size
参考解法
构造包含所有vocab都superstring
第四个 在一个语言里面 用一个string 包含所有这个语言里的vocab
他先说了这个问题 但是没有要求用真的vocab ，而是四个digit的code等于一个string 包括所有possible 4 digit code
第四个题没要求最小 我们讨论出一个optimazation就直接做了 没要求best case
也许可以follow up 但是也许我做的慢 就没机会 哈哈
这个题 如果你们去sunnyvale还是有可能碰到的 这个哥说他问了200+人这个问题
类似 lc cracking the safe吗？（感觉像）
Cpp参考代码（Provider: Dingli Zeng）
如果词汇量未知，单词长度未知，可以考虑用trie来辅助搜索，用前一个单词在trie里寻找prefix相同的单词，找到后，从trie里移除。这个方案不一定是最优解，但肯定可以得到superstring。
下面是我的答案：
string getSuperString(string keys[], int n) {
unordered_set<string> unprocessed; /* hashset for unprocessed words */
int maxlen = 0; /* max length of any word */
struct TrieNode* root = getNode(); /* trie */
for (int i=0; i<n; i++) {
insert(root, keys[i]);
unprocessed.insert(keys[i]);
if(maxlen < keys[i].length()) maxlen = keys[i].length();
}
string res;
while (unprocessed.size() > 0) {
int prevLength = maxlen - 1;
if(prevLength > res.length()) prevLength = res.length();
while(prevLength > 0) {
string prev = res.substr(res.length() - prevLength);
if(startWith(root, prev)) { /* modify search method as startWith if the node is the end of word or has children */
string word = getWord(root, prev); /* modify search method by adding traversal to locate the first word having the prefix */
res += word.substr(prevLength);
remove(root, word);
unprocessed.erase(word);
break;
}
prevLength--; /* reduce the size of prefix if not found a match */
}
if(prevLength == 0) { /* no prefix match, just get the first one from the hashset */
string word = *unprocessed.begin();
res += word;
remove(root, word);
unprocessed.erase(word);
}
}
return res;
}
Jan 22
矩阵流水的问题，水会从一个点流向周围八个点钟=中最小的那个，一直流到local minimum为止，给一个矩阵，然后把每个matrix cell更新为每个点最后水流到的低点的坐标
给数组照相
第二轮，国人小姐姐，进来的时候刚好听到我对三姐说have a good night, 用中文说让我别紧张。。我顿时感动的啊，我面试还没见过中国人。。后来英文面的，是面鲸有过的题，给一个数组take snapshot，每次take snapshot后存一下当时的数组状况。后面会访问某一次snapshot时数组的值。
N-ary Tree的最长路径(LC559)
第四轮：国人小哥，n-ary tree里面的最长路径。
public int maxDepth(Node root) {
if(root == null) return 0;
int maxDepth = 0;
for(Node child : root.children)
if(child != null) maxDepth = Math.max(maxDepth, maxDepth(child));
return maxDepth + 1;
}数组偶数位大和奇数位小
一个已经sort 过的数组。[1,2,3,4,5,6,7] for example.
把它变成一个，偶数位的数字要大于所有这个位置之后的数字。 奇数位的数字要小于所有这个位置之后的所有数字。
上面那个例子变形之后应该是[7, 1, 6, 2, 5, 3, 4]
follow up如果数组没有sort 过呢？
思路：
如果不需要in-place，用一个额外的buffer数组双指针merge
如果需要in-place
- [1, 2, 3, 4, 5 , 6, 7]
- 将原数组分成两半，先reverse后半部分, [1, 2, 3, 7, 6, 5, 4]
- 然后用shuffle string的方法将数组shuffle
参考代码：
Provider: null
public void reform(int[] source) {
int mid = source.length / 2;
reverse(source, mid, source.length - 1);
if(source.length % 2 == 0) shuffle(source, 0, source.length - 1);
else shuffle(source, 0, source.length - 2);
}
private void shuffle(int[] nums, int left, int right) {
if(left >= right) return;
if(left + 1 == right) {
swap(nums, left, right);
return;
}
int len = right - left + 1;
int mid = left + len / 2;
int lMid = left + len / 4;
int rMid = mid + len / 4;
reverse(nums, lMid, mid - 1);
reverse(nums, mid, rMid - 1);
reverse(nums, lMid, rMid - 1);
shuffle(nums, left, left + (len / 4) * 2 - 1);
shuffle(nums, left + (len / 4) * 2, right);
}
private void reverse(int[] nums, int left, int right) {
int l = left, r = right;
while(l < r) swap(nums, l++, r--);
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
看题目似乎是leetcode Wiggle sort I & II
求从start能否所有路径到end
给一个state machine的图，每个节点是一个state，问某一个节点是不是唯一可以走到success state。可以有多条路，但是必须都通向唯一的success state。 dfs秒了，优化到O(N) ，大哥让我找找更快的方法，我想了半天硬着头皮说 worst case还是要访问所有节点, 真的不知道还有什么方法了, 可以hint吗？大哥很开心的告诉我对的没有更快的方法了。然后还剩十分钟写了个Top K。
求两个subarray的差值
第三轮 白人小哥。套了个外壳，不过题目大意是，有一个数组，分成两个subarray，求所有的两个subarray的差值。注意是所有的，不是求最小差值。做题前问问题clear了一些条件，subarray可以是empty的，元素是1-10000的int，想起来了再补充。
补充：把原array分成两个之后，求两个subarray中的元素的和的差值 math.abs(sum(sub1) - sum(sub2))
删除相同字母的pair
第四轮 白人大叔（老爷爷），给一个string，相邻两个字母如果分别是同个字母的大小写，就删掉这个pair。example： aBbA 返回aA. 然后follow up是可以递归消除 aBbA 返回“”. 然后又扯了一个big integer的实现什么的没说完就到时间了。老爷爷人很好，一直笑眯眯的，后来我没写完他跟我说这是你的homework。
https://www.geeksforgeeks.org/recursively-remove-adjacent-duplicates-given-string/
隔段时间统计player的得分
第五轮 白人小哥。 类似于一个设计题。有一个游戏，每个player做不同的任务有不同得分，每三十秒统计一次得分最高的人，整个游戏结束后返回在任意三十秒得分最高的<player，得分, 开始时间>的一个tuple。这轮的小哥全程低头敲代码记录，不管问什么都是好好好对对对up to you。最后我写完了以后，他问我怎么优化，然后扯了cpu cache，大哥讲兴奋了在纸上写写画画给我讲了一堆cpu 优化的事儿，想不起来一个名词非要查清楚告诉我，最后还跟我说别紧张这些都不是面试内容，就是希望我会这些就pretty cool。
房子到buildings到最短路径
题目是 leetcode 317 shortest distance from all buildings. 略微有些改动， 中间加了些 blocks 用2表示。我当天一面完晚上就在 leetcodes上碰到这道题了，不知道算不算不幸
给一个grid，里面有0（表示空地，可以通过），1（表示building，不能通过），2（block，不能通过），现在需要在一块空地上建造一个house，需要house到所有的1距离和最短
思路：
每遇到一个1，我们为它跑一次dijkstra算法得到每一块可以到达该building的空地距离它的最短距离
同时我们需要统计每块空地能到达的building的数量，我们只关心能到达所有building的空地
图中的边不带权值，dijkstra算法的队列可以用普通队列实现
Time Complexity: O(kn)，k为building数量，n为格子数量
找list中有给定prefix的所有String
给一个 String 类型的list都小写 ，然后还有一个String 类型的 prefix也小写， 要求是返回一个list 找出在给定list中所有以这个prefix开始的所有String
Example：
list : ["word","work","apple"]
prefix "w"
结果就是返回 一个list，里面有"word" 和 "work"
然后分别用了暴力解法和trie，分析时间复杂度。
Example：
list : ["word","work","apple"]
prefix "w"
结果就是返回 一个list，里面有"word" 和 "work"
然后分别用了暴力解法和trie，分析时间复杂度。
思路:
- 暴力解法 : 直接用startsWith挨个匹配
- DFS + Trie
三个数字能否组成合法日期
1. 给三个integers, 判断这三个integers组成的（a,b,c）是否构成一个valid date.
yyyy-MM-dd也算valid， MM-dd-yyyy也算valid， 要考虑所以可能的合法的date格式。
补充：
给三个integer，然后可以让这三个integer分别作为year, month 和day，然后看他们能不能组成一个有效的日期
注意corner case
思路：
- 考虑leap year和non-leap year
- 考虑负数和0
- 月份范围1-12
- day范围1-31
- year范围正整数
参考代码：
Provider: null
public boolean canFormDate(int[] nums) {
return firstFrom(nums, 0);
}
int[] days = new int[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
// yyyy-mm-dd
private boolean firstFrom(int[] nums, int curr) {
if(curr >= nums.length) return true;
for(int i = curr ; i < nums.length ; i++) {
if(curr == 0) {
if(nums[i] > 0) {
swap(nums, curr, i);
if(firstFrom(nums, curr + 1)) return true;
swap(nums, curr, i);
}
} else if(curr == 1) {
if(nums[i] >= 1 && nums[i] <= 12) {
swap(nums, curr, i);
if(firstFrom(nums, curr + 1)) return true;
swap(nums, curr, i);
}
} else {
int year = nums[0];
int month = nums[1];
if(month == 2) {
// leap year
if((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
if(nums[i] >= 1 && nums[i] <= 29) return true;
} else {
if(nums[i] >= 1 && nums[i] <= 28) return false;
}
} else {
if(nums[i] >= 1 && nums[i] <= days[month-1]) {
return true;
}
}
}
}
return false;
}
private void swap(int[] nums, int i , int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
Follow up: 判断上一题的date是否是ambiguous
比如（2018,5,6）可以是2018年5月6号，也可以是2018年6月5号，这就算ambiguous，产生了歧义。
思路
看一个数字是否能满足year，month，day中的多个限制
RLEIterator，
国人大哥，上来直接做题
热身题：
What's the difference between s.equals("abc") and "abc".equals(s). 没指名任何方向，想到什么说什么。
热身题：
What's the difference between s.equals("abc") and "abc".equals(s). 没指名任何方向，想到什么说什么。
思路: (Yunwen Zhu：好像是s为null的话，一个exception,一个false )
第二题：
类似LC 900，next只用返回下一个element就可以了，还需要实现hasNext.
第二题：
类似LC 900，next只用返回下一个element就可以了，还需要实现hasNext.
热身题目:
String.equals -> compare reference -> compare length -> compare chars one by one
“abc” is in the constant pool.
RLEIterator 变种
Code
Provider: LC discussion
class RLEIterator {
private int[] A;
private int p;
public RLEIterator(int[] A) {
this.A = A;
p = 0;
}
public int next() {
while (p < A.length - 1 && A[p] <= 0) {
p += 2;
}
if(p >= A.length - 1) return -1;
A[p]--;
return A[p - 1];
}
public boolean hasNext() {
while (p < A.length - 1 && A[p] <= 0) {
p += 2;
}
if(p < A.length - 1) return true;
else return false;
}
}
}
LC Basic Calculator II
面试官是个印度姐姐，感觉她有点笨拙（或者是认真仔细），我们bb了很多没用的，所以最后只有题目，没有follow up question
题目很简单，输出string “5*3+10” 的运算结果，我是用stack做的
我觉得我解法还是挺常规的，但是不知道为什么她好像有些细节处理的地方不是很明白，稍微浪费了一点时间
N行诗的所有rhyme组合 (LC940 Distinct Subsequences II 变种)
一首N行的诗的所有RHYME的组合。N=1， 韵脚A = B =C =。。。输出{A}就可以， N=2 输出{AA，AB}。。当时用N基于N-1的类似BFS的算法做的
我是这么做的，每次新加一个字母有两种选择： 1.从已经出现的字母里面随意选一个 2. 从没有出现的字母里面选一个字典序列最小的
时间复杂度 O(n * B(n))，其中 B(n)是Bell number， 这块是面试官给了提示的。
|
就一个字母一个字母的加，直到长度为n，每次加字母的原则就我说的那俩个，可以用一个hashset记录已经出现过的字母。实现就是通常的bakctracking。
比如n = 3，过程是这样的
A => AA => AAA,
A=> AA=>AAB,
A => AB=>ABA,
A=> AB=>ABB,
A=>AB=>ABC
比如n = 3，过程是这样的
A => AA => AAA,
A=> AA=>AAB,
A => AB=>ABA,
A=> AB=>ABB,
A=>AB=>ABC
Code
Provider: null
Set<String> findRhyme(int n) {Set<String> res = new HashSet<>();
findUtil(n, 0, (char)('A'-1), new StringBuilder(), res);
return res;
}
void findUtil(int n, int curr, char max, StringBuilder sb, Set<String> res) {
if (curr >= n) {
res.add(sb.toString());
return;
}
for(int i = 0 ; (char)('A' + i) <= max ; i++) {
sb.append((char)('A' + i));
findUtil(n, curr + 1, max, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
max = (char)(max + 1);
if (max > 'Z') return;
sb.append(max);
findUtil(n, curr + 1, max, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
Morris 遍历
Code
Provider: GeeksforGeeks
void inOrder(TreeNode root) {
if(root == null) return;
TreeNode curr = root;
while (curr != null) {
if(curr.left != null) {
TreeNode predecessor = findPred(curr);
if(predecessor.right == null) {
predeccessor.right = curr;
curr = curr.left;
} else {
predecessor.right = null;
System.out.print(curr.key);
curr = curr.right;
}
} else {
System.out.println(curr.key);
curr = curr.right;
}
}
}
TreeNode findPred(TreeNode root) {
TreeNode curr = root.left;
while (curr.right != null && curr.right != root) {
curr = curr.right;
}
return curr;
}
计算等式中x的值
LC 640 Solve The Equation
给定input是一个valid的str，一次方程 ，只有x，数字，space, +, -, =, 比如“ x + 21 - x = 12 - x”， 计算x的值。
followup是加括号怎么做。
followup是加括号怎么做。
Code (不带括号）
Provider: (Fill your name)
/**
* cntx记录x前面的系数
* sum记录和
*/
double calcX(string equation) {
int flag = 1, sign = 1;
int cntx = 0, sum = 0, tmp = 0;
for (int i = 0; i < equation.size(); i++) {
cout << equation[i] << endl;
if (equation[i] == '=') {
sum += tmp * flag * sign;
tmp = 0;
flag = -1;
sign = 1;
continue;
}
if (isdigit(equation[i])) {
tmp = tmp * 10 + equation[i] - '0';
} else if (equation[i] == '+' || equation[i] == '-') {
tmp = tmp * sign * flag;
sum += tmp;
tmp = 0;
sign = equation[i] == '+' ? 1 : -1;
} else if (equation[i] == 'x') {
if (tmp == 0) cntx = sign == 1 ? cntx + 1 : cntx - 1;
else {
tmp = tmp * sign * flag;
cntx += tmp;
tmp = 0;
}
}
}
sum += tmp * sign * flag;
return sum * (-1.0) / cntx;
}
Idea:
- use co to record the total coefficients of x
- use sum to track the total sum of numbers
- Recursion to solve the brackets
Code (带括号)
Provider: null
// return: res[0]: sum of numbers, res[1]: coefficients
private int[] calculate(char[] exp, int[] index) {
int[] res = new int[2];
int sign = 1;
int num = 0;
while (index[0] < exp.length) {
if (Character.isDigit(exp[index[0]])) {
num = num * 10 + (exp[index[0]] - '0');
index[0]++;
} else if (exp[index[0]] == '+'
|| exp[index[0]] == '-') {
res[0] += sign * num;
if (exp[index[0]] == '+')
sign = 1;
else
sign = -1;
num = 0;
index[0]++;
} else if (exp[index[0]] == 'x') {
if (index[0] == 0 ||
!Character.isDigit(exp[index[0] - 1])) {
res[1] += sign * 1;
} else {
res[1] += sign * num;
}
num = 0;
sign = 1;
index[0]++;
} else if (exp[index[0]] == '(') {
index[0]++;
int[] tmp = calculate(exp, index);
res[0] += sign * tmp[0];
res[1] += sign * tmp[1];
num = 0;
sign = 1;
} else if (exp[index[0]] == ')') {
index[0]++;
res[0] += num * sign;
return res;
}
}
res[0] += num * sign;
return res;
}
Number of Island和limiter
第一面很简单，利口200，1和0换成圈圈叉叉，经典面筋。第二面先问了两个BQ，然后问了道OOD。设计一个limiter，input是event的个数和cooldown时间，每次调用来查询还有没有event在继续。
有些同学问limiter的问题，是这样的：
补充内容 (2018-11-30 05:45):
limiter = new MyLimiter(2, 60)
limiter.MayContinue() // true
limiter.MayContinue() // true
limiter.MayContinue() // false
sleep(60)
limiter.MayContinue() // true
sleep(30)
limiter.MayContinue()//true
补充内容 (2018-11-30 05:47):
这是面试官给的例子，用系统时间，不用实现sleep()。
希望能帮到大家～～
Code:
Provider: null
/*
start
0
*/
class MyLimiter {
private int events;
private int coolDown;
private long startCoolDown;
private int currEvents;
public MyLimiter(int events, int coolDown) {
this.events = events;
this.coolDown = coolDown;
this.currEvents = events;
}
public boolean MayContinue() {
if (currEvents > 0) {
currEvents--;
if (currEvents <= 0) {
startCoolDown = System.currentTimeMillis();
}
return true;
} else {
long now = System.currentTimeMillis();
if (now - startCoolDown < (long) coolDown * 1000) {
return false;
} else {
currEvents = events;
currEvents--;
if (currEvents <= 0) {
startCoolDown = System.currentTimeMillis();
}
return true;
}
}
}
}
