一亩三分地论坛

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

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

11/03 AMAZON VIDEO面经

[复制链接] |试试Instant~ |关注本帖
seashore115 发表于 2015-3-12 03:38:57 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Amazon - 网上海投 - 其他 |Other

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

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

x
刚刚面完vedio,来地里发布一下,攒一下人品,求offer。具体内容如下:

刚开场是一个叫Mike的30左右的男人,他先自我介绍。之后让我回忆之前oa的coding题,说一下思路。他根本就不把代码贴到collabit,让你自己想。幸亏背的腹稿。5分钟就说完了,他说他想不到更好的了,没有问我voewl 的那道题(他说他对pattern string searching不感兴趣)。之后就是聊了25分钟,我就问了a家的优缺点和当地环境。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
下面是我的腹稿
-----------------
We need to know how many different bits between element1 and element2.
First step, exclusive or element1 and element2 together and store the result byte data into the res. In the bitwise operation, xor is a logical operation that outputs true whenever both inputs differ. so we could know that the bit in res that is one shows the bit in same position from element1 and from element2 are different. likewise. In addition, we knows that the two grey code neighbors differ by only one bit.The possible res that satisfy the condition has only one bit that is one, and expect this bit, other seven bits are zero. Next step we use loop to compare res with eight possible values. If the one situation matches the res, we return true. If all the possible situations could not equal to the res, we would return false.
.鐣欏璁哄潧-涓浜-涓夊垎鍦


我写的代码是:


----------------------


. From 1point 3acres bbspublic static int greyCode(byte element1, byte element2) {                byte res = (byte) (element1 ^ element2);. From 1point 3acres bbs
                for (int i = 0; i <= 7; i++) {
                        byte temp = (byte)(1 << i);. From 1point 3acres bbs
                        if (temp == res) {
                                return 1;. more info on 1point3acres.com
                        }. more info on 1point3acres.com
                }
                Sy[color=rgb(85, 85, 85) !important]stem.out.println("No");. from: 1point3acres.com/bbs
                return 0;

        }
.鐣欏璁哄潧-涓浜-涓夊垎鍦
求offer啊。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.





补充内容 (2015-3-19 02:47):-google 1point3acres
今天收到offer,谢谢大家祝福也祝大家收到理想offer
yapingchen1990 发表于 2015-3-20 09:11:08 | 显示全部楼层
亲~我不知道stringRotate扯啥。。能推荐些资料看看么。跪谢!希望当同事!
回复 支持 1 反对 0

使用道具 举报

oldman09 发表于 2015-3-12 03:41:45 | 显示全部楼层
楼主一定会有offer的!
回复 支持 反对

使用道具 举报

 楼主| seashore115 发表于 2015-3-12 03:43:06 | 显示全部楼层
oldman09 发表于 2015-3-12 03:41
楼主一定会有offer的!

多谢你吉言啊
回复 支持 反对

使用道具 举报

头像被屏蔽
mstc123 发表于 2015-3-12 03:46:44 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| seashore115 发表于 2015-3-12 03:55:19 | 显示全部楼层
mstc123 发表于 2015-3-12 03:46. 1point 3acres 璁哄潧
lz是什么时候due的oa?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2月23日due的。。
回复 支持 反对

使用道具 举报

patrick2015 发表于 2015-3-12 07:07:10 | 显示全部楼层
难道写graycode的才有video?
回复 支持 反对

使用道具 举报

 楼主| seashore115 发表于 2015-3-12 07:13:58 | 显示全部楼层
patrick2015 发表于 2015-3-12 07:07. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
难道写graycode的才有video?

不是吧。。。。
回复 支持 反对

使用道具 举报

海拔2纳米 发表于 2015-3-12 07:33:12 | 显示全部楼层
怎么坛子里很多人都喜欢打成vedio,看着好别扭...
歪题了,祝LZ早日拿到offer
回复 支持 反对

使用道具 举报

 楼主| seashore115 发表于 2015-3-12 07:35:27 | 显示全部楼层
海拔2纳米 发表于 2015-3-12 07:33
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴怎么坛子里很多人都喜欢打成vedio,看着好别扭...
歪题了,祝LZ早日拿到offer

谢谢了,求好运。
回复 支持 反对

使用道具 举报

TsenAlex 发表于 2015-3-12 08:39:01 | 显示全部楼层
LZ HR啥时候给你的video?
回复 支持 反对

使用道具 举报

 楼主| seashore115 发表于 2015-3-12 11:50:40 | 显示全部楼层
TsenAlex 发表于 2015-3-12 08:39
LZ HR啥时候给你的video?

3月4号
回复 支持 反对

使用道具 举报

xjwun 发表于 2015-3-13 05:24:26 | 显示全部楼层
额,我似乎也是这个人。就聊了二十分钟就没话说了,有点担忧
回复 支持 反对

使用道具 举报

 楼主| seashore115 发表于 2015-3-13 05:26:19 | 显示全部楼层
