yanjinbin/gist:750e57f4d85734b3a9b5b357840af90f

## gistfile1.txt

https://www.1point3acres.com/bbs/thread-564384-1-1.html
二维矩阵旋转

https://www.1point3acres.com/bbs/thread-475376-1-1.html
单链表，绝对值从大到小排列，现在让变成按照正常的值从大到小排
https://www.geeksforgeeks.org/sort-linked-list-already-sorted-absolute-values/


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


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


第一轮:
实现BST中的delete API

第二轮:
1. BFS 遍历 Binary Tree
2. 返回Binary Tree中largest independent set
类似于 https://www.geeksforgeeks.org/la ... -set-problem-dp-26/

第三轮:
找出一个array中出现次数超过半数的元素，要求O(n)时间, O(1)空间
Moore’s Voting Algorithm

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

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

139

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

算法1：二叉树最长路径
给定一个浮点数，求其平方根
算法2 lc239
算法1：字符串内的词调换顺序
算法2：并查集
算法3：快排

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

74. Search a 2D Matrix

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

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

lc 224
Code: compress string 例： "aaabbbccc" => "a{3}b{3}c{3}"
要求：return a String， 不需要inplace。

BQ：Most challenging project
Code： find the missing number in a sequence of number(only one missing)
例： [2, 3] return 1, [1, 2, 4, 5] return 3, [1, 2, 3] return -1
这轮没答好。。。最终的post processing没处理好，给的两个例子都没有bug free跑出来。。但是改对了。
follow up: what if there's more than one missing number in the array, 1. get the number of missing numbers 2. print all the missing numbers.

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

第一题 top k，用最小堆几分钟写完，然后面试官也没让我优化。
第二题手写快排，5分钟。


第一道：单词反转“hello word”这种变成“world hello“
  我用的扫描法，遇到连续非空的字符组成一个单词，然后放入栈里面，最后再全pop。
  注意的坑是开头结尾空格以及中间连续空格
第二题：大数相加（数位用单链表形式表示）
  easy中的easy题，我就不费口水了。面试官对行数有要求，我行数太多，面试官要求我从20几行简化到10几行。
最后聊了一会儿人生。


sudoku（数独）

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

一.第一道题目是有1到100这一百个数字，其中一个数字被0给替换 掉了，请找出被替换的数字。
方法1：先求出1到100的和sum1，然后再求出现在这一百个数字的和sum2，两数相减即为被替换的数字；
方法2：先将这一百个数字排序，然后开始便利，当遇到arr != i 的时候，i即为所求的数字；
方法3: 将现在这一百个数字和1到100这个100个数字异或，最后剩下的就是所求的数字；

二、coding  题目，用户随意输入一段字符串，请统计出每个英文单词出现的次数，其中每个单词以空格分隔

https://www.1point3acres.com/bbs/thread-509731-1-1.html
求二叉树里的最长路径

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


https://www.1point3acres.com/bbs/thread-482779-1-1.html
lc 117 40

bfs 求最短路径

Coding 删除 BST 节点并rebalance。 再coding String to Integer

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


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

https://www.1point3acres.com/bbs/thread-573694-1-1.html
后序遍历 topk

https://www.1point3acres.com/bbs/thread-474828-1-1.html
设计一个hashmap
twitter

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

https://www.1point3acres.com/bbs/thread-468068-1-1.html
LC 450 79 215

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

之前3月海投的微软中国，苏州sde intern，4月发来oa，4道题都很简单，基本是数组加dp，当时觉得微软应该不难，现在想想真是naive，刚电面完，两轮背靠背，直接决定有没有offer，面完就凉了，第一题实现cpp的split function，给string和delimiter，读了好久都没太明白题。。。string是cpp的char pointer所以相当于mutable，我是写java的所以很不习惯，最后随便写了写，面我的是一个senior engineer，当时听他一直在写感觉就是-1s -1s -1s。。。 第二轮还好点，上来聊简历10分钟，然后reverse linked list，出了个小bug，改好后第二题是target sum，给一个array和一个target number，用+ 或者 - 来组合array里的数，（从头到尾有序），返回所有的可能用string的形式。 比如arr：1，2，3，4， target number：10， 返回1+2+3+4，注意要用到所有的数（我当时用的dfs subset的做法）结果返回了子集的情况，也没时间改了，感觉刷了微软leetcode上的tag，但过了一阵都忘了。。果然还是要反复刷呀，微软中国的oa还是很简单的，电面好好准备应该不成问题，难度在medium到easy之间

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

LC 31

linkedin 上 HR 联系的，目前拿到 offer 在走背调流程

Phone screen：lc 31, Next Permutation

一面：简历吹水；输入边（x,y）的列表找第一个成环的边

二面：继续吹水；输入 N 个数切分成 m 个子数组，求使得各子数组的和最大值最小的分法，返回最大值，比如 1 2 3 1 2，切分 3 份，应该（1 2）（3）（1 2），返回 3；lc 126, Word Ladder II

