一道面试题# JobHunting - 待字闺中
s*e
1 楼
输入是一个数列长度N，和一个数L。 求一个cover最多的数字，并且长度为L的 interval。
看着是道简单题，先排序，然后两重循环，找出cover数字最多的interval. 这个题有
陷阱没有？
看着是道简单题，先排序，然后两重循环，找出cover数字最多的interval. 这个题有
陷阱没有？
w*o
2 楼
能否给个例子？
这里interval指的是什么？什么是"cover最多的数字"?
还有interval [5 6]的长度是1 还是2? interval [5 5]的长度是0 还是1?
xiexie!
interval。
【在 s****e 的大作中提到】
: 输入是一个数列长度N，和一个数L。 求一个cover最多的数字，并且长度为L的 interval。
: 看着是道简单题，先排序，然后两重循环，找出cover数字最多的interval. 这个题有
: 陷阱没有？
这里interval指的是什么？什么是"cover最多的数字"?
还有interval [5 6]的长度是1 还是2? interval [5 5]的长度是0 还是1?
xiexie!
interval。
【在 s****e 的大作中提到】
: 输入是一个数列长度N，和一个数L。 求一个cover最多的数字，并且长度为L的 interval。
: 看着是道简单题，先排序，然后两重循环，找出cover数字最多的interval. 这个题有
: 陷阱没有？
s*e
3 楼
输入的数列是没有排序的。 如果排序过后数列是 2，6，6，7, 8，9，13,13，20
L = 4；我的理解是： [6, 10]， cover 了 {6，6，7，8, 9} 5个数字。 [5,5] 应该
是0吧。
【在 w****o 的大作中提到】
: 能否给个例子？
: 这里interval指的是什么？什么是"cover最多的数字"?
: 还有interval [5 6]的长度是1 还是2? interval [5 5]的长度是0 还是1?
: xiexie!
:
: interval。
L = 4；我的理解是： [6, 10]， cover 了 {6，6，7，8, 9} 5个数字。 [5,5] 应该
是0吧。
【在 w****o 的大作中提到】
: 能否给个例子？
: 这里interval指的是什么？什么是"cover最多的数字"?
: 还有interval [5 6]的长度是1 还是2? interval [5 5]的长度是0 还是1?
: xiexie!
:
: interval。
w*o
4 楼
谢谢，这个好像不是唯一解。以你的例子来说，返回[5, 9]也是一样的。对吧？
【在 s****e 的大作中提到】
: 输入的数列是没有排序的。 如果排序过后数列是 2，6，6，7, 8，9，13,13，20
: L = 4；我的理解是： [6, 10]， cover 了 {6，6，7，8, 9} 5个数字。 [5,5] 应该
: 是0吧。
【在 s****e 的大作中提到】
: 输入的数列是没有排序的。 如果排序过后数列是 2，6，6，7, 8，9，13,13，20
: L = 4；我的理解是： [6, 10]， cover 了 {6，6，7，8, 9} 5个数字。 [5,5] 应该
: 是0吧。
w*o
5 楼
按照你的理解，排除排序后，你的两重循环的时间复杂度是O(n^2)吗？
我觉得排除排序后,可以做到O(nlgn).
大概的想法是可以用 a[i]+L 作为key,做binary search,就是类似于STL里的函数upper
_bound，
这样upper_bound-i 就是 interval [a[i] a[i]+L]可以cover的数字的个数。
【在 s****e 的大作中提到】
: 输入的数列是没有排序的。 如果排序过后数列是 2，6，6，7, 8，9，13,13，20
: L = 4；我的理解是： [6, 10]， cover 了 {6，6，7，8, 9} 5个数字。 [5,5] 应该
: 是0吧。
我觉得排除排序后,可以做到O(nlgn).
大概的想法是可以用 a[i]+L 作为key,做binary search,就是类似于STL里的函数upper
_bound，
这样upper_bound-i 就是 interval [a[i] a[i]+L]可以cover的数字的个数。
【在 s****e 的大作中提到】
: 输入的数列是没有排序的。 如果排序过后数列是 2，6，6，7, 8，9，13,13，20
: L = 4；我的理解是： [6, 10]， cover 了 {6，6，7，8, 9} 5个数字。 [5,5] 应该
: 是0吧。
l*8
6 楼
if the array is already sorted, O(n) algorithm can find the max coverage
interval. Just replace your binary search to sequential search.
upper
【在 w****o 的大作中提到】
: 按照你的理解，排除排序后，你的两重循环的时间复杂度是O(n^2)吗？
: 我觉得排除排序后,可以做到O(nlgn).
: 大概的想法是可以用 a[i]+L 作为key,做binary search,就是类似于STL里的函数upper
: _bound，
: 这样upper_bound-i 就是 interval [a[i] a[i]+L]可以cover的数字的个数。
interval. Just replace your binary search to sequential search.
upper
【在 w****o 的大作中提到】
: 按照你的理解，排除排序后，你的两重循环的时间复杂度是O(n^2)吗？
: 我觉得排除排序后,可以做到O(nlgn).
: 大概的想法是可以用 a[i]+L 作为key,做binary search,就是类似于STL里的函数upper
: _bound，
: 这样upper_bound-i 就是 interval [a[i] a[i]+L]可以cover的数字的个数。
s*e
7 楼
觉的你说的是对的。
upper
【在 w****o 的大作中提到】
: 按照你的理解，排除排序后，你的两重循环的时间复杂度是O(n^2)吗？
: 我觉得排除排序后,可以做到O(nlgn).
: 大概的想法是可以用 a[i]+L 作为key,做binary search,就是类似于STL里的函数upper
: _bound，
: 这样upper_bound-i 就是 interval [a[i] a[i]+L]可以cover的数字的个数。
upper
【在 w****o 的大作中提到】
: 按照你的理解，排除排序后，你的两重循环的时间复杂度是O(n^2)吗？
: 我觉得排除排序后,可以做到O(nlgn).
: 大概的想法是可以用 a[i]+L 作为key,做binary search,就是类似于STL里的函数upper
: _bound，
: 这样upper_bound-i 就是 interval [a[i] a[i]+L]可以cover的数字的个数。
w*o
8 楼
对，排序后，就是O(n)了。我自己写了一个，应该是对的。不过有点儿ugly.
typedef struct {
int start;
int end;
} Interval;
int intcomp (const void * p1, const void * p2)
{
return *(int *)p1 - *(int *)p2;
}
Interval find_interval_cover(int a[], int N, int L)
{
Interval result;
int i, j;
int count = 0;
qsort(a, N, sizeof(int), intcomp);
print_arr(a, N);
for (i = 0, j = 0; j < N; ) {
if (a[j] <= a[i] + L) {
j++;
} else {
if (j- i > count) {
count = j - i;
result.start = a[i];
result.end = a[i] + L;
}
i++;
}
}
if (j- i > count) {
count = j - i;
result.start = a[i];
result.end = a[i] + L;
}
printf("count = %d\n", count);
return result;
}
【在 l*********8 的大作中提到】
: if the array is already sorted, O(n) algorithm can find the max coverage
: interval. Just replace your binary search to sequential search.
:
: upper
typedef struct {
int start;
int end;
} Interval;
int intcomp (const void * p1, const void * p2)
{
return *(int *)p1 - *(int *)p2;
}
Interval find_interval_cover(int a[], int N, int L)
{
Interval result;
int i, j;
int count = 0;
qsort(a, N, sizeof(int), intcomp);
print_arr(a, N);
for (i = 0, j = 0; j < N; ) {
if (a[j] <= a[i] + L) {
j++;
} else {
if (j- i > count) {
count = j - i;
result.start = a[i];
result.end = a[i] + L;
}
i++;
}
}
if (j- i > count) {
count = j - i;
result.start = a[i];
result.end = a[i] + L;
}
printf("count = %d\n", count);
return result;
}
【在 l*********8 的大作中提到】
: if the array is already sorted, O(n) algorithm can find the max coverage
: interval. Just replace your binary search to sequential search.
:
: upper
l*a
9 楼
这个题显然跟有没有序没有任何关系
为什么要排序处理呢？排序之后显然破坏了原来数组啊
结果怎能正确？
为什么要排序处理呢？排序之后显然破坏了原来数组啊
结果怎能正确？
l*8
10 楼
没有说不能改变原来数组吧
【在 l*****a 的大作中提到】
: 这个题显然跟有没有序没有任何关系
: 为什么要排序处理呢？排序之后显然破坏了原来数组啊
: 结果怎能正确？
【在 l*****a 的大作中提到】
: 这个题显然跟有没有序没有任何关系
: 为什么要排序处理呢？排序之后显然破坏了原来数组啊
: 结果怎能正确？
l*a
11 楼
人家要得结果是依赖于输入顺序的
你给改了算咋回事？
【在 l*********8 的大作中提到】
: 没有说不能改变原来数组吧
你给改了算咋回事？
【在 l*********8 的大作中提到】
: 没有说不能改变原来数组吧
l*8
12 楼
结果跟输入顺序没有关系吧。 不然interval是怎么cover数字的？
【在 l*****a 的大作中提到】
: 人家要得结果是依赖于输入顺序的
: 你给改了算咋回事？
【在 l*****a 的大作中提到】
: 人家要得结果是依赖于输入顺序的
: 你给改了算咋回事？
l*a
13 楼
1,2,3,4,5,3,4,5,6,2,1,7,5,3,4
假定找长为４的interval,有如下这些。。
你就想办法算出相应数字出现数目好了
1,2,3,4
2,3,4,5
3,4,5,3
4,5,3,4
.....
【在 l*********8 的大作中提到】
: 结果跟输入顺序没有关系吧。 不然interval是怎么cover数字的？
假定找长为４的interval,有如下这些。。
你就想办法算出相应数字出现数目好了
1,2,3,4
2,3,4,5
3,4,5,3
4,5,3,4
.....
【在 l*********8 的大作中提到】
: 结果跟输入顺序没有关系吧。 不然interval是怎么cover数字的？
l*i
14 楼
maintain a BST with elements in current size L window, when you slide window
from left to right, it amounts to one insertion and one deletion. So a
balanced binary tree with extra count of each element will do it in O(logn)
per move, and a total of O(nlogn)
from left to right, it amounts to one insertion and one deletion. So a
balanced binary tree with extra count of each element will do it in O(logn)
per move, and a total of O(nlogn)
l*8
15 楼
假如输入是 1,1,2,2,3,3,4,4,4,5,5,5,6,7
输出结果有不同吗？
【在 l*****a 的大作中提到】
: 1,2,3,4,5,3,4,5,6,2,1,7,5,3,4
: 假定找长为４的interval,有如下这些。。
: 你就想办法算出相应数字出现数目好了
: 1,2,3,4
: 2,3,4,5
: 3,4,5,3
: 4,5,3,4
: .....
输出结果有不同吗？
【在 l*****a 的大作中提到】
: 1,2,3,4,5,3,4,5,6,2,1,7,5,3,4
: 假定找长为４的interval,有如下这些。。
: 你就想办法算出相应数字出现数目好了
: 1,2,3,4
: 2,3,4,5
: 3,4,5,3
: 4,5,3,4
: .....
p*2
16 楼
这题看来有歧义了。我理解的也是需要排序。
l*8
17 楼
呵呵，我现在明白，你意思是，求哪个sub-array里面的unique numbers多？
【在 l*********8 的大作中提到】
: 假如输入是 1,1,2,2,3,3,4,4,4,5,5,5,6,7
: 输出结果有不同吗？
【在 l*********8 的大作中提到】
: 假如输入是 1,1,2,2,3,3,4,4,4,5,5,5,6,7
: 输出结果有不同吗？
l*a
18 楼
yes,I think that is what they want
just like the famous issue
"find the minimum slide windows contains all the given words"
【在 l*********8 的大作中提到】
: 呵呵，我现在明白，你意思是，求哪个sub-array里面的unique numbers多？
just like the famous issue
"find the minimum slide windows contains all the given words"
【在 l*********8 的大作中提到】
: 呵呵，我现在明白，你意思是，求哪个sub-array里面的unique numbers多？
l*8
19 楼
Thanks.
"find the minimum slide windows contains all the given words" 这个问题比楼
主贴的要难，因为window size是不定的。
【在 l*****a 的大作中提到】
: yes,I think that is what they want
: just like the famous issue
: "find the minimum slide windows contains all the given words"
"find the minimum slide windows contains all the given words" 这个问题比楼
主贴的要难，因为window size是不定的。
【在 l*****a 的大作中提到】
: yes,I think that is what they want
: just like the famous issue
: "find the minimum slide windows contains all the given words"
w*o
20 楼
lolhaha, longway2008,
根据你们的理解，这道题是不是找长度为 L 的subarray中含有最多的不同数字的那个
subarray?
xiexie!
【在 l*****a 的大作中提到】
: yes,I think that is what they want
: just like the famous issue
: "find the minimum slide windows contains all the given words"
根据你们的理解，这道题是不是找长度为 L 的subarray中含有最多的不同数字的那个
subarray?
xiexie!
【在 l*****a 的大作中提到】
: yes,I think that is what they want
: just like the famous issue
: "find the minimum slide windows contains all the given words"
相关阅读
A家电面被放鸽子了问个关于Citi的软件开发工作问题Interview时间有冲突，怎么和HR解释？G家电面面经转行CS的大部分要补多少本科课程？Fail掉了Intel的一个职位，影响申请其他职位么？offer求比较关于export license上的移民倾向问题Qualcomm面经leetcode一题没看明白CMU CS 系主任今年刚跳槽到微软请问C/C++里面如何使用hash这种情况怎么办？问个给 hiring manager回信的问题WalmartLabs求问Google Seattle如何啊？k,怒而不语H1B Approve 但是没收到hard copyData Engineer @ San Fran Startup找工作和自学编程的