推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3747|回复: 28
收起左侧

Amazon 1.25 phone interview

[复制链接] |试试Instant~ |关注本帖
tj474474 发表于 2016-1-26 03:11:42 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Amazon - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
刚面完Amazon,命中一题昨天刷到的面经来回馈地里一下. from: 1point3acres.com/bbs
是一个从VA打来的电话...
AWS组做Private Virtual Cloud的白人小哥

一开始就选一个project介绍一下自己
然后就开始做题
1. Version Number (leetcode原题,还好昨天有刷到). 1point3acres.com/bbs
2. [0, 0, 2, 2, 1, 1, 3] 类似这样长度不定没有sorting的阵列里面一定会有唯一一个只出现一次的数字,另外如果是pair一定连续出现。

第一题是leetcode就不多讨论了。
第二题O(n)的做法有不少,如果是一般情况我们会用hashtable, bit operation XOR。
我则是用了pair会两两出现的性质,直接traverse一遍阵列。
做完了之后问有没有办法优化。
这题可以用binary search变成O(lgN),观察mid与他相邻的左右的关系可以知道lonely number出现在左边还右边。

最后时间快到了就问我一个search term auto completion大概要怎么做?我是讲trie不知道有没有其他办法?

然后最后让我自己列出Hashtable跟binary tree的operation并比较他们的复杂度。

我比了find, insert, delete, range_search。. 1point3acres.com/bbs
求offer!



补充内容 (2016-2-14 03:41):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
足足等了两周又五天
中间催了一次没消息
2/13凌晨四点终于收到offer了

评分

3

查看全部评分

本帖被以下淘专辑推荐:

ningtaohaha 发表于 2016-2-11 11:17:11 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
我也贴一个:
public int findOdd(int[] array) {.1point3acres缃
        if (array == null ) {
            return -1;
        }. 1point 3acres 璁哄潧
        if (array.length == 1) {
            return 0;
        }
        int left = 0;. from: 1point3acres.com/bbs
        int right = array.length - 1;
        while (left < right - 1) {
            int mid = left + (right - left) / 2;
            if (array[mid] == array[mid - 1]) {
                int leftLength = mid - left;
                if (leftLength % 2 == 0) {
                    right = mid - 2;
                } else {
                    left = mid + 1;
                }
            } else {
                int leftLength = mid - left;
                if (leftLength % 2 == 0) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
. 1point 3acres 璁哄潧            }
        }
        return right;
    }
回复 支持 1 反对 0

使用道具 举报

gjxwin 发表于 2016-1-31 13:56:06 | 显示全部楼层
关注一亩三分地微博:
Warald

这题二分法做,一遍做对很难,必须得找几个例子对照着写和改。代码如下,lz参考一下
. From 1point 3acres bbs        int low = 0;
        int high = nums.length - 1;. 1point 3acres 璁哄潧
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) {. from: 1point3acres.com/bbs
                if (nums[mid] == nums[mid + 1])
                    low = mid + 2;
                else return nums[0];
            }

            if (mid % 2 == 1) {. 1point3acres.com/bbs
                if (nums[mid] != nums[mid - 1]) high = mid;
                else low = mid + 1;
            }
            else {
                if (nums[mid] != nums[mid - 1]) low = mid;
                else high = mid - 2;
            }
        }
        return nums[low];
回复 支持 1 反对 0

使用道具 举报

luofeidream 发表于 2016-1-29 07:33:00 | 显示全部楼层
小海 发表于 2016-1-29 06:17
[0, 0, 2, 2, 1, 1, 3] 类似这样长度不定没有sorting -- 为什么能用binary search 如果不是sorted ?

我觉得哈,因为数组的长度一定是奇数的,所以中间元素如果与其左边元素不相等,那么就在左边,如果与右边不相等,那么就在右边,仔细想一下

补充内容 (2016-1-29 07:34):
前提是不能有duplicated的pair
回复 支持 1 反对 0

使用道具 举报

googlerr 发表于 2016-1-29 08:37:21 | 显示全部楼层
刚才忘了加一些基本的注释,所以重新发一下:
  1.         /*. visit 1point3acres.com for more.
  2.          * facts:
  3.          * 1. array length N has to be odd
  4.          * 2. unique number has to occur at an even index
  5.          * 3. if unique number occur at index `k`, then [0, k-1] contains k/2 pairs and [k+1, N-1] contains the remaining (N-1-k)/2 pairs
  6.          */
  7.         public int uniqueNumber(int[] arr) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8.                 int N = arr.length, lo = 0, hi = N-1;
  9.                 while(lo < hi-1) { // if lo==hi-1, lo must be the unique number because lo is always an even index following the code below. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.                         int mid = lo + ((hi-lo)>>1);
  11.                         if(mid%2==0) { // mid is an even index
  12.                                 if(arr[mid]==arr[mid-1]) hi = mid-2; // unique number must be before mid-1
  13.                                 else lo = mid; // unique number must not be before mid
  14.                         }
  15.                         else {
  16.                                 if(arr[mid]==arr[mid-1]) lo = mid+1; // unique number must be after mid
  17.                                 else hi = mid; // unique number must not be after mid
  18.                         }
  19.                 }
  20.                 return arr[lo]; // since lo is guaranteed to be even, it must be the unique index when while loop ends
  21.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

