s*********e
发帖数: 36 | 1 昨天面完facebook第二轮，两次的面试题如下：
第一轮：
1. atoi, write exact code
2. 电话键盘上每个数字对应一系列字母，给任意长度电话号码，打印所有可能字母组
合。基本就是PIE
上的原题
第二轮：
1. Two sorted array, find their intersection, write exact code
2. Part of a sorted array is shifted, like:
1 2 3 4 5 6--> 6 5 1 2 3 4
but we don't know how many digits are shifted. Write a efficient method to
find the position of a given value in the array. |
s*********e
发帖数: 36 | 2 xie写错了
2. Part of a sorted array is shifted, like:
=======================
应该是 1 2 3 4 5 6--> 5 6 1 2 3 4 |
i**********b
发帖数: 77 | |
i**********b
发帖数: 77 | 4 第三轮电话面试？那可能因为你前两次面试的结果不是很好也不是很坏。
如果很好就应该onsite了。 |
s*********e
发帖数: 36 | 5 Programming Interviews Exposed
【在 i**********b 的大作中提到】
: PIE 是啥？
|
K******g
发帖数: 1870 | 6 第二轮第二题，题目不清楚。能否举个例子？
如果要判断一个given value的位置，直接扫描一遍，看有多少个数比它小，不就得了？
【在 s*********e 的大作中提到】
: 昨天面完facebook第二轮，两次的面试题如下：
: 第一轮：
: 1. atoi, write exact code
: 2. 电话键盘上每个数字对应一系列字母，给任意长度电话号码，打印所有可能字母组
: 合。基本就是PIE
: 上的原题
: 第二轮：
: 1. Two sorted array, find their intersection, write exact code
: 2. Part of a sorted array is shifted, like:
: 1 2 3 4 5 6--> 6 5 1 2 3 4
|
l*****a
发帖数: 14598 | 7 那你就是O（n）
这个题可以O（Logn）的
了？
【在 K******g 的大作中提到】
: 第二轮第二题，题目不清楚。能否举个例子？
: 如果要判断一个given value的位置，直接扫描一遍，看有多少个数比它小，不就得了？
|
K******g
发帖数: 1870 | 8 你怎么做到O(logn)？不管怎么样，你都要先扫描一遍数组找到那些被shift的地方，这
个就已经是O（n)了。
【在 l*****a 的大作中提到】
: 那你就是O（n）
: 这个题可以O（Logn）的
:
: 了？
|
b********w
发帖数: 110 | |
o**********t
发帖数: 406 | 10 这题无穷经典，不过网上很多解法很不直观，不停地 check boundry 程序看起来很乱。
我自己的解法是：binary search look for the shift point --- O(logN)
然后按照 shift 计算一个 virtual index，整个数组就可以认为是标准排序后的，再
次 binary search 找到所需的值 --- O(logN)
【在 K******g 的大作中提到】
: 你怎么做到O(logn)？不管怎么样，你都要先扫描一遍数组找到那些被shift的地方，这
: 个就已经是O（n)了。
|
y**i
发帖数: 1112 | 11 就是二分查找啊，才能做到O(logn)，不过比较麻烦的就是如果有重复元素的情况
【在 K******g 的大作中提到】
: 你怎么做到O(logn)？不管怎么样，你都要先扫描一遍数组找到那些被shift的地方，这
: 个就已经是O（n)了。
|
s*********e
发帖数: 36 | 12 确实需要多次check bound。 我写的这个不考虑重复元素的情况
int search(int arr[], int l, int r, int value )
{
int m = (l+r)/2;
if(value == arr[m]){
return m;
}
if(l > r){
return -1;
}
if(value < arr[m])
{ // number of shifted bits < length/2
if(arr[l] > arr[m])
return search(arr, l, m-1,value);
else{
// not shifted or shifted bits >= length/2
if(value < arr[l])
return search(arr, m+1, r, value); |
i*****r
发帖数: 265 | 13 I don't think you can achieve O(logn) with repetitive elements ... You
cannot even find shift point within O(logn)
【在 y**i 的大作中提到】
: 就是二分查找啊，才能做到O(logn)，不过比较麻烦的就是如果有重复元素的情况
|
c******f
发帖数: 2144 | |
