税改没整死范冰冰们先把编剧都整死了# TVChinese - 中文电视
i*s
1 楼
面了一家在SF的SNS公司(非twitter),一共见了4个人,2 software engineer, 1
senior SE and CTO, 废话不多,下面是on-site面经。
第一个,问了一些基本简历的问题,然后问了一个puzzle,就是那个经典的帽子问题。
1.有一堆人,每人都戴一顶帽子,帽子的颜色不是红色就是绿色,现在所有人都排成一
排,每个人都能看到前面所有人的帽子( 但看不到他后面人的)。现在从最后一个人开
始,每个人必须说出一个颜色:红色或者绿色,不能不说话也不能说除红色、绿色之外
的字句,所有人都能听到这个人的回答。如果报出的颜色和自己所戴帽子的颜色不一致
,该人就得挂掉,否则可以活下来。问:有没有一种方法能使活下来的人尽可能多。
2.现在假设有一堆整数数组,有一个flip函数,接受一个数组下标i为参数,作用是将
数组index 从0到i的元素反转。eg. 假设数组为5, 6, -1, 3, 2, 如果调用flip(3),
那么就将数组下标0, 1, 2, 3反转,数组变为 3, -1, 6, 5, 2。问:只使用flip函数(
不能直接用swap或数组下标操作[]等对数组进行修改),来对该数组排序。
3. 写一个求fibonacci 数列第n项的函数。如果用一个32位无符号的整型来保存结果,
问n最大为多少。
第二个,问的问题也不难。
1. 有一个stream,由很多行组成,有一个getline()函数可以返回当前行。写一个函数
,返回stream中任意一行,要求:保证stream中的每一行都有相同的概率被选中。
2. puzzle question,有一个M * N的board, 问其中最多包含多少个长方形。
3. 有一个matrix,每个元素都是一个数字,问怎样快速计算出一个子matrix的和?
第三个,先问了问简历,然后常规问题
1. 一个大小为N的数组,其中有N-1个不同的整数,范围从0-N, 问找出missing的那个
整数。然后又扩展,问如果有k个missing,如果用O(1) space去找出来。
2. 有一个binary tree (不是binary search tree), 每个node除有left, right指针外
,还有一个next指针。 初始的next都为NULL,现在让next指向相邻的node. eg.
Root
/ \
/ \
Left -> Right
/ \ / \
/ \ / \
Left -> Right->Left ->Right
之后问了点小puzzle,忘了具体的,反正很简单。
第四个是CTO,因为我申的是Back-end Software Enginner,所以主要先探讨了一下
distributed system和multi-thread的问题,问了问简历。然后问如果有一个大小为N
的数组,找两个数和为指定值(这个简单, O(n));然后问3个呢,我说O(n^2), 然后问
4个,我直接说O(n^3)。然后他就问有没有比O(n^3)更快的。我想了想,先枚举原数组
两两之和的所有情况,然后建一个新的数组,大小为N(N-1)/2,然后用hash(不知对不
对,讨论了复杂度好久),然后就问了问其他基本情况。
senior SE and CTO, 废话不多,下面是on-site面经。
第一个,问了一些基本简历的问题,然后问了一个puzzle,就是那个经典的帽子问题。
1.有一堆人,每人都戴一顶帽子,帽子的颜色不是红色就是绿色,现在所有人都排成一
排,每个人都能看到前面所有人的帽子( 但看不到他后面人的)。现在从最后一个人开
始,每个人必须说出一个颜色:红色或者绿色,不能不说话也不能说除红色、绿色之外
的字句,所有人都能听到这个人的回答。如果报出的颜色和自己所戴帽子的颜色不一致
,该人就得挂掉,否则可以活下来。问:有没有一种方法能使活下来的人尽可能多。
2.现在假设有一堆整数数组,有一个flip函数,接受一个数组下标i为参数,作用是将
数组index 从0到i的元素反转。eg. 假设数组为5, 6, -1, 3, 2, 如果调用flip(3),
那么就将数组下标0, 1, 2, 3反转,数组变为 3, -1, 6, 5, 2。问:只使用flip函数(
不能直接用swap或数组下标操作[]等对数组进行修改),来对该数组排序。
3. 写一个求fibonacci 数列第n项的函数。如果用一个32位无符号的整型来保存结果,
问n最大为多少。
第二个,问的问题也不难。
1. 有一个stream,由很多行组成,有一个getline()函数可以返回当前行。写一个函数
,返回stream中任意一行,要求:保证stream中的每一行都有相同的概率被选中。
2. puzzle question,有一个M * N的board, 问其中最多包含多少个长方形。
3. 有一个matrix,每个元素都是一个数字,问怎样快速计算出一个子matrix的和?
第三个,先问了问简历,然后常规问题
1. 一个大小为N的数组,其中有N-1个不同的整数,范围从0-N, 问找出missing的那个
整数。然后又扩展,问如果有k个missing,如果用O(1) space去找出来。
2. 有一个binary tree (不是binary search tree), 每个node除有left, right指针外
,还有一个next指针。 初始的next都为NULL,现在让next指向相邻的node. eg.
Root
/ \
/ \
Left -> Right
/ \ / \
/ \ / \
Left -> Right->Left ->Right
之后问了点小puzzle,忘了具体的,反正很简单。
第四个是CTO,因为我申的是Back-end Software Enginner,所以主要先探讨了一下
distributed system和multi-thread的问题,问了问简历。然后问如果有一个大小为N
的数组,找两个数和为指定值(这个简单, O(n));然后问3个呢,我说O(n^2), 然后问
4个,我直接说O(n^3)。然后他就问有没有比O(n^3)更快的。我想了想,先枚举原数组
两两之和的所有情况,然后建一个新的数组,大小为N(N-1)/2,然后用hash(不知对不
对,讨论了复杂度好久),然后就问了问其他基本情况。