由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问道题,谁给个效率高点的解法
相关主题
请教个面试题HashTable space complexity?
你们面试时候忽略了一个重要点面试题求解:remove first duplicate number from an array
Google电话面试题目一个实际碰到的问题
一道算法题求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)
google 面试题疑问[合集] Google电话面试题目
Given an int array and an int value. Find all pairs in arr这题怎么做?
点评网站Y面经Given an array of N integers from range [0, N] and one is missing. Find the missing number.
问一个狗狗的OnSite题菜鸟问个two sum的变型题
相关话题的讨论汇总
话题: dp话题: query话题: minindex话题: array话题: end
进入JobHunting版参与讨论
1 (共1页)
w****x
发帖数: 2483
1
Given an input array of integers of size n, and a query array of
integers of size k, find the smallest window of input array that
contains all the elements of query array and also in the same order
p*****2
发帖数: 21240
2

什么复杂度要求,感觉就是一道DP吧。

【在 w****x 的大作中提到】
: Given an input array of integers of size n, and a query array of
: integers of size k, find the smallest window of input array that
: contains all the elements of query array and also in the same order

l*****a
发帖数: 14598
3
为什么不是两指针
为什么不是slide window
就是slide windows然后要求有序吧

【在 p*****2 的大作中提到】
:
: 什么复杂度要求,感觉就是一道DP吧。

p*****2
发帖数: 21240
4

没序就是two pointer 和 sliding window了。
有序你怎么搞?

【在 l*****a 的大作中提到】
: 为什么不是两指针
: 为什么不是slide window
: 就是slide windows然后要求有序吧

w****x
发帖数: 2483
5

这题DP??我怎么感觉是reverse indexing?

【在 p*****2 的大作中提到】
:
: 没序就是two pointer 和 sliding window了。
: 有序你怎么搞?

