i******s
发帖数: 301 | 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（不知对不
对，讨论了复杂度好久），然后就问了问其他基本情况。 | f*****w
发帖数: 2602 | 2 bless~
btw, lz 啥背景阿？
要我碰到这些问题就肯定当场挂了... | c********0
发帖数: 112 | | f*****w
发帖数: 2602 | 4 有一个matrix，每个元素都是一个数字，问怎样快速计算出一个子matrix的和？
这个怎么搞？ | t****o
发帖数: 31 | 5 和那个最大子矩阵和一个算法吧
【在 f*****w 的大作中提到】
: 有一个matrix，每个元素都是一个数字，问怎样快速计算出一个子matrix的和？
: 这个怎么搞？
| i******s
发帖数: 301 | 6 站内信你了
【在 c********0 的大作中提到】
: 什么公司啊 楼主明示啊 :)
| i******s
发帖数: 301 | 7 没那么麻烦，就是事先预处理矩阵任意一点和左上角点构成矩形的sum, 有M * N个，然
后任意矩形的sum都可以用4个左上角矩形表示，比如要求矩形(a, b)， (c, d)的面积,
(a, b)表示矩阵左上角坐标，(c, d)表示右下角, 那么S = sum((0, 0), (c, d)) -
sum ((0, 0), (c, b)) - sum((0, 0), (a, d)) + sum((0, 0), (a, b)), O(1)时间
【在 t****o 的大作中提到】
: 和那个最大子矩阵和一个算法吧
| l*****g
发帖数: 685 | 8 请教下面这个问题：
2. puzzle question，有一个M * N的board, 问其中最多包含多少个长方形。
【在 i******s 的大作中提到】
: 面了一家在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)，
| g*********s
发帖数: 1782 | 9 recursion.
f(m,n) = f(m, n-1) + ***
【在 l*****g 的大作中提到】
: 请教下面这个问题：
: 2. puzzle question，有一个M * N的board, 问其中最多包含多少个长方形。
| g*********s
发帖数: 1782 | 10 1. 一个大小为N的数组，其中有N-1个不同的整数，范围从0-N, 问找出missing的那个
整数。然后又扩展，问如果有k个missing，如果用O(1) space去找出来。
n-1 unique, n # => one duplicate?
【在 i******s 的大作中提到】
: 面了一家在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)，
| | | g*********s
发帖数: 1782 | 11 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或数组下标操作[]等对数组进行修改)，来对该数组排序。
void my_swap(int i) // swap element b/w i and i + 1;
{
//let x = A[0..i-1], a = A[i], b = A[i+1]; let x_flip = flip(x);
//we want: x, a, b => x, b, a.
//1) flip(i) , we get a, x_flip, b
//2) flip(i+1), we get b, x, a
//3) flip(i), we get x_flip, b, a
//4) flip(i-1), we get x, b, a.
}
with my_swap defined, we can use bubble_sort.
【在 i******s 的大作中提到】
: 面了一家在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)，
| l*****g
发帖数: 685 | 12 谢谢，明白了
我刚才想到用
f(m, n) = f(m-1, n-1) + ***
结果发觉太复杂了，转不过弯来
【在 g*********s 的大作中提到】
: recursion.
: f(m,n) = f(m, n-1) + ***
| m****u
发帖数: 3915 | 13 这题是bill gates的一篇paper
http://www.eecs.berkeley.edu/~christos/papers/Bounds%20For%20So
数(
【在 g*********s 的大作中提到】
: 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或数组下标操作[]等对数组进行修改)，来对该数组排序。
: void my_swap(int i) // swap element b/w i and i + 1;
: {
: //let x = A[0..i-1], a = A[i], b = A[i+1]; let x_flip = flip(x);
: //we want: x, a, b => x, b, a.
: //1) flip(i) , we get a, x_flip, b
: //2) flip(i+1), we get b, x, a
| g*********s
发帖数: 1782 | | i******s
发帖数: 301 | 15 可以这么做，不过既然是puzzle，interviewer希望你能推导出答案，这个可以先从简
单情况开始推导。
如果board是1*N的，那么显然有N个1*1的矩形，N-1个1*2的矩形，。。。1个1*N的矩形
，所以1*N情况下，一共有N + (N-1) + (N-2) + .. + 1 = N(N+1)/ 2个矩形。
再设想如果是2*N的board，可以分成两个1*N的board，设1*N的board总共有X个矩形，
那么2*N至少有2X个矩形(两个1*N board未连接)，如果把两个2*N的board连接起来，那
么会多出2*1, 2*2, 2*3 ... 2*N的矩形，数量如同1*N board的数法，一共有 X个。所
以2*N board 一共包含3X个矩形，X为1*N board 所包含的矩形数。
如果是M*N的board, 我们把他拆解为M个1*N board, 那么至少有MX个(每个1*N board
都不相连)，现在我们可以选择将M个1×N board中任意两个相连来寻找所有2*1, 2*2,
... 2*N的矩形，一共有M-1种组合。如果考虑选取任意三个1*N board来寻找所有3*1,
3*2, ..., 3*N的矩形，那么有M-2种组合。。。所以一共有MX+(M-1)X+(M-2)X + ... X
= M(M+1)/2 *X个矩形。
所以答案是 (M(M+1)/2) * (N(N+1)/2)
【在 g*********s 的大作中提到】
: recursion.
: f(m,n) = f(m, n-1) + ***
| i******s
发帖数: 301 | 16 没说清楚，k missing的情况下，数组长度为N, 但是只有N-k个不同的整数(均为0~N)，
然后找k个missing的整数
【在 g*********s 的大作中提到】
: 1. 一个大小为N的数组，其中有N-1个不同的整数，范围从0-N, 问找出missing的那个
: 整数。然后又扩展，问如果有k个missing，如果用O(1) space去找出来。
: n-1 unique, n # => one duplicate?
| g*********s
发帖数: 1782 | 17 oh, i think from the recursion formula, we can also deduce the close form.
but i don't know if i can do it on the spot, as i only remember limited
combinatorics formula now.
,
【在 i******s 的大作中提到】
: 可以这么做，不过既然是puzzle，interviewer希望你能推导出答案，这个可以先从简
: 单情况开始推导。
: 如果board是1*N的，那么显然有N个1*1的矩形，N-1个1*2的矩形，。。。1个1*N的矩形
: ，所以1*N情况下，一共有N + (N-1) + (N-2) + .. + 1 = N(N+1)/ 2个矩形。
: 再设想如果是2*N的board，可以分成两个1*N的board，设1*N的board总共有X个矩形，
: 那么2*N至少有2X个矩形(两个1*N board未连接)，如果把两个2*N的board连接起来，那
: 么会多出2*1, 2*2, 2*3 ... 2*N的矩形，数量如同1*N board的数法，一共有 X个。所
: 以2*N board 一共包含3X个矩形，X为1*N board 所包含的矩形数。
: 如果是M*N的board, 我们把他拆解为M个1*N board, 那么至少有MX个(每个1*N board
: 都不相连)，现在我们可以选择将M个1×N board中任意两个相连来寻找所有2*1, 2*2,
| g*********s
发帖数: 1782 | 18 是1~N吧？这样数组长度为N，取值范围也是N，然后用grass那个把A[i]放在A[A[i]]的
技巧。
【在 i******s 的大作中提到】
: 没说清楚，k missing的情况下，数组长度为N, 但是只有N-k个不同的整数(均为0~N)，
: 然后找k个missing的整数
| i******s
发帖数: 301 | 19 呵呵，其实不用那么麻烦，关键是记住flip(i)只会影响数组前i个元素。所以每一步可
以先linear search找出目前数组中最大的元素，假设该元素坐标为i，那么只需flip(i
)，就可以将此元素至于数组首位。然后假设数组下表j ... N已排序，那么只要flip(j
-1)就可以将找到的最大元素置于j-1的位置。时间复杂度是O(n^2)，相当于变种
selection sort。 你的swap会call很多次flip, 虽然时间复杂度一样。
数(
【在 g*********s 的大作中提到】
: 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或数组下标操作[]等对数组进行修改)，来对该数组排序。
: void my_swap(int i) // swap element b/w i and i + 1;
: {
: //let x = A[0..i-1], a = A[i], b = A[i+1]; let x_flip = flip(x);
: //we want: x, a, b => x, b, a.
: //1) flip(i) , we get a, x_flip, b
: //2) flip(i+1), we get b, x, a
| i******s
发帖数: 301 | 20 没错，一开始我还没想到，后来猛然反应过来
【在 g*********s 的大作中提到】
: 是1~N吧？这样数组长度为N，取值范围也是N，然后用grass那个把A[i]放在A[A[i]]的
: 技巧。
| | | g*********s
发帖数: 1782 | 21
(i
(j
我第一感也是先找最大元素，然后设法递归，但没想明白。你这里怎么假设已排序呢？
【在 i******s 的大作中提到】
: 呵呵，其实不用那么麻烦，关键是记住flip(i)只会影响数组前i个元素。所以每一步可
: 以先linear search找出目前数组中最大的元素，假设该元素坐标为i，那么只需flip(i
: )，就可以将此元素至于数组首位。然后假设数组下表j ... N已排序，那么只要flip(j
: -1)就可以将找到的最大元素置于j-1的位置。时间复杂度是O(n^2)，相当于变种
: selection sort。 你的swap会call很多次flip, 虽然时间复杂度一样。
:
: 数(
| i******s
发帖数: 301 | 22 比如数组2, 4, -1, 3.
第一轮，找到最大元素，4， index为1, flip(1) -> 4, 2, -1, 3。然后因为数组没排
序，直接flip(3) -> 3, -1, 2, 4.
第二轮，因为我们已经找到最大数字4，现在从下标0 ~ N-2找最大数字，找到3，因为3
已是数组首个元素，可以不用flip(当然你也可以flip(0)), 然后flip(2) -> 2, -1, 3
, 4.
第三轮，找到下标0 ~ N-3中最大的数，是2，这里也可以跳过flip(0)，直接flip(1) -
> -1, 2, 3, 4。排序完成。
我这里说j-1 ~ N是因为你每一论都会找到数组前N-i个元素中最大的，然后放到数组下
标i-1的位置。大意就是这样，罗唆了点，中文文字表达可能不好，见谅。。。
【在 g*********s 的大作中提到】
:
: (i
: (j
: 我第一感也是先找最大元素，然后设法递归，但没想明白。你这里怎么假设已排序呢？
| g*********s
发帖数: 1782 | 23 en, i got ur point.
为3
3
-
【在 i******s 的大作中提到】
: 比如数组2, 4, -1, 3.
: 第一轮，找到最大元素，4， index为1, flip(1) -> 4, 2, -1, 3。然后因为数组没排
: 序，直接flip(3) -> 3, -1, 2, 4.
: 第二轮，因为我们已经找到最大数字4，现在从下标0 ~ N-2找最大数字，找到3，因为3
: 已是数组首个元素，可以不用flip(当然你也可以flip(0)), 然后flip(2) -> 2, -1, 3
: , 4.
: 第三轮，找到下标0 ~ N-3中最大的数，是2，这里也可以跳过flip(0)，直接flip(1) -
: > -1, 2, 3, 4。排序完成。
: 我这里说j-1 ~ N是因为你每一论都会找到数组前N-i个元素中最大的，然后放到数组下
: 标i-1的位置。大意就是这样，罗唆了点，中文文字表达可能不好，见谅。。。
| a********e
发帖数: 508 | 24 答案有点小错误吧，应该是M(M+1)/2*N(N+1)/2
也可以这么看，矩形由它在长和宽上的两条线段投影唯一决定
长上线段的取法有C(M+1,2)种，因为有M+1个端点选择；
同样，宽上的线段取法有C(N+1,2)种。答案就是两者乘级
,
【在 i******s 的大作中提到】
: 可以这么做，不过既然是puzzle，interviewer希望你能推导出答案，这个可以先从简
: 单情况开始推导。
: 如果board是1*N的，那么显然有N个1*1的矩形，N-1个1*2的矩形，。。。1个1*N的矩形
: ，所以1*N情况下，一共有N + (N-1) + (N-2) + .. + 1 = N(N+1)/ 2个矩形。
: 再设想如果是2*N的board，可以分成两个1*N的board，设1*N的board总共有X个矩形，
: 那么2*N至少有2X个矩形(两个1*N board未连接)，如果把两个2*N的board连接起来，那
: 么会多出2*1, 2*2, 2*3 ... 2*N的矩形，数量如同1*N board的数法，一共有 X个。所
: 以2*N board 一共包含3X个矩形，X为1*N board 所包含的矩形数。
: 如果是M*N的board, 我们把他拆解为M个1*N board, 那么至少有MX个(每个1*N board
: 都不相连)，现在我们可以选择将M个1×N board中任意两个相连来寻找所有2*1, 2*2,
| g*********s
发帖数: 1782 | 25 very elegant solution!
【在 a********e 的大作中提到】
: 答案有点小错误吧，应该是M(M+1)/2*N(N+1)/2
: 也可以这么看，矩形由它在长和宽上的两条线段投影唯一决定
: 长上线段的取法有C(M+1,2)种，因为有M+1个端点选择；
: 同样，宽上的线段取法有C(N+1,2)种。答案就是两者乘级
:
: ,
| i******s
发帖数: 301 | 26 typo。。。果然是大牛，居然想到这个解法，不过这个题我之前没见过，怕就算看过这
么牛的解法，也解释不清楚，面试的人是CS的，好像对组合数啥的不感冒，更别说投影
了。。。
【在 a********e 的大作中提到】
: 答案有点小错误吧，应该是M(M+1)/2*N(N+1)/2
: 也可以这么看，矩形由它在长和宽上的两条线段投影唯一决定
: 长上线段的取法有C(M+1,2)种，因为有M+1个端点选择；
: 同样，宽上的线段取法有C(N+1,2)种。答案就是两者乘级
:
: ,
| g**e
发帖数: 6127 | 27 牛人
【在 a********e 的大作中提到】
: 答案有点小错误吧，应该是M(M+1)/2*N(N+1)/2
: 也可以这么看，矩形由它在长和宽上的两条线段投影唯一决定
: 长上线段的取法有C(M+1,2)种，因为有M+1个端点选择；
: 同样，宽上的线段取法有C(N+1,2)种。答案就是两者乘级
:
: ,
| a********e
发帖数: 508 | 28 不敢当，碰巧。。。
其实，我想问，那个fibonacci数列的问题不能用计算器，要估算么？
要算的应该是(.5ln5+32ln2)/ln[(1+sqrt5)/2]，估算好像不太容易
【在 i******s 的大作中提到】
: typo。。。果然是大牛，居然想到这个解法，不过这个题我之前没见过，怕就算看过这
: 么牛的解法，也解释不清楚，面试的人是CS的，好像对组合数啥的不感冒，更别说投影
: 了。。。
| i******s
发帖数: 301 | 29 他其实想要你知道数值随n增长会接近指数级, 大概用2^32 >= 2^n就差不多了，精确值
好像40多一点，没算过。
【在 a********e 的大作中提到】
: 不敢当，碰巧。。。
: 其实，我想问，那个fibonacci数列的问题不能用计算器，要估算么？
: 要算的应该是(.5ln5+32ln2)/ln[(1+sqrt5)/2]，估算好像不太容易
| l*****g
发帖数: 685 | 30 swap index为i,j的任意两个元素的version
void Swap(uint i, uint j)
{
if (i == j)
return;
// Make sure i is always smaller than j
if (i > j)
{
uint tmp = i;
i = j;
j = i;
}
if (i > 1)
{
flip(i - 1);
}
flip(i);
flip(j);
flip(j - i - 1);
if (j > i + 2)
{
flip(j - i - 2);
}
flip(j - 1);
}
gandjmitbbs说的是j = i+1的special case，所以有：
if (i > 1)
{
flip(i - 1);
}
flip(i);
flip(i+1);
flip(i);
数(
【在 g*********s 的大作中提到】
: 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或数组下标操作[]等对数组进行修改)，来对该数组排序。
: void my_swap(int i) // swap element b/w i and i + 1;
: {
: //let x = A[0..i-1], a = A[i], b = A[i+1]; let x_flip = flip(x);
: //we want: x, a, b => x, b, a.
: //1) flip(i) , we get a, x_flip, b
: //2) flip(i+1), we get b, x, a
| | | a********e
发帖数: 508 | 31 谢谢！刚刚算了一下47
【在 i******s 的大作中提到】
: 他其实想要你知道数值随n增长会接近指数级, 大概用2^32 >= 2^n就差不多了，精确值
: 好像40多一点，没算过。
| i****c
发帖数: 102 | 32 这些题目难度可不低，虽然说大多都是经典题。
楼主的offer应该不远了！gxgx！是什么公司呀？不是linkedin吧？
3）
他是让你先写fibonacci程序吧？
写的过程中就应该想到overflow的处理。
【在 i******s 的大作中提到】
: 面了一家在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)，
| K*********a
发帖数: 210 | 33 有一个stream，由很多行组成，有一个getline()函数可以返回当前行。写一个函数
，返回stream中任意一行，要求：保证stream中的每一行都有相同的概率被选中。
有一个matrix，每个元素都是一个数字，问怎样快速计算出一个子matrix的和？
这两个怎么解？谢谢！祝楼主好运！ | i******s
发帖数: 301 | 34 Reservoir sampling
http://en.wikipedia.org/wiki/Reservoir_sampling
即第N行有1/N的概率替换掉当前的字符串
matrix那个我之前的回复中提了。
【在 K*********a 的大作中提到】
: 有一个stream，由很多行组成，有一个getline()函数可以返回当前行。写一个函数
: ，返回stream中任意一行，要求：保证stream中的每一行都有相同的概率被选中。
: 有一个matrix，每个元素都是一个数字，问怎样快速计算出一个子matrix的和？
: 这两个怎么解？谢谢！祝楼主好运！
| R***i
发帖数: 78 | 35
貌似第N行有k/N 几率换前k个字符中的某一个吧?此题目k=1 (只output出一行),所以第
N行有1/N几
率
【在 i******s 的大作中提到】
: Reservoir sampling
: http://en.wikipedia.org/wiki/Reservoir_sampling
: 即第N行有1/N的概率替换掉当前的字符串
: matrix那个我之前的回复中提了。
| P*******7
发帖数: 55 | 36 This question exists nlog(n) solutions. the O(n2) algorithm is not optimal.
为3
3
-
【在 i******s 的大作中提到】
: 比如数组2, 4, -1, 3.
: 第一轮，找到最大元素，4， index为1, flip(1) -> 4, 2, -1, 3。然后因为数组没排
: 序，直接flip(3) -> 3, -1, 2, 4.
: 第二轮，因为我们已经找到最大数字4，现在从下标0 ~ N-2找最大数字，找到3，因为3
: 已是数组首个元素，可以不用flip(当然你也可以flip(0)), 然后flip(2) -> 2, -1, 3
: , 4.
: 第三轮，找到下标0 ~ N-3中最大的数，是2，这里也可以跳过flip(0)，直接flip(1) -
: > -1, 2, 3, 4。排序完成。
: 我这里说j-1 ~ N是因为你每一论都会找到数组前N-i个元素中最大的，然后放到数组下
: 标i-1的位置。大意就是这样，罗唆了点，中文文字表达可能不好，见谅。。。
| g***s
发帖数: 3811 | 37 前提是flip是O(1)的
optimal.
【在 P*******7 的大作中提到】
: This question exists nlog(n) solutions. the O(n2) algorithm is not optimal.
:
: 为3
: 3
: -
| K*********a
发帖数: 210 | | g**********r
发帖数: 27 | 39 有个物理解释，先两条横线，两条竖线，就唯一确定了一个矩形，反之亦然。
所以 C(M+1,2)*C(N+1,2) = (M+1)*M/2*(N+1)*N/2
,
【在 i******s 的大作中提到】
: 可以这么做，不过既然是puzzle，interviewer希望你能推导出答案，这个可以先从简
: 单情况开始推导。
: 如果board是1*N的，那么显然有N个1*1的矩形，N-1个1*2的矩形，。。。1个1*N的矩形
: ，所以1*N情况下，一共有N + (N-1) + (N-2) + .. + 1 = N(N+1)/ 2个矩形。
: 再设想如果是2*N的board，可以分成两个1*N的board，设1*N的board总共有X个矩形，
: 那么2*N至少有2X个矩形(两个1*N board未连接)，如果把两个2*N的board连接起来，那
: 么会多出2*1, 2*2, 2*3 ... 2*N的矩形，数量如同1*N board的数法，一共有 X个。所
: 以2*N board 一共包含3X个矩形，X为1*N board 所包含的矩形数。
: 如果是M*N的board, 我们把他拆解为M个1*N board, 那么至少有MX个(每个1*N board
: 都不相连)，现在我们可以选择将M个1×N board中任意两个相连来寻找所有2*1, 2*2,
| g**********r
发帖数: 27 | 40 有个物理解释，先两条横线，两条竖线，就唯一确定了一个矩形，反之亦然。
所以 C(M+1,2)*C(N+1,2) = (M+1)*M/2*(N+1)*N/2
,
【在 i******s 的大作中提到】
: 可以这么做，不过既然是puzzle，interviewer希望你能推导出答案，这个可以先从简
: 单情况开始推导。
: 如果board是1*N的，那么显然有N个1*1的矩形，N-1个1*2的矩形，。。。1个1*N的矩形
: ，所以1*N情况下，一共有N + (N-1) + (N-2) + .. + 1 = N(N+1)/ 2个矩形。
: 再设想如果是2*N的board，可以分成两个1*N的board，设1*N的board总共有X个矩形，
: 那么2*N至少有2X个矩形(两个1*N board未连接)，如果把两个2*N的board连接起来，那
: 么会多出2*1, 2*2, 2*3 ... 2*N的矩形，数量如同1*N board的数法，一共有 X个。所
: 以2*N board 一共包含3X个矩形，X为1*N board 所包含的矩形数。
: 如果是M*N的board, 我们把他拆解为M个1*N board, 那么至少有MX个(每个1*N board
: 都不相连)，现在我们可以选择将M个1×N board中任意两个相连来寻找所有2*1, 2*2,
| | | c********0
发帖数: 112 | 41 用qsort? 每次把大于Pivot的flip到后面？
【在 P*******7 的大作中提到】
: This question exists nlog(n) solutions. the O(n2) algorithm is not optimal.
:
: 为3
: 3
: -
| i******s
发帖数: 301 | 42 请教nlogn的算法，当场我真没想出来
【在 P*******7 的大作中提到】
: This question exists nlog(n) solutions. the O(n2) algorithm is not optimal.
:
: 为3
: 3
: -
| k*j
发帖数: 153 | 43 请问帽子的题目有人能贴一下solution吗？ | g***s
发帖数: 3811 | 44 Xor
请问帽子的题目有人能贴一下solution吗？
★ Sent from iPhone App: iReader Mitbbs 6.8 - iPhone Lite
【在 k*j 的大作中提到】
: 请问帽子的题目有人能贴一下solution吗？
| i******s
发帖数: 301 | 45 每个人根据自己看到前面所有人戴绿色帽子的奇偶来报。比如如果有奇数个绿帽，就报
红色；偶数就报绿色。
一开始，最后一个人如果报绿色，表示剩下n-1个人中有偶数个绿帽，所以当轮到倒数
第二个人时，如果他看到前面只有奇数个绿帽，那么他知道他自己戴的是绿帽，反之，
他戴的是红帽。倒数第三个人听到倒数第二个答案时，可以知道所剩绿帽总数是奇是偶
，可以根据之前的判断方法来推断出自己的帽子颜色。
所以这种方法至少能让n-1个人活下来，第一个报的看RP.
【在 k*j 的大作中提到】
: 请问帽子的题目有人能贴一下solution吗？
| g***s
发帖数: 3811 | 46 lijiang give a function my_swap with O(1) -- assume flip is O(1)
then you can use the my_swap function to implement O(nlgn) algorithm
【在 i******s 的大作中提到】
: 请教nlogn的算法，当场我真没想出来
|
|
