i******n
发帖数: 94 | 1 find the longest run number within a sorted array.
For example:
1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
the longest long number is 8
do it with O(log(n)), constant space. | w*******t
发帖数: 62 | 2 Find the majority element since no specific element is provided.
Use Moore's voting algorithm:
1. Find the majority
2. Verify the majority (we can skip this step for this question.)
【在 i******n 的大作中提到】
: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.
| w*******t
发帖数: 62 | 3 想起来这个需要O(n)。
用binary search的话，需要知道找哪个element啊？
【在 w*******t 的大作中提到】
: Find the majority element since no specific element is provided.
: Use Moore's voting algorithm:
: 1. Find the majority
: 2. Verify the majority (we can skip this step for this question.)
| i******n
发帖数: 94 | 4 Thank you.
first it's linear, second it's wrong to apply to this question. The majority
means more than half.
【在 w*******t 的大作中提到】
: Find the majority element since no specific element is provided.
: Use Moore's voting algorithm:
: 1. Find the majority
: 2. Verify the majority (we can skip this step for this question.)
| s***n
发帖数: 373 | | w*******t
发帖数: 62 | 6 是的。不过第一个可以找出出现次数最多的element。
majority
【在 i******n 的大作中提到】
: Thank you.
: first it's linear, second it's wrong to apply to this question. The majority
: means more than half.
| S*******w
发帖数: 24236 | 7 findmax(int A[], int i, int j){
find the range of A[(i+j)/2] using binary search, say is [p, q]
return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
}
【在 i******n 的大作中提到】
: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.
| r****t
发帖数: 10904 | 8 log(N)^2?
【在 S*******w 的大作中提到】
: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }
| S*******w
发帖数: 24236 | 9 I am not sure it is O(log n) or (log^2n)
more analysis needed
【在 r****t 的大作中提到】
: log(N)^2?
| q****x
发帖数: 7404 | 10 yet another fake question from careercup site?
【在 i******n 的大作中提到】
: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.
| | | e***s
发帖数: 799 | 11 这个O(n)就很弱智了，O(log(n))又很难 | i******n
发帖数: 94 | 12 No just got interviewed.
【在 q****x 的大作中提到】
: yet another fake question from careercup site?
| i******n
发帖数: 94 | 13 I mentioned your method, but it doesn't met requirement
【在 S*******w 的大作中提到】
: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }
| a********m
发帖数: 15480 | 14 lg(n)似乎不可能。 如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。 | i******n
发帖数: 94 | 15 I mentioned to compare the begin with mid value and the index difference.
【在 a********m 的大作中提到】
: lg(n)似乎不可能。 如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。
| r**********1
发帖数: 292 | 16 good point.
【在 a********m 的大作中提到】
: lg(n)似乎不可能。 如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。
| q********c
发帖数: 1774 | 17 This is a variant of binary search. Idea:
Compare the middle item with both item[0] and item[n-1]
return the number that is equal to either one of them.
recursively do this process in both left and right subarray. | H***e
发帖数: 476 | 18 logn 每次要丢掉一半
11111233333
没有办法判断丢掉哪一半吧
【在 i******n 的大作中提到】
: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.
| j*****j
发帖数: 201 | 19 recursive必定要用非consistent空间，要写成iterative的
【在 q********c 的大作中提到】
: This is a variant of binary search. Idea:
: Compare the middle item with both item[0] and item[n-1]
: return the number that is equal to either one of them.
: recursively do this process in both left and right subarray.
| j*****j
发帖数: 201 | 20 worst case必须O(n)吧，average logn就行
【在 a********m 的大作中提到】
: lg(n)似乎不可能。 如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。
| | | a********m
发帖数: 15480 | 21 感觉还是不对。能省略某个branch计算的情况比较少，不需要worst case。 general
case就少。似乎只能通过二分法优化掉一些分支，但是不降低整体复杂度.
【在 j*****j 的大作中提到】
: worst case必须O(n)吧，average logn就行
| q********c
发帖数: 1774 | 22 worst case 2log(n) because unlike the standard binary search you do it both
branches. | d****o
发帖数: 1055 | 23 反例：
1 1 1 2 2 2 2 3 3 3
【在 q********c 的大作中提到】
: This is a variant of binary search. Idea:
: Compare the middle item with both item[0] and item[n-1]
: return the number that is equal to either one of them.
: recursively do this process in both left and right subarray.
| H****s
发帖数: 247 | 24 If you do both branches, that is O(n) not 2log(n)
How can log(n) be possible?
eq. 0 1 2 3 4 ... 10 11 11 13 ... INT_MAX-1
both
【在 q********c 的大作中提到】
: worst case 2log(n) because unlike the standard binary search you do it both
: branches.
| w***g
发帖数: 5958 | 25 可以证明最长出现次数K小于一定大小的话无法用O(log n)解， 如下：
假设算法复杂度< Clog(n), C为任意常数。
Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
(Clog(n)+1)大。令K = 1/3 m， 那么所有长度大于m的区间两个端点的值都不可能一样
，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
～1/3n/Clog(n)，当n大的时候可以很大。
好吧，我比较无聊。
【在 i******n 的大作中提到】
: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.
| H****s
发帖数: 247 | 26 有道理！
数，
到的
)/
【在 w***g 的大作中提到】
: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解， 如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m， 那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。
| S*******w
发帖数: 24236 | 27 高手就是不一样！
数，
到的
)/
【在 w***g 的大作中提到】
: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解， 如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m， 那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。
| p*****2
发帖数: 21240 | | i******n
发帖数: 94 | 29 i see, but it's actually asked by a google interviewer. And it takes me a
long time...
数，
到的
)/
【在 w***g 的大作中提到】
: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解， 如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m， 那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。
| w******n
发帖数: 39 | 30 装 继续装
【在 i******n 的大作中提到】
: i see, but it's actually asked by a google interviewer. And it takes me a
: long time...
:
: 数，
: 到的
: )/
| | | i******n
发帖数: 94 | 31 I appreciate those persons who help me to figure out what happened but what
you said really makes me disappointed.
【在 w******n 的大作中提到】
: 装 继续装
| l*********y
发帖数: 370 | 32 这个应该是O(n)复杂度吧
【在 S*******w 的大作中提到】
: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }
| i******n
发帖数: 94 | 33 find the longest run number within a sorted array.
For example:
1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
the longest long number is 8
do it with O(log(n)), constant space. | w*******t
发帖数: 62 | 34 Find the majority element since no specific element is provided.
Use Moore's voting algorithm:
1. Find the majority
2. Verify the majority (we can skip this step for this question.)
【在 i******n 的大作中提到】
: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.
| w*******t
发帖数: 62 | 35 想起来这个需要O(n)。
用binary search的话，需要知道找哪个element啊？
【在 w*******t 的大作中提到】
: Find the majority element since no specific element is provided.
: Use Moore's voting algorithm:
: 1. Find the majority
: 2. Verify the majority (we can skip this step for this question.)
| i******n
发帖数: 94 | 36 Thank you.
first it's linear, second it's wrong to apply to this question. The majority
means more than half.
【在 w*******t 的大作中提到】
: Find the majority element since no specific element is provided.
: Use Moore's voting algorithm:
: 1. Find the majority
: 2. Verify the majority (we can skip this step for this question.)
| s***n
发帖数: 373 | | w*******t
发帖数: 62 | 38 是的。不过第一个可以找出出现次数最多的element。
majority
【在 i******n 的大作中提到】
: Thank you.
: first it's linear, second it's wrong to apply to this question. The majority
: means more than half.
| S*******w
发帖数: 24236 | 39 findmax(int A[], int i, int j){
find the range of A[(i+j)/2] using binary search, say is [p, q]
return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
}
【在 i******n 的大作中提到】
: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.
| r****t
发帖数: 10904 | 40 log(N)^2?
【在 S*******w 的大作中提到】
: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }
| | | S*******w
发帖数: 24236 | 41 I am not sure it is O(log n) or (log^2n)
more analysis needed
【在 r****t 的大作中提到】
: log(N)^2?
| q****x
发帖数: 7404 | 42 yet another fake question from careercup site?
【在 i******n 的大作中提到】
: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.
| e***s
发帖数: 799 | 43 这个O(n)就很弱智了，O(log(n))又很难 | i******n
发帖数: 94 | 44 No just got interviewed.
【在 q****x 的大作中提到】
: yet another fake question from careercup site?
| i******n
发帖数: 94 | 45 I mentioned your method, but it doesn't met requirement
【在 S*******w 的大作中提到】
: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }
| a********m
发帖数: 15480 | 46 lg(n)似乎不可能。 如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。 | i******n
发帖数: 94 | 47 I mentioned to compare the begin with mid value and the index difference.
【在 a********m 的大作中提到】
: lg(n)似乎不可能。 如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。
| r**********1
发帖数: 292 | 48 good point.
【在 a********m 的大作中提到】
: lg(n)似乎不可能。 如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。
| q********c
发帖数: 1774 | 49 This is a variant of binary search. Idea:
Compare the middle item with both item[0] and item[n-1]
return the number that is equal to either one of them.
recursively do this process in both left and right subarray. | H***e
发帖数: 476 | 50 logn 每次要丢掉一半
11111233333
没有办法判断丢掉哪一半吧
【在 i******n 的大作中提到】
: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.
| | | j*****j
发帖数: 201 | 51 recursive必定要用非consistent空间，要写成iterative的
【在 q********c 的大作中提到】
: This is a variant of binary search. Idea:
: Compare the middle item with both item[0] and item[n-1]
: return the number that is equal to either one of them.
: recursively do this process in both left and right subarray.
| j*****j
发帖数: 201 | 52 worst case必须O(n)吧，average logn就行
【在 a********m 的大作中提到】
: lg(n)似乎不可能。 如果数组是1,2,3,4,5,6,7.....n. 看不出来哪个元素可以跳过。
| a********m
发帖数: 15480 | 53 感觉还是不对。能省略某个branch计算的情况比较少，不需要worst case。 general
case就少。似乎只能通过二分法优化掉一些分支，但是不降低整体复杂度.
【在 j*****j 的大作中提到】
: worst case必须O(n)吧，average logn就行
| q********c
发帖数: 1774 | 54 worst case 2log(n) because unlike the standard binary search you do it both
branches. | d****o
发帖数: 1055 | 55 反例：
1 1 1 2 2 2 2 3 3 3
【在 q********c 的大作中提到】
: This is a variant of binary search. Idea:
: Compare the middle item with both item[0] and item[n-1]
: return the number that is equal to either one of them.
: recursively do this process in both left and right subarray.
| H****s
发帖数: 247 | 56 If you do both branches, that is O(n) not 2log(n)
How can log(n) be possible?
eq. 0 1 2 3 4 ... 10 11 11 13 ... INT_MAX-1
both
【在 q********c 的大作中提到】
: worst case 2log(n) because unlike the standard binary search you do it both
: branches.
| w***g
发帖数: 5958 | 57 可以证明最长出现次数K小于一定大小的话无法用O(log n)解， 如下：
假设算法复杂度< Clog(n), C为任意常数。
Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
(Clog(n)+1)大。令K = 1/3 m， 那么所有长度大于m的区间两个端点的值都不可能一样
，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
～1/3n/Clog(n)，当n大的时候可以很大。
好吧，我比较无聊。
【在 i******n 的大作中提到】
: find the longest run number within a sorted array.
: For example:
: 1,1,1,2,2,2,2,6,8,8,8,8,8,8,8,8,9
: the longest long number is 8
: do it with O(log(n)), constant space.
| H****s
发帖数: 247 | 58 有道理！
数，
到的
)/
【在 w***g 的大作中提到】
: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解， 如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m， 那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。
| S*******w
发帖数: 24236 | 59 高手就是不一样！
数，
到的
)/
【在 w***g 的大作中提到】
: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解， 如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m， 那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。
| p*****2
发帖数: 21240 | | | | i******n
发帖数: 94 | 61 i see, but it's actually asked by a google interviewer. And it takes me a
long time...
数，
到的
)/
【在 w***g 的大作中提到】
: 可以证明最长出现次数K小于一定大小的话无法用O(log n)解， 如下：
: 假设算法复杂度< Clog(n), C为任意常数。
: Clog(n)的算法最多只能看到整个数列中Clog(n)个数。也就是说剩下的n-Clog(n)个数，
: 只要顺序不和已经看到的Clog(n)个数冲突，可以随便改，不会影响算法的输出。看到的
: 那些数把整个序列分成Clog(n)+1个区间，所以必有一个区间的会比 m = (n-Clog(n))/
: (Clog(n)+1)大。令K = 1/3 m， 那么所有长度大于m的区间两个端点的值都不可能一样
: ，而且中间还有第三个值(否则最长出现的次数就大于K了）。考虑任意一个这样的区间
: 。不管算法给出的预测是否包含这个区间的端点，都可以通过修改该区间中间的数字使
: 得该数字出现K次，也就是最多次。这样算法给出的预测至少就不是唯一的了。K的值在
: ～1/3n/Clog(n)，当n大的时候可以很大。
| i******n
发帖数: 94 | 62 I appreciate those persons who help me to figure out what happened but what
you said really makes me disappointed.
【在 w******n 的大作中提到】
: 装 继续装
| l*********y
发帖数: 370 | 63 这个应该是O(n)复杂度吧
【在 S*******w 的大作中提到】
: findmax(int A[], int i, int j){
: find the range of A[(i+j)/2] using binary search, say is [p, q]
: return max(findmax(A,i, p-1), p-q+1, findmax(A, q+1, j))
: }
| h******2
发帖数: 13 | 64 还是没有看到有logN的解法，呼唤大牛解答... | n*******w
发帖数: 687 | 65 如果both branches都要do，那就是O(n)，而不是2logN。
logN必须每次丢掉一半。
both
【在 q********c 的大作中提到】
: worst case 2log(n) because unlike the standard binary search you do it both
: branches.
| w****x
发帖数: 2483 | |
|
