由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问一道老题
相关主题
Random Array number, Find longest consecutive sequencefind longest subarray with the equal number of 0's, 1's
请教一个关于java comparator的问题刚电面完,分享两个题目
tripdavisor面经问一个给定的array 和一个sum value,找最小sub-array,谢谢
讨论个subarray sum的变种问题这题怎么做?
stable rearrange an integer array with + and -这个怎么弄?
谁有兴趣做道题?问几道算法题
一道算法题,N*N array里最大的subarrayQuestion:Given a array,find out if there exist a subarray such its sum is zero
[算法] unsorted arraylongest subarray with numbers arranged as a seq
相关话题的讨论汇总
话题: tmp话题: info话题: max话题: start话题: input
进入JobHunting版参与讨论
1 (共1页)
w***y
发帖数: 6251
1
maximum length subarray such that maximum difference is less than k
在这里看到解法 http://effprog.blogspot.com/2010/12/maximum-length-subarray-such-that.html
需要判断很多情况, 答案看了好几遍才看懂. 不知道这种题目考的是什么? 如果面
试被问到,怎么找切入点呢?
h********e
发帖数: 1972
2
两个指针扫描~这种题目没啥好说的。。就是有一些贪心(单调性)的思想,避免不必要
的计算。你给的那个网站程序写的很差。
w***y
发帖数: 6251
3
有没有好的算法啊? 我看那个implementation被绕的很晕
我现在还不太明白需要greedy和dynamic programming的问题怎么找切入点, 好搓啊,
咋办啊, 面试还有不到3周.........

【在 h********e 的大作中提到】
: 两个指针扫描~这种题目没啥好说的。。就是有一些贪心(单调性)的思想,避免不必要
: 的计算。你给的那个网站程序写的很差。

h********e
发帖数: 1972
4
这题硬算是dp也行。。算是贪心也行。。面试就爱考这种ad hoc的算法。一般都是有几
种套路,脑子要转的比较快就能知道那种适用了。。多看点题目想想吧。没什么好办法
。。这种题目无非就是那种最大substring sum的题目的变种。有时候一个指针就够了
,有时候要用两个。有时候还要用stack。。一般找出单调性,也就是哪些计算在brute
force的时候不必要重复,就能想到O(n)算法了。。
l***i
发帖数: 1309
5
dynamic programming?
dp[len][pos] = (minval, maxval) remembers minval and maxval in range pos to
pos+len-1
you can computer each len from 1 to n, for each pos from 0 to n-1
dp[len][pos] = update from dp[len-1][pos+1]
That is O(n^2)
faster solutions?
w***y
发帖数: 6251
6
多谢指点了!
我再多看看题目, 好好总结一下套路

brute

【在 h********e 的大作中提到】
: 这题硬算是dp也行。。算是贪心也行。。面试就爱考这种ad hoc的算法。一般都是有几
: 种套路,脑子要转的比较快就能知道那种适用了。。多看点题目想想吧。没什么好办法
: 。。这种题目无非就是那种最大substring sum的题目的变种。有时候一个指针就够了
: ,有时候要用两个。有时候还要用stack。。一般找出单调性,也就是哪些计算在brute
: force的时候不必要重复,就能想到O(n)算法了。。