三面：将 BST 中的一个值变大为原来 2 倍，维护 BST，描述测试方法；二维表格里有正整数，求从其中一个格走到另一个的最小路径

四面：吹水；系统设计：短网址服务，讲瓶颈，优化，如何测试

leader 面，仍然吹水，系统设计：爬虫

https://www.1point3acres.com/bbs/thread-512316-1-1.html
lc 53

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

LC 91

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

1.在一个数组里找任意两个数之和的绝对值最小值
https://www.techiedelight.com/find-pair-array-minimum-absolute-sum/

第二问问的应该是字典前缀树
https://leetcode.com/problems/implement-trie-prefix-tree/

https://www.1point3acres.com/bbs/thread-510474-1-1.html
1. 类似Best Time to Buy and Sell Stock

2. 链表后半段倒叙依次插入前半段空隙
3. 统计全由1-n组成的数组的各个数的个数
4. 切割ip，要求用C语言不用库函数
5. Swap Nodes in Pairs

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

https://www.1point3acres.com/bbs/thread-411805-1-1.html
第一轮上来就做题，介绍都不用。 find k th smallest element in N sorted array
第二轮： find the target number in BST，return target后一个的数。 follow up: 有parent 怎么写
楼主用iteration写的
写的挺快，follow up 也答完了还剩20 min就多加了一道题
给一堆多边形和一个点，找包含这个点的最小的多边形。 给了两个function：判断两个多边形是否是互相包含（input 是两个多边形，output是boolean），这个点在不在一个多边形里(input 点, 多边形，output boolean)
和面试官探讨了一阵，感觉快到答案了但死活想不到，面试官人好还给提示，说了是tree
然后就豁然开朗就是一个 k-nary tree，root是大的矩形，children是大的矩形包含的小的矩形
先建立起这个tree然后就是和之前的题一样找target


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


一面。
上来扯会简历。
之后做题。
加密一棵树的信息， 普通的树，不知道N是几的N叉树。
当场懵了，一个数据结构还能加密呢？
后来想了想。感觉考点可能是serialization和deserialization。
就把树变成了一个string，然后对string稍微处理了下，换换字符，rotate下啥的。。
然后写了个翻译回去的函数。

二面。
还是扯会简历，简单题。
merge+去重两个list，无序的，带重复的2list。
类似LRU cache。map+set+一个链表。遍历+插入。

但是还是GG了。感觉很懵逼。可能一面那个的问题

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

第一题： validate binary search tree. 想了一下做出来了。。。就是原题
第二题： 估计也是原题， 只是我没找到
有一个binary search tree(左小右大那种)， 给树中间的一个点找到最接近它但是比他大的节点

LC 285

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

第一轮：自我介绍+简历项目。求链表的环，follow up 找环的起点，两题都需要证明。跟面试官交流的不错，不到四十分钟就结束了。
第二轮：自我介绍+简历项目。第一题，求数组中第K大的元素，用了quick partition。第二题，m个球放进n个桶里，有的桶可以不放，求总共多少种放法。（相同组合不同顺序算同一种放法，如121和211）。大概50分钟结束。

终面：刚回国两年的manager。自我介绍+简历项目。第一题只讲思路，二维空间里很多点，求包裹所有点的凸多边形，我当时有点尬住，没遇到过这种题目（之后据朋友说是很经典的凸包算法）。当时提了一个O(n2)的做法，面试官觉得复杂度比较高，有O(n)的做法。第二题，merge 2 sorted list。第三题，LCA，初始条件只有两个target node，没有root。之后问了几个问题，面试大概持续了65min


https://www.1point3acres.com/bbs/thread-551057-1-1.html
实现hashmap
第一道题
实现哈希表
第二道题
象棋有马走日，给定一个起始节点和一个中止节点，求最快几步能走到这个位置-ba
给定一个有序数组，建立一颗高度最小的搜索二叉树
三面：
这个写了个ip判定


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


Round 1:
写一个函数来判断，过去任意一秒内来自同一ip的请求是否超过100次，如果超过，则返回该ip地址。
    这是一道我原来在地里见过的题目，当然可以用unordered_map 来完成，key是ip，value是存着来自该ip地址的所有请求的timestamp。来了一个ip之后，就去判断1秒内的请求数量是否超过100，如果超过100，就存在一个unordered_set里面（因为只要过去任意1秒内，同一ip地址的请求超过100次，之后请求，都认为该ip是bad ip）;
    第二种方法是用循环数组来判断，我一提到用循环数组，面试官就叫我马上实现循环数组这个类。这个我没有完成的很好，所以第一轮感觉一般；

Round 2:
给你一个长方体和一个点p(x,y,z),求这个长方体表面以及体内，离点p最近的那个点，并且返回坐标。
     反正第一眼看到这个题目，我是一点头绪都没有的。但是幸好面试官给了一些提示，然后一步一步的引导我，最后才实现一个方法。首先面试官让我实现一个类，来表示这个长方体，确定这个长方体的坐下点坐标在（0，0，0），然后类的构造函数给了长，宽，高分别为a,b,c，我就用a,b,c来表示了其他七个顶点。
     后面面试官提示降维操作。相当于先处理x，假设（minX，maxX）是长方体的x的范围。如果x < minX,则说明最短距离点在左侧面，如果x>maxX,则说明最短距离点在右侧面，如果 x>=minX && x <= maxX,则说明最短距离点在相对应x的横切面，然后就相当于求一个面到一个点的距离最短的点；

