找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2739|回复: 2
收起左侧

[精选面经题目] 一道Google面试题的解法

  [复制链接]
发表于 2-12-2016 11:03 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 Sophia 于 2-12-2016 01:02 PM 编辑
5 B4 e+ P) w* ?# x+ M' m( T: d4 f0 S+ M$ W; {6 u
题目:Find the pair of words in a dictionary that don\'t no same letter and the product of these two words\' length is maximum发表链接* o- E$ B7 F' [% }) }2 P  G* E4 _' b
这道题有一个暴力预处理的方法,需要理解位运算。先把单词表示成int(位图),比如一个单词abc,那么和它配对可能的位表其实是111后面跟23个0,表示只有abc出现。这样每个单词其实把把出现的字母标为1,得到了一个int。 : X4 w8 [5 k( |1 @' a+ `& J
我们状态也用int来表示,我们用位(bit)1来表示可以出现哪些字母,0表示这些字母不能出现
( V% m9 `8 `  H& y& t重要的是关于这个int的理解,这个int里为1的位表示和它配对的单词可以出现的字母。* c/ d9 ?( k2 e1 X) N) H7 `% Z! e
“可以”的意思是可能出现,也可能不出现,言外之意是出和它配对的单词出现的字母,一定是这个int中1的位对应字母的子集。
% s) A- o. D0 S; m7 S8 Q: T- X2 |9 h8 s& ^$ t
我们的首先把单词对应成int状态,再把每个状态的最长单词算出来就好了,关键是怎么算。
, S. e( r; k! e7 n2 W可以理解为dp,或者递推。
5 s4 B* [4 Z+ M# N/ }(1) 对所有的状态(共2^26个) 初值 dp[] 先给08 L( j) c$ N' ?3 ]4 G6 \( Q
(2) 对每个单词我们把它表示成整数x,令dp[x] = 单词长度 (如果有多个单词出现的字母相同,取最长的。例如at和att,显然要取3)4 j. g, v1 a: @
(3) 递推关键部分:4 {5 e3 {% R7 g& U4 x6 ~6 U) s' x
for each x from 1 to 2^26 - 1& ]1 ?3 I4 J' P3 l) k$ E% R7 G/ M/ ^
       for each y has exactly 1 bit of 1 less than x' E& R4 o, Y7 ~/ q: \
            dp[x] = max(dp[x], dp[y]) . l+ G$ |$ l# Y6 ^% j( N" R/ J6 ?
4 V; x! n4 p! U6 `$ h+ N3 e
我们从小到到遍历状态,假设较“小”的状态已经算好了,对于“大”状态,因为前面说的子集关系——少一个1的状态已经算好了,形象地说,我要枚举ABCDE的全部子集的最优值,它其实等于BCDE、ACDE、ABDE、ABCE、ABCD的子集合(这些其实即使y)的最优以及全集ABCD本身(这个状态是x)的值中的最优值。
5 d* u% T. E% k0 {3 p  ~关于y的枚举,i from 0 to 25, 看一下x的这位是1的话 (x & (1 << i)),y = x ^ (1 << i) 或者 y = x & (~(1 << i)), 这样y比x恰好少了第i位的1。* g1 W  g& v1 F5 _$ k3 V
, u% k# C! r/ M* y9 s
这是一个静态打表的算法,step (2)和字典规模有关(线性),但是表的大小是静态的2^26那么大,打表的复杂度是2^26 * 26,与字典大小无关。
. V! i/ L1 E; F1 y0 c! ~2 g
& p  ]2 O# g, D3 u* T有了这张表再遍历一次全部单词,对每个单词对应的int x,因为可以出现的实际上是x中那些为0的bit,我们需要对它取反。 所以最终
1 ]; Z' ^3 u6 T1 omax(length of word * dp[(~x) & ((1 << 26) - 1)]) 为所求…… ! n0 C' L6 u' x

- J- [7 W5 _" y' R- ?( \4 N2 B6 l$ o! {% K* }6 d: E

评分

参与人数 1金钱 +9 收起 理由
Sophia + 9 精华帖子!大赞!

查看全部评分

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

29

主题

2

精华

523

积分

超级会员

Rank: 4

积分
523
发表于 4-13-2016 08:18 AM | 显示全部楼层
很NB&隐晦的dp,runtime分析: 一共2^26字符集, 对于每个字符集找到相差1bit的子字符集,一共26*2^26,加上预处理的扫描整个字典进入每个set

29

主题

2

精华

523

积分

超级会员

Rank: 4

积分
523
发表于 4-13-2016 08:22 AM | 显示全部楼层
DP迭代这部分很难像得到,真的不知道如果onsite的时候,第一次遇到这样的题,会如何想到迭代呢?
' d& Q' ^- G2 }$ Y: p$ M8 F
9 `3 ^( I4 Y9 |, C3 y: ~DP的理解:9 a) r! L. d7 j# j  U
因为字典中,包含所有不overlap的字母集所构成的word不一定存在,所以要找到这个subset在字典中的最长word。

评分

参与人数 1金钱 +2 收起 理由
Sophia + 2 很给力!

查看全部评分

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表