发信人: kaikousen (2～hu), 信区: JobHunting
标 题: 贡献一道电面/校招题目
发信站: BBS 未名空间站 (Thu Oct 30 00:23:19 2014, 美东)
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下来了。这是不是就算挂了...
--
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 205.]
Thursday, October 30, 2014
贡献一道电面/校招题目
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment