k**********i
发帖数: 177 | 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自己了。 |
k**********i
发帖数: 177 | 2 对了 这种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)吧， 毕
: 竟最坏情
: 况下找到分界点要遍历一遍。
|
i********s
发帖数: 133 | 3 应该不用先找分解点，直接用binary search, 只不过需要分情况讨论每次应该往左边
还是右边跳。所以复杂度O(lgn)
>我首先说是找到分界点， 然后对两边用binary search， 这个效率应该是O(n)>吧， 毕
竟最坏情
况下找到分界点要遍历一遍。 |
D***h
发帖数: 183 | 4 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)吧， 毕
: 竟最坏情
: 况下找到分界点要遍历一遍。
|
k**********i
发帖数: 177 | 5 是啊， 我后来又写了这个， 修改下条件 然后递归做的
了.
【在 D***h 的大作中提到】
: shifted sorted array的binary search也是O(lg n)的,判断条件稍微修改一下就行了.
|
j**l
发帖数: 2911 | 6 这题不是前几天讨论过的么？是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 |
j**l
发帖数: 2911 | 7 如果有重复元素，还能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 |
k**********i
发帖数: 177 | 8 我觉得， 每次分一半， 有三种情况， 一遍是跟元来的一样的特点， 一遍是递增，或
者两边都
是递增，
然后对三种情况递归就可以了。 然后效率是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;
|
j**l
发帖数: 2911 | 9 不妨贴出你写的代码，验证下是否O(logn)时间也能解决重复元素的问题
【在 k**********i 的大作中提到】
: 我觉得， 每次分一半， 有三种情况， 一遍是跟元来的一样的特点， 一遍是递增，或
: 者两边都
: 是递增，
: 然后对三种情况递归就可以了。 然后效率是logn
|
k**********i
发帖数: 177 | 10 我发现我的程序 对重复元素好像不行。。。要修改， 刚看了看， 发现程序里有些小
问题， 但
是面试的三哥当时也没有问。。。
【在 j**l 的大作中提到】
: 不妨贴出你写的代码，验证下是否O(logn)时间也能解决重复元素的问题
|
|
|
x**y
发帖数: 10012 | 11 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)吧， 毕
: 竟最坏情
: 况下找到分界点要遍历一遍。
|
l*******y
发帖数: 1498 | 12 如果有重复元素，递增与否是无法判断的，比如 22222212 这个例子
如果没有重复的元素，logn是可以的，否则，我觉得只能O(n)了
【在 k**********i 的大作中提到】
: 我觉得， 每次分一半， 有三种情况， 一遍是跟元来的一样的特点， 一遍是递增，或
: 者两边都
: 是递增，
: 然后对三种情况递归就可以了。 然后效率是logn
|
j**l
发帖数: 2911 | 13 这个预处理是O(n),
不过以后都是一劳永逸的O(logn)了
【在 x**y 的大作中提到】
: re-index to make it sorted
: then binary
|
w****l
发帖数: 88 | |
B*****t
发帖数: 335 | 15 有没有重复元素都是log（n)
【在 l*******y 的大作中提到】
: 如果有重复元素，递增与否是无法判断的，比如 22222212 这个例子
: 如果没有重复的元素，logn是可以的，否则，我觉得只能O(n)了
|
r****o
发帖数: 1950 | 16 能不能说说有重复元素怎么作的?
多谢。
【在 B*****t 的大作中提到】
: 有没有重复元素都是log（n)
|
B*****t
发帖数: 335 | 17 sorry, worst case is still O(N) if there are duplicates. average case is O(
logn)
【在 r****o 的大作中提到】
: 能不能说说有重复元素怎么作的?
: 多谢。
|
x******3
发帖数: 245 | 18 好像预处理找sorted array的起点和结束可以是lgN, 用binary search找起点和结束
【在 j**l 的大作中提到】
: 这个预处理是O(n),
: 不过以后都是一劳永逸的O(logn)了
|
