c*****m
发帖数: 271 | 1 一直在本版看大家的面经，自己也贡献一下，自己在美国找工第一次面试，一血被拿走
了。。。
电面和onsite都是要写代码，同时要写test case，run出来结果。同时会问下复杂度
1. 电面
国人大哥，题目是找路问题，二维数组中0代表路，1代表墙，找从起点到终点的路并且
输出。
2. onsite
一面：中东人，题目：输入为一个文件，每一行格式：下级名字，上司名字。
输出：
>A
>>A的下级B的名字
>>>B的下级C的名字
>>A的下级D的名字
...
我的方法：
先建树，然后用inorder遍历树，将层序输出。代码写了近100行。
二面：国人大哥（英语很正，可能是ABC），人很nice。题目：输入：word字典，一个
string。输出：string是否可以由字典里面的word拼接而成
我的方法：先说的搜索的方法，然后让我先实现。实现之后，我说可以加入剪枝，加入
到代码里。并且说这样的话复杂度是O(N^2)的。后面和朋友聊，此题用DP也能解，也是
O(N^2)
三面：可能是版上有人说的ABC。题目：给一个二维平面上的点集，需要找一个点（不
是点集里面的点），使得其到所有点的曼哈顿距离之和最小。
我的方法：所有的点的X坐标找中间值，所有的点的Y坐标找中间值（如果点数是偶数，
得到的是一个区间；如果是奇数，得到是一个值）。然后问我怎么找中间值，我说可以
用排序，也可以用quick select，说到和quicksort里面的partition很像。然后让我直
接实现partition，他盯着我写每一行代码，并且每一行都要解释为什么。写完再改成
quickselect，正准备写，又问我要怎么写，解释完后说可以不用写了。ABC从进来到后
面没笑过，一直板着，可能是版上其它人说的ABC。
四面：amazon跳过来的director engineer。题目：输入为一个图，输出：图里面的点
是否可以分成两个集合，使得两个集合里面的点之间没有边。
我的方法：BFS，然后点分成两个集合，然后check每个集合里面的点是不是有边。O(N^
2)
除了一面因为项目聊的时间比较长没写testcase run之外，其它三面都写test run过了
。第二天晚上收到据信，觉得比较可惜。我的问题在于，写完code之后，会有grammar
问题，需要一个个fix之后再跑，写完code花了些时间在这上面；另外一个问题是有些
一二三面都有些小bug，然后自己fix了（一面里面CEO的上司是CEO自己，这个bug是面
试官指出的）。不知道后面挂跟这个有没有关系。觉得
snapchat整体士气应该挺高的。在此再次谢过帮我内推的国人小哥，和所有的面试官吧。
接下来继续面其它的公司，祝自己和大家找工顺利！ | p*****9
发帖数: 273 | | f*******t
发帖数: 7549 | | r****7
发帖数: 2282 | 4 小小的打击一下啊。。。我觉得你答的不算好
2. onsite
一面：中东人，题目：输入为一个文件，每一行格式：下级名字，上司名字。
输出：
>A
>>A的下级B的名字
>>>B的下级C的名字
>>A的下级D的名字
...
我的方法：
>> 先建树，然后用inorder遍历树，将层序输出。代码写了近100行。
typo? 这个怎么看也是preorder啊
二面：国人大哥（英语很正，可能是ABC），人很nice。题目：输入：word字典，一个
string。输出：string是否可以由字典里面的word拼接而成
我的方法：先说的搜索的方法，然后让我先实现。实现之后，我说可以加入剪枝，加入
到代码里。并且说这样的话复杂度是O(N^2)的。后面和朋友聊，此题用DP也能解，也是
O(N^2)
这个用trie的话，应该就是O(N + 字典size)的复杂度，所以depends on字典有多大
三面：可能是版上有人说的ABC。题目：给一个二维平面上的点集，需要找一个点（不
是点集里面的点），使得其到所有点的曼哈顿距离之和最小。
我的方法：所有的点的X坐标找中间值，所有的点的Y坐标找中间值（如果点数是偶数，
得到的是一个区间；如果是奇数，得到是一个值）。然后问我怎么找中间值，我说可以
用排序，也可以用quick select，说到和quicksort里面的partition很像。然后让我直
接实现partition，他盯着我写每一行代码，并且每一行都要解释为什么。写完再改成
quickselect，正准备写，又问我要怎么写，解释完后说可以不用写了。ABC从进来到后
面没笑过，一直板着，可能是版上其它人说的ABC。
四面：amazon跳过来的director engineer。题目：输入为一个图，输出：图里面的点
是否可以分成两个集合，使得两个集合里面的点之间没有边。
我的方法：BFS，然后点分成两个集合，然后check每个集合里面的点是不是有边。O(N^
2)
我觉得你这一个题答的容易被拒，这个就*FS，看是否有两个以上的source就OK了，O(N
)复杂度。。
【在 c*****m 的大作中提到】
: 一直在本版看大家的面经，自己也贡献一下，自己在美国找工第一次面试，一血被拿走
: 了。。。
: 电面和onsite都是要写代码，同时要写test case，run出来结果。同时会问下复杂度
: 1. 电面
: 国人大哥，题目是找路问题，二维数组中0代表路，1代表墙，找从起点到终点的路并且
: 输出。
: 2. onsite
: 一面：中东人，题目：输入为一个文件，每一行格式：下级名字，上司名字。
: 输出：
: >A
| b*********e
发帖数: 26 | 5 最后一题bfs从一个点开始把图里所有点都遍历一遍就好了吧？如果完全遍历就可以，
不能就不可以
如果是有向图的话就用topological sort之类的，应该也是可以在O（N）解决的。
【在 r****7 的大作中提到】
: 小小的打击一下啊。。。我觉得你答的不算好
: 2. onsite
: 一面：中东人，题目：输入为一个文件，每一行格式：下级名字，上司名字。
: 输出：
: >A
: >>A的下级B的名字
: >>>B的下级C的名字
: >>A的下级D的名字
: ...
: 我的方法：
| i*****h
发帖数: 1534 | | b*********e
发帖数: 26 | 7 用trie是O(N*字典size)吧？这题应该没有严格O(N)的解吧？ | c*****m
发帖数: 271 | 8 二面不知道用trie怎么解可以达到O(N*+ 字典size)，能讲下过程么？我在想用trie去
匹配string的时候如果不成功也得回溯吧？可能我没想对
四面我想用*FS也不会是O(N)的吧，因为对于每个结点要check它相邻的点
【在 r****7 的大作中提到】
: 小小的打击一下啊。。。我觉得你答的不算好
: 2. onsite
: 一面：中东人，题目：输入为一个文件，每一行格式：下级名字，上司名字。
: 输出：
: >A
: >>A的下级B的名字
: >>>B的下级C的名字
: >>A的下级D的名字
: ...
: 我的方法：
| W*********y
发帖数: 481 | 9 graph 2 coloring。
查一下wiki吧。遍历一个图，bfs和dfs都是linear time的。
【在 c*****m 的大作中提到】
: 二面不知道用trie怎么解可以达到O(N*+ 字典size)，能讲下过程么？我在想用trie去
: 匹配string的时候如果不成功也得回溯吧？可能我没想对
: 四面我想用*FS也不会是O(N)的吧，因为对于每个结点要check它相邻的点
| c*****m
发帖数: 271 | 10 应该是O(|V|) + O(|E|)的吧
【在 W*********y 的大作中提到】
: graph 2 coloring。
: 查一下wiki吧。遍历一个图，bfs和dfs都是linear time的。
| r****7
发帖数: 2282 | 11 二面不成功就直接挂掉了，不用回溯
四面看到讨论我都有点confuse了，是问一个graph是否存在一个cut没有任何crossing
edges么？
【在 c*****m 的大作中提到】
: 二面不知道用trie怎么解可以达到O(N*+ 字典size)，能讲下过程么？我在想用trie去
: 匹配string的时候如果不成功也得回溯吧？可能我没想对
: 四面我想用*FS也不会是O(N)的吧，因为对于每个结点要check它相邻的点
| c*****m
发帖数: 271 | 12 二面：比如字典是{hel, hello, loworl, world}，而需要查找的为helloworld。trie
第一次匹配到hel，然后继续匹配loworld的时候不成功（只有loworl）；这时不是要
回溯到去匹配到hello，再继续匹配world么？
四面没有描述清楚，不好意思：要求是图里面的点分成两个集合，对于其中任一集合，
两两点间都没有边。
crossing
【在 r****7 的大作中提到】
: 二面不成功就直接挂掉了，不用回溯
: 四面看到讨论我都有点confuse了，是问一个graph是否存在一个cut没有任何crossing
: edges么？
| x********u
发帖数: 1061 | 13 第二题难道不应该先hash一下然后直接找么？第一次需要求字典的hash，以后每次都只
需要O（nlog(字典长度）），考虑到string 的n很小，字典长度很长，这个应该比O（n
+字典长度）高效吧
【在 r****7 的大作中提到】
: 小小的打击一下啊。。。我觉得你答的不算好
: 2. onsite
: 一面：中东人，题目：输入为一个文件，每一行格式：下级名字，上司名字。
: 输出：
: >A
: >>A的下级B的名字
: >>>B的下级C的名字
: >>A的下级D的名字
: ...
: 我的方法：
| z*****u
发帖数: 51 | 14 哈，我加个snapchat的电面面经吧。
题目很完整，国人大哥面的。
/*
Consider a grid where all the points are represented by integers.
.........................................
...(-2,2) (-1,2) (0,2) (1,2) (2,2)...
...(-2,1) (-1,1) (0,1) (1,1) (2,1)...
...(-2,0) (-1,0) (0,0) (1,0) (2,0)...
...(-2,-1) (-1,-1) (0,-1) (1,-1) (2,-1)...
...(-2,-2) (-1,-2) (0,-2) (1,-2) (2,-2)...
..........................................
k-Snap point: A point whose digits sum up to less than or equal to k. In
this question, we ignore all the signs in the number. Example, (1, 0) is a
1-snap point, (0, 10) is a 1-snap point, and (-100, 0) is also a 1-snap
point; however (11, 0) is not a 1-snap point.
Question 1: Implement the following function
boolean isSnapPoint(Point p, int k)
Returns true if p is a k-snap point, and false otherwise.
Reachable k-snap point: A k-snap point is a reachable k-snap point if there
exists a path from (0,0) to that point, where the path only consists of k-
snap points.
Question 2: Given k, return all the reachable k-snap points.
Question 3: Given any k, is the number of k-snap points finite? Is the
number of reachable k-snap points finite? Why?
第二个美国哥们把我给挂了。
其实是two sum, three sum的变形。总感觉他表述不清，我也算是答上来，结果当然是
悲剧。
two sum跟leetcode上一样一样就可以，找出index.
three sum的题不是说找出sum的几个元素，是返回这几个元素的Index.要保证最大的
index是所有可能里面的最小。
比如-1,2,-3,4,5,-2
应该输出1,3,4,
我答了当然可以用brute force，他说不行。我说先sort，然后标记住Index。他说不行。
我说那用Hashmap吧，他说让我模仿two sum的做。就是用HashMap，也
算是写出来了。5分钟内收到拒信。 |
|
