468673
1. 原点有一个modem，周围有N台设备用两个X和Y坐标数组给出，求第K近的设备并将距离取上整返回，类似荔筘蛾药毋，只不过那题是第K大，这是第K小
LC215
2. Meeting Room II 基本是原题，只是interval给的是Start和End的两组数组，但是思路是一样的
LC 253
----------------------------
https://www.1point3acres.com/bbs/thread-469425-1-1.html
第一轮：
1. 给 array A B, 输出去掉A B中所有重复元素的array。for example: ([1,1,1,1,2,3], [1,2,4])-->[1,1,1,3,4]。一开始用了两个dictionary/hashmap，follow up 要求仅使用一个
一个map
public static void main(String[] ss) {
int[] a = {1,1,1,5,6,1,2,3};
int[] b = {1,2,4,9,6,6,1};
System.out.println(removeDup(a, b));
}
public static List<Integer> removeDup(int[] a, int[] b) {
Map<Integer, Integer> m = new HashMap<>();
for (int i : a) {
m.put(i, m.getOrDefault(i, 0) + 1);
}
for (int i : b) {
if (m.containsKey(i)) {
if (m.get(i) != 0) {
m.put(i, m.get(i) - 1);
}
}else {
m.put(i, -1);
}
}
List<Integer> rt = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : m.entrySet()) {
for (int i = 0; i < Math.abs(e.getValue()); i++) {
rt.add(e.getKey());
}
}
return rt;
}
2. Coin Change. 1point3acres
LC322
第二轮：
1.Sequence Iterator
2.写一个iterator, initialize的时候输入另一个list iterator,然后在另一个iterator的基础上实现hasNext和next:
for example:
初始化时候输入 [a,a,a,b,b,a]的iterator
while(it.hasNext()):
print(it.next())
这段代码会输出 (a,3) (b,2) (a,1)
这道题一开始讨论了半天没搞清题意，可能feedback不太好加面了一轮
Solution:
public static void main(String[] ss) {
List<String> l = new ArrayList<>();
l.add("a");
l.add("b");
l.add("b");
l.add("c");
Iterator<String> i = l.iterator();
ItrHelper itr = new ItrHelper(i);
while (itr.hasNext()) {
System.out.println(itr.next());
}
}
public static class ItrHelper{
private Iterator<String> itr;
private String cur;
private boolean itrHasNext;
public ItrHelper(Iterator<String> itr) {
this.itr = itr;
cur = null;
itrHasNext = itr.hasNext();
}
public boolean hasNext() {
return itr.hasNext() || itrHasNext;
}
public String next() {
int count = 1;
while (itr.hasNext()) {
String next = itr.next();
if (cur == null) {
cur = next;
}else if (cur.equals(next)) {
count++;
}else if (!cur.equals(next)) {
String rt = cur + " " + count;
cur = next;
return rt;
}
}
if (itrHasNext) {
itrHasNext = false;
return cur + " " + count;
}
return "";
}
}
第三轮：
1.感觉地里见过的，给两个string问第一个能否通过 暂时移走部分字符(总的顺序不能改变)+copy paste 构成另一个
for example: 输入"BZAXYZ"和"ZAZABY",可以"BZAXYZ"+"BZAXYZ"+"BZAXYZ"="ZAZABY"
最简单的办法就是判断是否第二个string中所有字符都在第一个中
follow up: 输出最少需要几次暂时移走+copy paste才能完成
这题写的太慢，
follow up
不断的找longest common subsequence，直到2个string相等
---------------------------------
https://www.1point3acres.com/bbs/thread-469405-1-1.html
大家好，楼主前几天去面了狗狗，准备了很久所以到了一月才面。。四轮面试两轮国人两轮天竺友人，想问一下第三轮这样的情况该怎么处理。
第一轮，三姐，萦绕在我脑海中一个题目，要写两个function，后来优化，本来是o(n) o(n) 后来优化到了o(1) o(logn)。。但是我居然就是想不起来是什么了。。。面完大概早上10:45走的时候我对她说了个have a good night。。。抱歉没想起来
-baidu 1point3acres
第二轮，国人小姐姐，进来的时候刚好听到我对三姐说have a good night, 用中文说让我别紧张。。我顿时感动的啊，我面试还没见过中国人。。后来英文面的，是面鲸有过的题，给一个数组take snapshot，每次take snapshot后存一下当时的数组状况。后面会访问某一次snapshot时数组的值。
得找一找题
午饭，一个外国小哥哥，带我吃了饭还逛了下，回来的时候看到会议室已经坐了人了，门关着的，狗家那个会议室玻璃墙中间是模糊的，上面和下面是透明的。于是小哥就踮着脚去看里面是不是有别人在面试，我就蹲下来歪着头看里面有几条腿。。。然而小哥虽然比我高，但还是不够高，所以最后还是我发现了里面就一个人。。开门的时候看到是三哥，心里惊了一下。
番外：我实习时候遇到的三哥都很好让我觉得三哥有很多好的，但是今年面fb全职和去年面fb实习遇到的三哥都好狠，让我害怕被他们面。就是很rude，经常问一些莫名其妙的问题，有时候发现不重要的错漏就盯着不放，一直耗在那里，浪费我时间。。所以fb实习和全职都一轮电面挂了。。都只做出来了一题。。因此我就很害怕谷歌面试遇到三。俗话说的好，怕啥来啥。。
第三轮，三哥，题目就一句话，让我先随机构造一颗size为N的树。我开始没听到“random”一词，就以为构成一颗树就行。秉着论坛经验贴说的，要提前考虑各种条件。我就开始问他，有木有其他限制，比如形状有木有要求，普通的树还是二叉树，N<=0怎么办等等。。。他就说没有，只要size是N就行了。（我后来知道是random的时候，我觉得他这时候应该高速告诉我要random，他就一开始说了一遍题目，我也没听到random这个词，我觉得他可能当时说了我没注意。。但到了这里，我问过他这些各种边界条件后，我很确定他这次说的是只要N就行）
然后我就开始边说边写，先写了个平衡树，因为觉得这样子左右子结点个数比较好算。完了他说为什么是这样的树勒？我就说了一下，他说你这样只能返回一种类型啊，不是landom的，我要landom的。（请脑补他们说的llllandom，不是rrrrrrrandom....emmmmm）这都是小事，后面才尴尬了。
我就开始random了，我本来写的是每一棵root节点的左子树有rand.nextInt(0,N)个数个子结点，右子树就是N-1-numOfLeft，然后递归构造这棵树。我本以为这是随机的，但是试了下N=3的case，发现并不是。。N=3应该有五种可能，概率都是1/5，我的这个方法概率都是1/6。然后三哥就说你这个概率是不是不对呢？我说是啊，是不对，想了会儿没想好怎么改，就问他hint，他就说你这个概率不对，你应该找到正确的概率。。我就继续看，我就发现了左子树1个节点的时候这一个节点只有一种排列方法，但是左子树2个节点的时候就有两种可能的排列方法了。也就是说我的算法其实把“根节点－一个左子结点－一个右子结点”这样的情况返回概率是2/6，其他四种概率都是1/6. 发现了这里我就想先把unique subtree的个数算出来好了，这种就可以得出每一种tree占全部的概率了。。但我有点动摇，就有问他有木有other hints，他就说你yeah, i do，然后告诉我这个概率不对，你应该找到正确的概率（这就是前一个hint啊...摔! ）。。我以前lc上做过一个题目就是用dp算n个节点树的形状的可能性的，我就和三哥说了，打算先用dp把1-n个节点可以构成的树的形状个数都算出来。三哥说你把关键代码写一下，别写所有的了，我就打算只从for开始写，他说你别写for了，直接写公式好了。。我想了一下，这不写for怎么看得懂公式勒？公式需要用到for循环里的参数啊。。但是我还是先按照他说的只写公式，后来发现不行，我就自作主张还是把for写了。写完他说算的是对的。
然后他就一直在问然后你怎么算出正确的概率呢？我就在说，让我想一下分子分母应该分别是dp[几]，然后他也一直在问。。我心里从landom那里就不淡定了，一直在想着要挂。后期阶段他又一直在旁边说无关痛痒的话，我心里就乱乱的，想了一下没确定分子分母该是哪个，他又说我没时间了，让我问他个问题，就结束了。
代码也没写多少，就一开始递归构造平衡树那个代码，加一个dp公式，还有些画的不同类型的树和一些草稿。。他拍了照。
还有他全程几乎都坐在椅子上看杀父仇人一样看着我，和他说话什么也没什么反馈，就全程黑着脸，问他hint了好几次他也都只是说我概率不对，并没有和其他面试官那样和我“交流问题&解法”的态度。我一看就知道要挂我。。毕竟和之前两次fb电面的天竺哥哥惊人的相似，全程不怎么踩我，盯着一个破绽就一直问问问。
Solution
类似96. Unique Binary Search Trees DP的方法 ，有待证明
第四轮：国人小哥，n-ary tree里面的最长路径。
Solution
只有1个leaf的时候算root＋这个leaf的距离
public static void main(String[] ss) {
Node root = new Node('A');
(root.child).add(new Node('B'));
(root.child).add(new Node('F'));
(root.child).add(new Node('D'));
(root.child).add(new Node('E'));
(root.child.get(0).child).add(new Node('K'));
(root.child.get(0).child).add(new Node('J'));
(root.child.get(2).child).add(new Node('G'));
(root.child.get(3).child).add(new Node('C'));
(root.child.get(3).child).add(new Node('H'));
(root.child.get(3).child).add(new Node('I'));
(root.child.get(0).child.get(0).child).add(new Node('N'));
(root.child.get(0).child.get(0).child).add(new Node('M'));
(root.child.get(3).child.get(2).child).add(new Node('L'));
maxPath(root);
System.out.println(max);
}
public static class Node{
public char key;
public List child;
public Node(char key) {
this.key = key;
this.child = new ArrayList<>();
}
}
static int max = 0;
static int maxPath(Node root) {
if (root == null) return 0;
int max1 = 0, max2 = 0;
for (Node c : root.child) {
int path = maxPath(c);
if (path > max1) {
max2 = max1;
max1 = path;
}else {
max2 = path;
}
}
max = Math.max(max, max1 + max2 + 1);
return Math.max(max1, max2) + 1;
}
---------------------------------
https://www.1point3acres.com/bbs/thread-469256-1-1.html
Sunnyvale
第一轮：国人小哥，leetcode原题应该，求最长valid parenthesis 有O（n）解法
LC32
第二轮：香港（？）小哥，比较基础，给一个数组，还有int top要你实现栈的pop（）函数，double linkedlist删除节点，很基础知识，最后还问了一个sort的问题，但是就说了几句，时间就到了
第三轮：国人小姐姐，面经原题，patition n task into k days to minimize the amount of resources used per day, usage per day is the same, task must be completed sequentially
得找一找
第四轮：国人小哥，给你一个string和list of change(class change{int offset, string before, string after}), 来实现string的更新，follow change无效有几种情况，分别怎么处理
只能想到最笨，最直接的解法
---------------------------------
https://www.1point3acres.com/bbs/thread-469219-1-1.html
一个已经sort 过的数组。[1,2,3,4,5,6,7] for example.
把它变成一个，偶数位的数字要大于所有这个位置之后的数字。 奇数位的数字要小于所有这个位置之后的所有数字。
上面那个例子变形之后应该是[7, 1, 6, 2, 5, 3, 4]
follow up如果数组没有sort 过呢？
Solution
public static void main(String[] ss) {
int[] n = {1,2,3,4,5,6,7};
int[] rt = reorder(n);
for (int i : rt) {
System.out.print(i + " ");
}
}
static int[] reorder(int[] nums) {
int n = nums.length;
int left = 0, right = n - 1;
int[] rt = new int[n];
for (int i = 0; i < n; i += 2) {
rt[i] = nums[right];
if (i + 1 < n) rt[i + 1] = nums[left];
left++;
right--;
}
return rt;
}
---------------------------------
https://www.1point3acres.com/bbs/thread-469186-1-1.html
第一轮 白人小哥。猜词游戏，写一下如何判断player猜词的score（guess word 和 secret word中相同char的个数），然后如何根据history判断guess word是不是good guess。
843
第二轮 白人小哥。给一个state machine的图，每个节点是一个state，问某一个节点是不是唯一可以走到success state。可以有多条路，但是必须都通向唯一的success state。 dfs秒了，优化到O(N) ，大哥让我找找更快的方法，我想了半天硬着头皮说 worst case还是要访问所有节点, 真的不知道还有什么方法了, 可以hint吗？大哥很开心的告诉我对的没有更快的方法了。然后还剩十分钟写了个Top K。
题意不清。如果success state定义是只有incoming edge, 没有outgoing edge话，那么recursion的base case就可以按照这个来写。或者是要知道对terminating state的定义
午餐 白人小哥，聊得挺开心的。午餐的鸡腿不错。
第三轮 白人小哥。套了个外壳，不过题目大意是，有一个数组，分成两个subarray，求所有的两个subarray的差值。注意是所有的，不是求最小差值。做题前问问题clear了一些条件，subarray可以是empty的，元素是1-10000的int，想起来了再补充。
第四轮 白人大叔（老爷爷），给一个string，相邻两个字母如果分别是同个字母的大小写，就删掉这个pair。example： aBbA 返回aA. 然后follow up是可以递归消除 aBbA 返回“”. 然后又扯了一个big integer的实现什么的没说完就到时间了。老爷爷人很好，一直笑眯眯的，后来我没写完他跟我说这是你的homework。
Solution
public static void main(String[] ss) {
String s = "CaeEAC";
System.out.println(deleteSame(s));
}
static String deleteSame(String s) {
Stack st = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!st.isEmpty() && compareTwo(c, st.peek())) {
st.pop();
}else {
st.push(c);
}
}
String rt = "";
while (!st.isEmpty()) {
rt = st.pop() + rt;
}
return rt;
}
static boolean compareTwo(char c1, char c2) {
return Math.abs(c1 - c2) == 32;
}
第五轮 白人小哥。 类似于一个设计题。有一个游戏，每个player做不同的任务有不同得分，每三十秒统计一次得分最高的人，整个游戏结束后返回在任意三十秒得分最高的<player，得分, 开始时间>的一个tuple。这轮的小哥全程低头敲代码记录，不管问什么都是好好好对对对up to you。最后我写完了以后，他问我怎么优化，然后扯了cpu cache，大哥讲兴奋了在纸上写写画画给我讲了一堆cpu 优化的事儿，想不起来一个名词非要查清楚告诉我，最后还跟我说别紧张这些都不是面试内容，就是希望我会这些就pretty cool。
思路
1. 写2个java executor， 一个用来每30s排序，另一个用来跑player的game（这个可有可不有）
2. 或者
总体感觉是五个白人小哥都挺...不太能聊的，但是感觉都很聪明。题都做出来了，交流也还可以，但是感觉有点凉，挂点是第一轮最后要了一些提示，第四轮没写完big integer的东西，这个不知道是老爷爷临时起意还是算是面试内容，第五轮真的太累了，一开始分析问题没太说清楚，后来缓过来改了一些思路，我跟小哥说，对不起我真的太累了，刚才脑子当机了，他说没事的我也经历过，这一天太漫长了，后来也跟我说我解决的pretty fine，不过感觉他过程中态度不积极，可能不是很满意。
抱歉哈第三轮没有说清楚，把原array分成两个之后，求两个subarray中的元素的和的差值 math.abs(sum(sub1) - sum(sub2))
---------------------------------
https://www.1point3acres.com/bbs/thread-468795-1-1.html
感恩节海投的简历年底才收到OA， 拖了一周在今天01/02才胆战心惊地做了。不小心一个小bug改了一个小时才改出来。
幸好最近的题目改过之后还没变 还是黎扣215和253
---------------------------------
https://www.1point3acres.com/bbs/thread-469613-1-1.html
12月 17号面的， 今天刚刚收到onsite的通知。 题目是 leetcode 317 . 略微有些改动， 中间加了些 blocks 用2表示。我当天一面完晚上就在 leetcodes上碰到这道题了，不知道算不算不幸。
心得： 多跟面试官交流 做题的时候一定以跟面交流的为主， 我当时做的时候的方法 在LeetCode上做 就超时了，但是当时面的时候面试官觉得我的方法复杂度okay.
并且，还犯了个可大可小的错误，我知道要写bfs, 定义的辅助函数名字也是 bfs， 但是当时太紧张，条件反射的写了个dfs的body。写到最后我意识到我写的东西是dfs。我跟面试官说
面试官也意识到了，但是由于时间原因，他让我继续完成主函数了，就没改。 比较尴尬。
---------------------------------
https://www.1point3acres.com/bbs/thread-468694-1-1.html
第一轮 sorting network 第一问 写一个算法验证一个sorting network working correctly， 第二问假设可以开无数条线程，需要多少步可以用一个给定的sorting network排完序
Zero One princple, 如果任意一个由｛0，1｝组成的数列可以被sort，则可证明sorting network是可行的
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap28.htm
Follow up: 是线性的
第二轮 有一对box，给定这些box的长和宽，放在坐标轴上，每个box之间要满足一个hgap和一个vgap，让最后所占用的面积最小
题意不清
错误：本质上应该就是排列组合，每2个box形成一个新的box，再随机取第3个box又形成一个新的。
枚举的应该可以解
第三轮 利口 溜散吴 利口久柏
635, 98
第四轮 第一问给定一个triangle sort，让他变成正常顺序的
2分找奇点，线性复制。或者全部用线性
第二问给一个list of （start， end， speed），start和end表示位置，计算出从0-last position的每一段的平均速度. 你可以想象成一条x轴，start是一个x轴上一个点，end是x轴上另一个点，然后这条线段上有一个平均速度。。。input是一个list的这样的线段，会有很多overlap。。。。最后要的output是把x轴上的每一段平均速度都输出出来
Solution#2
怎么想都是O(n^2), 把重复的地方都给切分成单独小段，然后可以指定给对应的线段。
最后对每一条线段做整合
上面的复杂度跟暴力解是一样的：对每一条线段，都遍历整个list
加面
第一问，有放回的从一个桶里拿不同颜色的球，保证每次随机拿出一个球，返回该球的颜色
第二问，如何测试我的算法是不是正确-baidu 1point3acres
第三问，有放回的从桶里拿球，保证每次随机拿出一个球，返回该球的颜色
---------------------------------
https://www.1point3acres.com/bbs/thread-468628-1-1.html
第一轮 一个华裔，题目是找一个以第一个str的后缀和第二个str的前缀match的最长str
ex: hellow owabc 这个就返回2
本质就是kmp
public static void main(String[] ss) {
String s1 = "hellowcd";
String s2 = "owcdabc";
int l = Math.max(longest(s1 + s2),
longest(s2 + s1));
System.out.println(l);
}
static int longest(String s) {
int n = s.length();
int[] table = new int[n];
int j = 0, i = 1;
while (i < n) {
if (s.charAt(i) == s.charAt(j)) {
table[i] = j + 1;
i++;
j++;
}else if (j > 0) {
j = table[j - 1];
}else {
i++;
}
}
return table[n - 1];
}
第二轮 应该是个白人小哥。面经题，棋盘放旗子，第一列0-15，第二列15-30 每一个不能重复，follow up是如果有很多棋盘怎么办，以及怎么优化
（感觉问怎么优化的时候说了几个常规的感觉面试官都不是很满意，一直问还有没有其他的）
题目看不明白
第三轮 应该是个中国大哥，以前从来没见过的题，很难描述，大致是几个函数，getValue(), left(), getParent(), getNext(), 走一遍这个tree的时候同事调用这几个function，然后传给另一个server，另一个server可以通过这几个function还原出这个树，问题是让你写出这几个function的实现。题目不太好理解，面试的时候花了一些时间去理解题目，理解了做出来就很快了。follow up忘记了，但是不难。
题目看不明白，有人说是Morris
午饭一个英格兰小哥，人很nice。吃完饭我建议回去休息吧，但是小哥非常想带我去散步，只能从了。。。
第四轮 一个欧洲大叔，题目是一个str只用一步变为另一个str，然后把这个变换用一个str return回来。比如abc-》def 就是replace abc with def， abc-》a就是delete bc from a，abc-》abcd就是 add d to abc。这个题乍一看简单写起代码就没那么容易，还设计到ood，因为面试官的意思是让我设计一个类可以很好的封装三种操作，用枚举，但是枚举面试中英语怎么说我给忘了，非常尴尬。到最后勉强写完了。
第五轮，韩国小哥，感觉这个小哥最不友好，出的题也是最难。一个n*n的迷宫，每个点都有四个门，中间有谢个障碍，一开始知道从起点到终点是不能通过的，求改变哪一个点的哪一个门的方向可以让从起点到终点可以通过。本来面了一天就已经非常累的，听到这个题直接晕倒。用bfs尽力写了，但是最后还是没有写完。
题目看不明白
门的方向可能是障碍。可以理解为取消一个障碍就能找到通路。算法是对每个障碍找到终点跟起点的通路，找到了就代表可以移除那个障碍。BFS可以做
感觉面试偏难了，可能还是自己水平比较菜。而且狗家面试的时候面试官一直在我写代码的时候跟我说你只有多少时间了，心里就更紧张。面完两天hr就打电话了也没什么feedback就说比较mix，结果面完就知道了，第一轮和第五轮都答的特别不好。无论如何move on了已经。好好准备其他家面试！！
---------------------------------
https://www.1point3acres.com/bbs/thread-468615-1-1.html
1. m*n 的棋盘上有若干棋子,如果同一行或者同一列中还有别的棋子的话,则可以扔掉一个棋子,问最少棋盘上能剩多少棋子.
LC 947
2. 有expiration的字典.
面经题
3. 读有timestamp的文件,给一个起始和终止的时间,返回其中所有的信息
4.给一个图和root,判断这个图是不是一个树.. 1point3acres
UnionFind, 261, 684, 685.
5. 给一个只能读一个固定长度的块的函数, 设计一个可以读取任意指定长度的函数.
157,158
---------------------------------
https://www.1point3acres.com/bbs/thread-468605-1-1.html
10月底MTV Onsite
第一轮：国人大哥 求2个BST相同的元素 要求O1 space 强制要求写Morris Traversal Iterator 血跪。。。
Solution
public class OA {
public static void main(String[] ss) {
Node n50 = new Node(50);
Node n40 = new Node(40);
Node n30 = new Node(30);
Node n1 = new Node(1);
Node n35 = new Node(35);
Node n45 = new Node(45);
Node n60 = new Node(60);
Node n55 = new Node(55);
n50.left = n40;
n50.right = n60;
n60.left = n55;
n40.left = n30;
n40.right = n45;
n30.left = n1;
n30.right = n35;
MoItr itr = new MoItr(n50);
for (int i = 0; i < 8; i++) {
System.out.println(itr.next());
}
}
static class MoItr{
private Node root;
public MoItr(Node root) {
this.root = root;
}
public int next() {
while (root != null) {
if (root.left != null) {
Node pre = root.left;
while (pre.right != null && root != pre.right) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = root;
root = root.left;
}else {
int rt = root.val;
pre.right = null;
root = root.right;
return rt;
}
}else {
int rt = root.val;
root = root.right;
return rt;
}
}
return -1;
}
}
}
第二轮：Snake and Ladder简化版 自定义数据结构 可以写一个1D array 用bfs909
第三轮：给定0-1 Matrix 把1形成的岛的内部的1都变成0 只剩一个周长1
把所有上下左右不是1的数做标记，然后第2次遍历给转换成0
第四轮：给定数组 输出长度为k的increasing subsequence 要求nlogk。。。
Solution,
每次遇到长度增加后，跟之前的长度做对比，如果当前数字可以加入到之前的长度。比之前长度的末尾要小，就直接取array里面的。
另一个方法就是每次加入到dp里面数字，都map到它之前的那个数字的index，最终可以用map串联起来
public static void main(String[] ss) {
// int[] nums = {1,4,8,2,9};
int[] nums = {1,4,8,2,1,2,3,4};
System.out.println(lengthOfLIS(nums, 3));
}
static List<Integer> lengthOfLIS(int[] nums, int k) {
int n = nums.length;
int[] que = new int[n];
int len = 0;
List<Integer> pre = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (len == 0 || que[len - 1] < nums[i]) {
que[len] = nums[i];
len++;
if (pre.size() == 0 || nums[i] > pre.get(pre.size() - 1)) {
pre.add(nums[i]);
}else {
List<Integer> tmp = new ArrayList<>();
for (int j = 0; j < len; j++) {
tmp.add(que[j]);
}
pre = tmp;
}
if (pre.size() == 3) return pre;
}else {
binary(nums[i], que, len);
}
}
return pre;
}
static private void binary(int target, int[] que, int len) {
int left = 0, right = len - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (que[mid] >= target && (mid == 0 ||que[mid - 1] < target)) {
que[mid] = target;
break;
}else if (que[mid] <= target) {
left = mid + 1;
}else {
right = mid - 1;
}
}
}
第五轮：research
过了2周送HC 再过2周HR打电话说fail 没有feedback。。
补充内容 (2019-1-2 02:36):
第四题是要求小于n^2 时间复杂度 类似LIS的题
---------------------------------
https://www.1point3acres.com/bbs/thread-468403-1-1.html
第一轮
List<Interval>，isCovered（int idx）,看idx是否被 list of interval 覆盖，说了如果insert新的interval怎么办
sort + merge, 然后2分查找
第二轮 expiring map
面经题
第三轮
第一题：cat+dog = fish, 就三个string，每个char和digit（0-9）一一对应，找这样一个对应使等式成立 dfs（backtracking） 解决，worst cast 10！
followup：提升， 可提升至 （10！/4！），把左边dfs出来，然后右边能不能assign对应的char即可
Solution
DFS + backtracking。如果只返回boolean的话代码会精简很多
public static void main(String[] ss) {
getMap("cat", "dog", "fish");
}
static void getMap(String s1, String s2, String a) {
Map<Character, Integer> cToI = new HashMap<>();
Map<Integer, Character> iToC = new HashMap<>();
if (dfs(s1 + s2, 0, iToC, cToI,s1.length(), a)) {
System.out.println(cToI);
}
}
static boolean dfs(String s, int index, Map<Integer, Character> iToC, Map<Character, Integer> cToI,
int divider, String target) {
if (index == s.length()) {
return isValid(s, cToI, iToC, divider, target);
}
char c = s.charAt(index);
if (cToI.containsKey(c)) {
return dfs(s, index + 1, iToC, cToI, divider, target);
}
for (int i = 0; i < 10; i++) {
if (iToC.containsKey(i)) continue;
iToC.put(i, c);
cToI.put(c, i);
if (dfs(s, index + 1, iToC, cToI, divider, target)) return true;
iToC.remove(i);
cToI.remove(c);
}
return false;
}
static boolean isValid(String s, Map<Character, Integer> cToI, Map<Integer,Character> iToC, int divider, String target) {
int sum = 0;
for (int i = 0; i < divider; i++) {
char c = s.charAt(i);
sum = cToI.get(c) + sum * 10;
}
int cur = 0;
for (int i = divider; i < s.length(); i++) {
cur = cToI.get(s.charAt(i)) + cur * 10;
}
sum += cur;
int n = target.length();
int tmp = sum;
int count = 0;
while (tmp > 0) {
tmp /= 10;
count++;
}
if (n != count) return false;
boolean flag = true;
List<Character> extra = new ArrayList<>();
for (int i = n - 1; i >= 0; i--) {
char c = target.charAt(i);
if (cToI.containsKey(c) && cToI.get(c) == sum % 10) {
sum /= 10;
continue;
}
if (cToI.containsKey(c) || iToC.containsKey(sum % 10)) {
flag = false;
break;
}
extra.add(c);
cToI.put(c, sum%10);
iToC.put(sum%10, c);
sum /= 10;
}
if (!flag) {
for (Character c : extra) {
iToC.remove(cToI.get(c));
cToI.remove(c);
}
}
return flag;
}
第二题： 给一个树， 给一个api：boolean shouldBeDeleted（Node node)
返回删除所有 should be deleted 节点后的森林
不懂
第四轮 一个2d array， A，可能涂黑或者没涂黑，read(x1,y1,x2,y2)会返回：
全黑： 1 全白： -1， Mix：0,只能通过这个read api 来获取这个2d图的信息
现在要给另外一个api： write（x1,y1,x2,y2）,在一个空白的图上把A画出来
Divide and conquer
void copy(int rows, int cols) {
draw(rows - 1, 0, 0, cols - 1);
}
void draw(int r1, int c1, int r2, int c2) {
if (r1 <= r2 || c1 <= c2) return;
int rt = read(r1, c1, r2, c2);
if (rt == 1 || rt == -1) write(r1,c1,r2,r2,rt);
else {
int midR = (r1 + r2) / 2;
int midC = (c1 + c2) / 2;
draw(r1,c1,midR,midC);
draw(midR + 1, c1, r2, midC);
draw(midR + 1, midC + 1, r2, c2);
draw(r1, midC + 1, midR, c2);
}
}
第五轮
第一题：给一个api，String getNameByIndex(int idx).如果有这个index，就返回name，如果没有index（这个index之后也没有index），就返回null.
实现 Integer getIndexByName(String Name); 如果name存在就返回其index，如果不存在就返回null
存一个map index -> name, 然后反过来name -> List of index, 如果name是按顺序存的，这时候可以用binary search
第二题：给一堆Iterator of sorted Integer, 实现一个iterator of iterators，相当于merge sort出来
类似23. Merge k Sorted Lists
然后问了些基础知识
问了BST和HashMap的区别和实现（没code）
全程交流极好，面完整个人都膨胀了
---------------------------------
https://www.1point3acres.com/bbs/thread-468398-1-1.html
isPalidrome热身
实现iterator(iterator, isPalidrome)
给一个string list 的iterator，实现iterator只返回Palidrome的string
存一个instance level的String，指向下一个palidrome。
---------------------------------
https://www.1point3acres.com/bbs/thread-468318-1-1.html
第一轮：面试官迟到15分钟， 给一个二叉树，里面是int, 求叶子节点的和。我说用recursion, 他让我把思路说一遍，然后问我时间空间复杂度， 讨论了一下树balance和不balance的区别。这时候有别人要用会议室，somehow我们就必须走，然后面试官现定了一个room，还是在楼下。尴尬的走下楼，到了问我不用recursion怎么做，我就说iterative + stack做，然后问我recursion/iterative优劣。 这时候还剩10分钟吧，他说now the interesting part begins...不用extra space怎么做，想了两三分钟没想出来，我就一直emm/well/interesting, 然后无助的看着他。他说加个parent pointer怎么样，我想既然能加variable，那就再加一个boolean flag called visited, 然后用parent + visited 遍历树怎么样，他说那就太简单了，然后又想了一分钟，想到用prev/cur，然后把算法讲了一遍，这时候时间到了而且我还得走回之前的会议室，小哥笑嘻嘻的说我照个相，我心想我一行代码没写你照个毛啊（全是画的各种图），真想把白板挡着不让他照。。这轮时间没有太延长，所以真正在面试的时间也就30分钟左右吧
面完后才知道还有morris遍历这种算法，但是我觉得面试背着写下来也没啥意义吧。 我最后提的解法有点类似利口姚思武的interative解法，仅供参考。
第二轮：类似利口流二， 从左下到右下，能走右上，右， 右下，写完让优化，就是有些区域没必要check, 因为永远走不到，加个if check一下就好了，我用dp做的. 1point3acres
面经题
第三轮：基本就是利口齐三柳， 只不过没有let, 只有add和mult。 从来没见过这题，因为我个人特别讨厌刷eval expression相关的题, 但是面试的时候就强迫自己冷静，一步步分析，最后写的代码跟标准的答案基本一样。这轮面试官感觉有点不耐烦，基本是说完题就开始抄我的代码和记笔记， 他的键盘声也搞得我有点无法集中
736
第四轮：给一个List<List<Integer>>, int offset, int count, return一个List<Integer> 表示从offset开始的count个数
Example:
list1: 1, 2, 3
list2: 4, 5, 6
offset: 2
count: 3
return 2, 3, 4
直接找到开始的list, 然后往下数就好，这道题需要注意corner case, indexOutofbound之类的，我有个越界bug被指出来后改了
双指针应该可以
第二题 利口伞思柳， 写完聊了聊数太大overflow了怎么办. 1point3acres
346
第五轮：利口三舅舅，装傻三分钟然后讲解思路，巨工整写完，follow up问query太多了怎么办，我说加个cache。最后小哥很开心的送我下楼
399
---------------------------------
https://www.1point3acres.com/bbs/thread-468281-1-1.html
系统设计
Linux系统上设计一个文件copy。先要求单机单进程单线程。可以用任何系统调用。C++
我的实现是：1，判断是否可以copy（鉴权，路径合法性，磁盘容量等） 这一部分他要求写comment就可以了，不用写代码；2，在求出源文件长度后，fopen打开源文件（读）和目的文件（写）；分配new char* buffer[BLOCK]，开始初始化，准备copy；3，while（true）：read_size = fread（）, write_size = fwrite(), 会有read_size < BLOCK （直接break）, write_size != read_size的情况（ret_code = WRITE_FAILURE; goto END）；4，退出3的循环后，再次检查total_write_size是否等于源文件长度；5，收尾：我用goto写的统一的收尾，释放buffer，fclose，最后return ret_code。
这个写完后，先问了BLOCK设多少；copy到中途出现问题挂了怎么办。然后问了分布式读写的一些设计。
---------------------------------
https://www.1point3acres.com/bbs/thread-468271-1-1.html
第一面：汇率转换，似乎高频了一年，没想到还能面到
。面试官小哥明确要求我用union find写。楼主写得磕磕绊绊
399
第二面：人车匹配，地里很多帖子都详细描述了。
面经题
第三面：王位继承，也有很多帖子详述。
面经题
public static void main(String[] ss) {
String k = "king";
Inh i = new Inh(k);
i.birth("king","l1");
i.birth("king","l2");
i.birth("king","l3");
i.birth("l1","l11");
i.birth("l11","l111");
i.birth("l2","l21");
i.birth("l21","l211");
System.out.println(i.getOrder());
i.dealth("l11");
i.dealth("king");
System.out.println(i.getOrder());
}
static class Inh{
private Node king;
private Set<String> dead;
private Map<String, Node> map;
public Inh(String king) {
this.king = new Node(king);
dead = new HashSet<>();
map = new HashMap<>();
map.put(king, this.king);
}
public String getOrder() {
List<String> rt = new ArrayList<>();
dfs(king, rt);
StringBuilder sb = new StringBuilder();
for (String s : rt) {
sb.append(s).append(" ");
}
return rt.toString();
}
private void dfs(Node root, List<String> order) {
if (root == null) return;
if (!dead.contains(root.id)) {
order.add(root.id);
}
for (Node c : root.children) {
dfs(c, order);
}
}
public void birth(String father, String son) {
Node s = new Node(son);
map.get(father).children.add(s);
map.put(son, s);
}
public void dealth(String p) {
dead.add(p);
}
}
第四面：find relation。这道题在地里看过，但是似乎描述都不太详细，所以多说两句楼主面的版本：
Given a collection of relations, find the relations between two people.
A relation between two people (x and y) can be:
- x manages y.
- x is managed by y.
- x is a peer of y.
For simplicity, two people are peers if and only if they are managed by the same person.
A person can have at most one manager. One's manager's manager is not his manager.
Implement two methods: `is_peer(x, y)` and `is_manager(x, y)`.
在一个有向图上做BFS就可以了。
Solution
2个map，employee -> manager，employee -> peers
难点＃1先处理上下的关系，＃2dfs遍历所有上下关系的点，在处理平级之间的关系，用visited来去重
---------------------------------
https://www.1point3acres.com/bbs/thread-468256-1-1.html
还是email那题，不过变为找到重复最多的email有多少次
第二题
给一个int array，找到两个重复出现的数字最短的距离。
比如 [4,3,5,6,3,5,4]，最短的是3和5，距离都是4
---------------------------------
No comments:
Post a Comment