贡献一道电面/校招题目 - 未名空间MITBBS历史存档

k*n2014-10-30 07:10

1 楼

adpu中的一家，就不说是哪家了。
题目大概就是用pattern p匹配字符串s。已知如下
p="abba", s="red blue blue red", true
p="aaaa", s="red red red red", true
p="abab", s="red blue blue red", false
p="abba", s="red red red red", false
然后就让开始做。问了一下大概问出来没有定义好a对应red，b对应blue，只要a和a对
应相同的单词，a和b对应不同的单词就可以了。大概问了一下各种corner case就开始
做题，还算顺利，做完以后问了复杂度。
以上是第一问。第二问是假设单词之间没有空格怎么办。想一下说用dp和递归应该都行
，然后面试官让说说递归怎么做于是感到面试官应该希望听到递归的解法，于是就说
partition s呗，前一半跟p的前n-1个字母match，后一半跟第一问一样的检查是否可行
。面试官让写code，写啊写，写啊写，匹配的那个map的回溯总是写不对（不回溯空间
岂不爆掉了？），到最后看到面试官把错误的版本copy下来了。这是不是就算挂了...

H*72014-10-30 07:10

2 楼

模式只是两种？还是可以多种？我的意思是需要处理abcabc么

★ 发自iPhone App: ChineseWeb 8.7

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

: adpu中的一家，就不说是哪家了。
: 题目大概就是用pattern p匹配字符串s。已知如下
: p="abba", s="red blue blue red", true
: p="aaaa", s="red red red red", true
: p="abab", s="red blue blue red", false
: p="abba", s="red red red red", false
: 然后就让开始做。问了一下大概问出来没有定义好a对应red，b对应blue，只要a和a对
: 应相同的单词，a和b对应不同的单词就可以了。大概问了一下各种corner case就开始
: 做题，还算顺利，做完以后问了复杂度。
: 以上是第一问。第二问是假设单词之间没有空格怎么办。想一下说用dp和递归应该都行

l*a2014-10-30 07:10

3 楼

你不说无所谓
刚才已经有人说是D家的

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

: adpu中的一家，就不说是哪家了。
: 题目大概就是用pattern p匹配字符串s。已知如下
: p="abba", s="red blue blue red", true
: p="aaaa", s="red red red red", true
: p="abab", s="red blue blue red", false
: p="abba", s="red red red red", false
: 然后就让开始做。问了一下大概问出来没有定义好a对应red，b对应blue，只要a和a对
: 应相同的单词，a和b对应不同的单词就可以了。大概问了一下各种corner case就开始
: 做题，还算顺利，做完以后问了复杂度。
: 以上是第一问。第二问是假设单词之间没有空格怎么办。想一下说用dp和递归应该都行

s*l2014-10-30 07:10

4 楼

Dropbox吗？

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

: 你不说无所谓
: 刚才已经有人说是D家的

s*l2014-10-30 07:10

5 楼

那个帖子里说的？

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

: 你不说无所谓
: 刚才已经有人说是D家的

k*n2014-10-30 07:10

6 楼

模式有任意多种，理论上ascii都行

【在 H******7 的大作中提到】

: 模式只是两种？还是可以多种？我的意思是需要处理abcabc么
:
: ★ 发自iPhone App: ChineseWeb 8.7

n*a2014-10-30 07:10

7 楼

多谢分享，收藏了

z*m2014-10-30 07:10

8 楼

abba -> 0110，每个digit是该字母第一次出现时的位置。
同理， red blue blue red -> 0110, 只不过，这时的每个digit是该word第一次出现在
vector里的位置（假设我们已经trim掉空格了）。
这样一mapping，就很好判断了。

P*f2014-10-30 07:10

9 楼

现场写感觉好难啊

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

: adpu中的一家，就不说是哪家了。
: 题目大概就是用pattern p匹配字符串s。已知如下
: p="abba", s="red blue blue red", true
: p="aaaa", s="red red red red", true
: p="abab", s="red blue blue red", false
: p="abba", s="red red red red", false
: 然后就让开始做。问了一下大概问出来没有定义好a对应red，b对应blue，只要a和a对
: 应相同的单词，a和b对应不同的单词就可以了。大概问了一下各种corner case就开始
: 做题，还算顺利，做完以后问了复杂度。
: 以上是第一问。第二问是假设单词之间没有空格怎么办。想一下说用dp和递归应该都行

f*g2014-10-30 07:10

10 楼

如果ascii码多了没法这么处理吧

现在

【在 z***m 的大作中提到】

: abba -> 0110，每个digit是该字母第一次出现时的位置。
: 同理， red blue blue red -> 0110, 只不过，这时的每个digit是该word第一次出现在
: vector里的位置（假设我们已经trim掉空格了）。
: 这样一mapping，就很好判断了。

k*n2014-10-30 07:10

11 楼

