hp smb 重新charge了，有啥希望么？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

hp smb 重新charge了，有啥希望么？

hp smb 重新charge了，有啥希望么？# PDA - 掌中宝

s*e2011-09-01 07:09

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.

a*h2011-09-01 07:09

2 楼

还是hp就是喜欢这么涮人啊。。。也没收到什么在不在25k之内的邮件

s*e2011-09-01 07:09

3 楼

xie写错了
2. Part of a sorted array is shifted, like:
=======================
应该是 1 2 3 4 5 6--> 5 6 1 2 3 4

i*b2011-09-01 07:09

4 楼

PIE 是啥？

i*b2011-09-01 07:09

5 楼

第三轮电话面试？那可能因为你前两次面试的结果不是很好也不是很坏。
如果很好就应该onsite了。

s*e2011-09-01 07:09

6 楼

Programming Interviews Exposed

【在 i**********b 的大作中提到】

: PIE 是啥？

K*g2011-09-01 07:09

7 楼

第二轮第二题，题目不清楚。能否举个例子？
如果要判断一个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*a2011-09-01 07:09

8 楼

那你就是O（n）
这个题可以O（Logn）的

了？

【在 K******g 的大作中提到】

: 第二轮第二题，题目不清楚。能否举个例子？
: 如果要判断一个given value的位置，直接扫描一遍，看有多少个数比它小，不就得了？

K*g2011-09-01 07:09

9 楼

你怎么做到O(logn)？不管怎么样，你都要先扫描一遍数组找到那些被shift的地方，这
个就已经是O（n)了。

【在 l*****a 的大作中提到】

: 那你就是O（n）
: 这个题可以O（Logn）的
:
: 了？

b*w2011-09-01 07:09

10 楼

我上次通知说第三轮，结果后来又说把我据了。

o*t2011-09-01 07:09

11 楼

这题无穷经典，不过网上很多解法很不直观，不停地 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*i2011-09-01 07:09

12 楼

就是二分查找啊，才能做到O(logn)，不过比较麻烦的就是如果有重复元素的情况

【在 K******g 的大作中提到】

: 你怎么做到O(logn)？不管怎么样，你都要先扫描一遍数组找到那些被shift的地方，这
: 个就已经是O（n)了。

s*e2011-09-01 07:09

13 楼

确实需要多次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);