logo
Redian新闻
>未名空间
>Hardware - 计算机硬件
>
64G mSATA是不是MyDigital那个最划算？
avatar
64G mSATA是不是MyDigital那个最划算？# Hardware - 计算机硬件
k*i
1 楼
晚了半个小时才打电话。。。
是个三哥， 英语很是费解， 不停的i am sorry， excuse me。。
接下来问了project 的东西， 问的很详细，就不多说了，
然后是个算法题，
给一个rotated sorted array，
例如： 3 4 5 1 2
然后给一个数 例如 6， 然后去找他是否在array里面。
我首先说是找到分界点， 然后对两边用binary search， 这个效率应该是O(n)吧， 毕
竟最坏情
况下找到分界点要遍历一遍。
然后他就问binary search 为啥不写成recuisive的， 然后问recursive和平常的有啥
区别。。。
然后他问怎么能够提高算法的效率， 我说能到logn。。。就跟就是用binary和递归每
次找中点。
。。
bless自己了。
avatar
x*m
2 楼
15年re-fin的居然还要4.375%.
avatar
s*d
3 楼
看到这个想起国内一个笑话
有一老头尿急，找不到公厕。转到一个墙角，刚掏出家伙，边上突然闪出一个戴红袖章
的老太太。小红旗一挥：随地大小便，罚款5元。老头急了：操，我看看自己的东西也
不行啊。
估计拿这个理由上法庭不会被法官采信。唉，还是国内好。。。
avatar
k*i
5 楼
对了 这种engineer面完给谁发 thank you letter呢？

【在 k**********i 的大作中提到】
: 晚了半个小时才打电话。。。
: 是个三哥， 英语很是费解， 不停的i am sorry， excuse me。。
: 接下来问了project 的东西， 问的很详细，就不多说了，
: 然后是个算法题，
: 给一个rotated sorted array，
: 例如： 3 4 5 1 2
: 然后给一个数 例如 6， 然后去找他是否在array里面。
: 我首先说是找到分界点， 然后对两边用binary search， 这个效率应该是O(n)吧， 毕
: 竟最坏情
: 况下找到分界点要遍历一遍。
avatar
j*8
6 楼
之前低的时候多少啊
avatar
l*n
7 楼
那个性能没有他说的那么好
avatar
i*s
8 楼
应该不用先找分解点，直接用binary search, 只不过需要分情况讨论每次应该往左边
还是右边跳。所以复杂度O(lgn)
>我首先说是找到分界点， 然后对两边用binary search， 这个效率应该是O(n)>吧， 毕
竟最坏情
况下找到分界点要遍历一遍。
avatar
j*8
9 楼
之前低的时候多少啊
avatar
t*s
10 楼
我提到过，这个网站很厚道地在产品图片上明示了Phison，群联主控的SSD历来给人一
种大U盘的错觉，这个AS数据虽然还能看，但是鬼知道它们怎么测出来的
avatar
D*h
11 楼
shifted sorted array的binary search也是O(lg n)的,判断条件稍微修改一下就行了.

【在 k**********i 的大作中提到】
: 晚了半个小时才打电话。。。
: 是个三哥， 英语很是费解， 不停的i am sorry， excuse me。。
: 接下来问了project 的东西， 问的很详细，就不多说了，
: 然后是个算法题，
: 给一个rotated sorted array，
: 例如： 3 4 5 1 2
: 然后给一个数 例如 6， 然后去找他是否在array里面。
: 我首先说是找到分界点， 然后对两边用binary search， 这个效率应该是O(n)吧， 毕
: 竟最坏情
: 况下找到分界点要遍历一遍。
avatar
x*m
12 楼
我看见最低4.25%, 听说有人去年12月拿到过4.125%.
avatar
p*o
13 楼
目前有啥适合x220的msata ssd (<=80GB)可以推荐的？

【在 t*****s 的大作中提到】
: 我提到过，这个网站很厚道地在产品图片上明示了Phison，群联主控的SSD历来给人一
: 种大U盘的错觉，这个AS数据虽然还能看，但是鬼知道它们怎么测出来的
avatar
k*i
14 楼
是啊， 我后来又写了这个， 修改下条件 然后递归做的

了.

【在 D***h 的大作中提到】
: shifted sorted array的binary search也是O(lg n)的,判断条件稍微修改一下就行了.
avatar
w*a
15 楼
4.375已经持续很久了.我前天锁了,不等了.12月底的时候要4.75呢.
avatar
w*n
16 楼
intel 310