adpu中的一家，就不说是哪家了。
题目大概就是用pattern p匹配字符串s。已知如下
p="abba", s="red blue blue red", true
p="aaaa", s="red red red red", true
p="abab", s="red blue blue red", false
p="abba", s="red red red red", false
然后就让开始做。问了一下大概问出来没有定义好a对应red，b对应blue，只要a和a对
应相同的单词，a和b对应不同的单词就可以了。大概问了一下各种corner case就开始
做题，还算顺利，做完以后问了复杂度。
以上是第一问。第二问是假设单词之间没有空格怎么办。想一下说用dp和递归应该都行
，然后面试官让说说递归怎么做于是感到面试官应该希望听到递归的解法，于是就说
partition s呗，前一半跟p的前n-1个字母match，后一半跟第一问一样的检查是否可行
。面试官让写code，写啊写，写啊写，匹配的那个map的回溯总是写不对（不回溯空间
岂不爆掉了？），到最后看到面试官把错误的版本copy下来了。这是不是就算挂了...

H*72014-10-30 07:10

12 楼

模式只是两种？还是可以多种？我的意思是需要处理abcabc么

★ 发自iPhone App: ChineseWeb 8.7

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

: adpu中的一家，就不说是哪家了。
: 题目大概就是用pattern p匹配字符串s。已知如下
: p="abba", s="red blue blue red", true
: p="aaaa", s="red red red red", true
: p="abab", s="red blue blue red", false
: p="abba", s="red red red red", false
: 然后就让开始做。问了一下大概问出来没有定义好a对应red，b对应blue，只要a和a对
: 应相同的单词，a和b对应不同的单词就可以了。大概问了一下各种corner case就开始
: 做题，还算顺利，做完以后问了复杂度。
: 以上是第一问。第二问是假设单词之间没有空格怎么办。想一下说用dp和递归应该都行

l*a2014-10-30 07:10

13 楼

你不说无所谓
刚才已经有人说是D家的

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

: adpu中的一家，就不说是哪家了。
: 题目大概就是用pattern p匹配字符串s。已知如下
: p="abba", s="red blue blue red", true
: p="aaaa", s="red red red red", true
: p="abab", s="red blue blue red", false
: p="abba", s="red red red red", false
: 然后就让开始做。问了一下大概问出来没有定义好a对应red，b对应blue，只要a和a对
: 应相同的单词，a和b对应不同的单词就可以了。大概问了一下各种corner case就开始
: 做题，还算顺利，做完以后问了复杂度。
: 以上是第一问。第二问是假设单词之间没有空格怎么办。想一下说用dp和递归应该都行

s*l2014-10-30 07:10

14 楼

Dropbox吗？

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

: 你不说无所谓
: 刚才已经有人说是D家的

s*l2014-10-30 07:10

15 楼

那个帖子里说的？

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

: 你不说无所谓
: 刚才已经有人说是D家的

k*n2014-10-30 07:10

16 楼

模式有任意多种，理论上ascii都行

【在 H******7 的大作中提到】

: 模式只是两种？还是可以多种？我的意思是需要处理abcabc么
:
: ★ 发自iPhone App: ChineseWeb 8.7

n*a2014-10-30 07:10

17 楼

多谢分享，收藏了

z*m2014-10-30 07:10

18 楼

abba -> 0110，每个digit是该字母第一次出现时的位置。
同理， red blue blue red -> 0110, 只不过，这时的每个digit是该word第一次出现在
vector里的位置（假设我们已经trim掉空格了）。
这样一mapping，就很好判断了。

f*g2014-10-30 07:10

19 楼

如果ascii码多了没法这么处理吧

现在

【在 z***m 的大作中提到】

: abba -> 0110，每个digit是该字母第一次出现时的位置。
: 同理， red blue blue red -> 0110, 只不过，这时的每个digit是该word第一次出现在
: vector里的位置（假设我们已经trim掉空格了）。
: 这样一mapping，就很好判断了。

m*g2014-10-30 07:10

20 楼

RED BLUE 去掉空格难处理啊。

s*i2014-10-30 07:10

21 楼

有空格的版本解法:
p里面读到新的字母则将p里字母和s里单词插入map.
读到已出现过的字母,则在map里检查旧的s里的单词和刚读到的单词是否相同.

m*g2014-10-30 07:10

22 楼

RED BLUE 去掉空格难处理啊。

s*i2014-10-30 07:10

23 楼

有空格的版本解法:
p里面读到新的字母则将p里字母和s里单词插入map.
读到已出现过的字母,则在map里检查旧的s里的单词和刚读到的单词是否相同.

t*e2014-10-30 07:10

24 楼

这题没空格怎么做

d*62014-10-30 07:10

25 楼

没有空格的话，假设：
a对应字符长度为l1
b对应字符长度为l2
。。。
。。。
分析pattern，得出要对应的位置，存入数组
比如abba这个pattern就要求
for i in 0 to l1-1
s[0] == s[l1+2*l2+i]
for j in 0 to l2-1
s[l1+j] == s[l1+l2+j]
把这个写成一个判断函数 isPatternMatch(pattern, string, l1, l2)
从l1=1,l2=1开始一直搜索，直到穷尽所有case满足l1+l2

e*22014-10-30 07:10

26 楼

没什么好办法，先从重复次数最多的开始找起。

【在 d**********6 的大作中提到】

: 没有空格的话，假设：
: a对应字符长度为l1
: b对应字符长度为l2
: 。。。
: 。。。
: 分析pattern，得出要对应的位置，存入数组
: 比如abba这个pattern就要求
: for i in 0 to l1-1
: s[0] == s[l1+2*l2+i]
: for j in 0 to l2-1