问个google面试题 - 未名空间MITBBS历史存档

h*n2011-07-02 07:07

1 楼

Job Details
The Henan University in China invites applications for tenure-track
positions in the field of Electrical Engineering (Automation), Information
Technology and Environmental Engineering. The positions will be open at the
Assistant to the Full Professor level. Doctorate in Electrical Engineering,
Information Technology, Environmental Engineering or closely related fields
is required. Responsibility will include teaching undergraduate engineering
courses and conducting sponsored research.
The salary will be negotiable ranging from RMB￥300,000 (about USD
$43,000) to RMB￥800,000 (about USD$115,000), plus other benefits.
Please send CV, 3 letters of recommendation and a cover letter to
[email protected] The search will continue until the positions are
filled.
Requirements
(1) Doctoral Degree in Electrical Engineering, Information Technology,
Environmental Engineering, or closely related fields;
(2) Teaching experience is preferred;
(3) Native English speaker is preferred.
http://jobs.ieee.org/jobs/tenured-faculty-positions-at-the-henan-university-in-china-kaifeng-henan-450000-99456434-d

B*12011-07-02 07:07

2 楼

Write a function which takes as parameters one regular expression(only ? and
* are the special characters) and a string and returns whether the string
matched the regular expression.
不是很熟悉regex，但是在match的时候是不是每次都要判断当前字符下一个是不是? 或
者* ,而不是判断当前字符是不是?或者*。这是careercup上面的题目，看了那里的人
的讨论，似乎没有一个完全正确的。
譬如ab?c match ac
当当前字符是b的时候，同时下一个字符是?,那么就可以去直接跳2个字符去match c了？

Y*N2011-07-02 07:07

3 楼

本来想推荐给虎肉，结果看到这个
(3) Native English speaker is preferred.

the
,
fields
engineering
USD

【在 h****n 的大作中提到】

: Job Details
: The Henan University in China invites applications for tenure-track
: positions in the field of Electrical Engineering (Automation), Information
: Technology and Environmental Engineering. The positions will be open at the
: Assistant to the Full Professor level. Doctorate in Electrical Engineering,
: Information Technology, Environmental Engineering or closely related fields
: is required. Responsibility will include teaching undergraduate engineering
: courses and conducting sponsored research.
: The salary will be negotiable ranging from RMB￥300,000 (about USD
: $43,000) to RMB￥800,000 (about USD$115,000), plus other benefits.

c*g2011-07-02 07:07

4 楼

感觉跟编译词法分析很像，构造NFA，转化成DFA，得到状态转移表，匹配字符串。每一
步都有标准算法的，不过不确定是不是expect这个答案啊。

and
了？

【在 B*******1 的大作中提到】

: Write a function which takes as parameters one regular expression(only ? and
: * are the special characters) and a string and returns whether the string
: matched the regular expression.
: 不是很熟悉regex，但是在match的时候是不是每次都要判断当前字符下一个是不是? 或
: 者* ,而不是判断当前字符是不是?或者*。这是careercup上面的题目，看了那里的人
: 的讨论，似乎没有一个完全正确的。
: 譬如ab?c match ac
: 当当前字符是b的时候，同时下一个字符是?,那么就可以去直接跳2个字符去match c了？

A*82011-07-02 07:07

5 楼

国内怎么这么蠢，英语是母语的人如果学术也不错怎么可能去河南大学？这显然就是为
了找个美国人来充门面的，浪费钱。人傻钱多！

a*02011-07-02 07:07

6 楼

ab?c match ac?

and
了？

【在 B*******1 的大作中提到】

: Write a function which takes as parameters one regular expression(only ? and
: * are the special characters) and a string and returns whether the string
: matched the regular expression.
: 不是很熟悉regex，但是在match的时候是不是每次都要判断当前字符下一个是不是? 或
: 者* ,而不是判断当前字符是不是?或者*。这是careercup上面的题目，看了那里的人
: 的讨论，似乎没有一个完全正确的。
: 譬如ab?c match ac
: 当当前字符是b的时候，同时下一个字符是?,那么就可以去直接跳2个字符去match c了？

z*x2011-07-02 07:07

7 楼

河南人，去那里开过一天的会。一般非河南人大概不会去那里工作。
可能是找一个给他们修改论文的下手吧。

a*02011-07-02 07:07