h********e
发帖数: 1972
7
这种题目会出现的非常频繁。建议熟练掌握。全是O(n)算法。
e*****e
发帖数: 1275
8
这题目一看就最好是DP,又快又简单,不会被指针绕来绕去绕晕。DP就如下情况,最大
subarray + 1, 新的最大subarray. DP 是 O(n),可以不O(n2)。就记下尾巴下新的最大
subarray就可以了。
h********e
发帖数: 1972
9
指针dp都一样的。。都是同一个算法。关键就是搞个数据结构。每次如果+1 爆仓了,能快速把尾指针挪到正确位置,也就是动态维护一个max,min的跳表之类的结构,每个max都指向该max的位置+1到头指针位置的数组元素中的max(i.e., the second largest after max's position)。
H****r
发帖数: 2801
10
数组是排序好的吗?

【在 w***y 的大作中提到】
: maximum length subarray such that maximum difference is less than k
: 在这里看到解法 http://effprog.blogspot.com/2010/12/maximum-length-subarray-such-that.html
: 需要判断很多情况, 答案看了好几遍才看懂. 不知道这种题目考的是什么? 如果面
: 试被问到,怎么找切入点呢?

相关主题
谁有兴趣做道题?find longest subarray with the equal number of 0's, 1's
一道算法题,N*N array里最大的subarray刚电面完,分享两个题目
[算法] unsorted array问一个给定的array 和一个sum value,找最小sub-array,谢谢
进入JobHunting版参与讨论
h********e
发帖数: 1972
11
排好序就很无聊了。。。
e*****e
发帖数: 1275
12
这题目一看就最好是DP,又快又简单,不会被指针绕来绕去绕晕。DP就如下情况,最大
subarray + 1, 新的最大subarray. DP 是 O(n),可以不O(n2)。就记下尾巴下新的最大
subarray就可以了。
p*****2
发帖数: 21240
13

,能快速把尾指针挪到正确位置,也就是动态维护一个max,min的跳表之类的结构,每
个max都指向该max的位置+1到头指针位置的数组元素中的max(i.e., the second
largest after max's position)。
跳表用什么数据结构呢?TreeSet是不是可以?

【在 h********e 的大作中提到】
: 指针dp都一样的。。都是同一个算法。关键就是搞个数据结构。每次如果+1 爆仓了,能快速把尾指针挪到正确位置,也就是动态维护一个max,min的跳表之类的结构,每个max都指向该max的位置+1到头指针位置的数组元素中的max(i.e., the second largest after max's position)。
h********e
发帖数: 1972
14
跳表是我很早以前学数据结构国内书翻译的。。我也不知道叫啥。。就是数组指针做成的链表把。。
btw 刚才看了楼主贴的老印网站的程序。。丫的写了个平方的算法。。。
p*****2
发帖数: 21240
15

成的链表把。。
你的意思是链表每一个元素指向一个数组?

【在 h********e 的大作中提到】
: 跳表是我很早以前学数据结构国内书翻译的。。我也不知道叫啥。。就是数组指针做成的链表把。。
: btw 刚才看了楼主贴的老印网站的程序。。丫的写了个平方的算法。。。

h********e
发帖数: 1972
16
不是。。是用数组存链表哈哈哈。。。最土的那种啊。。我记得是一本90年代的数据结构的蓝色皮的书。。。。。 跟并查集差不多的那种表示法.
可恶的是这个阿三写了个加阶的程序贴到网上。。。让LZ琢磨了一阵子。。太误导人了
p*****2
发帖数: 21240
17
我用TreeSet写了一个,然后发现不能有重复的元素。看来还得自定义数据结构。
int[] Max(int[] arr, int k)
{
if (arr == null || arr.length == 0)
return arr;
TreeSet ts = new TreeSet();
int max = 0;
int mstart = 0;
int mend = 0;
int start = 0;
int end = 0;
for (int i = 0; i < arr.length; i++)
{
while (!ts.isEmpty() && Math.abs(ts.first().value - arr[i]) >= k)
{
start = Math.max(start, ts.first().index + 1);
ts.remove(ts.first());
}
while (!ts.isEmpty() && Math.abs(ts.last().value - arr[i]) >= k)
{
start = Math.max(start, ts.last().index + 1);
ts.remove(ts.last());
}
Node[] nodes = ts.toArray(new Node[0]);
for (Node node : nodes)
{
if (node.index < start)
ts.remove(node);
}
ts.add(new Node(i, arr[i]));
end = i;
if (ts.size() > max)
{
max = ts.size();
mstart = start;
mend = end;
}
}
return Arrays.copyOfRange(arr, mstart, mend + 1);
}
e*****e
发帖数: 1275
18
用DP乱写了点code,发现还是得O(n2),不好意思,刚刚想歪了。
typedef struct subarray_info
{
int start;
int end;
int min;
int max;
int new_start;
}subarray_info;
void calculate_subarray_info (subarray_info * info, int input_array[], int n
, int k)
{
if ( n == 1)
{
info[0].start = 0;
info[0].end = 0;
info[0].min = input_array[0];
info[0].max = input_array[0];
info[0].new_start = 0;
return;
}
calculate_subarray_info (info, input_array, n-1, k);
subarray_info tmp_info = info[n-2];
if ( tmp_info.start == tmp_info.new_start)
{
//currently the solution is from start all the way to the end
if ( (tmp_info.max - input_array[n-1]) <= k && (input_array[n-1] -
tmp_info.min) <= k)
{
//and the soluton continue grow
info[n-1].start = tmp_info.start;
info[n-1].end = n-1;
info[n-1].min = (input_array[n-1] < tmp_info.min)? input_array[n
-1] :tmp_info.min;
info[n-1].max = (input_array[n-1]> tmp_info.max)? input_array[n-
1] :tmp_info.max;
info[n-1].new_start = tmp_info.new_start;
return;
}
else
{
//now the solution break, calculate all the way back for the new
solution start from end
int tmp_max, tmp_min;
tmp_max = input_array[n-1];
tmp_min = input_array[n-1];
int tmp_new_start = n -1;
for (int i = n -2; i >tmp_info.start; i--)
{
if ((tmp_max - input_array[i]) > k || (input_array[i] - tmp_
min ) > k)
{
tmp_new_start = i + 1;
break;
}
tmp_max = (input_array[i]>tmp_max)? input_array[i]:tmp_max;
tmp_min = (input_array[i] }
//something went wrong here.throw a exception
info[n-1].start = tmp_info.start;
info[n-1].end = tmp_info.end;
info[n-1].min = tmp_min;
info[n-1].max = tmp_max;
info[n-1].new_start = tmp_new_start;
return;
}
}
else
{
//current best solution is a subarray in the middle and can not grow
anymore
if ( (tmp_info.max - input_array[n-1]) <= k && (input_array[n-1] -
tmp_info.min) <= k)
{
//and the new soluton continue grow, compare the new solution's
lenght with the old one
if ( (n-1 - tmp_info.new_start) > (tmp_info.end - tmp_info.start
))
{
//the new solution is the longer one, update it
info[n-1].start = tmp_info.new_start;
info[n-1].end = n-1;
info[n-1].min = (input_array[n-1] < tmp_info.min)? input_
array[n-1] :tmp_info.min;
info[n-1].max = (input_array[n-1]> tmp_info.max)? input_
array[n-1] :tmp_info.max;
info[n-1].new_start = tmp_info.new_start;
return;
}
else
{
//still the old solution is the best solution so far
info[n-1].start = tmp_info.start;
info[n-1].end = tmp_info.end;
info[n-1].min = (input_array[n-1] < tmp_info.min)? input_
array[n-1] :tmp_info.min;
info[n-1].max = (input_array[n-1]> tmp_info.max)? input_
array[n-1] :tmp_info.max;
info[n-1].new_start = tmp_info.new_start;
return;
}
}
else
{
//now the new solution break, calculate all the way back for the
new solution start from end
int tmp_max, tmp_min;
tmp_max = input_array[n-1];
tmp_min = input_array[n-1];
int tmp_new_start = n -1;
for (int i = n -2; i >tmp_info.new_start; i--)
{
if ((tmp_max - input_array[i]) > k || (input_array[i] - tmp_
min ) > k)
{
tmp_new_start = i+1;
break;
}
tmp_max = (input_array[i]>tmp_max)? input_array[i]:tmp_max;
tmp_min = (input_array[i] }
info[n-1].start = tmp_info.start;
info[n-1].end = tmp_info.end;
info[n-1].min = tmp_min;
info[n-1].max = tmp_max;
info[n-1].new_start = tmp_new_start;
return;
}
}
}
//maximum length subarray such that maximum difference is less than k
//gonna solve this problem using dynamical programming
int get_max_len_subarray_with_maxdiff ( int input_array [] , int n, int k)
{
///remember veirfy the input: input_array, n, k
subarray_info * info = new subarray_info[n];
calculate_subarray_info (info, input_array, n, k);
int max_len = info[0].end - info[0].start + 1;
for (int i = 0; i < n; i++)
{
int new_len = info[i].end - info[i].start + 1;
if (new_len > max_len)
max_len = new_len;
}
return max_len;
}
void test_get_max_subarray (void)
{
int a [] = { 1, 2, 3, 4, 6, 11, 14, 33, 28, 29, 30, 31, 32, 28, 28, 29,
30, 1, 2, 3};
int result = get_max_len_subarray_with_maxdiff ( a , 20, 10);
printf ("result %d\n",result);
}
h********e
发帖数: 1972
19
这题O(n)不难吧。。就是写起来麻烦了点。
主要是h,t 两个指针,每次h往前挪到爆了k 为止。过程中要维护如下内容:
h和t之间的 最大元素 max 的位置, max的位置到h 之间 最大元素max的位置, 第一
个用指针指向第二个,然后指向第三个,等等。
min 也同样要记下这些。
每次刷新max或者min,都从当前位置重新来建立这么一个linked list。可以直接在数
组上维护。
每次爆了如果是max 爆,去min 的linked list里面找一个对的(i.e., 最靠前面的和h
比相差小于k)然后update tail位置 (要注意tail的位置其实是linked list上一个元
素+1),然后继续挪h;
如果爆了min,就去max里面干同样的事情。
p*****2
发帖数: 21240
20

h
应该跟我写的那个意思差不多。

【在 h********e 的大作中提到】
: 这题O(n)不难吧。。就是写起来麻烦了点。
: 主要是h,t 两个指针,每次h往前挪到爆了k 为止。过程中要维护如下内容:
: h和t之间的 最大元素 max 的位置, max的位置到h 之间 最大元素max的位置, 第一
: 个用指针指向第二个,然后指向第三个,等等。
: min 也同样要记下这些。
: 每次刷新max或者min,都从当前位置重新来建立这么一个linked list。可以直接在数
: 组上维护。
: 每次爆了如果是max 爆,去min 的linked list里面找一个对的(i.e., 最靠前面的和h
: 比相差小于k)然后update tail位置 (要注意tail的位置其实是linked list上一个元
: 素+1),然后继续挪h;

相关主题
这题怎么做?Question:Given a array,find out if there exist a subarray such its sum is zero
这个怎么弄?longest subarray with numbers arranged as a seq
问几道算法题问一道amazon的Onsite题
进入JobHunting版参与讨论
l***i
发帖数: 1309
21
use hellobruce's idea, here is code
assume input is a[N] and difference is K
typedef pair pii;
// small keeps track of min while p1 is moving to right
// large keeps track of max while p1 is moving to right
deque small, large;
int p1, p2;
int ans=0, curr=0;
small.clear(); large.clear();
for(p1=p2=0; p2 {
int val = a[p2];
while(!small.empty() && val > small.front().first + K)
{
p1=small.front().second +1;
small.pop_front();
}
while(!large.empty() && val < large.front.first - K)
{
p1=max(p1, large.front().second+1);
large.pop_front();
}
curr = p2-p1+1;
ans = max(ans, curr);
while(!small.empty() && small.back().first >= val)
{ small.pop_back(); }
small.push_back(make_pair(val, p2));
while(!large.empty() && large.back().first <= val)
{ large.pop_back(); }
large.push_back(make_pair(val, p2));
}
return ans;
m********g
发帖数: 272
22
这样也不是O(n)呀,每次diff超过k, 找下一个最大或最小还要遍历max_list or min_
list,which is not O(1).

h

【在 h********e 的大作中提到】
: 这题O(n)不难吧。。就是写起来麻烦了点。
: 主要是h,t 两个指针,每次h往前挪到爆了k 为止。过程中要维护如下内容:
: h和t之间的 最大元素 max 的位置, max的位置到h 之间 最大元素max的位置, 第一
: 个用指针指向第二个,然后指向第三个,等等。
: min 也同样要记下这些。
: 每次刷新max或者min,都从当前位置重新来建立这么一个linked list。可以直接在数
: 组上维护。
: 每次爆了如果是max 爆,去min 的linked list里面找一个对的(i.e., 最靠前面的和h
: 比相差小于k)然后update tail位置 (要注意tail的位置其实是linked list上一个元
: 素+1),然后继续挪h;

z*****n
发帖数: 447
23
跳表是不是skiplist

成的链表把。。

【在 h********e 的大作中提到】
: 跳表是我很早以前学数据结构国内书翻译的。。我也不知道叫啥。。就是数组指针做成的链表把。。
: btw 刚才看了楼主贴的老印网站的程序。。丫的写了个平方的算法。。。

h********e
发帖数: 1972
24
仔细想啊-0- 。。。别重复找,每次min,max都是list的第一个元素,不需要扫一遍list。。找过的都扔掉了。。amortize下来肯定O(1).就两个指针,永远不回头的。不可能搞出n^2的复杂度。
应该叫skiplist。。不过这里的用法跟skiplist的本意应该不一样。反正很简单,就是个array里面每个元素都有可能有一个指针指向下一个要去的地方。这样就有O(1) access, which is better than linked list.

【在 m********g 的大作中提到】
: 这样也不是O(n)呀,每次diff超过k, 找下一个最大或最小还要遍历max_list or min_
: list,which is not O(1).
:
: h

s******n
发帖数: 3946
25
这个不对吧?,举个反例
k=10
前5个元素是
-10, -7, -9, -8,0
第6个元素是1
照你的做法,前5个元素处理完min linklist是-10, -9, -8。新元素1让max暴仓,你去
linklist找了-9。但选-7是更优解。

h

【在 h********e 的大作中提到】
: 这题O(n)不难吧。。就是写起来麻烦了点。
: 主要是h,t 两个指针,每次h往前挪到爆了k 为止。过程中要维护如下内容:
: h和t之间的 最大元素 max 的位置, max的位置到h 之间 最大元素max的位置, 第一
: 个用指针指向第二个,然后指向第三个,等等。
: min 也同样要记下这些。
: 每次刷新max或者min,都从当前位置重新来建立这么一个linked list。可以直接在数
: 组上维护。
: 每次爆了如果是max 爆,去min 的linked list里面找一个对的(i.e., 最靠前面的和h
: 比相差小于k)然后update tail位置 (要注意tail的位置其实是linked list上一个元
: 素+1),然后继续挪h;

h********e
发帖数: 1972
26
你理解错了或者你没有仔细阅读。 我说去找list里面下一个in range max的上一个元
素+1的位置。也就是-7的位置开始。
z**********2
发帖数: 307
27
强大

【在 w***y 的大作中提到】
: maximum length subarray such that maximum difference is less than k
: 在这里看到解法 http://effprog.blogspot.com/2010/12/maximum-length-subarray-such-that.html
: 需要判断很多情况, 答案看了好几遍才看懂. 不知道这种题目考的是什么? 如果面
: 试被问到,怎么找切入点呢?

1 (共1页)
进入JobHunting版参与讨论
相关主题
longest subarray with numbers arranged as a seqstable rearrange an integer array with + and -
问一道amazon的Onsite题谁有兴趣做道题?
请教一题一道算法题,N*N array里最大的subarray
sorted arry, 找最长重复subarray[算法] unsorted array
Random Array number, Find longest consecutive sequencefind longest subarray with the equal number of 0's, 1's
请教一个关于java comparator的问题刚电面完,分享两个题目
tripdavisor面经问一个给定的array 和一个sum value,找最小sub-array,谢谢
讨论个subarray sum的变种问题这题怎么做?
相关话题的讨论汇总
话题: tmp话题: info话题: max话题: start话题: input