什么样的男女适合做夫妻 10大基本条件# Piebridge - 鹊桥
c*m
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整体士气应该挺高的。在此再次谢过帮我内推的国人小哥，和所有的面试官吧。
接下来继续面其它的公司，祝自己和大家找工顺利！
了。。。
电面和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整体士气应该挺高的。在此再次谢过帮我内推的国人小哥，和所有的面试官吧。
接下来继续面其它的公司，祝自己和大家找工顺利！