8 楼

when you are at b, it doen't match
for another example, ab?c match abdc, when you are at ?, any next char from
string is accepted

and
了？

【在 B*******1 的大作中提到】

: Write a function which takes as parameters one regular expression(only ? and
: * are the special characters) and a string and returns whether the string
: matched the regular expression.
: 不是很熟悉regex，但是在match的时候是不是每次都要判断当前字符下一个是不是? 或
: 者* ,而不是判断当前字符是不是?或者*。这是careercup上面的题目，看了那里的人
: 的讨论，似乎没有一个完全正确的。
: 譬如ab?c match ac
: 当当前字符是b的时候，同时下一个字符是?,那么就可以去直接跳2个字符去match c了？

P*c2011-07-02 07:07

9 楼

你是说abc match a?c吗？
如果regular experession当前是?，则跳过match下一个。
ab?c 和ac 到b已经不match了，不用到?
如果regular expression里只有?, 那么只要碰到第一个不match的就可以返回。
但是有*就比较麻烦，需要找到string下一个match *后面的pattern, 比如如果要match
a*cb?a 跟abcacacacbaccbaa
先找到第一个cb,但是后面不match，但是这不说明整个就不match, 因为可以跳过这个
cb再找下一个cb, 结果是match的。不知道有没有什么好的方法。

and
了？

【在 B*******1 的大作中提到】

: Write a function which takes as parameters one regular expression(only ? and
: * are the special characters) and a string and returns whether the string
: matched the regular expression.
: 不是很熟悉regex，但是在match的时候是不是每次都要判断当前字符下一个是不是? 或
: 者* ,而不是判断当前字符是不是?或者*。这是careercup上面的题目，看了那里的人
: 的讨论，似乎没有一个完全正确的。
: 譬如ab?c match ac
: 当当前字符是b的时候，同时下一个字符是?,那么就可以去直接跳2个字符去match c了？

a*02011-07-02 07:07

10 楼

how about build a suffix tree and search every path starting with the next
char of *

match

【在 P**********c 的大作中提到】

: 你是说abc match a?c吗？
: 如果regular experession当前是?，则跳过match下一个。
: ab?c 和ac 到b已经不match了，不用到?
: 如果regular expression里只有?, 那么只要碰到第一个不match的就可以返回。
: 但是有*就比较麻烦，需要找到string下一个match *后面的pattern, 比如如果要match
: a*cb?a 跟abcacacacbaccbaa
: 先找到第一个cb,但是后面不match，但是这不说明整个就不match, 因为可以跳过这个
: cb再找下一个cb, 结果是match的。不知道有没有什么好的方法。
:
: and

P*c2011-07-02 07:07

11 楼

我觉得这个应该就是答案，不过implement起来挺繁的。

【在 a*********0 的大作中提到】

: how about build a suffix tree and search every path starting with the next
: char of *
:
: match

a*02011-07-02 07:07

12 楼

suffix tree is the tree of the input string, not the regular expression

【在 P**********c 的大作中提到】

: 我觉得这个应该就是答案，不过implement起来挺繁的。

B*12011-07-02 07:07

13 楼

Quantification
A quantifier after a token (such as a character) or group specifies how often that preceding element is allowed to occur. The most common quantifiers are the question mark ?, the asterisk * (derived from the Kleene star), and the plus sign + (Kleene cross).
? The question mark indicates there is zero or one of the preceding element. For example, colou?r matches both "color" and "colour".
* The asterisk indicates there are zero or more of the preceding element. For example, ab*c matches "ac", "abc", "abbc", "abbbc", and so on.
+ The plus sign indicates that there is one or more of the preceding element. For example, ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac".
colou?r match color,
为什么ab?c match ac 不对啊？

match

【在 P**********c 的大作中提到】

: 你是说abc match a?c吗？
: 如果regular experession当前是?，则跳过match下一个。
: ab?c 和ac 到b已经不match了，不用到?
: 如果regular expression里只有?, 那么只要碰到第一个不match的就可以返回。
: 但是有*就比较麻烦，需要找到string下一个match *后面的pattern, 比如如果要match
: a*cb?a 跟abcacacacbaccbaa
: 先找到第一个cb,但是后面不match，但是这不说明整个就不match, 因为可以跳过这个
: cb再找下一个cb, 结果是match的。不知道有没有什么好的方法。
:
: and

