https://www.1point3acres.com/bbs/thread-460780-1-1.html
第一轮 黑人小哥哥。完全没有口音。就是一道least used element remove的题，领扣应该有原题。 用的hashmap+double linked list。 但是他问我为什么不用array的时候，忽然傻了，说了也可以。结果搞了很久，经过他的提示才想起不行的原因，然后写码写得一塌糊涂。指针和对象搞得有点混乱。最后他指出了问题之后，没时间改就结束了。
146 LRU
第二轮 拜仁小哥哥。 第一题过于简单忘了，第二题好像是用已经有的每次取4096的字符串的function取implement取任意长度的字符串的function。感觉就是easy难度，写得一塌糊涂还是，写完，他开始纠正我问题，也是没时间改就结束了。这么简单的题我估计后面还有follow up没来得及问。
157,158 Read N Characters Given Read4
第三轮 拜仁小哥哥。领扣猜词，用dfs做完最差的解法就到时间了。狗带。
843. Guess the Word
第四轮 拜仁小哥哥 一棵树 每个节点有包含这个节点以及他所有子节点树木的信息，求中序遍历地k个节点是啥。因为一开始完全懵住，就自己在那里找规律，结果他问你要跟我说说你想法吗，估计这轮连沟通都要打叉了！然后找规律做出来。第二题是给个graph 上面有石头，有花，石头会挡住花。问站那个点看到的花最多。我只想到用dp做 O(n^2)复杂度。但是没时间写完代码。
#1 见下面460761
#2 开一个2d数组
逐行扫描，记录花朵数量，碰到石头就停止并更新所有该行走过的空格。石头后面重新开始
然后再按列扫描，结果加到2d数组里。O(m * n)
好多坑，要小心, 见注释
public static void main(String[] ss) {
int[][] g = {
{1,0,2,1},
{0,1,1,1},
{1,2,0,2},
{0,0,1,0}};
int[] rt = mostFlowers(g);
System.out.println(rt[0] + " " + rt[1]);
}
private static int[] mostFlowers(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
int f = 0, start = 0;
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
f++;
}
if (grid[i][j] == 2) {
while (start < j) {
matrix[i][start] = f;
start++;
}
start = j + 1;
f = 0;
}else if (j == n - 1) {
while (start <= j) {
matrix[i][start] = f;
start++;
}
}
}
}
for (int i = 0; i < n; i++) {
int f = 0, start = 0;
for (int j = 0; j < m; j++) {
if (grid[j][i] == 1) {
f++;
}
if (grid[j][i] == 2) {
while (start < j) {
matrix[start][i] += f;
if (grid[start][i] == 1) matrix[start][i]--;
start++;
}
start = j + 1;
f = 0;
}else if (j == n - 1) { // 末尾要考虑
while (start <= j) { // 末尾特殊考虑 start == j
matrix[start][i] += f;
// 当前花朵不能计算2次
if (grid[start][i] == 1) matrix[start][i]--;
start++;
}
}
}
}
int[] rt = new int[]{-1,-1};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rt[0] == -1 || matrix[i][j] > matrix[rt[0]][rt[1]]) {
rt[0] = i;
rt[1] = j;
}
}
}
return rt;
}
------------------------------------https://www.1point3acres.com/bbs/thread-460777-1-1.html
第一轮：印度小哥，看起来比我还紧张。有m个人一起出去旅游 n个event 每个event (i,j) 代表第i个人花了多少钱 最后要均摊 要求给出任意一种均摊solution， 比如一共花了45 A花了20 B花了10块 C花了15 B要给A5块。lz一开始随便想了一个pq，小哥说可以就让我写，写完发现根本不用pq，所以后面又花了小部分时间讨论优化。没什么follow up
类似LC 465 https://shibaili.blogspot.com/2018/11/465-optimal-account-balancing.html
第二轮：国人小姐姐，比第一轮的印度小哥还紧张，模拟TCP的拥塞控制协议，basically只需要你画出状态转移的图然后随便写一些代码，比如什么时候重传，CWND怎么update之类的。小姐姐很nice，先问我学没学过network，我说学过但是很久不用了，然后小姐姐帮我梳理了大致的原理。
午饭轮 印度大哥，应该工作好几年了，结婚戒指抢镜。（string bean比冰块还硬，忍着泪水吞下去的。）然后上楼喝了咖啡，午饭轮一般不给feedback，吃好喝好就完事了。
下午
第三轮：刚工作一年的小哥，口音是native但是看起来像印度裔。给一个长度为n的数组，所有相同的元素在数组中都是相邻的，for example 1,1,1,3,4,0,0,0,0,0,9，让你返回任意一个出现次数大于n/k的元素，k是随便一个常数。确认细节之后先提出one pass，小哥说可以让我开始写，写完让分析时间空间复杂度，然后问如何优化。可以先确定候选的list，因为任意给定k的情况下，候选值最多为k个，之后二分确定start end position，复杂度从logN
Solution #1, one pass, linear
Solution #2. 因为最多只能有k个候选值，所以我们可以对 [1 * n / k - 1], [2 * n / k - 1], [3 * n / 3 - 1].... [i * n / k - 1]... 做2分法，找到左右的最远距离，来跟n/k做对比。如果存在符合要求的数，那它一定会存在在上面的至少一个点
O (k lg n / k) < O (n)
public static void main(String[] ss) {
// int[] g = {1,1,1,0,0,3,3,3,3};
int[] g = {1,1,1,1,3,4,0,0,0,0,0,9};
int rt = foo(g, 3);
System.out.println(rt);
}
private static int foo(int[] nums, int k) {
int n = nums.length;
for (int i = n / k - 1; i < n; i += n / k) {
if (isValid(nums, i, k)) return nums[i];
}
return -1;
}
private static boolean isValid(int[] nums, int i, int k) {
int n = nums.length;
// 注意不要超过范围
int left = getLeftPos(nums, i - n / k < 0 ? 0 : i - n / k, i);
int right = getRightPos(nums, i, i + n / k > n - 1 ? n - 1 : i + n / k);
return n / k < right - left + 1;
}
private static int getRightPos(int[] nums, int left, int right) {
int val = nums[left];
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid + 1] != val && nums[mid] == val) return mid;
else if (nums[mid] == val) left = mid + 1;
else right = mid - 1;
}
return left;
}
private static int getLeftPos(int[] nums, int left, int right) {
int val = nums[right];
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid + 1] == val && nums[mid] != val) return mid + 1;
else if (nums[mid] == val) right = mid - 1;
else left = mid + 1;
}
return left;
}
第四轮（感觉这轮有丶小炸）：（印度小哥，迟到了一会儿，先进来说因为是最后一轮，所以时间充裕，结果到最后说有会要开，没到45分钟就提前走了）随机迷宫。我记得地里有提到这个面经，先给思路，然后写代码，写完发现dfs有丶小问题，可能会死循环，然后就开始改，改的过程面试官提出了一个更好的修改意见，无奈和印度小哥口语沟通有丶坎坷，第一遍理解错了，第二遍才理解他的意思，然后把好不容易改好的代码又擦了重新改，最后没改完小哥要开会就走了。希望小哥念在我本该还有几分钟才到45的份上网开一面不计较这个没改完的代码。。
maze generation. 输入是int[][] board, int[] start, int[] dest,返回一个int[][] maze. 这题题意比较复杂。简单来说就是让你随机生成一个迷宫， 条件是：
(1) 你肯定要生成一些墙，这些墙宽度为1，意思就是board[0][0] - board[0][3]可以是墙，s宽度为1， 长度为4。 但是不能生成board[0][0] - board[1][3]这样的厚墙（2*4). from: 1point3acres (2) 要求这个迷宫有且仅有一条路可以从start到达destination， 另外对于那些不是墙的blank cell，也要有可以从start到达它的路径。 也就是说不能有一些孤岛是不能到达的
(3) 后来大哥给我简化了一点，如果输入board里面已经有一些墙， 用1表示，但是这个迷宫并不是具有通路的，然后让你根据以上条件，生成迷宫。
Solution
ref: https://www.1point3acres.com/bbs/thread-447125-1-1.html
https://zhuanlan.zhihu.com/p/27381213 （重点看）
https://en.wikipedia.org/wiki/Maze_generation_algorithm
写法很简单，典型的dfs。但是还要跟面试官探讨获得具体需求
以下做法是假设终点满足i % 2 == 1 && j % 2 == 1. 如果任意取的话得稍加改动
另外根据题意，墙的厚度不能超过1，不能有多条path通向end(说明path的厚度也不能超过1)。所以可以预先处理maze，而且maze的长宽一定是奇数。
private static int[][] dir = {{2,0},{-2,0},{0,2},{0,-2}};
private static Random random = new Random();
public static void main(String[] ss) {
int row = 21, col = 21;
int start_row = 3, start_col = 1;
int[][] maze = generateMaze(row,col, start_row, start_col);
drawMaze(row, col, maze);
}
private static void drawMaze(int row, int col, int[][] maze) {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
String s = maze[i][j] == 1 ? " " : "#";
if (i == 0 || i == row - 1 || j == 0 || j == col - 1) s = "#";
System.out.print(s + " ");
}
System.out.println();
}
}
private static int[][] generateMaze(int m, int n, int row, int col) {
int[][] maze = initMaze(m, n);
boolean[][] visited = new boolean[m][n];
visited[row][col] = true;
dfs(maze,visited,row + 2,col,row + 1, col);
dfs(maze,visited,row - 2,col,row - 1, col);
dfs(maze,visited,row,col + 2,row, col + 1);
dfs(maze,visited,row,col - 2,row, col - 1);
return maze;
}
private static void dfs(int[][] maze, boolean[][] visited, int row, int col, int wallRow, int wallCol) {
if (row <= 0 || row >= maze.length - 1
|| col <= 0 || col >= maze[0].length - 1
|| visited[row][col]) {
return;
}
visited[row][col] = true;
maze[wallRow][wallCol] = 1;
boolean[] b = new boolean[4];
int count = 0;
while (count < 4) {
int next = getRandom();
if (b[next]) continue;
b[next] = true;
dfs(maze, visited, row + dir[next][0], col + dir[next][1], row + dir[next][0] / 2, col + dir[next][1] / 2);
count++;
}
}
private static int getRandom() {
return random.nextInt(4);
}
// 0 is wall
// 1 is path
private static int[][] initMaze(int row, int col) {
int[][] maze = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i % 2 == 1 && j % 2 == 1) {
maze[i][j] = 1;
}
}
}
return maze;
}
--------------------------https://www.1point3acres.com/bbs/thread-460761-1-1.html
电面 ： 1. unsorted array, 要求把所有负数排到所有正数前面，inplace。这题应该是LC原题吧，two pointer可以秒了。
2. 3sum。
两题码代码加解释应该30分钟不到吧，然后硬聊了10分钟。
onsite：
1. 国人小哥。给定binary tree，value是子树个数，求preorder排序中第K个node，并输出这个node。follow up，只给这个node，你还需要什么条件，最快知道这个node在这个树的preorder排序中排第几位。
Solution
public static void main(String[] s) {
int k = 3;
TreeNode n1 = new TreeNode(1, 4);
TreeNode n2 = new TreeNode(2, 2);
TreeNode n3 = new TreeNode(3, 0);
TreeNode n4 = new TreeNode(4, 0);
TreeNode n5 = new TreeNode(5, 0);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
System.out.println(findK(n1,k).key);
}
static class TreeNode {
public int key;
public int count;
public TreeNode left;
public TreeNode right;
public TreeNode (int key, int count) {
this.key = key;
this.count = count;
left = null;
right = null;
}
}
public static TreeNode findK(TreeNode root, int k) {
if (k == 1) return root;
if (root.left != null) {
if (root.left.count + 1 >= k) {
return findK(root.left, k);
}else {
return findK(root.right, k - root.left.count - 2);
}
}else {
return findK(root.right, k - 1);
}
}
Follow-up, 再给一个父节点的连接
2. 纯behavior。
3. TIC TAC TOE， LC 348. Follow up : 从3行扩展到n行，如何用multi-threading来做，给个idea，写几行关键代码就可以了。
4. 面经题，给string，fonts，然后给个window 说能容纳的最大font是多大。这个很多面经题里都有，二分+强塞就行了 :)
已知screen的高和宽，给你最小和最大的fontSize，要求给定一个string，将string用竟可能大的fontSize显示在screen里。已知两个API getHeight(intfontSize), getWidth(char c, int fontSize)，可以得到每个character在不同fontSize下的高和宽。
https://www.1point3acres.com/bbs/thread-423513-1-1.html
// int getHeight(int fontSize)
// int getWidth(char c, int fontSize)
// 假设所有字符同一个font下height相同
// Font 是单调递增
int getMax(String s, int width, int height, int maxFont, int minFont) {
int rt = 0;
while (minFont <= maxFont) {
int mid = (maxFont + minFont) / 2;
int h = getHeight(mid);
if (h > height) {
maxFont = mid - 1;
}else {
if (getLength(s, mid) > width) {
maxFont = mid - 1;
}else {
rt = mid;
minFont = mid + 1;
}
}
}
return rt;
}
int getLength(String s, int font) {
int rt = 0;
for (int i = 0; i < s.length(); i++) {
rt += getWidth(s.charAt(i), font);
}
return rt;
}
5. 给一个scenario class，里面有3个不同的instance variable （具体是啥忘了）。然后给一堆scenarios，找出出现频率最多的3种scenario（scenario 相同的意思就是内部3个不同的variable都相同）。其实就是把scenario这个class写出来，里面写个hashcod()和equals()。用个hashmap把scenarios过一遍把频率记下来。再自己定义一个size=3的minHeap就可以秒了。考hashing的基础跟实现
1. 对比class相同
2. 递归对比每一个field
3. Object.hash 或者 Arrays.hashCode
--------------------------
https://www.1point3acres.com/bbs/thread-460720-1-1.html
面的职位是SETI
1. 在一个2D的grid里面分布若干person和bike。求最小人车距离之和
求最小sum of distance that each person travels to the assigned bike
2. triple booking
LC 731, triple的话用第2种方法treemap会更方便
3. word link。给个dictionary， 里面的word差一个字可以连在一起（directed， in -> sin ->sing）。求dictionary里面的最长link
Solution: 典型的backtracking dfs。还是得写一遍
1. visited要设
2. 前后加减4种情况都考虑
3. 不能用排序。考虑 ab -> abc -> bc
// 假设只有头尾可变
public static void main(String[] ss) {
Set<String> set = new HashSet<>();
set.add("in");
set.add("sing");
set.add("sin");
set.add("ab");
set.add("abc");
set.add("c");
set.add("bc");
Set<String> cp = new HashSet<>(set);
int rt = 0;
for (String s : cp) {
set.remove(s);
rt = Math.max(rt, dfs(set, s, 1));
set.add(s);
}
System.out.println(rt);
}
private static int dfs(Set<String> dict, String s, int len) {
int max = len;
for (char i = 'a'; i <= 'z'; i++) {
String c = "" + i;
String next = s + c;
if (dict.contains(next)) {
dict.remove(next);
max = Math.max(dfs(dict, next, len + 1), max);
dict.add(next);
}
next = c + s;
if (dict.contains(c + s)) {
dict.remove(next);
max = Math.max(dfs(dict, next, len + 1), max);
dict.add(next);
}
next = s.substring(1);
if (dict.contains(next)) {
dict.remove(next);
max = Math.max(dfs(dict, next, len + 1), max);
dict.add(next);
}
next = s.substring(0, s.length() - 1);
if (dict.contains(s.substring(0, s.length() - 1))) {
dict.remove(next);
max = Math.max(dfs(dict, next, len + 1), max);
dict.add(next);
}
}
return max;
}
4. On call log file - input其实已经是一个个entry，sorted，并不需要parse。要找特定时间范围内oncall的人。follow up是如果有多个这样的log object， entry里面会存在refer到别的log object的情况。这题算是简单的class设计和简单的算法。5. cipher - 给一个key string， 加密别的string。key string其实是offset。比如说ABCD，对应offset 1,2,3,4。根据offset改变input string。然后循环使用key string（就是说 1， 2， 3， 4， 1， 2.。。。）
----------------------
https://www.1point3acres.com/bbs/thread-460696-1-1.html
上来一个24点游戏，leetcode原题，dfs秒之，follow up时间复杂度开始没打对，后来再提示下改对，就是利口流气就原题
LC 679
然后安卓手机锁屏长度为6密码组合，比leetcode同题目稍简单一些，因为只能沿着主对角线滑动了，也做出来，没时间follow up了，利口三无要简易版
LC 351
---------------------------
https://www.1point3acres.com/bbs/thread-460692-1-1.html
其实是跪在第一问，上来就问 输入google.com后会发生什么楼主好久没碰这方面知识，只记得high level，就只说了look up ip addr via DNS之类的
然后一定要我detail
无奈之下说了几个layer, 然后提到TCP，
然后他逼着我说怎么send data
我就记得会分包，然后有好多fields帮助routing啥的。。。。-baidu 1point3acres
尴尬过渡到coding
两问，估计因为上一问实在懵，coding都非常简单，估计已经想好挂我了
一道string arr去重
一道encode arr to string/decode string to arr
Solution:
- DNS lookup, four layers of caches - browser, os, router, ISP
- TCP handshake
- Server sends response
- Browser renders
太坑了吧, T_T
算了，只能怪自己基础不扎实
------------------------------
https://www.1point3acres.com/bbs/thread-460647-1-1.html
刚刚做了19summer intern oa,还是两道原题。祖先树和最近商店感谢地里的面经。求好运～
1. store and hourse 这题给你两个 array, 都是一维的，而是都是int int houses[] and int stores[], 分别代表各house/store 的location. 让你找出每个houses 最近的 stores。 return 一个int array[], index = houses index, value = 最近的stores的location
Solution 另一种方法是只sort stores，然后对每一个house做2分搜索
public static void main(String[] ss) {
int[] houses = {1,5,3,9};
int[] stores = {2,3,7,13};
int[] rt = nearestStores(houses, stores);
for (int i : rt) {
System.out.print(i + " ");
}
}
private static int[] nearestStores(int[] houses, int[] stores) {
Arrays.sort(houses);
Arrays.sort(stores);
int m = houses.length, n = stores.length;
int i = 0, j = 0;
int[] rt = new int[m];
while (i < m) {
while (j < n - 1) {
if (Math.abs(houses[i] - stores[j]) >= Math.abs(houses[i] - stores[j + 1])) {
j++;
}else {
break;
}
}
rt[i] = stores[j];
i++;
}
return rt;
}
2. tree ancestor 给你一个array［］， 每一个element存的是它parents的位置。 给你一个distance n, 是一个 int, 让你 return 一个array，表示每个element与它n距离的ancestor
Solution
public static void main(String[] ss) {
int[] p = {-1,0,0,1,1,2,2,4,5};
int[] rt = nAncestors(p, 2);
for (int i : rt) {
System.out.print(i + " ");
}
}
private static int[] nAncestors(int[] parents, int n) {
int len = parents.length;
int[] rt = new int[len];
boolean[] done = new boolean[len];
for (int i = 0; i < len; i++) {
int count = n;
int p = parents[i];
while (count > 1 && p != -1) {
count--;
p = parents[p];
}
int start = i;
count = n;
while (count > 1 && start != -1) {
if (done[start]) break;
done[start] = true;
rt[start] = p;
start = parents[start];
if (p != -1) p = parents[p];
count--;
}
}
return rt;
}
------------------------------http://www.mitbbs.com/article_t/JobHunting/33451347.html
给你矩阵的每行和每列的和。要你把矩阵的可能都算出来。矩阵都是非负数。
Solution
Dfs + backtracking, 尝试所有的可能性。类似 n queen 和 Sudoku Solver
因为可能性会有很多，count是为了控制打印出第几个可能的矩阵
private static int count = 0;
public static void main(String[] ss) {
int[] r = {6,15,13};
int[] c = {8,14,12};
possible2D(r,c);
}
private static int[][] possible2D(int[] rows, int[] cols) {
int m = rows.length, n = cols.length;
int[][] rt = new int[m][n];
dfs(rt, rows, cols, 0, 0);
return rt;
}
private static void dfs(int[][] matrix, int[] rows, int[] cols, int row, int col) {
if (col == cols.length) {
if (rows[row] > 0) return;
if (row == rows.length - 1) {
if (allColIsDone(cols)) {
count++;
if (count == 1000) printOut(matrix);
}
return;
}
col = 0;
row++;
}
int max = Math.min(rows[row], cols[col]);
for (int i = 0; i <= max; i++) {
matrix[row][col] = i;
rows[row] -= i;
cols[col] -= i;
dfs(matrix, rows, cols, row, col + 1);
rows[row] += i;
cols[col] += i;
}
}
private static boolean allColIsDone(int[] cols) {
for (int i : cols) {
if (i != 0) return false;
}
return true;
}
private static void printOut(int[][] m) {
for (int[] r : m) {
for (int i : r) {
System.out.print(i + " ");
}
System.out.println();
}
}
------------------------------
https://www.1point3acres.com/bbs/thread-460431-1-1.html
LC399
一边写的过程中还问为什么java queue用poll和offer，不用add和remove。（我是不记得了强答）
------------------------------
https://www.1point3acres.com/bbs/thread-460692-1-1.html
LC 128
------------------------------
https://www.1point3acres.com/bbs/thread-460402-1-1.html
最近查面经好多人都碰到股票题目，如：
1）https://www.1point3acres.com/bbs/thread-208578-1-1.html
2nd round: 紧接着进来一个白人大叔。他的macbook air的电池出了问题，先问了hashtable实现方法，于是直接开始出问题。给一个stock，这只股票在不同的timestamp下有不同的price，(800, 1), (700, 2), (900, 3), (400, 4)。 Looks like this. 需要实现几个方法：1.getMaxHistory, 2.getCurrentPrice, 3.Correction, 4. update。比如说刚才给出的例子是900最高，但是如果调用correction，将ts = 3的price改为600，那么最高的将变为800
2）https://www.1point3acres.com/bbs ... p;extra=&page=1
void update(double price, int timestamp) 更新/修正/删除股票价格，其中timestamp大部分时间是递增的，但是有时候发现过去的记录有错误，所以会对过去数据修正或invalidate。对过去数据修正是指input argument中的timestamp是一个已经记录在案的timestamp，让price为function新提供的price；invalidat时候function argument中的price为-1，删除timestamp对应的记录. 1point3acres
double max() 返回历史最大值
double min() 返回历史最低值
double current() 返回最近一次的记录。
我的想法是，不知道大神们有没有更好的对这道题的解读和方法？
1）先问面试官需不需要查询区间内的最大值，最小值；如果查询区间内的，好像只能线段树
2）如果只是查询当前的最大，最小，TreeSe和Hashmapt就能搞定如下。-baidu 1point3acres
class Test {
class StockNode implements Comparable{
public long timeStamp; public double price;-baidu 1point3acres @Override public int compareTo(Object o) {
return Double.compare(this.price, ((StockNode)o).price); }
}
public static void main(String[] args) {
TreeSet<StockNode> treeSet = new TreeSet<>(); Map<Long, StockNode> map = new HashMap(); //.... }
}
Solution
TreeMap
或Heap也可以
------------------------------
https://www.1point3acres.com/bbs/thread-460338-1-1.html
1. 一个中国小姐姐，感觉刚开始面试别人，业务有点不熟练。第一类似于graph里面找从A点出发回到A点的最短loop，要求输出长度以及path，BFS和DFS都说了，BFS更加好，要求我用BFS。要打印path，所以我用了两个queue，小姐姐希望其他更加省memory的做法，没想出来，就按照我的想法写了代码，写完跑了testcase。最后她有讨论一下她觉得可以省memory的做法，用hashmap，但是她好像自己也记不清到底怎么实现了，讲的我感觉不太对，我也没和她继续讨论。第二题类似topological sorting变形，讨论了做法没有实现代码。
2. 一个白人小哥哥，给你一个source string, 要求找长度为K的字母排序最前面的subsequence，一开始思路不明确，先随便讨论了一下brute force的解法，时间复杂度2^n * K，问能不能提高，想出了N*K的解法，写了代码。继续问对于最差的Corner case怎么提高，用上了heap，继续改了代码。follow-up问如果要top 10 subsequence。
Solution
单调递增的stack
public static void main(String[] ss) {
String s = "aidunfghjik";
int k = 5;
System.out.println(topK(s, k));
}
private static String topK(String s, int k) {
Stack<Character> st = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (st.isEmpty()) {
st.push(c);
}else {
while (!st.isEmpty() && st.peek() > c) {
if (st.size() + s.length() - i <= k) return getStack(st, st.size()) + s.substring(i);
st.pop();
}
st.push(c);
}
}
return getStack(st, k);
}
private static String getStack(Stack<Character> st, int size) {
StringBuilder sb = new StringBuilder();
while (!st.isEmpty()) {
if (st.size() <= size)
sb.insert(0, st.pop());
else st.pop();
}
return sb.toString();
}
Follow-up， top 10 subsequences:
如果用以上解法的话得考虑多种情况，取决于单调栈的大小是否大于10
3. 一个白人小哥哥，给你一个map，知道state和state之间相连的关系，再给你一个dictionary，包含words，让你找出从任意一个state出发，每个state取首字母，可以找到的word。讨论的时候小哥说可以重复visit一个state，我就问他那停止条件是什么，他可能自己都没想过这个问题，我就问那就统计字典里最长单词的长度作为停止条件，他说可以的。先用了最简单的hashset和DFS做了，写完代码，问我能improve吗，我就说用trie，可以剪枝，代码重新改了一遍。follow-up问如果是要你找出anagram呢？
看不明白，可能是类似上面460720的那题
4. 一个白人大妈，一道graph题目，给你一个graph，要求你根据给定的order，找出最长的path，不能有环，一开始朝graph方向想，最后发现是用slide window做，代码写完以后，跑了testcase, 大妈有问一些基础问题，类似linkedlist和arraylist区别，hashset原理。第二题是一道经典BFS题目，一个board上面有Bacteria，Air以及blank，找出有几团B是可以接触到A的，其实就是number of islands变形，讨论了解法没有实现代码。
第一问应该是类似LC329
------------------------------
https://www.1point3acres.com/bbs/thread-460274-1-1.html
面的Embedded software engineer，同学内推，跳过了电面直接去的onsite . check 1point3acres for more. 刷了很多题准备了很多算法，结果方向全错了，embedded的考了很多OS, Kernel 的东西 1.第一轮就遇到三哥，题很简单，一个先增再减的array, 先verify是不是有效的, 直接O(n), 然后再找最大值，二分。然后follow up先问我了二分o(logN)的系数，我说汇编展开，读内存，在比较，跳转这些的话大概是7，8条指令吧，瞎说的。 然后他说不止，问我二分是不是比顺序的O(N)快。从embedded的角度来说。我说内存访问是连续的话，应该会比二分这样跳转的快很多，那N比较小的时候应该是O(N)其实更快，但是N很大了应该还是要二分。也不知道他满不满意。这里其实想考的是cache里的prefech, 我只答到了有cache，连续访问的时候应该会把整个内存block都Load到cache里，二分的话每次都是一个cache miss所以时间长。但是当时没想起prefech这个词。。
2. 第二轮是一个hardware timer的应用。只有一个hw_timer, 让用它实现多个software_timer。 给了3个API，hw_timer_timeout(int timeout), 这个可以设置hardware timer 的timeout，然后时间到了就会给一个硬件中断，触发handle_hw_timer()这个call back, 然后还有个get_hw_timer_current_time()。 每次调用hw_timer_timeout就会覆盖之前的一个timeout，重新开始。让我实现一个timer_set_timeout(int timeout, void* cb)。思路也很简单，用个priority queue把currenttime和relativetimeout存起来，然后每次在handle_hw_timer()里把下一个要到的时间设置进去就行。但是留给我的时间太少了，前面问了十几分钟简历。最后这题也没写代码，就让我说思路。说完了就问我一些线程保护的问题，这个set_timer里要加个mutex,然后问我mutex怎么实现，我说了可以用atomic instruction,一般cpu都有test_and_set, 然后又问了我multicore的情况下怎么实现atomic，这里没回答上来。其实也是一样的，在一个shared_memory上用test and set 或者compare and swap就行。
3. 第三轮，美国老大爷，考了个搜索。给一个array of objects, 一个API，bool compatible(T t1, T t2), 可以判断两个object是不是compatilbe 的，然后让我返回这个array里compatilbe的两个元素的index.很简单直接o(n2)就行。然后他说现在把array改成无限长的。当时的循环就不能用了，只能从（0，1），（0，2）一直找到（0，无穷）。 然后改了一下循环的写法就行，（0，1）（1，0）（0，2）（1，1）（2，0）这样一层一层往下走就可以。最后又问，假设这个array可以有负的index, 从负无穷到正无穷。思路还是一样的，想象一个矩阵，一层一层往外找就行。
4. 第四轮，美国geek老大爷。上来就先问了一堆概念，semaphore 和mutex的区别。reader/writer mutex这些的，问了太多已经忘了，反正大部分都是我没听说过的Unix Kernel里用到的一些黑科技。这轮全程都有点懵逼。问了一会问题，就给了道题目，写一个Logger, 有write 和read两个API， 然后别的process会用这个logger来Log event.然后event要按时间顺序排序，先发生的event可能后到，有个populate delay. 一开始想的用个priority queue。他说不对，然后给了点提示，然后我说要用linked list. 最后实现出来其实是个doubly linked list,就是个链表的基本的插入操作，很简单。就是在插入前后加个lock就可以了。最后他说这个其实可以用read/write mutex,然后不用把这个list都lock，只用在写的时候lock最近几秒钟的list就可以
-------------
https://www.1point3acres.com/bbs/thread-460120-1-1.html
终于尘埃落定有空来写写面经
朋友内推狗云，直接onsite，5轮coding，无系统设计
第一轮非常温柔地问了LC169+LC229
第二轮给两个tree，每个leaf node上有一个string，问tree1 leaf node上的string按从左到右的顺序加在一起和tree2 leaf node上的string按从左到右的顺序加在一起是否相等，不能用extra space，extra stack也不行（不能recursive traverse）。tree node的structure可以自行设计。
Solution, 加一个parent pointer跟visited flag在tree node上。然后类似2 pointer的写法
public static void main(String[] ss) {
Node n1 = new Node();
n1.s = "abc";
Node n2 = new Node();
n2.s = "abc";
Node n3 = new Node();
n3.s = "aabc";
n1.left = n2;
n1.right = n3;
n2.parent = n1;
n3.parent = n1;
Node m1 = new Node();
m1.s = "ac";
Node m2 = new Node();
m2.s = "abc";
Node m3 = new Node();
m3.s = "aabc";
m1.left = m2;
m1.right = m3;
m2.parent = m1;
m3.parent = m1;
System.out.println(isSame(n1 , m1));
}
static class Node{
public Node parent;
public Node left;
public Node right;
public String s;
public boolean visited;
public Node() {
parent = null;
left = null;
right = null;
s = "";
}
}
private static Node getNextLeaf(Node node) {
while (node != null) {
if (node.visited) node = node.parent;
else if (node.left != null && !node.left.visited) node = node.left;
else if (node.right!= null && !node.right.visited) node = node.right;
else if (node.left == null && node.right == null) {
node.visited = true;
return node;
}else {
node.visited = true;
node = node.parent;
}
}
return null;
}
private static boolean isSame(Node root1, Node root2) {
int i = 0, j = 0;
Node n1 = getNextLeaf(root1);
Node n2 = getNextLeaf(root2);
while (true) {
if (i >= n1.s.length()) {
i = 0;
n1 = getNextLeaf(n1);
}
if (j >= n2.s.length()) {
j = 0;
n2 = getNextLeaf(n2);
}
if (n1 == null && n2 == null) return true;
if (n1 == null || n2 == null) return false;
if (n1.s.charAt(i) == n2.s.charAt(j)) {
i++;
j++;
}else {
return false;
}
}
}
第三轮给两个set，implement两个function，一个返回一个intersect set，一个返回一个union set。时间只能O(1)
第四轮three sum <= X
第五轮高频面经题，从tree里面移除一些node，把剩下的一堆tree放在list里return
得找找是什么题
------------------------------
https://www.1point3acres.com/bbs/thread-460117-1-1.html
第一轮题目和这个楼主一样：
https://www.1point3acres.com/bbs ... 6orderby%3Ddateline
我感觉就是给你一个doubled linked list，然后给了一帮node，求出这些node中哪些是连在一起的。 比如第一个list是abcdefghijk，第二个是abdghi，答案就是3(ab连着，d单独一组，ghi连着）
Solution #1 类似LC128
Solution #2
如果前后两个元素有一个在集合里，说明是和已知的某个集合连着的，所以count不变
如果前后都不在集合里，说明是自成一个集合的，所以count++
如果前后两个元素都在集合里，说明这个家伙把左边的集合和右边的集合连起来了，合二为一count--
我有follow up：删除指定的block
如果给定里block的前后2个node，应该简单
第二轮信号真的很差，杂音很多，会有些听不清……
有一些磁盘被分成了若干个sectors，设计两个api：
save(index): 检查该sector是否free，是的话标记成occuiped，返回true。否则返回false
find(index): 如果该sector是free，并且有更高位的sector也是free，返回更高位的free sectors中的最小index。否则返回-1
第二个api的要求有点绕，举个例子：
[0, 0, 1, 1, 0, 1, 1, 1] 0: free, 1: occuiped
find(0) return 1
find(1) return 4
find(4) return -1
find(2) return -1
Solution: doubly linked list + hashmap
public static void main(String[] ss) {
int[] a = {0, 0, 1, 1, 0, 1, 1, 1};
Sect s = new Sect(a);
System.out.println(s.find(0));
System.out.println(s.find(1));
System.out.println(s.find(4));
System.out.println(s.find(2));
}
static class Node{
public Node pre;
public Node next;
public int val;
public Node(int val) {
this.val = val;
pre = null;
next = null;
}
}
static class Sect{
private Map<Integer, Node> map;
private Node start;
private Node end;
public Sect(int[] sectors) {
map = new HashMap<>();
start = new Node(-1);
end = new Node(-1);
start.next = end;
end.pre = start;
Node itr = start;
for (int i = 0; i < sectors.length; i++) {
if (sectors[i] == 1) continue;
Node node = new Node(i);
map.put(i, node);
insert(itr, node);
itr = node;
}
}
private void insert(Node cur, Node node) {
Node next = cur.next;
cur.next = node;
node.pre = cur;
node.next = next;
next.pre = node;
}
private void remove(int index) {
Node node = map.get(index);
Node pre = node.pre;
Node next = node.next;
pre.next = next;
next.pre = pre;
node.pre = null;
node.next = null;
map.remove(index);
}
public boolean save(int index) {
if (!map.containsKey(index)) {
return false;
}
remove(index);
return true;
}
public int find(int index) {
if (!map.containsKey(index)) return -1;
if (map.get(index).next == end) return -1;
return map.get(index).next.val;
}
}
------------------------------https://www.1point3acres.com/bbs/thread-460104-1-1.html
10.26 svl昂赛，四轮几乎全部都是面经题，利口六八四，六八五 + 汇率 + 利口三五九，自行车 + random generate a maze。感觉自己还是比较幸运的吧，没有碰到特别难的题，除了最后一道题花了很久才做完。. check 1point3acres for more.
lc684,685, redundant connection I, II.
lc399
lc359, 自行车 关键得看：https://www.cnblogs.com/lightwindy/p/9808666.html
random generate a maze 同460777第4轮
------------------------------
https://www.1point3acres.com/bbs/thread-460051-1-1.html
大约一个月前面的吧，拖延到现在才写。
在职9个月跳槽。面的狗狗家的infra组。HR直接找的。聊了一下目前工作的内容就约了面试。
面试小哥是跟Jeff Dean做TPU 的，问的都比较偏底层。
上来直接做题。问题很简单：如何释放掉一颗二叉树的内存。
一开始听的有点懵。因为一直在写java，我直接说 garbage collection 会自动收的。。。。
小哥说没有garbage collection，自己用 c/c++ 调用 delete 实现。
方法一：recurrsion：先删孩子，再删parent。
小哥问：递归在production上潜在影响？
我：爆栈。
小哥要我详细解释system heap怎么爆栈的。
我：一顿解释。。。
接下来，方法二：那就把recurrsion写个iteration版呗。
小哥问：空间占用
我：最坏是树的深度。
小哥问：如果树很深，严重不平衡，甚至直接成linked list了，怎么降空间占用，最好降到O(1)，不care时间复杂度。
那好，方法三：拆树吧。
1）从root 开始，先把右孩子连到最左叶子的左孩子。
2）然后吧root->left当作newRoot
3）释放oldRoot内存。
4）回到1）迭代。
小哥问：如果care时间呢？
我想用morris 遍历一遍。面试时间快到了，没继续说。
之后又跟小哥聊了一下tensorflow. device placement 的一些算法。就结束了。
一周后hr电话据了。
不知道问题在哪。自己感觉可能是前面占用时间太多了，有一些点没聊透彻。
也可能hr看简历自己本来做过系统优化的research， 又是全职。bar比new grad高一些。
回馈地里，祝大家都有心仪offer。
------------------------------
https://www.1point3acres.com/bbs/thread-460042-1-1.html
nput: an array of char, such as {a,b,c}
设计一个方法，每一次被调用就返回一个string,由input array 里面的char组成。 要求是，1）每次输出的string，前面都没有出现过 2）输出的string要尽可能的compact, 不能是a, aa, aaa, aaaa,...
Solution
类似进制转换，都是稍微有些不同，{a, b, c} 对应的是{1, 2, 3}
被注释掉的是进制转换
public static void main(String[] ss) {
char[] arr = {'a','b','c'};
Foo f = new Foo(arr);
// int base = 2;
// int a = 8;
// String rt = "";
// while (a > 0) {
// rt = a % base + rt;
// a /= base;
// }
//
// System.out.println(rt);
for (int i = 0; i < 20; i++) {
System.out.println(f.getNext());
}
}
static class Foo{
private char[] arr;
private int dec;
private int n;
public Foo(char[] base) {
arr = base;
dec = 1;
n = arr.length;
}
public String getNext() {
String s = "";
int i = dec;
while (i > 0) {
s = arr[(i - 1) % n] + s;
i = (i - 1) / n;
}
dec++;
return s;
}
}
follow up:
3) 相同的字符不能连续出现超过 n 次
2种思路，＃1一种是当遇到重复的时候，abort掉，增加计数重新计算
＃2用一个list记录所有被抛弃的，每次都先从被抛弃里面开始搜索
------------------------------
https://www.1point3acres.com/bbs/thread-459920-1-1.html
When people send messages on their phones they sometimes modify word spelling by adding extra letters for emphasis. For example if you want to emphasize 'hello' you might write it 'hellloooooooo'. Let's call the 'l's and the 'o's 'word extensions'.
Assumption: Regular text contains 2 or fewer of the same character in a row, while word extensions have 3 or more of the same character in a row.
Question: Given an input string representing one word, write a method that returns the start and end indices of all extensions in the word.
Example: hellloooooooo Return [[2,4],[5,12]]
Follow Up:
Now we want to spell-check extended words. You have a boolean function that takes in a string, boolean isDictionaryWord(String s). Implement a function bool isExtendedDictionaryWord(String s) that will return:
-- True if isDictionaryWord(s) is true
-- True if you collapse the extensions in the word and it is a dictionary word
-- False otherwise
For example let's assume isDictionaryWord("hello") is true, and isDictionaryWord("xyz") is false. Then we want:
. 1point3acres
isExtendedDictionaryWord("hello") == true
isExtendedDictionaryWord("heeello") == true
isExtendedDictionaryWord("xyz") == false-baidu 1point3acres
每一个extension只能condense到出现一次或两次
第一题很快就写完了扫一遍就行，followup一开始想用iterative的方法写没有写对，再改用递归写时间来不及了，而且没有写对忘记把不用展开的Characters添加进去了。
45min结束开始聊了会天，小哥是Ads组的，我问了问他用不用YouTube一天用多久他说不怎么用但原来和朋友上传过Game Parody的视频。
感觉要在欢声笑语中打出GG了。
Solution + follow up
public static void main(String[] ss) {
String s = "hellooooo";
List<int[]> l = getExtend(s);
for (int[] i : l) {
System.out.println(i[0] + " " + i[1]);
}
// follow up
String a = "hellooo";
Set<String> set = new HashSet<>();
set.add("helo");
set.add("hello");
System.out.println(isExtendedDictionaryWord(a, set));
}
private static List<int[]> getExtend(String s) {
List<int[]> rt = new ArrayList<>();
int start = 0, end = 0;
for (;end < s.length(); end++) {
if (s.charAt(start) == s.charAt(end)) continue;
if (end - start > 2) {
int[] r = {start, end - 1};
rt.add(r);
}
start = end;
}
if (end - start > 2) {
int[] r = {start, end - 1};
rt.add(r);
}
return rt;
}
private static boolean isExtendedDictionaryWord(String s, Set<String> dict) {
return helper(dict, s, "", 0);
}
private static boolean helper(Set<String> dict, String ori, String sofar, int i) {
if (i >= ori.length()) return dict.contains(sofar);
int itr = i;
while (itr < ori.length() && ori.charAt(i) == ori.charAt(itr)) {
itr++;
}
if (itr - i <= 2) {
return helper(dict, ori, sofar + ori.substring(i,itr), itr);
}
return helper(dict, ori, sofar + ori.substring(i, i + 2), itr)
|| helper(dict, ori, sofar + ori.substring(i, i + 1), itr);
}
------------------------------https://www.1point3acres.com/bbs/thread-460338-1-1.html
面试官一上来 说 let's begin with some warm up questions. 就问了一堆data structure的问题。我记得的有：difference between bst and hash table. bst和hash table的搜索时间. 既然bst 搜索时间久then why bst? hash table为啥是O(1)? 能记住的就这些了然后问了大概15分钟。。。 接着上了一道判断是不是balanced tree. 秒了
lc110
然后。。他很吐槽的说了一句 你怎么没有mobile develop的经历呀？ （楼主是转专业的也确实是没做过这方面的。。QAQ）然后我把我做过的项目和他说了一下他显然没有认真在听。。。感觉他可能觉得我是转专业的，就又问了我一道easy题，remove duplicate 问了一下时间复杂度和worst case
No comments:
Post a Comment