10.28 Google 电面 及 寻求加拿大小伙伴

楼主，请问这种情况你如何处理的 “当然要考虑 1）b中字符重复，“dead”这种情况”

gnijuohz 发表于 2015-10-30 01:58
不在呢，在calgary。。。不过想去温哥华或者toronto那边工作。我们加好友私聊吧😄

咦～这个还能私聊咩～已经加了

pengzewen37 发表于 2015-10-29 11:29
楼主，请问这种情况你如何处理的 “当然要考虑 1）b中字符重复，“dead”这种情况”

未优化的解法是只记录第一次字符出现的位置。dead，d第一次出现下标为0记在hash table中再出现就不管。

优化之后我是用一个set记录的，先把dead的字符加入一个set {‘d'， ’e‘， ’a‘}，然后遍历的时候去掉字符即可，也可以搞个visited set一样的思路。
```python
# 估计坛内编辑器不支持markdown，but 。。。
charSet = set(b)
for c in b:
    if c in charSet:
         ...
        charset.remove(c)
```

大致就是这样子。

flyaway25 发表于 2015-10-29 11:13
Donald Trump都能front run。。。莫名戳中笑点

Donald Trump也是每次都戳中我笑点。。。可是。。。没想到他front runner这么久，我已然笑不出来了哎

gnijuohz 发表于 2015-10-30 03:00
Donald Trump也是每次都戳中我笑点。。。可是。。。没想到他front runner这么久，我已然笑不出来了哎

原本最大的竞争对手希拉里先在丑闻缠身，一想到以后很有可能就是Trump当家，就只能呵呵了。。每次在gym里面都是循环播放他的演讲

gnijuohz 发表于 2015-10-29 13:48
未优化的解法是只记录第一次字符出现的位置。dead，d第一次出现下标为0记在hash table中再出现就不管。
...

所以优化之后的意思是 只用考虑第一次出现的值按照b的顺序排，后面再出现就还是按照a～z的顺序？

flyaway25 发表于 2015-10-29 12:01
原本最大的竞争对手希拉里先在丑闻缠身，一想到以后很有可能就是Trump当家，就只能呵呵了。。每次在gym里 ...

你的gym播放？还是你自己放着听？

不管哪种都是好痛苦的感觉。。。

pengzewen37 发表于 2015-10-29 13:36
所以优化之后的意思是 只用考虑第一次出现的值按照b的顺序排，后面再出现就还是按照a～z的顺序？

恩。。。好像不是的。举个全点的例子吧。
a = “abeeedbbbad” b = “dead”， 以b sort a。

这样的话结果a就变成了ddeeeaabbbb。
他说如果不在的话放在后面就可以不用以a~z来搞。

优化的O（n）算法：

1. <div>a_counter = collections.Counter(a)</div><div>b_set = set(b)</div><div>
   
2. </div><div>result = ""</div><div>for c in b:</div><div>    if c in b_set:</div><div>        result += a_counter[c]*c</div><div>        b_set.remove(c)</div><div>        del <span style="line-height: 1.5;">a_counter[c]</span></div><div><span style="line-height: 1.5;">
   
3. </span></div><div><span style="line-height: 1.5;">for key in a_counter:</span></div><div><span style="line-height: 1.5;">    result += a_counter[key]*key</span></div>

复制代码

大致就是这个样子的~






补充内容 (2015-10-29 15:15):
乱码了不好意思。。。

gnijuohz 发表于 2015-10-29 17:14
恩。。。好像不是的。举个全点的例子吧。
a = “abeeedbbbad” b = “dead”， 以b sort a。

谢啦，谢啦，明白了～～～～

Lz面的Waterloo office嘛？