Amazon Intern面经

刚面完的的Amazon Intern, 题目不难，感觉是跪了，发个面经。
电话接起来，先让我自我介绍一下，然后就开始coding。这时我才听出来是个三哥。

先是写binary search, 脑子有点短路，最后跳出left <= right的loop后还加了个if条件判断是否找到，被三哥指出来，直接return -1就好了。然后给他描述一下是怎么运行的。

follow up是有duplicates的情况，返回任意index怎么做，返回最左边的index怎么做，这里又写了一个bug

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

两个问题结束。


总的来说，感觉三哥人超级好，口音也还好（虽然有好几次让他重复），会一直引导我写，可是我写出了各种bug。。。肯定是跪了。。心塞。


补充内容 (2016-1-9 07:14):
12/30 offer get.

先找到pivot点也就是题目中的那个最小点，然后将数组分成两部分之后继续做BS

1. public int search(int[] nums, int target) {
   
2.         // find the smallest point
   
3.         int start = 0, end = nums.length - 1;
   
4.         int pivot = 0;
   
5.         while(start <= end) {
   
6.             int mid = start + (end - start) / 2;
   
7.             if(nums[mid] == target) {
   
8.                 return mid;
   
9.             }
   
10.             if(mid > 0 && mid < nums.length - 1) {
    
11.                 if(nums[mid - 1] > nums[mid] && nums[mid + 1] > nums[mid]) {
    
12.                     pivot = mid;
    
13.                     break;
    
14.                 }
    
15.                 else if(nums[mid - 1] < nums[mid]) {
    
16.                     end = mid - 1;
    
17.                 }
    
18.                 else {
    
19.                     start = mid + 1;
    
20.                 }
    
21.             }
    
22.             else {
    
23.                 break;
    
24.             }
    
25.         }
    
26.         
    
27.         start = 0;
    
28.         end = pivot;
    
29.         while(start <= end) {
    
30.             int mid = start + (end - start) / 2;
    
31.             if(nums[mid] == target) {
    
32.                 return mid;
    
33.             }
    
34.             else if(nums[mid] > target) {
    
35.                 start = mid + 1;
    
36.             }
    
37.             else {
    
38.                 end = mid - 1;
    
39.             }
    
40.         }
    
41.         
    
42.         start = pivot;
    
43.         end = nums.length - 1;
    
44.         while(start <= end) {
    
45.             int mid = start + (end - start) / 2;
    
46.             if(nums[mid] == target) {
    
47.                 return mid;
    
48.             }
    
49.             else if(nums[mid] < target) {
    
50.                 start = mid + 1;
    
51.             }
    
52.             else {
    
53.                 end = mid - 1;
    
54.             }
    
55.         }
    
56.         
    
57.         
    
58.         return -1;
    
59.     }

复制代码

lpx1989 发表于 2016-1-9 07:28
我想到一个方法，第一遍logN找到最小点，然后分两边各搜一下，其实还是logN。就找到了

{1, 3, 50, 10, 9, 7, 6}
这种数组的最小点一定是最左，或者最又。

可行方法是，找到最大点，然后把array parition成2部分，然后每部分都会是单一上升，或者下降。
然后在写2个binary search一个是上升的，一个是下降的。
所以这题需要写3个binary search

yhfyhf 发表于 2016-1-9 07:37
哦哦 我忘了是返回true/false还是index。反正算法对了就行了，这个不重要哈哈哈哈

不是返回index的问题。。
是一个binary search没发做啊。
{1, 3, 50, 10, 9, 7, 6}
binary search第一部找pivot, 10是pivot,但是下一部呢？怎么判断是向左走还是向又走呢？

这样就可以了，binary search。。。。。。。希望我的电面也这样

楼主有消息了么，过了吗？

follow up是[9, 8, 7, 1, 2, 3, 4]

是找一个input的数字，还是最大，或者最小。

xiaozhuxiaozhu 发表于 2016-1-9 07:08
follow up是[9, 8, 7, 1, 2, 3, 4]

是找一个input的数字，还是最大，或者最小。

找一个给定的数字。

yhfyhf 发表于 2016-1-9 07:14
找一个给定的数字。

这是个好问题，以前还真没考虑过。
{1, 3, 50, 10, 9, 7, 6}

这个数组，怎么搜？比如要找7
第一遍pivot = 10，然后发现10的左面比他大，右边比他小。然后呢？因为小数可能出现在10个左边，也可能出现在右边。难道还要在加个dfs?

补充内容 (2016-1-9 07:20):
求龟哥给个解法

xiaozhuxiaozhu 发表于 2016-1-9 07:19
这是个好问题，以前还真没考虑过。
{1, 3, 50, 10, 9, 7, 6}

找pivot时比较的是相邻的两个元素。

xiaozhuxiaozhu 发表于 2016-1-8 19:19
这是个好问题，以前还真没考虑过。
{1, 3, 50, 10, 9, 7, 6}

我想到一个方法，第一遍logN找到最小点，然后分两边各搜一下，其实还是logN。就找到了

lpx1989 发表于 2016-1-9 07:28
我想到一个方法，第一遍logN找到最小点，然后分两边各搜一下，其实还是logN。就找到了

对，我写的就是这种方法。所以其实是两遍或三遍binary search。

yhfyhf 发表于 2016-1-9 07:25
找pivot时比较的是相邻的两个元素。

我比较了啊， 10的左边比他大，右边比他小，但是因为不是sorted，所以左边右边都可能出现比他小的数