10.29 google mtv onsite new grad

Skill tasks 那题感觉像Leetcode里course Arrange, 然后有prerequisites 那道，不知是否类似？请教楼主 谢谢！

宝贝忆彼岸 发表于 2015-11-5 02:33
恩，感觉这样空间复杂度确实会减少，但是感觉时间复杂度增大，了，因为worst case对于每个task都要遍历所 ...

或者换一种角度，每个人就是一个bitmap，每一位是某一个skill，0代表不会，1代表会。同理每一个task就是一个bitmap,每一位也是skill，0代表需要，1代表不需要，做与运算，看看每个人的bitmap能不能包含task的bitmap。

请问第四题，“旋转180度”是回文嘛？

第三题是不是二分图的匹配？

lianlu 发表于 2015-11-10 07:03
第三题是不是二分图的匹配？

是network flow的典型例子

第三题，遍历每个人，将对应的skill放到一个set。再遍历task，看对应的skill是否在set里面，应该可以解决第一题。
follow up；建一个hashtable。 skill－》count。每个skill有几个人会。再遍历task，对于skill也可以建立相同的map，比较一下就成了。

maomaoxiong 发表于 2015-11-11 12:20
第三题，遍历每个人，将对应的skill放到一个set。再遍历task，看对应的skill是否在set里面，应该可以解决第 ...

比如Task TA 需要 Skills S1 S2。 然后people: P1 会S1, P2会S2, 楼上的方法会返回true但应该是false, 因为一个任务只能一个人完成. 感觉HashMap的value应该再存hashSet<People>, 也就是 HashMap<Skill, HashSet<People>> 不过复杂度会提高

看前面的回复 第三题第二问想到了一个快速判断的方法 给每一个人编号1 2 ...100。 建一个hashtable<skill， people>, 不过people的表现形式不用HashSet的list形式。 而是用bitmap: 每一位是某一个person，0代表该person不会这个skill，1代表会。 HashTable setup之后， 遍历tasks, 把每个task里面的skills 在前面的HashTable里找到value。 把所有value取bit and (&), 不为0的话就表示有某个人包含了所有需要的skills。 这样o (m)时间复杂下解决了问题

请问trie为什么可以优化呢？都需要scan整个prefix的长度吧，每次都需要，不和两个for循环一样吗？

请问最长公共路径只的是/abc/xyz/hij/f1  /abc/xyz/f2 /xyz/f3 公共路径是xyz?还是根本没有？