Round 3:
给一个二叉树，然后求二叉树中有祖先和子代关系的节点之间的差值的绝对值最大的是多少。要求时间复杂度O(n);
    dfs的一道题目。用minVal,和maxVal来保存之前祖先节点的最小和最大值，遍历到当前节点，res = max(res,abs(node->val-minVal)), res = max(res,abs(node->val-maxVal)), 然后更新minVal和maxVal;


Round 4:
给两个正int数，a和b，然后求a%b,不能用乘法和除法。
     首先用的方法是
     while(a>b){
         a = a - b;
     }
     return a;
   就是一直减b直到a<b,但是面试觉得每次只减一个b有点慢，在面试官的提示下，每次减完之后，如果a还大于，就把b<<1 ,左移一位，相当于乘以2，如果a == 0，就返回0，如果 a<0了，就把a在加上此时的b，然后b>>1，再重新进入循环。直接贴代码：
  int getMod(int a,int b){
     if(b == 1)
        return 0;
     int ob = b;
     while(a > ob){
          int t = a - b;
          if(t>0){
              a = t;
              b = b<<1;
             }-baidu 1point3acres
         else if(t == 0){
              return 0;}
        else {


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

前三轮都是算法题，如下：. check 1point3acres for more.
[hide=150]. check 1point3acres for more.
一面：
先问了工作项目情况，讲了下系统架构啥的，很不错，然后是算法题。
leetcode原题：https://leetcode.com/problems/sliding-window-maximum/
这道题没刷到，写了复杂度高的算法，复杂度低的算法和面试官纠结了半天。。

二面
两道算法题
1、找链表倒数第K个节点
2、给出两个整数相除，结果的循环小数的循环位数，如果不是循环小数，可以返回-1
这两道题都做得很不错

三面
项目经验、数据库优化等等
两道算法题
1、最大子数组和
2、数组元素减去数组右边的元素的最大差，和这道题的思路很像：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
都写出来了，最后可能是一面答得不好，挂掉了


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

mypow island


-----


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


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


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


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

1. 给一个array 长度是n+1。每一个元素大小都是1到n之间。只有一个数字会重复出现(可能会重复很多次) 。找出重复出现的数字。要求空间复杂度O(1)
2. 利口445
3. string compression。例如"aabccc"，变成"2{a}1{b}3{c}"。这轮主要有很多follow up。比如如果这个string特别长怎么办，怎么scale等等
4. 给一个从小到大sorted array n-1。每个元素都在1到n之间。只有一个missing number。找出这个数字。follow up: 如果不止一个missing number怎么办？


补充内容 (2019-10-13 08:53):
不好意思我第四题说的不太清楚！是这样的。sorted array长度是n-1然后每个元素都是1到n而且只出现一次。就比如n如果是5, array可能就是1,2,4,5


补充内容 (2019-10-15 15:29):
第一题不能修改input array。LC 287

https://www.1point3acres.com/bbs/thread-562931-1-1.html
lc 450

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

 Leetcode 341


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

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


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

LC 621

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

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

1. convert seconds to datetime
2. LRU cache
3. two sum，three sum，valid ip address
4. stock1， 第二个问题。面试官自己想的，他工作中碰到的问题（我用拓扑做的）

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


https://www.1point3acres.com/bbs/thread-473242-1-1.html
71. Simplify Path
722. Remove Comments
402. Remove K Digits
33. Search in Rotated Sorted Array

https://www.1point3acres.com/bbs/thread-455442-1-1.html
198. House Robber
213. House Robber II
99. Recover Binary Search Tree

31. Next Permutation
60. Permutation Sequence

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

312. Burst Balloons

https://www.1point3acres.com/bbs/thread-477509-1-1.html
LC 59 138

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


1. largest integer


2. longest semi altering substring

https://leetcode.com/discuss/interview-question/376700/american-express-longest-semi-alternating-substring


3. max network rank

https://www.1point3acres.com/bbs/thread-413557-1-1.html
LC 297  430 链表有环 删除链表节点

https://www.iteye.com/blog/kickcode-2263808

https://www.1point3acres.com/bbs/thread-317006-1-1.html
LC 73
LC 208
LC 142
LC 235

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


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

LC 81

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

1.输入一个String，只由大写和小写字母组成，要求返回一个大写字母，which is the largest alphabetically order and occurs both in lower and upper cases in the string。如果找不到的话，返回"NO"
例如，"aAbxeEX"，A，E， X都符合题意，但X的字母序比较大，所以返回X。
2.给一个字符串，要求得到最长子串的长度，子串中一样不可以出现连续三个一样的字符。
例如，"baaabbabbb"，最长字串为"aabbabb"，因此返回7
3.给定一个string, 问如何去掉一个character，使得剩下的string字典序意义上最小。
例如，
给出acd，去掉d返回剩下的ac就是正确的。因为去掉c留下ad，去掉a留下cd，都比ac要大。
给出hot，去掉t返回剩下的ho就是正确的。因为去掉h留下ot，去掉o留下ht，都比ho要大。
给出aaaa，只要返回aaa就是正确的

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

LC277

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

LC236

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

53
448 38 142 240

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


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


1.
void remove(node *head) {. From 1point 3acres bbs
   free(head);
   head = head->next;. 1point3acres
}
问这段从链表里删除头结点的函数有什么bug，怎么改

2.
给一个String，判断这个String里面是否所有的char都是唯一的。
（限制: 不能用额外的数据结构。我的理解就是数组跟set都不行）

3.
找K个离参考点最近的点。
输入给的不是一个数组或者list，而是set<Point>
（限制：一共有百万级数量的点，K只有几百）


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

这三条代码是我之前练手的，当时做的时候和这个也都差不多，可能注释解释更详细一些。
1. 把字符串的问号变成和左右不相同的其他字符  ?a?b? -> bacba 或其他都可以
我的代码： https://leetcode.com/playground/XVPpEqVm

2. 没有3个相同连续字母的字符串 https://leetcode.com/discuss/interview-question/398039/
我的代码：https://leetcode.com/playground/HTwGvEJZ

3. 最小删除使每个字母的频率唯一 https://leetcode.com/discuss/interview-question/398035/
我的代码：https://leetcode.com/playground/UCQ4YBjT

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

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

lc256


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

第一轮：这个题目有个手机锁屏图案是否valid的背景。给我一个array，然后按照array index的顺序看看图案是否valid。不能有backtracking
第二轮：Given two points in a matrix, find all the possible paths from A to B. Follow up: What about the shortest path?
第三轮：find the first 100 max numbers in a large set. The set can be any type but you can assume it is an integer set at first.
第四轮: The input is the amount of seconds, calculate the date based on the input. The date starts from 01/01/1980. If you are given 31,536,000 seconds which is a year, the output should be 12/31/1980 since 1980 is a leap year. You can create the help functions by yourself if needed.
第五轮：merge two sorted array. 这一轮我的嗓子已经不行了，所以10分钟写完了code问了问一些trivial questions他就放我走了。。


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


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

第一轮
一个十进制的正数转26进制的数a-z，1对应A，不是0index的，所以corner case比较多

第二轮，
给一个coin amount array，做coin change，先讨论了什么时候能用greedy 什么时候不能，然后写了greedy，bfs 和 dp解法
最后口述了A*，给了个收敛的heuristic函数

第三轮，用constant space traverse一个有parent指针和sibling指针的tree，不能recursion，不能建stack，不能修改树，我大四见过这个题，本科同学面头条被问到的，我们当时也没想出来。今天灵感来了就解了。

第四轮，设计Office word/excel 在resize时候的上边栏的按钮的显示与堆叠的切换，挖开之后实质是两种情况简单算法题，一个用greedy，另一个用binary search。

第五轮，LCA，H是树高度，给了O(H)解法，最后口述了O(log H)解法


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

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


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


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

3SUM

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

LC 171 165

https://www.1point3acres.com/bbs/thread-288885-1-1.html
Get next higher permutation，LC原题


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

lc 796

https://www.1point3acres.com/bbs/thread-517597-1-1.html
LC80  53 5   3SUM

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

lc 19 142  347

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

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

设计一个编辑器 ，数据结构的运用

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


https://www.1point3acres.com/bbs/thread-561504-1-1.html
103 369 328 287 324

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

89
1. Find the length of the longest path in a binary tree
2. Find the minimum absolute sum of two numbers in an array
https://www.geeksforgeeks.org/minimum-sum-absolute-difference-pairs-two-arrays/


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

是自己建一个栈去用循环的办法代替递归。

LC 85


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

第一关：美国小哥
题目：reverse words in a string（"The sky is blue" -> "ehT ykS si eulb"），以空格为分界线翻转单词。
Follow up：给我几个test case（edge case），比如全是空格，没有空格，单词之间有多个空格，开头全是空格，结尾全是空格，空字符串。。。
解：略

第二关：华人大哥
题目：设计一个timer
假设你需要设计一个 setTimer(int time, function callback)，意思为 time 秒后触发那个 callback，你当然不可以每被call一次这个function就建立一个新线程，这种情况下你需要如何设计？
例：在第0秒的时候发来setTimer(10, A)，第1秒的时候发来setTimer(5, B)，你需要在第6秒的时候执行B，第10秒的时候执行A。
解：将所有发过来的任务存起来，只设置距离最近执行的那个任务。每当来新任务的时候检查是否新任务会插队，每当一个任务执行之后检查是否要设定下一个timer。
感想：完全是经验题，还好我以前project搞过这个玩意。

第三关：美国大爷
题目：设计一个File存储的data structure
你需要设计一个可以表现File如何被存储在磁盘上的data structure，储存的定义是记录下“磁头的位置”。
比如一个100字节的文件，可以存在磁头位置100~199的这段空间，或者100~189+1000~1009这两段空间中。

第四关：印度大哥
题目：设计一个HashMap
请你设计一个HashMap，要求写好get()，put() 和 delete()。可以给定一些降低难度的条件：
1. Bucket size = 100 并且不会变
2. 送你一个 hash(char* key) function
3. 送你一个 HashMapObject 的class
4. 出现hash collusion 的情况用 linked list 解决
解：如果不会的话请在网上搜一下HashMap的Implementation

所有题目的难点（吐槽）：
这四个人全都想让我拿c/c艹写！作为一个整天写high level代码的人感觉非常不习惯，比要注意的是第一题如果用c的话需要考虑'\0'字符。印度大哥人超好，他听说我很久没写c之后就一直给我说语法提示，比如我写到比较两个char* 是否相同的时候他瞬间给我蹦出一个strncmp。


昨天收到offer，感觉百感交集，接近一年的找工作也到此结束了。当初微软我压根就觉得自己没希望，这次面试机会是微软去学校举行coding competition后优胜拿到的，没想到一路打到on site然后拿到了offer，这简直是个奇迹。。。


补充内容 (2017-11-24 06:22):
第三题的补充个人解法在五楼，纯属个人见解，如果帮到大家的话请顺手撒点米吧。

补充内容 (2017-11-24 21:34):
第二题的题解补充在九⑨楼


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

LC 6

第四题：
给你一个binary tree，你需要写一个post-order tree traversal iterator。这个iterator的next()方法应该返回下一个node。注意返回的顺序是post-order。最简单的方法就是把 tree flatten成一个array，但这样space complexity就是O(n)。要求你把space complexity控制在O(log n）。
答案在下面。。。


Define a stack in your iterator.
In the constructor of the iterator, push all nodes that are on the path from the root to the leftmost child of the root to the stack.
In the next() method of the iterator, do this:

pop from the stack and name it T.
Find the right child of the parent of T and name it R.
if R is not null, push all nodes that are on the path from R to its leftmost child to the stack.
return T


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


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


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

329
amicable number.

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

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

第一轮：

给一棵二叉树的root，结点定义如下
struct Node  {. From 1point 3acres bbs
  Int val;. 1point3acres
  Node *left;
  Node *right;
}
实现 int find(Node* root, int sum) 返回这颗树有多少从根到叶子路径和为sum
大概实现了个递归，面试官追问假如树很深，递归会爆栈怎么解决
答用一个数组记录宽搜的访问顺序，宽搜用队避免递归，再从访问顺序逆序求上去，写到一半面试官问是不是没有必要求两遍
想了下确实在求访问顺序的时候顺便记录剩余的sum，到0直接ans++就好，其实遍历一遍就能做完，blabla写完
面试官追问假如现在换一个题目，find返回的是这棵树有多少段路径和为sum，不一定从根开始，也不一定到叶子结点-baidu 1point3acres
我准备直接在上面改被面试官打断说没这么简单，可以想清楚再写
我追问这次需不需要考虑爆栈道情况，面试官说不用，我又问了下val的范围是不是int整型，他说是的
于是我就写了一个树形dp，维护了子树到当前根节点的和的集合
面试官让我在一个例子上表示一下这个集合的内容，我就表示了一下
然后面试官问我复杂度，我说n方，他让我确认是不是n方，我确认了是的，然后他想了想说确实是的，结束
最后临走的时候我试探的问一下这道题是不是有O(n)的解法，得到了肯定答复

第二轮：

1、给一棵二叉树的root，结点定义跟上面一样，多一个 Node* next，初始化为nullptr
实现一个函数将一棵树中next都指向他的sibling（同层右边的结点）
先实现了一个宽搜，每次解决同一层，去要额外一个数组，面试官问这样空间复杂度是O(n)，问我能不能优化
我问能不能用全局变量，面试官说能，我就用了一个记录深度的全局变量，和一个全局变量代表当前左边的结点位置
我说递归的时候加入一个记录深度的的参数，每次深度到了下一层全局深度加一，如果当前在全局深度那一层就全局左连当前，否则更新全局深度++-baidu 1point3acres
面试官演算的时候发现问题，递归其实是深搜，会一下子全局深度到最大，再回去，不能一点一点更新
于是问我是否确定常数的空间复杂度能解，他说一开始需要O(n)，我只需要优化到O(h)，h是树的深度就好
于是我明白了大概就是全局记录下每一层当前点左边的结点即可，搜索的时候当前深度左节点连过来，再更新当前深度左节点为当前结点即可

2、给一个文件路径，展开实际路径
比如/a/b/./../c要得到/a/c
先问了下细节，比如结尾会不会是/，会不会解析出来不合理（到根目录前面去了），然后说都可能的，让我都记得处理
于是基本就是写一个栈+字符串解析吧，注意细节，最后面试官演算了一遍代码说没问题，结束

第三轮：

1、已知函数rand3（可以随机生成0、1、2），用rand3实现rand6（随机生成0、1、2、3、4、5）
我说是rand3 * 2 + rand2即可，想了半天rand2不好做，就说用一个循环求rand3，生成0或1返回，生成2再继续rand3. check 1point3acres for more.
然后面试官也认可了这个做法，问我平均需要多少次该怎么做，我说sigma(i从1到正无穷)(1/3)^(i-1)*(2/3)
面试官问怎么求，不要求求出来，我大概说了下错位相减，面试官get了，追问，假如要用rand3求randn
我先说求rand(3 * ceil(n/3))，如果大于等于n就重复做，然后设m=ceil(n/3)，rand3m就是rand3 * m + randm
然后我自己发现randm又可能要重复，我就立马说不求rand(3 * ceil(n/3))，而是求rand(3 ^ ceil(log(3, n)))
这样中间就不用反复重复，只是最后的结果大于等于n需要重复，因为这个时候到m一定是3k，k一定是3p等等，推下去一定不需要重复

2、给一个地形高度序列，问下雨后有积水的段，比如高度是3 2 5 1 3 2 4 3，最后是（下标）0 2 6 7
其实就是先找最高点然后往两边找下降序列，用栈维护，遇到当前比栈顶高的把栈顶pop到比当前高，再当前入栈
我大概写了下，问了下细节，两个连续相同高度怎么处理，面试官说保留最外边的就好，于是写完，
面试官问最高点的细节，我以为最高点保留一个就好，后来发现不对，于是一开始找最高点就要把最高的两个最外侧找到，再从两边遍历

3、给一棵二叉树的root，结点定义跟上面一样，再给两个树中结点的位置，问两个的最近公共祖先
我先做了两个算法，都是要从叶到根的，面试官说结点不带父亲信息，于是我还是用了递归
用了一个bool dfs，返回当前子树有没有这两个输入结点的任意一个，那么只有以下两种情况
要么输入两个结点相同，结果就是这个结点，否则当且仅当会在最近公共祖先处的dfs左儿子、dfs右儿子、以及当前结点为输入的某一个，这3个bool值至少两个为true，面试官表示认同，结束


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


刚面完微软北京的三面，睡不着觉，发个面经吧。
Timeline：. check 1point3acres for more.
3月份内推完成
4月18号通知面试

约北京时间4月25号 11：30am
第一轮结束后，面试官估计去吃午饭了
下午两点开始第二面
-baidu 1point3acres
每轮一小时，面到了4点30

第一面
上来先让自我介绍，我自然一顿吹牛逼，然后问简历项目，又开始吹牛逼，面试管还挺配合的说挺好，中文。
题目，比较两个链表的长度，挺简单的，做完之后让我写testcase，写着写着我发现自己一开始考虑得不全面，它给的链表可能是循环的，然后我就问面试官，面试官说对，然后改代码，改完面试官让再把代码简练一下，然后经过提醒想到了对每个节点加一个标志位来判断有没有被访问过。最后让问问题，问完结束大概就一个小时。

第二面
上来让自我介绍，问简历，我又开始吹牛逼，然后这个面试官很配合地让我多说一点，感觉他挺有兴趣，大概聊了10多分钟吧，聊得很愉快，甚至讲起了段子。。。然后他说挺好的，但是这个还是个面试，还是要考一下计算机能力，然后他就出题了，把字符串转化成整型。
我前几天刚复习到，然后还假装自己没做过慢慢思考，问他问题，然后一边问一边就A出来了。写完让写testcase，我应该说全了，然后经过他提醒，发现自己写了一个bug，然后很快就该过来了。然后开始follow up，问如果是八进制和16进制怎么改代码，因为时间关系他让我讲思路就行。最后他说本来还可以继续扩展，问问科学计数法，但是没时间了，算了，你等HR进来通知你下一轮时间吧。


第三面
是个manager，她迟到了一小会，说不好意思，然后闲聊了几句。开始看我简历，然后让我介绍自己的项目，然后我又开始吹牛逼了，然后说觉得项目里最难的地方是什么。这样子的问题都准备到了，然后又一顿套路。. check 1point3acres for more.
说完之后开始coding，问了OOD，让设计贪吃蛇游戏。一开始让写几个主要的函数，然后我一边想一边说一边写，把大概的函数名都写完了，她说恩差不多写全了。然后下面让我具体实现一下这几个函数功能。OOD真的不太熟悉，然后有点慌了。反正就一边想一边说，面试官也会给反馈，然后让我写怎么存蛇的数据，让实现move函数。我慢慢想慢慢写，面试官提示了我几下，然后写两个大概。后来她突然断线了，回来之后问了我随机出现食物这个函数可能存在什么bug，我就说要出现在屏幕内不要越界了，然后可能和蛇的身体碰到一块。然后她说那要怎么办，我说随机产生的位置和蛇身的数据进行比较，不行的话再重新生成。她又问可能要几次才可以。我说因为是随机的，可能不知道吧？然后说了另一种方法是随机生成前把蛇身的位置数据考虑进去，避开蛇身。. From 1point 3acres bbs
最后让我问问题，然后我就问了问，平时干什么，然后她慢慢透露自己做AI的，然后是个Manager。面完大概美国这边半夜四点半了吧。
第三面感觉不是特别好，主要还是OOD太不熟悉了，准备了好多题，以为只有前两面才可能有OOD，结果发现在第三面。最后大概写完了吧，只有等结果了，希望有好运吧。

顺便求大米呀～


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

国内大三EE专业找实习中，3月21日在微软官网上海投的苏州E+D暑期实习，之前已经找学长内推了微软上海的AI+Cloud组，但是可能因为项目不匹配所以没过简历关，最后被微软苏州捞起来了。

一开始先要做一个在线笔试，3道算法题，难度都挺大的，感觉应该是LC Hard难度。我做了其中2道，但都没有100%过。最后还是很幸运地收到了现场面试邀请。
4.19 现场一面
面试官直接看简历，说了句本科生有这么多项目挺不容易的（其实都是udemy上抄的。。惭愧惭愧_(:з)∠)_）看完简历之后没有问项目，直接开始做题

1. 给定一个数组，其中的元素先递减后递增，要求找出最小的那个元素的下标

    一开始先和面试官沟通，确认各种情况，比如输入数组是否可能为null、长度是否可能为空，是否可能只存在递增的部分或者只存在递减的部分，是否存在重复等等
    各种边界情况确认完之后开始写代码，思路很简单，先判断输入数组是否属于上面提到的各种特殊情况，如果属于，就直接返回相应的下标。如果不属于，就用二分查找来看arr[mid]是否同时小于它的左边元素和右边元素，如果小于，那么mid就是要求的下标；如果不小于，根据arr[mid]比哪边更小来二分地缩小搜索范围。
    代码写完之后面试官让写一些测试用例，随便写了两个需要用二分来查找的case一步步按前面的代码的思路做，都成功找到了，这题就结束了。自我感觉这一题做得还不错，应该是达到了面试官的预期。

2. 输入一个char[] str，要求把str中所有的"ab"都替换成"c"，把所有单个的"b"都替换成"ef"。要求in-place，并且保证str中"ab"的个数 > "b"的个数（也就是str的长度足够放下替换后的结果）
这道题我没有在lc上做过类似的，一头雾水完全不知道该怎么下手，大概卡了有快10分钟了面试官看我还毫无头绪，就问我哪里不太明白，然后提示我可以先把所有的"ab"换成"c"而暂时不考虑单个的"b"，但我真的太菜了，还是不知道该怎么写。。最后面试官就让我先把"ab"替换为"c"的代码写出来，写完之后让我自己考虑怎么解决单独的"b"，我一开始想出的方法是从str的尾部开始插入，因为之前把"ab"替换成了"c"，所以现在str中的空间一定已经足够。但是这个方法有一个问题就是最终得到的结果会堆在数组的尾部而不是头部，面试官让我继续向怎么解决这个问题。最后我提出在第一个循环把"ab"替换为"c"的时候用一个变量记录单个"b"出现的次数，这样就可以知道最终全部替换好之后str的长度会是多少。从这个位置开始从后向前插入，最终就能让结果位于str的头部。
    这一题估计耗了快有40分钟吧，面试官各种提示之后才勉强写出来，感觉非常不好。做完之后时间就到1小时了，连提问的环节都没有就带去下一个面试官那里了。

这一轮因为第二题做得太差，感觉面试官的feedback肯定不是positive，当时出来之后感觉应该是没戏了。。. From 1point 3acres bbs

4.19 现场二面

面试官先让我做个自我介绍，介绍完后他看了一遍简历，看到我大多数项目都是java，就问了几个简单的java相关的问题

1. 有没有用过synchronized
     在自己的项目里没用过，但是有了解
2. 一个类中有3个方法a、b、c，都用synchronized修饰。问两个线程能不能同时访问这些方法
    先确认这三个方法不是static，然后说如果访问的是同一个对象，那么就不能并行，否则可以。
3. volatile作用是什么，为什么有了synchronized还需要volatile
    两个基本作用：1. 保证可见性 2. 禁止指令重排序优化。再展开扯一些blabla
从面试官的反应来看这几个回答还是挺让他满意的。然后开始做题

1. 给一个字符串，是一个普通的英语句子，要求把里面所有单词的出现顺序反序，但是单词本身不反序，例如"This is a test" -> "test a is This"
    同样先确认各种特殊情况，例如有没有特殊字符，输入是不是保证合法等等
    我给出的第一个方法是直接用split函数，根据空格来split，放到一个数组中，然后逆序把数组中的元素放到结果中
    follow up 1: 如果单词之间的空格大于1个怎么办。回答说根据两个单词之间空字符串的数量来判断出有几个空格，例如"this  is"，this和is之间有2个空格，那么split之后，数组中"this"和"is"之间会出现一个空字符串""，连续空字符串的个数为n，就说明空格个数为n + 1。
    follow up 2: 如果句子有前导空格和后继的空格怎么办。我说用一个boolean记录当前是不是前导空格。
    follow up 3: 不用split解决这个问题。我说用字符串cur记录当前的单词或连续空格，再用一个boolean记录当前是不是空格，每次从单词变成空格或者从空格变成单词的时候，就把cur添加到栈里，并把那个boolean反一下。遍历完成后连续pop这个栈，把栈顶元素加到结果字符串的末尾，直到栈变成空。
    follow up 4: 直接把整个输入字符串反向，然后对里面的每一个单词再做一次反向。
     这一题自我感觉良好

2. 实现一个数据结构，判断某个IP是否在1秒内请求了>=100次，用来在服务器上防止拒绝服务攻击。

    我稍微想了一下，给出了一个HashMap的解法， String是IP，Queue是来自这个IP的请求。每次有IP进来的时候查map，如果查到是null，那么是新的IP，存到map中；如果不是null，先从queue的头部把所有与当前时间相差超过1秒的全部出队，然后判断剩余的queue.size()是否>=100。这个想法应该已经比较接近面试官期望的答案了，他提示我用循环数组，只需要长度为100，后来的请求覆盖掉之前的请求，然后判断最新的一个请求和队列中最早的请求时间差是否>=1。 . From 1point 3acres bbs
     这一题感觉回答得中规中矩。。没有大的亮点，但也没有像一面第二题那样爆炸。

二面自我感觉应该是positive的feedback吧。。大概。。


2轮一个小时的面试，从3点半面到5点半，面完回家。在车上刷邮箱发现5点48分hr就发了邮件约线上终面，约在4.23周二下午。这两轮能过真的是非常幸运。。如果面试官考我简历问题的话我基本就凉了_(:з)∠)_

最后想问问地理有没有小伙伴已经参加过线上的最终面试的？主要是问些什么内容？技术面考算法还是说聊聊天为主呀


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


北京时间4.12日上午前两轮背靠背，面试经历如下：
[hide=110]
第一面： 上来只是开了语音和一个共享文档。先问了项目经历，我尽量扯拉长时间。然后问了一个OOD：设计一个2048的逻辑函数，我想一点写一点，大概把主要的函数名定义了出来，然后让我实现其中两个，我完成度在70%左右。

第二面：自我介绍之后立马丢题目，实现一个逐行将SQL查询结果转化成JSON文档格式保存下来，要求实现结果的独特化（distinguish），我一路套话一路慢慢A，大概写了出来，然后让写test case，我没写好，没考虑非法输入，最后面试官给我说了。

第三面： 在北京时间4.16上午。自我介绍，BQ:你最有挑战的项目，coding: Three sum closest to the target. 返回三数的值。我写出一个O(N^3)，follow up:更快的写法。我说有O(N^2)的写法，但是写了一半发现思路不对只能返回最近的三数和、无法返回三数值，于是跟面试官说明，他说理解了但是时间不够就算了。然后问了两个问题：
1. 为什么不投美国投国内？我据实以答说我秋招投晚了小公司要有工作经验的人，我是new grad，他又说其实很多最近内推的学生都是美国留学生，人数很多但是坑位很少希望理解......我顿时心凉了半截
2. 你相对于其他学生的优势？我随便扯看一些。
[/hide=110]
然后给HR打了电话问什么时候出结果，结果等了一个多小时就收到了Thank you letter，获得“谢谢参与奖”。

总结：光准备算法题是不够的，OOD要有准备。
          三面lead说我小错误很多，说明不熟练；跟面试官交流不彻底，最后还要改参数。


      最后估计也确实是竞争者太多，并且已经录了不少，目测之后的录取难度会越来越大，祝各位好运了~


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


          3rd
求3的n次方的末尾数字以及末三位数字，rotate array。review代码，给出代码的不合理之处以及如何改正。. From 1point 3acres bbs

4th
给定一个数组，数组长度为2的倍数，要求奇数位的值是偶数位的2倍，求该数组是否能通过重新排列满足上述要求，数组的值可能会重复，且无长度限制-baidu 1point3acres

5th
给定两个int数a和b，不能用乘除，求a%b。求一定范围內，n个矩形中的最大独立集，n个矩形中互相可能有重叠。


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


--------------------------


why software engineer?
What's is the most technically difficult project?
What challenges did you have in your xxx project?
What about conflicts?
What's your favorite Microsoft product?
How do you want to improve it?
Explain recursion to a five-year-old kid(......
Why Microsoft?
How do you learn new technologies


-----

	189
Rotate Array    		32.2%	Easy
81
Search in Rotated Sorted Array II    		32.8%	Medium
33
Search in Rotated Sorted Array    		33.4%	Medium
153
Find Minimum in Rotated Sorted Array    		43.9%	Medium
154
Find Minimum in Rotated Sorted Array II    		40.0%	Hard
48
Rotate Image