googlerr 发表于 2016-1-29 08:24:33 | 显示全部楼层
楼主能这么短时间内想到O(log N)的方法确实很赞!
贴个第二题的Binary Search的代码吧,欢迎拍砖:
  1.         public int uniqueNumber(int[] arr) {
  2.                 int N = arr.length, lo = 0, hi = N-1;
  3.                 while(lo < hi-1) {
  4.                         int mid = lo + ((hi-lo)>>1);
  5.                         if(mid%2==0) {
  6.                                 if(arr[mid]==arr[mid-1]) hi = mid-2;
  7.                                 else lo = mid;
  8.                         }
  9.                         else {
  10.                                 if(arr[mid]==arr[mid-1]) lo = mid+1;
  11.                                 else hi = mid;
  12.                         }
  13.                 }
  14.                 return lo;
  15.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

七七要加油 发表于 2016-1-26 03:18:22 | 显示全部楼层
楼主offer妥妥的~
回复 支持 1 反对 0

使用道具 举报

gouber 发表于 2016-1-26 03:30:20 | 显示全部楼层
楼主offer妥妥的!下周面,求好运求原题~~
回复 支持 反对

使用道具 举报

wangsnowyin 发表于 2016-1-26 04:29:17 | 显示全部楼层
楼主跟我面的一毛一样 感觉楼主好强大!!!
回复 支持 反对

使用道具 举报

JunoJ 发表于 2016-1-26 05:45:29 | 显示全部楼层
楼主好厉害啊。。如果是我就跪了
回复 支持 反对

使用道具 举报

ljdsoft 发表于 2016-1-26 06:17:49 | 显示全部楼层
粘粘楼主喜庆,后天也要面了~~
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-1-26 09:19:56 | 显示全部楼层
JunoJ 发表于 2016-1-26 05:45. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主好厉害啊。。如果是我就跪了

累积八场跪掉的面试的经验跟运气哈哈
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-1-26 09:22:38 | 显示全部楼层
gouber 发表于 2016-1-26 03:30
楼主offer妥妥的!下周面,求好运求原题~~

會的放心吧
回复 支持 反对

使用道具 举报

小海 发表于 2016-1-29 06:17:50 | 显示全部楼层
[0, 0, 2, 2, 1, 1, 3] 类似这样长度不定没有sorting -- 为什么能用binary search 如果不是sorted ?
回复 支持 反对

使用道具 举报

uuubbb123 发表于 2016-1-29 07:21:59 | 显示全部楼层
如果被我碰到这些题。。。该如何是好
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-1-29 07:44:49 | 显示全部楼层
luofeidream 发表于 2016-1-29 07:33
我觉得哈,因为数组的长度一定是奇数的,所以中间元素如果与其左边元素不相等,那么就在左边,如果与右边 ...

确实我也是这么想的
可以分三种状况
第一种就是mid刚好就是那个lonely number那他会跟两边都不一样。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二种mid跟左边一样. more info on 1point3acres.com
这表示mid的左边现在的成员有. visit 1point3acres.com for more.
x x x mid
一共有偶数个(因为总共是奇数个数字扣掉中间值之后两边会是偶数个数字)

既然已经知道偶数个当中其中一个是mid,那就表示剩下的奇数个xxx有包含一个lonely number,于是就不用看右边了。

第三种情况就是mid跟他右边一样,那只是第二种情况换一边想。. from: 1point3acres.com/bbs

补充内容 (2016-1-29 09:04):
看完googlerr的代码发现我的思路确实有不完整的地方
.1point3acres缃
mid的左右两边不一定是偶数个,若不是偶数个的时候反而发现邻居一样的时候要看的是另外一边,总之就是要看剩下奇数个的那一边。

所以要加上判断mid是奇数偶數
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-1-29 07:46:13 | 显示全部楼层
uuubbb123 发表于 2016-1-29 07:21
如果被我碰到这些题。。。该如何是好

多刷题多看面经就会发现都是差不多啦. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
最难的题型应该是OOD才是该担心的
回复 支持 反对

使用道具 举报

elvisxyu 发表于 2016-1-29 10:15:20 | 显示全部楼层
看来是要去VA office的节奏啊 高端office  员工都是有3年以上工作经验的
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-1-31 23:03:20 | 显示全部楼层
gjxwin 发表于 2016-1-31 13:56. from: 1point3acres.com/bbs
这题二分法做,一遍做对很难,必须得找几个例子对照着写和改。代码如下,lz参考一下
        int low =  ...

看完地里各位大神的代码发现当初少考虑好多情形...
希望别跪了...
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-2-1 00:11:04 | 显示全部楼层
tj474474 发表于 2016-1-31 23:03
看完地里各位大神的代码发现当初少考虑好多情形...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴希望别跪了...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我觉得你应该没问题,这个二分法要写对真的非常难。
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-2-3 09:29:19 | 显示全部楼层
tj474474 发表于 2016-1-29 07:44
确实我也是这么想的. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
可以分三种状况
第一种就是mid刚好就是那个lonely number那他会跟两边都不一样。

为什么左右两边不一定为偶数?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-25 08:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表