xjwun 发表于 2015-3-13 05:24
额,我似乎也是这个人。就聊了二十分钟就没话说了,有点担忧

是不是胖胖的那个?祝都有offer啊
回复 支持 反对

使用道具 举报

xjwun 发表于 2015-3-13 06:20:52 | 显示全部楼层
seashore115 发表于 2015-3-13 05:26.1point3acres缃
是不是胖胖的那个?祝都有offer啊

恩恩,是他,早点看到lz帖子就好了,没准备腹稿现场想不起来xor英文怎么说。。。他有没有和你说下一步等recrutier联系?
回复 支持 反对

使用道具 举报

 楼主| seashore115 发表于 2015-3-13 07:45:47 | 显示全部楼层
xjwun 发表于 2015-3-13 06:20
恩恩,是他,早点看到lz帖子就好了,没准备腹稿现场想不起来xor英文怎么说。。。他有没有和你说下一步等r ...

他说了,一周内有结果
回复 支持 反对

使用道具 举报

 楼主| seashore115 发表于 2015-3-20 11:27:07 | 显示全部楼层
yapingchen1990 发表于 2015-3-20 09:11. 1point3acres.com/bbs
亲~我不知道stringRotate扯啥。。能推荐些资料看看么。跪谢!希望当同事!
.鐣欏璁哄潧-涓浜-涓夊垎鍦
有这几个主流的pattern search methods 你可以了解一下。geeksforgeeks有详解
Kmp

The KMP matching algorithm uses degenerating property (pattern having same sub-patterns appearing more than once in the pattern) of the pattern and improves the worst case complexity to O(n). The basic idea behind KMP’s algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text (since they matched the pattern characters prior to the mismatch). We take advantage of this information to avoid matching the characters that we know will anyway match.
KMP algorithm does some preprocessing over the pattern pat[] and constructs an auxiliary array lps[] of size m (same as size of pattern). Here name lps indicates longest proper prefix which is also suffix.. For each sub-pattern pat[0…i] where i = 0 to m-1, lps stores length of the maximum matching proper prefix which is also a suffix of the sub-pattern pat[0..i].. from: 1point3acres.com/bbs

Rabin-Karp algorithm:

Rabin Karp algorithm matches the hash value of the pattern with the hash value of current substring of text, and if the hash values match then only it starts matching individual characters. So Rabin Karp algorithm needs to calculate hash values for following strings.

Calculate hash value for next window of text: Remove leading digit,add trailing digit   . more info on 1point3acres.com

1) Pattern itself.
2) All the substrings of text of length m. .1point3acres缃

Since we need to efficiently calculate hash values for all the substrings of size m of text, we must have a hash function which has following property.
Hash at the next shift must be efficiently computable from the current hash value and next character in text or we can say hash(txt[s+1 .. s+m]) must be efficiently computable from hash(txt[s .. s+m-1]) and txt[s+m] i.e.,  hash(txt[s+1 .. s+m])= rehash(txt[s+m], hash(txt[s .. s+m-1])and rehash must be O(1) operation.


Boyer Moore pattern searching algorithm
. 鍥磋鎴戜滑@1point 3 acres
The character of the text which doesn’t match with the current character of pattern is called the Bad Character. Whenever a character doesn’t match, we slide the pattern in such a way that aligns the bad character with the last occurrence of it in pattern. We preprocess the pattern and store the last occurrence of every possible character in an array of size equal to alphabet size. If the character is not present at all, then it may result in a shift by m (length of pattern). Therefore, the bad character heuristic takes O(n/m) time in the best case.
. 鍥磋鎴戜滑@1point 3 acres
Finite Automata. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

In FA based algorithm, we preprocess the pattern and build a 2D array that represents a Finite Automata. Construction of the FA is the main tricky part of this algorithm. Once the FA is built, the searching is simple. In search, we simply need to start from the first state of the automata and first character of the text. At every step, we consider next character of text, look for the next state in the built FA and move to new state. If we reach final state, then pattern is found in text. Time complexity of the search prcess is O(n).
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-3-20 11:41:32 | 显示全部楼层
seashore115 发表于 2015-3-20 11:27
有这几个主流的pattern search methods 你可以了解一下。geeksforgeeks有详解
Kmp
-google 1point3acres
谢谢楼主回复!不过我有点不能理解的是。。。stringRotate算是pattern search???求解释
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-3-20 11:43:26 | 显示全部楼层
seashore115 发表于 2015-3-20 11:27
有这几个主流的pattern search methods 你可以了解一下。geeksforgeeks有详解
Kmp

哦~~~~~懂了 substring search。。。原谅我的自言自语。。。呜呜(我也不太懂,,为什么拿到video后开始失眠。。)
回复 支持 反对

使用道具 举报

ppcheng 发表于 2015-3-24 23:36:37 | 显示全部楼层
楼主请问下你当时string rotate写得腹稿是啥?能share一下嘛. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 01:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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