一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2426|回复: 28
收起左侧

Amazon 1.25 phone interview

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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

第一题是leetcode就不多讨论了。
第二题O(n)的做法有不少,如果是一般情况我们会用hashtable, bit operation XOR。
我则是用了pair会两两出现的性质,直接traverse一遍阵列。.鏈枃鍘熷垱鑷1point3acres璁哄潧
做完了之后问有没有办法优化。
这题可以用binary search变成O(lgN),观察mid与他相邻的左右的关系可以知道lonely number出现在左边还右边。. 鍥磋鎴戜滑@1point 3 acres

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

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

我比了find, insert, delete, range_search。
求offer!


. From 1point 3acres bbs
补充内容 (2016-2-14 03:41):-google 1point3acres
足足等了两周又五天
中间催了一次没消息
2/13凌晨四点终于收到offer了

评分

3

查看全部评分

本帖被以下淘专辑推荐:

ningtaohaha 发表于 2016-2-11 11:17:11 | 显示全部楼层
我也贴一个:.鏈枃鍘熷垱鑷1point3acres璁哄潧
public int findOdd(int[] array) {
        if (array == null ) {
            return -1;
        }
        if (array.length == 1) {
            return 0;
        }
        int left = 0;
        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;
                }
            }
        }
        return right;
    }
回复 支持 1 反对 0

使用道具 举报

gjxwin 发表于 2016-1-31 13:56:06 | 显示全部楼层
tj474474 发表于 2016-1-26 09:22.鐣欏璁哄潧-涓浜-涓夊垎鍦
會的放心吧

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

            if (mid % 2 == 1) {
                if (nums[mid] != nums[mid - 1]) high = mid;
                else low = mid + 1;
            }. Waral 鍗氬鏈夋洿澶氭枃绔,
            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.鏈枃鍘熷垱鑷1point3acres璁哄潧
[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.         /*
  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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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) {. From 1point 3acres bbs
  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. 1point 3acres 璁哄潧
我觉得哈,因为数组的长度一定是奇数的,所以中间元素如果与其左边元素不相等,那么就在左边,如果与右边 ...

确实我也是这么想的
可以分三种状况
第一种就是mid刚好就是那个lonely number那他会跟两边都不一样。

第二种mid跟左边一样
这表示mid的左边现在的成员有
x x x mid. 1point3acres.com/bbs
一共有偶数个(因为总共是奇数个数字扣掉中间值之后两边会是偶数个数字)

既然已经知道偶数个当中其中一个是mid,那就表示剩下的奇数个xxx有包含一个lonely number,于是就不用看右边了。
. visit 1point3acres.com for more.
第三种情况就是mid跟他右边一样,那只是第二种情况换一边想。

补充内容 (2016-1-29 09:04):
看完googlerr的代码发现我的思路确实有不完整的地方
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
mid的左右两边不一定是偶数个,若不是偶数个的时候反而发现邻居一样的时候要看的是另外一边,总之就是要看剩下奇数个的那一边。. Waral 鍗氬鏈夋洿澶氭枃绔,

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

使用道具 举报

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

多刷题多看面经就会发现都是差不多啦. 1point 3acres 璁哄潧
最难的题型应该是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 1point 3acres bbs
这题二分法做,一遍做对很难,必须得找几个例子对照着写和改。代码如下,lz参考一下
        int low =  ...

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

使用道具 举报

gjxwin 发表于 2016-2-1 00:11:04 | 显示全部楼层
tj474474 发表于 2016-1-31 23:03
看完地里各位大神的代码发现当初少考虑好多情形.... visit 1point3acres.com for more.
希望别跪了...
. 鍥磋鎴戜滑@1point 3 acres
我觉得你应该没问题,这个二分法要写对真的非常难。
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-2-3 09:29:19 | 显示全部楼层
tj474474 发表于 2016-1-29 07:44
确实我也是这么想的
可以分三种状况
第一种就是mid刚好就是那个lonely number那他会跟两边都不一样。

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 02:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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