l*****a
发帖数: 14598
6
HashMap 存query array value,query array index
然后每次循环初始currentIndex=-1;意思是准备先找query array的第0个
if(!map.containsKey(input[index])) {end++;}
if(map.containsKey(input[index]) {
if(map.get(input[index])==currentIndex){end++;}
else if (map.get(input[index])==currentIndex+1){end++; currentIndex++;}
else {break;}
}
找到currentIndex==Query array size 算是找到一组
###第一个的出现次数还得计数。。

【在 p*****2 的大作中提到】
:
: 没序就是two pointer 和 sliding window了。
: 有序你怎么搞?

p*****2
发帖数: 21240
7

你的算法是啥样的?

【在 w****x 的大作中提到】
:
: 这题DP??我怎么感觉是reverse indexing?

w****x
发帖数: 2483
8

短的在长的那个做reverse indexing,
比如按顺序是如下的:
1 3 5 8 13 17
0 2 4 6 9
7 10 14 21
那么第一条是1 2 7
然后第二条是3, 4, 10
然后5, 6, 10
8, 9, 10
然后就没了

【在 p*****2 的大作中提到】
:
: 你的算法是啥样的?

p*****2
发帖数: 21240
9

这个可行,不过太麻烦了。为什么不用DP呢?

【在 w****x 的大作中提到】
:
: 短的在长的那个做reverse indexing,
: 比如按顺序是如下的:
: 1 3 5 8 13 17
: 0 2 4 6 9
: 7 10 14 21
: 那么第一条是1 2 7
: 然后第二条是3, 4, 10
: 然后5, 6, 10
: 8, 9, 10

p*****2
发帖数: 21240
10

能不能说说算法呢?发现我现在java太弱了。

【在 l*****a 的大作中提到】
: HashMap 存query array value,query array index
: 然后每次循环初始currentIndex=-1;意思是准备先找query array的第0个
: if(!map.containsKey(input[index])) {end++;}
: if(map.containsKey(input[index]) {
: if(map.get(input[index])==currentIndex){end++;}
: else if (map.get(input[index])==currentIndex+1){end++; currentIndex++;}
: else {break;}
: }
: 找到currentIndex==Query array size 算是找到一组
: ###第一个的出现次数还得计数。。

相关主题
Given an int array and an int value. Find all pairs in arrHashTable space complexity?
点评网站Y面经面试题求解:remove first duplicate number from an array
问一个狗狗的OnSite题一个实际碰到的问题
进入JobHunting版参与讨论
b*****n
发帖数: 482
11
这题跟leetcode OJ上的minimum window substring有什么区别?我感觉好像是一模一
样的。

【在 w****x 的大作中提到】
: Given an input array of integers of size n, and a query array of
: integers of size k, find the smallest window of input array that
: contains all the elements of query array and also in the same order

l*****a
发帖数: 14598
12
我就会滑动窗口的算法啊,dp/reverse index都不会

【在 p*****2 的大作中提到】
:
: 能不能说说算法呢?发现我现在java太弱了。

p*****2
发帖数: 21240
13

那你说说滑动窗口吧。找到之后怎么继续处理?

【在 l*****a 的大作中提到】
: 我就会滑动窗口的算法啊,dp/reverse index都不会
w****x
发帖数: 2483
14

这题怎么DP?

【在 p*****2 的大作中提到】
:
: 那你说说滑动窗口吧。找到之后怎么继续处理?

l*****a
发帖数: 14598
15
第一个要计数,
如果只有一个,这一块全跳过,start=end+1;重新开始
如果有多个,start++,直到最后一个 query array的第一项,然后跳过。
每次碰上乱序,也跳过

【在 p*****2 的大作中提到】
:
: 那你说说滑动窗口吧。找到之后怎么继续处理?

p*****2
发帖数: 21240
16

我好像给你讲过吧?你有没有test case,我做做试试

【在 w****x 的大作中提到】
:
: 这题怎么DP?

w****x
发帖数: 2483
17

没test case,你先丢一个上来

【在 p*****2 的大作中提到】
:
: 我好像给你讲过吧?你有没有test case,我做做试试

b*****n
发帖数: 482
18
直接去OJ做啊
l*****a
发帖数: 14598
19
你这个是query array有三个元素的例子吧
为什么 5,6,7不是呢?

【在 w****x 的大作中提到】
:
: 没test case,你先丢一个上来

w****x
发帖数: 2483
20

因为我看走眼了 :P

【在 l*****a 的大作中提到】
: 你这个是query array有三个元素的例子吧
: 为什么 5,6,7不是呢?

相关主题
求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)Given an array of N integers from range [0, N] and one is missing. Find the missing number.
[合集] Google电话面试题目菜鸟问个two sum的变型题
这题怎么做?请教一道算法题
进入JobHunting版参与讨论
l*****a
发帖数: 14598
21
而且你这个多用了空间
时间上也没节省
没看出来比slide windows有什么优点啊,虽然解题思想很好

【在 w****x 的大作中提到】
:
: 因为我看走眼了 :P

s*****1
发帖数: 134
22
这题和leetcode上的Minimum Windwo Substring 差不多额,是吗?
p*****2
发帖数: 21240
23

复杂度O(n)吗?

【在 l*****a 的大作中提到】
: 第一个要计数,
: 如果只有一个,这一块全跳过,start=end+1;重新开始
: 如果有多个,start++,直到最后一个 query array的第一项,然后跳过。
: 每次碰上乱序,也跳过

s*****1
发帖数: 134
24
amortized的情况下,是O(N)吧
l*****a
发帖数: 14598
25
两个指针一起向前走,为什么还要amortized

【在 s*****1 的大作中提到】
: amortized的情况下,是O(N)吧
w****x
发帖数: 2483
26

不懂,按顺序怎么滑动?
上个代码吧

【在 l*****a 的大作中提到】
: 第一个要计数,
: 如果只有一个,这一块全跳过,start=end+1;重新开始
: 如果有多个,start++,直到最后一个 query array的第一项,然后跳过。
: 每次碰上乱序,也跳过

l*****a
发帖数: 14598
27
就是找到了第i个,旧可以继续向前找第i/i+1个,如果i到了array.size说明找到了
如果找到了地i个的时候,出现了第i+1或以后的,整个这段作废
start=end+1再开始

【在 w****x 的大作中提到】
:
: 不懂,按顺序怎么滑动?
: 上个代码吧

l*****a
发帖数: 14598
28
HashMap 存query array value,query array index
然后每次循环初始currentIndex=-1;意思是准备先找query array的第0个
if(!map.containsKey(input[index])) {end++;}
if(map.containsKey(input[index]) {
if(map.get(input[index])==currentIndex){end++;}
else if (map.get(input[index])==currentIndex+1){end++; currentIndex++;}
else {break;}
}
找到currentIndex==Query array size 算是找到一组
###第一个的出现次数还得计数。。

【在 w****x 的大作中提到】
:
: 不懂,按顺序怎么滑动?
: 上个代码吧

p*****2
发帖数: 21240
29

他已经给了代码了

【在 w****x 的大作中提到】
:
: 不懂,按顺序怎么滑动?
: 上个代码吧

w****x
发帖数: 2483
30

逻辑好复杂
时间复杂度是O(n^2)感觉

【在 l*****a 的大作中提到】
: 第一个要计数,
: 如果只有一个,这一块全跳过,start=end+1;重新开始
: 如果有多个,start++,直到最后一个 query array的第一项,然后跳过。
: 每次碰上乱序,也跳过

相关主题
问一道面试题目你们面试时候忽略了一个重要点
Minimum number of moves to make an integer array balanceGoogle电话面试题目
请教个面试题一道算法题
进入JobHunting版参与讨论
p*****2
发帖数: 21240
31
void minWindows(int[] S, int[] T)
{
int m=S.length;
int n=T.length;
int[][] dp=new int[m+1][n+1];
int minindex=-1;

for(int i=0;i<=m;i++)
{
Arrays.fill(dp[i], -1);
dp[i][n]=0;
}

for(int i=m-1;i>=0;i--)
{
for(int j=n-1;j>=Math.max(0, n-(m-i));j--)
if(S[i]==T[j] && dp[i+1][j+1]>=0)
dp[i][j]=dp[i+1][j+1]+1;
else if(dp[i+1][j]>=0)
dp[i][j]=dp[i+1][j]+1;
if(dp[i][0]>=0 && (minindex==-1 || dp[i][0] minindex=i;
}
if(minindex>=0)
{
System.out.println("start:"+minindex);
System.out.println("len:"+dp[minindex][0]);
}
}
l*****a
发帖数: 14598
32
我明明每次start,end一起向前走,你非说O(n2)
无语了

【在 w****x 的大作中提到】
:
: 逻辑好复杂
: 时间复杂度是O(n^2)感觉

p*****2
发帖数: 21240
33

真没看明白,能不能举个例子?这题如果能O(n)还是挺牛逼的。

【在 l*****a 的大作中提到】
: 就是找到了第i个,旧可以继续向前找第i/i+1个,如果i到了array.size说明找到了
: 如果找到了地i个的时候,出现了第i+1或以后的,整个这段作废
: start=end+1再开始

l*****a
发帖数: 14598
34
query array [A,B,C,D]
a b c A B D D a b c A b A d d B C D
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
start=0; end=start;
a not in query array ,OK end++
b end++
c end++
A first one in query array,OK end++
B met 1st before, now 2nd ,OK end++
D met 2nd before, now 4th,wrong
so [0,5] is illegal,we have to start from 6.
D in current slide windows, we met the 4th of query array, illegal
skip
start=7;end=start;
a not in query array ,OK end++
b end++
c end++
A first one in query array,OK end++
b end++
A met 1st before, now still 1st ,OK end++
d end++
d end++
B met 1st before, now 2nd ,OK end++
C met 2nd before, now 3rd ,OK end++
D met 3rd before, now 4th,ok, end++
since we meet the final one of query array,
we know we got the result as what we want.
7->17
since there is more A in this windows, we can move start until the end of
1st, so 12-17 will be the shortest in this part.
then start=end++;end=start;判断下一段
简单说,对有序用一个index判断。
index=-1
if current is Query[index] or Query[index+1]
都是有序,否则就是illegal的

【在 p*****2 的大作中提到】
:
: 真没看明白,能不能举个例子?这题如果能O(n)还是挺牛逼的。

p*****2
发帖数: 21240
35

感觉这个有问题
D met 2nd before, now 4th,wrong
so [0,5] is illegal,we have to start from 6.

【在 l*****a 的大作中提到】
: query array [A,B,C,D]
: a b c A B D D a b c A b A d d B C D
: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
: start=0; end=start;
: a not in query array ,OK end++
: b end++
: c end++
: A first one in query array,OK end++
: B met 1st before, now 2nd ,OK end++
: D met 2nd before, now 4th,wrong

l*****a
发帖数: 14598
36
why?ABD乱序,肯定要淘汰啊
丢掉了什么?
注意每次match 到query array的相应项目,index++

【在 p*****2 的大作中提到】
:
: 感觉这个有问题
: D met 2nd before, now 4th,wrong
: so [0,5] is illegal,we have to start from 6.

w****x
发帖数: 2483
37

逻辑太复杂了,怎么想出来的,放弃了

【在 l*****a 的大作中提到】
: why?ABD乱序,肯定要淘汰啊
: 丢掉了什么?
: 注意每次match 到query array的相应项目,index++

l*****a
发帖数: 14598
38
我哭了,明明就是slide windows
那你slide windows怎么做?那题是包含所有query array的item
现在就多了一个有序吗,用index判断一下就好了

【在 w****x 的大作中提到】
:
: 逻辑太复杂了,怎么想出来的,放弃了

p*****2
发帖数: 21240
39

题目有歧义。我的理解是
ABDCD是有效的。如果算无效的,slide window确实可以。

【在 l*****a 的大作中提到】
: 我哭了,明明就是slide windows
: 那你slide windows怎么做?那题是包含所有query array的item
: 现在就多了一个有序吗,用index判断一下就好了

w****x
发帖数: 2483
40

ABDCD 当然有效

【在 p*****2 的大作中提到】
:
: 题目有歧义。我的理解是
: ABDCD是有效的。如果算无效的,slide window确实可以。

相关主题
一道算法题点评网站Y面经
google 面试题疑问问一个狗狗的OnSite题
Given an int array and an int value. Find all pairs in arrHashTable space complexity?
进入JobHunting版参与讨论
l*****a
发帖数: 14598
41
contains all the elements of query array and also in the same order
如果这个叫 in the same order
那什么叫 not in the same order呢?

【在 w****x 的大作中提到】
:
: ABDCD 当然有效

w****x
发帖数: 2483
42

只要有sub sequence in the same order就算

【在 l*****a 的大作中提到】
: contains all the elements of query array and also in the same order
: 如果这个叫 in the same order
: 那什么叫 not in the same order呢?

p*****2
发帖数: 21240
d*********g
发帖数: 154
44

想到这个计算DP的公式还真不太容易~~感觉主要是dp[i][j]表示什么含义这个比较难想
,把它想明白之后公式就比较好想出来了~

【在 p*****2 的大作中提到】
: 我放到我的博客里了。
: http://blog.sina.com.cn/s/blog_b9285de20101h6jx.html

M*********n
发帖数: 4839
45
这道题最简单的思想是build一个状态机吧
1 (共1页)
进入JobHunting版参与讨论
相关主题
菜鸟问个two sum的变型题google 面试题疑问
请教一道算法题Given an int array and an int value. Find all pairs in arr
问一道面试题目点评网站Y面经
Minimum number of moves to make an integer array balance问一个狗狗的OnSite题
请教个面试题HashTable space complexity?
你们面试时候忽略了一个重要点面试题求解:remove first duplicate number from an array
Google电话面试题目一个实际碰到的问题
一道算法题求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)
相关话题的讨论汇总
话题: dp话题: query话题: minindex话题: array话题: end