c*********u
发帖数: 361 | 1 1. Algorithm (I think this question has appeared in this board multiple time
s before):
given n arrays of integers, each array represent the indices of a word in a
text, e.g.
hello: 5 14 19 35 52
world: 11 17 29 40
goodbye: 1 25 63 72
Find the smallest window that contains all words (in this case 17-25).
2. Coding: Given a text and a pattern, find if the elements of the pattern
appear in the text in the given order (but the elements don't have to be
contiguous), e.g.
text = hello world |
x*******7
发帖数: 223 | 2 是用java还是c/c++?如果是java,我觉得用正则表达式很容易做第二题吧。
time
a
【在 c*********u 的大作中提到】
: 1. Algorithm (I think this question has appeared in this board multiple time
: s before):
: given n arrays of integers, each array represent the indices of a word in a
: text, e.g.
: hello: 5 14 19 35 52
: world: 11 17 29 40
: goodbye: 1 25 63 72
: Find the smallest window that contains all words (in this case 17-25).
: 2. Coding: Given a text and a pattern, find if the elements of the pattern
: appear in the text in the given order (but the elements don't have to be
|
c*********u
发帖数: 361 | 3 我用的是C++，state machine，正则的话有点取巧了吧
【在 x*******7 的大作中提到】
: 是用java还是c/c++?如果是java,我觉得用正则表达式很容易做第二题吧。
:
: time
: a
|
l******c
发帖数: 2555 | 4 why state machine? two pointers scan and match is enough
【在 c*********u 的大作中提到】
: 我用的是C++，state machine，正则的话有点取巧了吧
|
c*********u
发帖数: 361 | 5 essentialy the same I think
【在 l******c 的大作中提到】
: why state machine? two pointers scan and match is enough
|
x****n
发帖数: 74 | 6 agree :)
【在 l******c 的大作中提到】
: why state machine? two pointers scan and match is enough
|
l******c
发帖数: 2555 | 7 maybe when character repeats andmust reset, then state machine, I guess
【在 x****n 的大作中提到】
: agree :)
|
a****n
发帖数: 70 | |
c*********u
发帖数: 361 | 9 don't know just think I've thought it before.
One way to solve this is to do a binary search regarding to the lower bound
and upper bound.
【在 a****n 的大作中提到】
: 第一题哪里有？
|
x****n
发帖数: 74 | 10 Not sure. Just my two cents. May have missed some special cases you
mentioned
bool DoesStringMatchPatternOrder(char* pString, char* pPattern)
{
if( !pString && !pPattern)
return false;
char* pCursorS = pString;
char* pCursorP = pPattern;
while(*pCursorS && *pCursorP){
while( *pCursorS && *pCursorS != *pCursorP)
pCursorS++;
pCursorP++;
}
return (*pCursorS) && (!*pCursorP);
}
guess
【在 l******c 的大作中提到】
: maybe when character repeats andmust reset, then state machine, I guess
|
|
|
c*********u
发帖数: 361 | 11 Mine:
bool findPattern(const string& text, const string& pattern)
{
int n = strlen(pattern);
int count = 0;
for (int i = 0; i < strlen(text); i++) {
if (text[i] == pattern[count]) {
count++;
if (count == n)
return true;
}
}
return false;
}
【在 x****n 的大作中提到】
: Not sure. Just my two cents. May have missed some special cases you
: mentioned
: bool DoesStringMatchPatternOrder(char* pString, char* pPattern)
: {
: if( !pString && !pPattern)
: return false;
: char* pCursorS = pString;
: char* pCursorP = pPattern;
: while(*pCursorS && *pCursorP){
: while( *pCursorS && *pCursorS != *pCursorP)
|
x****n
发帖数: 74 | 12 Then same idea :) So I guess I didn't miss special cases
【在 c*********u 的大作中提到】
: Mine:
: bool findPattern(const string& text, const string& pattern)
: {
: int n = strlen(pattern);
: int count = 0;
: for (int i = 0; i < strlen(text); i++) {
: if (text[i] == pattern[count]) {
: count++;
: if (count == n)
: return true;
|
c*********u
发帖数: 361 | 13 For this one it doesn't matter I guess. But state machine is convenient for
string matching algorithms because it's hard to get wrong imo:)
【在 l******c 的大作中提到】
: maybe when character repeats andmust reset, then state machine, I guess
|
a****n
发帖数: 70 | 14 怎么没有人讨论第一题？ 这个比第二题难吧
用binary search合适吗？
这里应该在每个有序数组里 拿出一个数，组成集合，让集合的range最小。还没想出跟
binary search的关系。
bound
【在 c*********u 的大作中提到】
: don't know just think I've thought it before.
: One way to solve this is to do a binary search regarding to the lower bound
: and upper bound.
|
c*********u
发帖数: 361 | 15 yes you can.
For the original set
hello: 5 14 19 35 52
world: 11 17 29 40
goodbye: 1 25 63 72
The range in the example is 1-72. You should have a recursive algorithm
to narrow down the range. The question is: do you move the lower or upper bo
und? It turns that you should consider both siutations (or you will miss som
e cases), you should should do new search for the range of 5-72 and 1-63, so
on and so forth.
【在 a****n 的大作中提到】
: 怎么没有人讨论第一题？ 这个比第二题难吧
: 用binary search合适吗？
: 这里应该在每个有序数组里 拿出一个数，组成集合，让集合的range最小。还没想出跟
: binary search的关系。
:
: bound
|
x****n
发帖数: 74 | 16 有编程之美的话，上面有类似的题。应该不是binary search，对于这种输入应该是用
三个指针遍
历，只是行进策略有些特殊，纯粹瞎猜的:)
【在 a****n 的大作中提到】
: 怎么没有人讨论第一题？ 这个比第二题难吧
: 用binary search合适吗？
: 这里应该在每个有序数组里 拿出一个数，组成集合，让集合的range最小。还没想出跟
: binary search的关系。
:
: bound
|
c*********u
发帖数: 361 | 17 指针遍历时间复杂度太高，而且3个只是例子，如果有n个array呢？
【在 x****n 的大作中提到】
: 有编程之美的话，上面有类似的题。应该不是binary search，对于这种输入应该是用
: 三个指针遍
: 历，只是行进策略有些特殊，纯粹瞎猜的:)
|
x****n
发帖数: 74 | 18 不好意思，不是很明白，如果是n， 你的方法确定下一个要搜索的新range时好像也需
要O(n)的时
间，能不能再细讲一下
【在 c*********u 的大作中提到】
: 指针遍历时间复杂度太高，而且3个只是例子，如果有n个array呢？
|
c*********u
发帖数: 361 | 19 貌似是，不知道有没有其它解法
【在 x****n 的大作中提到】
: 不好意思，不是很明白，如果是n， 你的方法确定下一个要搜索的新range时好像也需
: 要O(n)的时
: 间，能不能再细讲一下
|
l******c
发帖数: 2555 | 20 I don't think it's so simple;
string : abac,
pattern: abc
return should be false, because a repeats again.
【在 c*********u 的大作中提到】
: Mine:
: bool findPattern(const string& text, const string& pattern)
: {
: int n = strlen(pattern);
: int count = 0;
: for (int i = 0; i < strlen(text); i++) {
: if (text[i] == pattern[count]) {
: count++;
: if (count == n)
: return true;
|
|
|
c*********u
发帖数: 361 | 21 by definition for this problem I think this one should return true.
【在 l******c 的大作中提到】
: I don't think it's so simple;
: string : abac,
: pattern: abc
: return should be false, because a repeats again.
|
l******c
发帖数: 2555 | 22 3 pointers, minWindow = min{( max(abs(a-b), abs(b-c), abs(c-a)), ......}
I don'y know any other algorithm).
O(3n)
【在 c*********u 的大作中提到】
: 貌似是，不知道有没有其它解法
|
x****n
发帖数: 74 | 23 我觉得我们理解题目上有些偏差，你的例子我的理解应该是return true，因为题目只
在乎出现的顺序
【在 l******c 的大作中提到】
: I don't think it's so simple;
: string : abac,
: pattern: abc
: return should be false, because a repeats again.
|
c*********u
发帖数: 361 | 24 3 is only an example, consider the case for n arrays
【在 l******c 的大作中提到】
: 3 pointers, minWindow = min{( max(abs(a-b), abs(b-c), abs(c-a)), ......}
: I don'y know any other algorithm).
: O(3n)
|
e******n
发帖数: 3 | 25 If n >> x, I think it is better to do bottom up search.
consider the interval with length x. extend the interval to length x + 1,
if the interval contains all the arrays, return. |
t********t
发帖数: 5415 | 26 同意，并没要求最短。例如：
string = hohowl
pattern = howl
如果只要求lz说的true or false，这个肯定是true，但是如果要求最短的话，state
machine就得加入针对pattern首字符的reset。时间上应该是O(len(string))就好了。
第一题给的arrays是sort好的吗？是的话是不是可以这么做：
造个数组ind[n]，每个元素初始化为某word第一次出现的index。然后记录ind[n]中最大/最小元素之差为distance。把最小元素move到该单词下一次出现的index，再算ind[n]中最大/最小元素之差，如果比distance小就替换掉。如此反复直到某次移动导致out of bound。（这个bound不是整个text的长度，而应该是某单词出现的次数）。如果有错还请指出
【在 x****n 的大作中提到】
: 我觉得我们理解题目上有些偏差，你的例子我的理解应该是return true，因为题目只
: 在乎出现的顺序
|
d***g
发帖数: 252 | 27 对于第一题，如果有n个array，每个array有m个元素，我能想到的时间复杂度是O(m*n*
lgn)，用堆来存最大和最小元素，取出最小元素，移到下一个，然后比较最大和最小元
素的差
【在 e******n 的大作中提到】
: If n >> x, I think it is better to do bottom up search.
: consider the interval with length x. extend the interval to length x + 1,
: if the interval contains all the arrays, return.
|
c***p
发帖数: 221 | 28 第二题的一个recursive解
int contains(char * text, char * pattern)
{
if (!*pattern){
return 1;
}
if ( !*text){
return 0;
}
if (* text != *pattern){
return contains(text+1, pattern);
} else {
return contains(text+1, pattern+1);
}
} |
