w******a
发帖数: 236 | 1 一不小心，上次写的面经第一部分上了十大推荐。太激动了，谢谢斑斑奖励的包子。还
要特别感谢aeon同学送的大包子。（第一部分在这里：http://www.mitbbs.com/article_t/JobHunting/31659453.html）
话说第一次on-site，我本人自己感觉良好，觉着题目都做出来了，虽然有些多余变量
，也没关系吧。于是喜滋滋的等着那轮四个人的interview。没想到，过了几天，HR哥
哥写信来，说面试官觉得我写程序不够快不够简洁，建议再来coding的面试。无语，谁
让咱不是那种在whiteboard上写code如流水的牛人，只好灰溜溜的同意再来一次on-
site。
第二次是一个很nice的哥哥面我，一直微笑，在我卡壳的时候，也都提示我。废话少说
，上题目：
1. 一个rotated的排序整数数组，比如A=[6，8，1，2，4，5]，写code找一个给定元素
，并分析复杂度。其实就是binary search的变体，但是需要考虑两种A[m]中值的情况
加以判断。
2. 他谈到facebook的log，如果每个log文件有10 billion行，每行包括t |
w*******e
发帖数: 312 | 2 牛。。。
【在 w******a 的大作中提到】
: 一不小心，上次写的面经第一部分上了十大推荐。太激动了，谢谢斑斑奖励的包子。还
: 要特别感谢aeon同学送的大包子。（第一部分在这里：http://www.mitbbs.com/article_t/JobHunting/31659453.html）
: 话说第一次on-site，我本人自己感觉良好，觉着题目都做出来了，虽然有些多余变量
: ，也没关系吧。于是喜滋滋的等着那轮四个人的interview。没想到，过了几天，HR哥
: 哥写信来，说面试官觉得我写程序不够快不够简洁，建议再来coding的面试。无语，谁
: 让咱不是那种在whiteboard上写code如流水的牛人，只好灰溜溜的同意再来一次on-
: site。
: 第二次是一个很nice的哥哥面我，一直微笑，在我卡壳的时候，也都提示我。废话少说
: ，上题目：
: 1. 一个rotated的排序整数数组，比如A=[6，8，1，2，4，5]，写code找一个给定元素
|
w******a
发帖数: 236 | 3 第一个rotated array问题，参考程序如下：
rotated array
==找元素 key
int rotated_binary_search(int key, int A[], int L, int R) {
if (L > R) return -1;
// Avoid overflow, same as M=(L+R)/2
int M = L + ((R - L) / 2);
if (A[M] == key) return M;
if (A[M] >= A[L]) {
if (key < A[M] && key >= A[L])
R = M - 1;
else
L = M + 1;
} else {
if (key > A[M] && key <= A[R])
L = M + 1;
else
R = M - 1;
}
return rotated_b |
j**l
发帖数: 2911 | 4 如果数组已经是排序好的，是否规定rotation的位置点是0?
另外，如果L = 0, R = 1
那么M = 0
A[M-1]会数组下标越界
int FindSortedArrayRotation(int A[], int L, int R) {
if (L > R) return 0;
// Avoid overflow, same as M=(L+R)/2
int M = L + ((R - L) / 2);
if (A[M] < A[M-1])
return M; |
f*********5
发帖数: 576 | 5 你这个还是越界把？
【在 j**l 的大作中提到】
: 如果数组已经是排序好的，是否规定rotation的位置点是0?
: 另外，如果L = 0, R = 1
: 那么M = 0
: A[M-1]会数组下标越界
: int FindSortedArrayRotation(int A[], int L, int R) {
: if (L > R) return 0;
: // Avoid overflow, same as M=(L+R)/2
: int M = L + ((R - L) / 2);
: if (A[M] < A[M-1])
: return M;
|
f*********5
发帖数: 576 | 6 你这算法不对
A[M] < A[M-1] return M
明显不对
【在 j**l 的大作中提到】
: 如果数组已经是排序好的，是否规定rotation的位置点是0?
: 另外，如果L = 0, R = 1
: 那么M = 0
: A[M-1]会数组下标越界
: int FindSortedArrayRotation(int A[], int L, int R) {
: if (L > R) return 0;
: // Avoid overflow, same as M=(L+R)/2
: int M = L + ((R - L) / 2);
: if (A[M] < A[M-1])
: return M;
|
S**********n
发帖数: 41 | 7 赞！
赶快写第三部分吧！
祝拿到offer! :) |
j**l
发帖数: 2911 | 8 faint, 我只是原文一字不动摘抄了他的代码片断，说明下标可能越界，并没有给出我
的fix
【在 f*********5 的大作中提到】
: 你这个还是越界把？
|
j**l
发帖数: 2911 | 9 他的思路还是对的，
比如 4 5 6 7 8 1 2 3, 1就是转折点，
转折点的特点是，比左边的相邻元素要小。
他是想用二分查找的思想来找出这个转折点，但边界情况没有完整考虑。
【在 f*********5 的大作中提到】
: 你这算法不对
: A[M] < A[M-1] return M
: 明显不对
|
f*********5
发帖数: 576 | 10 hehe
sorry...
【在 j**l 的大作中提到】
: faint, 我只是原文一字不动摘抄了他的代码片断，说明下标可能越界，并没有给出我
: 的fix
|
|
|
f*********5
发帖数: 576 | 11 这两个程序的一个共同问题就是性能差。
直接
while（L〈R）
{}
一个loop就结束了
用递归明显性能上差很多阿
【在 w******a 的大作中提到】
: 第一个rotated array问题，参考程序如下：
: rotated array
: ==找元素 key
: int rotated_binary_search(int key, int A[], int L, int R) {
: if (L > R) return -1;
: // Avoid overflow, same as M=(L+R)/2
: int M = L + ((R - L) / 2);
: if (A[M] == key) return M;
: if (A[M] >= A[L]) {
: if (key < A[M] && key >= A[L])
|
f*********5
发帖数: 576 | 12 which one will u return for
8 7 6 5 4 3 2 1
no A[m]
【在 j**l 的大作中提到】
: 他的思路还是对的，
: 比如 4 5 6 7 8 1 2 3, 1就是转折点，
: 转折点的特点是，比左边的相邻元素要小。
: 他是想用二分查找的思想来找出这个转折点，但边界情况没有完整考虑。
|
m*******i
发帖数: 8711 | 13 bless. got the offer yet? |
l*****a
发帖数: 559 | 14 我觉得lz假设了数组是升序且rotate了的。
你的反例是降序无rotate。
【在 f*********5 的大作中提到】
: which one will u return for
: 8 7 6 5 4 3 2 1
: no A[m]
|
j**l
发帖数: 2911 | 15 是很多A[m] < A[m-1]吧
而且这个不符合rotation的定义，不是循环升序
【在 f*********5 的大作中提到】
: which one will u return for
: 8 7 6 5 4 3 2 1
: no A[m]
|
j**l
发帖数: 2911 | 16 又发现一个bug
对test case
4 5 6 1 2 3, 应该返回1的下标，结果返回的是下标0
首先是[4 5 6 1 2 3], 判断6
然后是[1 2 3], 判断2
然后是[3], 返回0 |
w******a
发帖数: 236 | 17 呵呵，没消息，还在等呢。不过想好了，即使给offer，多半也不去了。老实说，主要
是自己coding差，感觉FB注重coding又快又好，而不是鼓励新idea，至少我和六个人谈
感觉是这样。这样的话，我到了那里会很辛苦，长处用不上，短处被人鄙视。对未来发
展没啥好处。
FB最为人诟病的每天push code听说倒是改了，一般情况下一周push一次。
【在 m*******i 的大作中提到】
: bless. got the offer yet?
|
w******a
发帖数: 236 | 18 那个rotated数组找元素的，是有些bug，原先是从一个习题集的答案里搬来的，自己没
写test cases。脸红一个。 |
f*********5
发帖数: 576 | 19 定义从哪里来的？请share，谢谢
排序数组没说一定是升序吧？
【在 j**l 的大作中提到】
: 是很多A[m] < A[m-1]吧
: 而且这个不符合rotation的定义，不是循环升序
|
j**l
发帖数: 2911 | 20 降序的情况考虑类似，所以不失一般性，可以认为是升序。
【在 f*********5 的大作中提到】
: 定义从哪里来的？请share，谢谢
: 排序数组没说一定是升序吧？
|
|
|
f*********5
发帖数: 576 | 21 sigh
这个不能做假设，至少要问清楚吧
我的判断是split点是最大点
a[m]>a[(m-1+N)%N] && a[m]>a[(m+1)%N]
i think it covered all the situation
【在 j**l 的大作中提到】
: 降序的情况考虑类似，所以不失一般性，可以认为是升序。
|
H****r
发帖数: 2801 | 22 有点笨，欢迎拍砖
1. 一个rotated的排序整数数组，比如A=[6，8，1，2，4，5]，写code找一个给定元素
// Ranged search
// returns index or size if not found
bool FindInRotatedArray(const std::vector &rotatedArray,
int iVal,
unsigned int &index,
unsigned int leftIndex,
unsigned int rightIndex)
{
while (leftIndex < rightIndex)
{
if (rotatedArray.at(leftIndex)==iVal)
{
// found!
index = leftIn
【在 w******a 的大作中提到】
: 一不小心，上次写的面经第一部分上了十大推荐。太激动了，谢谢斑斑奖励的包子。还
: 要特别感谢aeon同学送的大包子。（第一部分在这里：http://www.mitbbs.com/article_t/JobHunting/31659453.html）
: 话说第一次on-site，我本人自己感觉良好，觉着题目都做出来了，虽然有些多余变量
: ，也没关系吧。于是喜滋滋的等着那轮四个人的interview。没想到，过了几天，HR哥
: 哥写信来，说面试官觉得我写程序不够快不够简洁，建议再来coding的面试。无语，谁
: 让咱不是那种在whiteboard上写code如流水的牛人，只好灰溜溜的同意再来一次on-
: site。
: 第二次是一个很nice的哥哥面我，一直微笑，在我卡壳的时候，也都提示我。废话少说
: ，上题目：
: 1. 一个rotated的排序整数数组，比如A=[6，8，1，2，4，5]，写code找一个给定元素
|
j**l
发帖数: 2911 | 23 首先，是否可以假定没有重复元素？有重复元素的话更复杂
比如
2 2 2 4 4 5 2 2
假定没有重复元素
int FindSortedArrayRotation(int A[], int L, int R)
{
assert(L >= 0 && R >= 0 && L <= R);
if (A[L] <= A[R])
return L;
if (R - L <= 2)
{
// 最多三个元素，穷举
return L or (L + 1) or (L + 2)
}
int M = L + ((R - L) / 2);
if (A[M] < A[M-1])
return M;
if (A[M] >= A[L])
return FindSortedArrayRotation(A, M+1, R);
else
return FindSortedArrayRotation(A, L, M-1);
}
【在 j**l 的大作中提到】
: 又发现一个bug
: 对test case
: 4 5 6 1 2 3, 应该返回1的下标，结果返回的是下标0
: 首先是[4 5 6 1 2 3], 判断6
: 然后是[1 2 3], 判断2
: 然后是[3], 返回0
|
f*********5
发帖数: 576 | 24 这题有重复的话就是O（N）了
【在 j**l 的大作中提到】
: 首先，是否可以假定没有重复元素？有重复元素的话更复杂
: 比如
: 2 2 2 4 4 5 2 2
: 假定没有重复元素
: int FindSortedArrayRotation(int A[], int L, int R)
: {
: assert(L >= 0 && R >= 0 && L <= R);
: if (A[L] <= A[R])
: return L;
: if (R - L <= 2)
|
p*u
发帖数: 136 | 25 谢谢freemail165提醒，最开始写的有问题，下面是修改过的版本。
写一个第一题的C程序，假设是升序的，没有重复元素：
int bsearch(int *A, int size, int wanted)
{
int left = 0;
int right = size - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
if (A[mid] == wanted) {
return mid;
} else if (wanted >= A[0]) {
if (A[mid] > wanted) {
right = mid - 1;
} else {
if (A[mid] >= A[0]) {
left = mid + 1;
} e
【在 w******a 的大作中提到】
: 一不小心，上次写的面经第一部分上了十大推荐。太激动了，谢谢斑斑奖励的包子。还
: 要特别感谢aeon同学送的大包子。（第一部分在这里：http://www.mitbbs.com/article_t/JobHunting/31659453.html）
: 话说第一次on-site，我本人自己感觉良好，觉着题目都做出来了，虽然有些多余变量
: ，也没关系吧。于是喜滋滋的等着那轮四个人的interview。没想到，过了几天，HR哥
: 哥写信来，说面试官觉得我写程序不够快不够简洁，建议再来coding的面试。无语，谁
: 让咱不是那种在whiteboard上写code如流水的牛人，只好灰溜溜的同意再来一次on-
: site。
: 第二次是一个很nice的哥哥面我，一直微笑，在我卡壳的时候，也都提示我。废话少说
: ，上题目：
: 1. 一个rotated的排序整数数组，比如A=[6，8，1，2，4，5]，写code找一个给定元素
|
p*u
发帖数: 136 | 26 第三题没啥好的想法，目前更倾向于用的方法是：
Facebook应该不止会计算一个月以内访问量最大的N个网页，一定也会计算一周以内，
一个季度以内或者一年以内的吧。
所以，我想是否应该都记录下来这样一些信息呢？前K天的各个网页的访问量。由于
timestamp都是排序好的，所以有前K天推到前(K + 1)天，也是很方便的。把这些数据
都写到磁盘上，用的时候再读入内存就好了。
那样要计算某一个区间[a, b]内的网页访问量的时候，就直接用前b天减去前(a - 1)天
的就好了。
现在已知了某一个区间的网页访问量之后，要求访问量最大的N个网页。可以用一个大
小为N的最小堆的结构。当发现某个值大于堆顶元素的值是，弹出堆顶元素，把当前这
个值压入堆中。这样把所有访问量扫一遍，最后留在堆中的就是最大的N个了。
【在 w******a 的大作中提到】
: 一不小心，上次写的面经第一部分上了十大推荐。太激动了，谢谢斑斑奖励的包子。还
: 要特别感谢aeon同学送的大包子。（第一部分在这里：http://www.mitbbs.com/article_t/JobHunting/31659453.html）
: 话说第一次on-site，我本人自己感觉良好，觉着题目都做出来了，虽然有些多余变量
: ，也没关系吧。于是喜滋滋的等着那轮四个人的interview。没想到，过了几天，HR哥
: 哥写信来，说面试官觉得我写程序不够快不够简洁，建议再来coding的面试。无语，谁
: 让咱不是那种在whiteboard上写code如流水的牛人，只好灰溜溜的同意再来一次on-
: site。
: 第二次是一个很nice的哥哥面我，一直微笑，在我卡壳的时候，也都提示我。废话少说
: ，上题目：
: 1. 一个rotated的排序整数数组，比如A=[6，8，1，2，4，5]，写code找一个给定元素
|
f*********5
发帖数: 576 | 27 your logic is wrong when
A[mid]>wanted>A[0]
【在 p*u 的大作中提到】
: 第三题没啥好的想法，目前更倾向于用的方法是：
: Facebook应该不止会计算一个月以内访问量最大的N个网页，一定也会计算一周以内，
: 一个季度以内或者一年以内的吧。
: 所以，我想是否应该都记录下来这样一些信息呢？前K天的各个网页的访问量。由于
: timestamp都是排序好的，所以有前K天推到前(K + 1)天，也是很方便的。把这些数据
: 都写到磁盘上，用的时候再读入内存就好了。
: 那样要计算某一个区间[a, b]内的网页访问量的时候，就直接用前b天减去前(a - 1)天
: 的就好了。
: 现在已知了某一个区间的网页访问量之后，要求访问量最大的N个网页。可以用一个大
: 小为N的最小堆的结构。当发现某个值大于堆顶元素的值是，弹出堆顶元素，把当前这
|
p*u
发帖数: 136 | 28 谢谢提醒，确实有问题，感觉应该再加上wanted和A[0]的比较。
原帖中已经更新。
【在 f*********5 的大作中提到】
: your logic is wrong when
: A[mid]>wanted>A[0]
|
p*****o
发帖数: 543 | |
l*****a
发帖数: 559 | 30 这个也有问题。
如果split点的值有重复的话。
【在 f*********5 的大作中提到】
: sigh
: 这个不能做假设，至少要问清楚吧
: 我的判断是split点是最大点
: a[m]>a[(m-1+N)%N] && a[m]>a[(m+1)%N]
: i think it covered all the situation
|
|
|
f*********5
发帖数: 576 | 31 在你这个前提下，你认为怎么解呢？
【在 l*****a 的大作中提到】
: 这个也有问题。
: 如果split点的值有重复的话。
|
D***h
发帖数: 183 | |
i**********e
发帖数: 1145 | 33 http://www.ihas1337code.com/2010/04/searching-element-in-rotated-array.html
这是我写的代码吧，竟然被贴出来了，FindSortedArrayRotation()还被揪出bug来（感
谢jntl），当初没好好测试...
rotated_binary_search() 的代码我重新测试了一下，应该是对的，前提是数组没有重
复的元素。如果数组有重复的元素，那只能用linear search。给个最坏情况，数组里
找 1：
000000000000000100000
也就是说，binary search的变种不管用了。不一个一个挨着找是不可能找到 1 的。
freemail165，你说的没错，递归实在是没必要，用一个 while loop 就搞定了。基于
是 tail recursion，转换成 while loop 很直接，我就不多说了。
我重写了一下 FindSortedArrayRotation，找 rotation 的位置点。其思路是找数组里
的最小元素的位置，就是 rotation 的位置点。怎么找最小元素呢？
首先，我们有三个值：一个左边，一个中间，一个右边。
把中间的元素跟右边的比较，如果中间大于右边，那么我们可以完全放弃它+它左边所
有的元素，因为最小值根本不可能在左边。
相反，如果中间小于右边，那么最小值肯定是中间或者比它左边的元素。所以可以完全
放弃它右边所有元素。
int FindSortedArrayRotation(int A[], int n) {
int L = 0;
int R = n - 1;
while (A[L] > A[R]) {
int M = L + (R - L) / 2;
if (A[M] > A[R])
L = M + 1;
else
R = M;
}
return L;
}
测试数据有：
{ 1 }
return 0
{ 1, 2 }
return 0
{ 2, 1 }
return 1
{ 1, 2, 3 }
return 0
{ 3, 1, 2 }
return 1
{ 2, 3, 1 }
return 2
{ 1, 2, 3, 4, 5 }
return 0
{ 2, 3, 4, 5, 1 }
return 4
{ 3, 4, 5, 1, 2 }
return 3
{ 4, 5, 1, 2, 3 }
return 2
{ 5, 1, 2, 3, 4 }
return 1
{ 1, 2, 3, 4, 5, 6 }
return 0
{ 2, 3, 4, 5, 6, 1 }
return 5
{ 3, 4, 5, 6, 1, 2 }
return 4
{ 4, 5, 6, 1, 2, 3 }
return 3
{ 5, 6, 1, 2, 3, 4 }
return 2
{ 6, 1, 2, 3, 4, 5 }
return 1
{ 6, 8, 1, 2, 4, 5 }
return 2
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 w******a 的大作中提到】
: 第一个rotated array问题，参考程序如下：
: rotated array
: ==找元素 key
: int rotated_binary_search(int key, int A[], int L, int R) {
: if (L > R) return -1;
: // Avoid overflow, same as M=(L+R)/2
: int M = L + ((R - L) / 2);
: if (A[M] == key) return M;
: if (A[M] >= A[L]) {
: if (key < A[M] && key >= A[L])
|
j*****u
发帖数: 1133 | 34 3. pratical的方法是按天process，sort好存起来，这样任意几天的都可以merge
因为pageview一般符合long tail，merge的时候一般每天取比如top 100就可以了
【在 w******a 的大作中提到】
: 一不小心，上次写的面经第一部分上了十大推荐。太激动了，谢谢斑斑奖励的包子。还
: 要特别感谢aeon同学送的大包子。（第一部分在这里：http://www.mitbbs.com/article_t/JobHunting/31659453.html）
: 话说第一次on-site，我本人自己感觉良好，觉着题目都做出来了，虽然有些多余变量
: ，也没关系吧。于是喜滋滋的等着那轮四个人的interview。没想到，过了几天，HR哥
: 哥写信来，说面试官觉得我写程序不够快不够简洁，建议再来coding的面试。无语，谁
: 让咱不是那种在whiteboard上写code如流水的牛人，只好灰溜溜的同意再来一次on-
: site。
: 第二次是一个很nice的哥哥面我，一直微笑，在我卡壳的时候，也都提示我。废话少说
: ，上题目：
: 1. 一个rotated的排序整数数组，比如A=[6，8，1，2，4，5]，写code找一个给定元素
|
j*****u
发帖数: 1133 | 35 赶紧FB有点BT，experienced的还要on-site两次才进formal interview，不够
efficient也不尊重interviewee的时间
而且只面算法也挺无聊的，个人感觉
对于experienced的candidate，纯算法的coding在实际工作中能占多大比例？远不如
OOD，system design，performance/threading重要吧。。
【在 w******a 的大作中提到】
: 一不小心，上次写的面经第一部分上了十大推荐。太激动了，谢谢斑斑奖励的包子。还
: 要特别感谢aeon同学送的大包子。（第一部分在这里：http://www.mitbbs.com/article_t/JobHunting/31659453.html）
: 话说第一次on-site，我本人自己感觉良好，觉着题目都做出来了，虽然有些多余变量
: ，也没关系吧。于是喜滋滋的等着那轮四个人的interview。没想到，过了几天，HR哥
: 哥写信来，说面试官觉得我写程序不够快不够简洁，建议再来coding的面试。无语，谁
: 让咱不是那种在whiteboard上写code如流水的牛人，只好灰溜溜的同意再来一次on-
: site。
: 第二次是一个很nice的哥哥面我，一直微笑，在我卡壳的时候，也都提示我。废话少说
: ，上题目：
: 1. 一个rotated的排序整数数组，比如A=[6，8，1，2，4，5]，写code找一个给定元素
|
c***2
发帖数: 838 | 36 int binary_search_rotation(int a[], int l, int u, int x)
{
int m;
while (l <= u) {
m = (l + u) / 2;
if (x == a[m]) {
return m;
}
else if (a[l] <= a[m]) {
if (x > a[m]) {
l = m+1;
}
else if (x >=a [l]) {
u = m-1;
} else {
l = m+1;
}
}
else if (x < a[m]) u = m-1;
else if (x <= a[u]) l = m+1;
else u = m - 1;
}
return -1;
} |
z***e
发帖数: 5393 | 37 new idea？？
you must be kidding me...
【在 w******a 的大作中提到】
: 呵呵，没消息，还在等呢。不过想好了，即使给offer，多半也不去了。老实说，主要
: 是自己coding差，感觉FB注重coding又快又好，而不是鼓励新idea，至少我和六个人谈
: 感觉是这样。这样的话，我到了那里会很辛苦，长处用不上，短处被人鄙视。对未来发
: 展没啥好处。
: FB最为人诟病的每天push code听说倒是改了，一般情况下一周push一次。
|
i**********e
发帖数: 1145 | 38 According to programming pearls, your code will have bug in the line:
m = (l + u) / 2;
This will cause overflow when l and u is large.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 c***2 的大作中提到】
: int binary_search_rotation(int a[], int l, int u, int x)
: {
: int m;
: while (l <= u) {
: m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: }
: else if (a[l] <= a[m]) {
: if (x > a[m]) {
|
S*********r
发帖数: 5693 | 39 恩，我也觉得除非是酷爱编程，要不去这种公司还是不太爽。尤其是PhD，一般长处根
本发挥不出来。
【在 j*****u 的大作中提到】
: 赶紧FB有点BT，experienced的还要on-site两次才进formal interview，不够
: efficient也不尊重interviewee的时间
: 而且只面算法也挺无聊的，个人感觉
: 对于experienced的candidate，纯算法的coding在实际工作中能占多大比例？远不如
: OOD，system design，performance/threading重要吧。。
|
r******d
发帖数: 308 | 40 非常赞同这个
实际工作中面试的这些用到的很少， 就算需要用到的去goole就出来一堆， 所以面试
这些很可笑也浪费时间
不过， 既然都面试这个还是得去准备准备。。。。。
【在 j*****u 的大作中提到】
: 赶紧FB有点BT，experienced的还要on-site两次才进formal interview，不够
: efficient也不尊重interviewee的时间
: 而且只面算法也挺无聊的，个人感觉
: 对于experienced的candidate，纯算法的coding在实际工作中能占多大比例？远不如
: OOD，system design，performance/threading重要吧。。
|
|
|
g*****e
发帖数: 282 | 41 想起一道题，1,2,3,4->shift left by k=2=>3,4,1,2。求对应array和k，要求完成
shift right/left的高效率算法
【在 w******a 的大作中提到】
: 一不小心，上次写的面经第一部分上了十大推荐。太激动了，谢谢斑斑奖励的包子。还
: 要特别感谢aeon同学送的大包子。（第一部分在这里：http://www.mitbbs.com/article_t/JobHunting/31659453.html）
: 话说第一次on-site，我本人自己感觉良好，觉着题目都做出来了，虽然有些多余变量
: ，也没关系吧。于是喜滋滋的等着那轮四个人的interview。没想到，过了几天，HR哥
: 哥写信来，说面试官觉得我写程序不够快不够简洁，建议再来coding的面试。无语，谁
: 让咱不是那种在whiteboard上写code如流水的牛人，只好灰溜溜的同意再来一次on-
: site。
: 第二次是一个很nice的哥哥面我，一直微笑，在我卡壳的时候，也都提示我。废话少说
: ，上题目：
: 1. 一个rotated的排序整数数组，比如A=[6，8，1，2，4，5]，写code找一个给定元素
|
i**********e
发帖数: 1145 | 42 http://www.ihas1337code.com/2010/04/rotating-array-in-place.html
This is a famous problem mentioned in Programming Pearls. It is a good trick
to know.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g*****e 的大作中提到】
: 想起一道题，1,2,3,4->shift left by k=2=>3,4,1,2。求对应array和k，要求完成
: shift right/left的高效率算法
|