【在 p**o 的大作中提到】
: 目前有啥适合x220的msata ssd (<=80GB)可以推荐的？
avatar
j*l
17 楼
这题不是前几天讨论过的么？是Google盗用Amazon的题目还是反过来？
发信人: bokertov (早上好), 信区: JobHunting
标 题: Amazon二面
发信站: BBS 未名空间站 (Thu Apr 1 20:17:29 2010, 美东)
面试官是位华人，非常nice，问的题目也不难
不过我又没答好，一道在circular sorted array里binary search的题目，
当时一着急，大脑一片空白。
挂了电话，几分钟内就有了思路。
唉，看来这次又黄了。
http://www.mitbbs.com/article_t/JobHunting/31563639.html
avatar
t*o
18 楼
这个东西和location有关系么?
比如加州和德州最低rate能一样么?
avatar
j*l
19 楼
如果有重复元素，还能O(logn)么？
比如
22222212
找1
如果没有重复元素
假定当前搜索区间开始的下标是s, 中点的下标是m, 结束的下标是e,
要查找的数是x，可以证明A[s] <= A[m]和A[m] <= A[e]至少有一个成立
if (s > e)
查找失败返回;
m = (s + e) / 2;
if (x == A[m] || x == A[s] || x == A[e])
查找成功返回;
if (A[s] <= A[m])
{
if (x > A[s] && x < A[m]
在区间[s, m-1]继续找
else
在区间[m+1, e]继续找
}
else if (A[m] <= A[e])
{
if (x > A[m] && x < A[e]
在区间[m+1, e]继续找
else
在区间[s, m-1]继续找
}
else
{
// This is not possible if the original array is circular sorted
avatar
k*i
20 楼
我觉得， 每次分一半， 有三种情况， 一遍是跟元来的一样的特点， 一遍是递增，或
者两边都
是递增，
然后对三种情况递归就可以了。 然后效率是logn

【在 j**l 的大作中提到】
: 如果有重复元素，还能O(logn)么？
: 比如
: 22222212
: 找1
: 如果没有重复元素
: 假定当前搜索区间开始的下标是s, 中点的下标是m, 结束的下标是e,
: 要查找的数是x，可以证明A[s] <= A[m]和A[m] <= A[e]至少有一个成立
: if (s > e)
: 查找失败返回;
: m = (s + e) / 2;
avatar
j*l
21 楼
不妨贴出你写的代码，验证下是否O(logn)时间也能解决重复元素的问题

【在 k**********i 的大作中提到】
: 我觉得， 每次分一半， 有三种情况， 一遍是跟元来的一样的特点， 一遍是递增，或
: 者两边都
: 是递增，
: 然后对三种情况递归就可以了。 然后效率是logn
avatar
k*i
22 楼
我发现我的程序 对重复元素好像不行。。。要修改， 刚看了看， 发现程序里有些小
问题， 但
是面试的三哥当时也没有问。。。

【在 j**l 的大作中提到】
: 不妨贴出你写的代码，验证下是否O(logn)时间也能解决重复元素的问题
avatar
x*y
23 楼
re-index to make it sorted
then binary

【在 k**********i 的大作中提到】
: 晚了半个小时才打电话。。。
: 是个三哥， 英语很是费解， 不停的i am sorry， excuse me。。
: 接下来问了project 的东西， 问的很详细，就不多说了，
: 然后是个算法题，
: 给一个rotated sorted array，
: 例如： 3 4 5 1 2
: 然后给一个数 例如 6， 然后去找他是否在array里面。
: 我首先说是找到分界点， 然后对两边用binary search， 这个效率应该是O(n)吧， 毕
: 竟最坏情
: 况下找到分界点要遍历一遍。
avatar
l*y
24 楼
如果有重复元素，递增与否是无法判断的，比如 22222212 这个例子
如果没有重复的元素，logn是可以的，否则，我觉得只能O(n)了

【在 k**********i 的大作中提到】
: 我觉得， 每次分一半， 有三种情况， 一遍是跟元来的一样的特点， 一遍是递增，或
: 者两边都
: 是递增，
: 然后对三种情况递归就可以了。 然后效率是logn
avatar
j*l
25 楼
这个预处理是O(n),
不过以后都是一劳永逸的O(logn)了

【在 x**y 的大作中提到】
: re-index to make it sorted
: then binary
avatar
w*l
26 楼
应该是直接二分查找就可以了吧
avatar
B*t
27 楼
有没有重复元素都是log（n)

【在 l*******y 的大作中提到】
: 如果有重复元素，递增与否是无法判断的，比如 22222212 这个例子
: 如果没有重复的元素，logn是可以的，否则，我觉得只能O(n)了
avatar
r*o
28 楼
能不能说说有重复元素怎么作的?
多谢。

【在 B*****t 的大作中提到】
: 有没有重复元素都是log（n)
avatar
B*t
29 楼
sorry, worst case is still O(N) if there are duplicates. average case is O(
logn)

【在 r****o 的大作中提到】
: 能不能说说有重复元素怎么作的?
: 多谢。
avatar
x*3
30 楼
好像预处理找sorted array的起点和结束可以是lgN, 用binary search找起点和结束

【在 j**l 的大作中提到】
: 这个预处理是O(n),
: 不过以后都是一劳永逸的O(logn)了
相关阅读
“机器人他爹”吴玉禄新的win7 upgrade ver还能clean install么以后还有什么噱头能忽悠人升级电脑呢？如何安装笔记本屏幕难道这tmd是常识？好像国内很多网站上不了了这个显卡有点老了，值110刀么？请教：买电脑有必要买保修吗x120e第一天汇报[zz] Intel have announced a new high speed solid state drive这个算deal吗？ATT DSL的USAGE CAP，究竟有多大影响？ (转载)请问下哪些租服务器商比较便宜Re: 大家ipad背后都刻字么？ (转载)460 $105 AMIR!Ethernet over Coax这事靠谱不？真浪費听说WD把Hitachi买了推荐个HAF 912档次的机箱吧上电源还是下电源
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。