g*y2011-07-02 07:07

14 楼

不能，?是greedy match.

and
了？

【在 B*******1 的大作中提到】

: Write a function which takes as parameters one regular expression(only ? and
: * are the special characters) and a string and returns whether the string
: matched the regular expression.
: 不是很熟悉regex，但是在match的时候是不是每次都要判断当前字符下一个是不是? 或
: 者* ,而不是判断当前字符是不是?或者*。这是careercup上面的题目，看了那里的人
: 的讨论，似乎没有一个完全正确的。
: 譬如ab?c match ac
: 当当前字符是b的时候，同时下一个字符是?,那么就可以去直接跳2个字符去match c了？

a*02011-07-02 07:07

15 楼

we thought ? means match one symbol, * means match 0 or any number of
symbols.

how often that preceding element is allowed to occur. The most common
quantifiers are the question mark ?, the asterisk * (derived from the Kleene
star), and the plus sign + (Kle
preceding element. For example, colou?r matches both "color" and "colour".
preceding element. For example, ab*c matches "ac", "abc", "abbc", "abbbc",
and so on.
preceding element. For example, ab+c matches "abc", "abbc", "abbbc", and so
on, but not "ac".

【在 B*******1 的大作中提到】

: Quantification
: A quantifier after a token (such as a character) or group specifies how often that preceding element is allowed to occur. The most common quantifiers are the question mark ?, the asterisk * (derived from the Kleene star), and the plus sign + (Kleene cross).
: ? The question mark indicates there is zero or one of the preceding element. For example, colou?r matches both "color" and "colour".
: * The asterisk indicates there are zero or more of the preceding element. For example, ab*c matches "ac", "abc", "abbc", "abbbc", and so on.
: + The plus sign indicates that there is one or more of the preceding element. For example, ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac".
: colou?r match color,
: 为什么ab?c match ac 不对啊？
:
: match

s*v2011-07-02 07:07

16 楼

一般实现的时候都是状态鸡吧

string
? 或
的人
c

【在 g**********y 的大作中提到】

: 不能，?是greedy match.
:
: and
: 了？

B*12011-07-02 07:07

17 楼

这题如果只是? 和 * 的话，用简单迭代不行吗？
现场怎么写状态机出来啊？

【在 s********v 的大作中提到】

: 一般实现的时候都是状态鸡吧
:
: string
: ? 或
: 的人
: c

a*02011-07-02 07:07

18 楼

with the limitation of only two special chars, the DFA is pretty easy to
produced by an algorithm. For *, there is only a loop of node pointed to by
the last char. for ?, it's a two path, one is jumping to the next char, one
is match previous

【在 B*******1 的大作中提到】

: 这题如果只是? 和 * 的话，用简单迭代不行吗？
: 现场怎么写状态机出来啊？

g*y2011-07-02 07:07

19 楼

写了个Java版的：
public boolean matches(String pattern, String str) {
int i = 0;
while (icharAt(i)!='*') i++;

if (i == pattern.length()) return pattern.equals(str);

char c = pattern.charAt(i-1);
if (pattern.charAt(i) == '?') {
return pattern.substring(0, i-2).equals(str.substring(0, i-2)) &&
(equals(c, str, i-1) && matches(pattern.substring(i+1),
str.substring(i)) ||
matches(pattern.substring(i+1), str.substring(i-
1)));
}

// pattern.charAt(i) == '*'
int j = i-1;
while (j < str.length() && str.charAt(j) == c) j++;

for (int k=j-1; k>=i-2; k--) {
if (matches(pattern.substring(i+1), str.substring(k+1))) return
true;
}

return false;
}

private boolean equals(char c, String str, int index) {
return str.length() > index && str.charAt(index) == c;
}

B*12011-07-02 07:07

20 楼

thanks very much.

&&
,

【在 g**********y 的大作中提到】

: 写了个Java版的：
: public boolean matches(String pattern, String str) {
: int i = 0;
: while (i: charAt(i)!='*') i++;
:
: if (i == pattern.length()) return pattern.equals(str);
:
: char c = pattern.charAt(i-1);
: if (pattern.charAt(i) == '?') {

a*02011-07-02 07:07

21 楼

recursion version
boolean StringMatch(String reg, int i, String input, int j){
if(i>=reg.length && j>=input.length){
return true;
}

if(i>=reg.length && jreturn false;

if(i+1while(j){
if(StringMatch(reg, i+2, input, j+1))
return true;
j++;
}

if(j>=input.length)
return StringMatch(reg, i+2, input, j+1)
else
return false;
}

if(i+1if(jreturn StringMatch(reg, i+2, input, j+1);
else if(j>=input.length)
return StringMatch(reg, i+2, input, j);
}

if(jreturn StringMatch(reg, i+1, input, j+1);

return false;
}

【在 B*******1 的大作中提到】

: 这题如果只是? 和 * 的话，用简单迭代不行吗？
: 现场怎么写状态机出来啊？

a*02011-07-02 07:07

22 楼

some clarificiation?

&&
,

【在 g**********y 的大作中提到】

: 写了个Java版的：
: public boolean matches(String pattern, String str) {
: int i = 0;
: while (i: charAt(i)!='*') i++;
:
: if (i == pattern.length()) return pattern.equals(str);
:
: char c = pattern.charAt(i-1);
: if (pattern.charAt(i) == '?') {

B*12011-07-02 07:07

23 楼

thanks
I thought you will implenemnt the DFA one.

))

【在 a*********0 的大作中提到】

: recursion version
: boolean StringMatch(String reg, int i, String input, int j){
: if(i>=reg.length && j>=input.length){
: return true;
: }
:
: if(i>=reg.length && j: return false;
:
: if(i+1

g*y2011-07-02 07:07

24 楼

Fail test:
"ab?c*d", "accccd"
"ac?c*c", "ac"
Both should match.

【在 a*********0 的大作中提到】

: recursion version
: boolean StringMatch(String reg, int i, String input, int j){
: if(i>=reg.length && j>=input.length){
: return true;
: }
:
: if(i>=reg.length && j: return false;
:
: if(i+1

s*n2011-07-02 07:07

25 楼

面得那个office?

and
了？

【在 B*******1 的大作中提到】

: Write a function which takes as parameters one regular expression(only ? and
: * are the special characters) and a string and returns whether the string
: matched the regular expression.
: 不是很熟悉regex，但是在match的时候是不是每次都要判断当前字符下一个是不是? 或
: 者* ,而不是判断当前字符是不是?或者*。这是careercup上面的题目，看了那里的人
: 的讨论，似乎没有一个完全正确的。
: 譬如ab?c match ac
: 当当前字符是b的时候，同时下一个字符是?,那么就可以去直接跳2个字符去match c了？

B*12011-07-02 07:07

26 楼

Saw it on careercup.

【在 s*****n 的大作中提到】

: 面得那个office?
:
: and
: 了？

a*02011-07-02 07:07

27 楼

泪奔，我都没调，现在work了，full code
import java.util.*;
public class SimpleRegMatch {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("reg:?");
Scanner in=new Scanner(System.in);
String reg=in.nextLine();

System.out.println("string:?");
String input=in.nextLine();
if(StringMatch(reg, 0, input, 0))
System.out.println("accepted");
else
System.out.println("unaccepted");
}
private static boolean StringMatch(String reg, int i, String input,
int j){
if(i>=reg.length() && j>=input.length()){
return true;
}

if(i>=reg.length() && jreturn false;

if(i+1if(StringMatch(reg, i+2, input, j))
return true;

while(jcharAt(i)){
if(StringMatch(reg, i+2, input, j+1))
return true;
j++;
}

return StringMatch(reg, i+2, input, j);
}

if(i+1if(j))
return StringMatch(reg, i+2, input, j+1) ||
StringMatch(reg, i+2, input, j);
else
return StringMatch(reg, i+2, input, j);
}

if(jreturn StringMatch(reg, i+1, input, j+1);

return false;
}
}

【在 g**********y 的大作中提到】

: Fail test:
: "ab?c*d", "accccd"
: "ac?c*c", "ac"
: Both should match.

l*t2011-07-02 07:07

28 楼

应该考的就是这个

【在 a*********0 的大作中提到】

: how about build a suffix tree and search every path starting with the next
: char of *
:
: match

t*52011-07-02 07:07

29 楼

You guys are making things too complicated:
"A string match a regular expression"
"A string has a substring that match a regular expression"
It is just a walk along the two strings at the same time.

g*y2011-07-02 07:07

30 楼

sigh, 边界条件又写错了，修改版：
public boolean matches(String pattern, String str) {
int i = 0;
while (i < pattern.length() && pattern.charAt(i) != '?'
&& pattern.charAt(i) != '*')
i++;
if (i == pattern.length())
return pattern.equals(str);
char c = pattern.charAt(i - 1);
if (pattern.charAt(i) == '?') {
return pattern.substring(0, i - 1).equals(str.substring(0, i - 1
))
&& (matches(c + pattern.substring(i + 1), str.substring(
i - 1))
|| matches(pattern.substring(i + 1), str.substring(i - 1
)));
}
// pattern.charAt(i) == '*'
int j = i - 1;
while (j < str.length() && str.charAt(j) == c) j++;
for (int k = j; k >= i - 1; k--) {
if (matches(pattern.substring(i + 1), str.substring(k)))
return true;
}
return false;
}

c*g2011-07-02 07:07

31 楼

recursive top down parsing 不仅能分析正则表达式，还能分析上下文无关文法。感
觉杀鸡用牛刀了。

【在 g**********y 的大作中提到】

: sigh, 边界条件又写错了，修改版：
: public boolean matches(String pattern, String str) {
: int i = 0;
: while (i < pattern.length() && pattern.charAt(i) != '?'
: && pattern.charAt(i) != '*')
: i++;
: if (i == pattern.length())
: return pattern.equals(str);
: char c = pattern.charAt(i - 1);
: if (pattern.charAt(i) == '?') {

g*y2011-07-02 07:07

32 楼

有什么更简单的办法吗？贴出来让我们参考一下。

【在 c******g 的大作中提到】

: recursive top down parsing 不仅能分析正则表达式，还能分析上下文无关文法。感
: 觉杀鸡用牛刀了。

c*g2011-07-02 07:07

33 楼

以前使用flex自动生成的，我试试看吧。。。

【在 g**********y 的大作中提到】

: 有什么更简单的办法吗？贴出来让我们参考一下。

w*32011-07-02 07:07

34 楼

实现上来说递归是最简单的吧

【在 c******g 的大作中提到】

: 以前使用flex自动生成的，我试试看吧。。。

t*r2011-07-02 07:07

35 楼

mark

a*y2011-07-02 07:07

36 楼

如果是用perl写,很简单.
sub mymatch {
my $regexp,$s;
$regexp = shift;
$s = shift;
return $s =~ $regexp;
}

and
了？

【在 B*******1 的大作中提到】

: Write a function which takes as parameters one regular expression(only ? and
: * are the special characters) and a string and returns whether the string
: matched the regular expression.
: 不是很熟悉regex，但是在match的时候是不是每次都要判断当前字符下一个是不是? 或
: 者* ,而不是判断当前字符是不是?或者*。这是careercup上面的题目，看了那里的人
: 的讨论，似乎没有一个完全正确的。
: 譬如ab?c match ac
: 当当前字符是b的时候，同时下一个字符是?,那么就可以去直接跳2个字符去match c了？

g*y2011-07-02 07:07

37 楼

你这是作弊，如果可以这么用library, Java就一句，
return str.matches(pattern);

【在 a***y 的大作中提到】

: 如果是用perl写,很简单.
: sub mymatch {
: my $regexp,$s;
: $regexp = shift;
: $s = shift;
: return $s =~ $regexp;
: }
:
: and
: 了？

a*y2011-07-02 07:07

38 楼

题目没有写不能用perl啊.我这个还没用到module.

【在 g**********y 的大作中提到】

: 你这是作弊，如果可以这么用library, Java就一句，
: return str.matches(pattern);

h*k2011-07-02 07:07

39 楼

用动态规划

and
了？

【在 B*******1 的大作中提到】

: Write a function which takes as parameters one regular expression(only ? and
: * are the special characters) and a string and returns whether the string
: matched the regular expression.
: 不是很熟悉regex，但是在match的时候是不是每次都要判断当前字符下一个是不是? 或
: 者* ,而不是判断当前字符是不是?或者*。这是careercup上面的题目，看了那里的人
: 的讨论，似乎没有一个完全正确的。
: 譬如ab?c match ac
: 当当前字符是b的时候，同时下一个字符是?,那么就可以去直接跳2个字符去match c了？